Как реализовать это уравнение в Java?

Question

ОК, это больше последующий вопрос: How to compute optimal paths for traveling salesman bitonic tour?

Прежде всего, для bitonic тура задачи коммивояжера У меня есть следующее рекуррентное соотношение:

(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 представляет собой таблицу предыдущих результатов. Мой вопрос с частью C: Предполагая, что l(k,i) и dist(pk,pj) определены, как реализовать часть C на Java? Моя первоначальная мысль заключалась в том, что я перебираю k от 1 до i и сохраняю минимальный результат (l(k,i) + dist(pk,pj)), но я не думаю, что это правильно.

, например:

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

// min is the result 

Это может показаться глупый вопрос (и, вероятно, это, я сильно не хватает сна), но я надеюсь, кто-то может помочь.

Answer 1

Очевидная оптимизация предварительно вычислить ваше dist(pk,pj) значения перед циклом

, например

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

Примечания Я не делал подобную оптимизацию для л (как в предвычислениях таблицы л) потому что вы заявили, что это уже предвыборная таблица. Если бы это было не так, я бы выполнил ту же оптимизацию :)

Но, как сказано в предыдущем комментарии, Java-компилятор может очень хорошо сделать эту оптимизацию для вас. Я не эксперт в отношении того, какие оптимизации выполняет Java-компилятор, поэтому сделайте последний комментарий с зерном соли.

Наконец, есть ли какие-либо специальные свойства, которые имеет таблица l(k,i)? Например, некоторая симметрия l(i,k) = l(k,i) (я просто догадываюсь, потому что я мало знаю о проблеме, поэтому игнорируйте этот комментарий, если это звучит дурацко). Если есть какие-то специальные свойства, они будут опубликованы, и мы могли бы придумать дальнейшую оптимизацию.

Answer 2

Я думаю, что Java-компилятор оптимизирует вашу петлю на своем пути. И это нормально.

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; 

}