¿Cómo puedo aplicar esta ecuación en Java?

Question

OK, esto es más una cuestión de seguimiento: Cómo calcular rutas óptimas para el vendedor ambulante recorrido bitónica?

En primer lugar, para la gira bitónica del problema del viajante de comercio que tengo la siguiente relación de recurrencia:

(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 es una tabla de resultados anteriores. Mi pregunta es en la parte C: Suponiendo l(k,i) y dist(pk,pj) se definen, ¿cómo iba a aplicar la parte C en Java? Mi idea inicial era que iterar sobre k de 1 a i y almacenar el resultado mínimo de (l(k,i) + dist(pk,pj)), pero no creo que sea adecuado.

por ejemplo:

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

// min is the result

Esto puede parecer una pregunta estúpida (y probablemente lo sea, me falta grave del sueño), pero estoy esperando que alguien puede ayudar.

Answer 1

Una optimización obvia es pre calcular sus valores dist(pk,pj) antes del bucle

por ejemplo

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

Tenga en cuenta que no hice una optimización similar para l (como en calcular previamente una tabla de l), ya que indicó que ya era una tabla precalculada. Si no fuera entonces yo realizo la misma optimización:)

Pero como el comentario anterior declaró el compilador de Java podría muy bien hacer que la optimización para usted. No soy un experto en lo que optimizaciones del compilador de Java realiza embargo a fin de tomar ese último comentario con un grano de sal:)

Por último hay ninguna propiedad especial que la tabla tiene l(k,i)? Por ejemplo, algunos l(i,k) = l(k,i) simetría (sólo estoy adivinando aquí porque no sé mucho sobre el problema de modo Ignorar este comentario si suena loco). Si hay algún propiedades especiales CP ellos y que podrían llegar a optimizaciones adicionales.

Answer 2

Creo compilador Java optimizará su bucle en su camino. Y está bien.

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;

}