Como posso implementar esta equação em Java?

Question

OK, esta é mais uma questão de acompanhamento: Como calcular caminhos ideais para viajar vendedor turnê bitonic?

Em primeiro lugar, para a turnê bitonic do problema caixeiro-viajante Eu tenho a seguinte relação de recorrência:

(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 é uma tabela de resultados anteriores. A minha pergunta é com a parte C: Assumindo l(k,i) e dist(pk,pj) são definidos, como eu ia implementar parte C em Java? Meu pensamento inicial era que eu iterar sobre k de 1 para i e armazenar o resultado mínimo de (l(k,i) + dist(pk,pj)), mas eu não acho que é certo.

Por exemplo:

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

// min is the result

Isto pode parecer uma pergunta estúpida (e provavelmente é, estou faltando severamente o sono), mas eu estou esperando que alguém pode ajudar.

Answer 1

Uma otimização óbvia é a pré calcular seus valores dist(pk,pj) antes do laço

Por exemplo

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 que não fiz uma otimização semelhante para l (como no precompute uma tabela de l) porque você declarou que já havia uma mesa precomputed. Se não fosse, então eu iria executar a mesma otimização:)

Mas como o comentário anterior declarou o compilador Java poderia muito bem fazer isso otimização para você. Não sou especialista no que otimizações executadas pelo compilador Java que assim que tomar esse último comentário com um grão de sal:)

Finalmente existem propriedades especiais que a tabela de l(k,i) tem? Por exemplo, alguns l(i,k) = l(k,i) simetria (estou apenas supondo aqui, porque eu não sei muito sobre o problema de modo Ignorar este comentário se isso soa maluco). Se houver quaisquer propriedades especiais publicá-las e nós poderia vir acima com otimizações adicionais.

Answer 2

Eu acho compilador Java irá otimizar o seu ciclo em seu caminho. E é 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;

}