Как я могу реализовать это уравнение в Java?
-
22-08-2019 - |
Вопрос
Хорошо, это скорее дополнительный вопрос: Как рассчитать оптимальные пути для битонического тура коммивояжера?
Прежде всего, для битонического тура задачи коммивояжера у меня есть следующее рекуррентное соотношение:
(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
Это может показаться глупым вопросом (и, вероятно, так оно и есть, мне очень не хватает сна), но я надеюсь, что кто-нибудь сможет помочь.
Решение
Одной из очевидных оптимизаций является предварительное вычисление 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;
}
}
Обратите внимание: я не проводил аналогичную оптимизацию для l (как при предварительном вычислении таблицы l), потому что вы заявили, что это уже предварительно вычисленная таблица.Если бы это было не так, я бы провел ту же оптимизацию :)
Но, как говорилось в предыдущем комментарии, компилятор Java вполне может выполнить эту оптимизацию за вас.Я не эксперт в том, какие оптимизации выполняет Java-компилятор, поэтому отнеситесь к последнему комментарию с недоверием :)
Наконец, существуют ли какие-либо особые свойства, которыми обладает l(k,i)
стол есть?Например, некоторая симметрия l(i,k) = l(k,i)
(Я просто предполагаю, потому что мало что знаю об этой проблеме, поэтому проигнорируйте этот комментарий, если он звучит странно).Если есть какие-либо специальные свойства, опубликуйте их, и мы сможем предложить дальнейшие оптимизации.
Другие советы
Я думаю, что компилятор Java по-своему оптимизирует ваш цикл.И это нормально.
(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;
}