Comment puis-je mettre en œuvre cette équation en Java?

Question

OK, cela est plus une question de suivi: Comment calculer les chemins optimaux pour VRP Tour Bitonic?

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 un tableau des résultats précédents. Ma question est la partie C: En supposant l(k,i) et dist(pk,pj) sont définies, comment pourrais-je mettre en œuvre une partie C en Java? Ma première pensée était que j'itérer sur k de 1 à i et stocker le résultat minimum de (l(k,i) + dist(pk,pj)), mais je ne pense pas que cela soit.

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 valeurs dist(pk,pj) avant que 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;
  }
}

Note Je ne l'ai pas une optimisation similaire pour l (comme dans Précalculer une table de l) parce que vous avez déclaré qu'il était déjà une table précalculée. Si ce n'était pas je puis exploiter certaines optimisation:)

Mais comme le commentaire précédent a déclaré le compilateur Java pourrait très bien faire l'optimisation pour vous. Je ne suis pas un expert en ce qui optimisations du compilateur Java effectue bien afin de prendre ce dernier commentaire avec un grain de sel:)

Enfin, il y a des propriétés particulières que la table a l(k,i)? Par exemple, certains l(i,k) = l(k,i) de symétrie (je devine juste ici parce que je ne sais pas grand chose sur le problème pour ignorer ce commentaire si cela semble farfelue). S'il y a des propriétés particulières affichez-les et nous pourrions trouver d'autres optimisations.

Answer 2

Je pense que le compilateur Java optimiser votre boucle à sa manière. Et il 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;

}