Comment puis-je implémenter cette équation en Java?

Question

OK, ce qui est plus d'une question de suivi: How to compute optimal paths for traveling salesman bitonic tour?

Tout d'abord, pour la tournée Bitonic du problème du voyageur de commerce J'ai la relation de récurrence suivante:

(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 est une table des résultats précédents. Ma question est avec la partie C: En supposant que l(k,i) et dist(pk,pj) sont définis, comment pourrais-je implémenter la partie C en Java? Ma pensée initiale était que je crois sur k de 1 à i et de stocker le résultat minimum de (l(k,i) + dist(pk,pj)), mais je ne pense pas que ce soit juste.

par exemple:

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

// min is the result 

Cela peut sembler une question stupide (et est probablement, je suis sérieusement le sommeil manquais), mais j'espère que quelqu'un peut aider.

Answer 1

Une optimisation évidente consiste à pré calculer vos dist(pk,pj) valeurs avant la boucle

par exemple

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; 
    } 
} 

Remarque Je ne l'ai pas une optimisation similaire pour l (comme dans Précalculer une table de l) parce que vous avez déclaré que c'était déjà une table précalculée. Si ce n'était pas alors je ferais la même optimisation :)

Mais comme le commentaire précédent a déclaré le compilateur Java pourrait très bien faire cette optimisation pour vous. Je ne suis pas expert sur les optimisations que le compilateur Java effectue, alors prenez ce dernier commentaire avec un grain de sel :)

Enfin, y a-t-il des propriétés spéciales que la table l(k,i) a? Par exemple une certaine symétrie l(i,k) = l(k,i) (Je devine juste ici parce que je ne connais pas grand chose au problème donc Ignore ce commentaire si ça sonne farfelu). S'il y a des propriétés spéciales, affichez-les et nous pourrions proposer d'autres optimisations.

Answer 2

Je pense que le compilateur Java optimisera votre boucle dans son chemin. Et c'est 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; 

}