Come posso implementare questa equazione in Java?

Question

OK, questo è più di una domanda di follow-up: Come calcolare percorsi ottimali per viaggiare venditore giro bitonico?

Prima di tutto, per il tour bitonico del problema del commesso viaggiatore Ho la seguente relazione di ricorrenza:

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )
(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)
(c) When i = j - 1 and j > 2, min 1<=k<i (l(k; i) + dist(pk; pj ))

l è una tabella dei risultati precedenti. La mia domanda è con parte C: Supponendo l(k,i) e dist(pk,pj) sono definiti, come avrei implementare parte C in Java? Il mio primo pensiero è stato che ho iterare su k da 1 a i e memorizzare il risultato minimo di (l(k,i) + dist(pk,pj)), ma non credo che sia giusto.

Ad esempio:

for (int k = 1; k < i; ++k) {
  tmp = l(k,i) + dist(pk,pj);
  if (tmp < min) {
    min = tmp;
  }
}

// min is the result

Questo può sembrare una domanda stupida (e probabilmente lo è, io sono gravemente carente sonno), ma spero che qualcuno possa dare una mano.

Answer 1

Un'ottimizzazione ovvia è quella di controllare la validità calcolare i valori dist(pk,pj) prima del ciclo

per esempio

dist_pk_pj = dist(pk,pj);

/* then do as you did before */
for (int k = 1; k < i; ++k) {
  tmp = l(k,i) + dist_pk_pj;
  if (tmp < min) {
    min = tmp;
  }
}

Si noti che non ho fatto un'ottimizzazione simile per l (come in Precompute una tabella di l), perché lei ha affermato che era già un tavolo precalcolate. Se non fosse stato poi vorrei eseguire la stessa ottimizzazione:)

Ma, come il commento precedente ha dichiarato il compilatore Java potrebbe benissimo fare che l'ottimizzazione per voi. Non sono un esperto su ciò che le ottimizzazioni del compilatore Java svolge però in modo da prendere che ultimo commento con un grano di sale:)

Infine ci sono delle proprietà speciali che la tabella l(k,i) ha? Per esempio alcuni l(i,k) = l(k,i) simmetria (sto solo indovinando qui perché non so molto circa il problema in modo Ignorare questo commento se suona stravagante). Se ci sono particolari proprietà pubblicarli e potremmo venire con ulteriori ottimizzazioni.

Answer 2

Credo compilatore Java ottimizzare il ciclo a suo modo. Ed è ok.

Answer 3

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )

(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)

(c) When i = j - 1 and j > 2, min 1<=k<i (l(k; i) + dist(pk; pj ))

import system.math

unsigned long i;

unsigned long j;

if ((i==j-1)&& (j>2))

{

unsigned long k=1;

unsigned long result;

while (k<i)

{

  result = l(k; i) + dist(pk; pj )

  min = minus(min, result);

  k++;

}

return min;

}