Как я могу реализовать это уравнение в Java? - PullRequest
Новая
       33

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

3 голосов
/ 18 мая 2009

ОК, это больше вопрос для продолжения: Как рассчитать оптимальные пути для путешествующего коммивояжера Битон-тур?

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

(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

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

Ответы [ 3 ]

2 голосов
/ 18 мая 2009

Одной из очевидных оптимизаций является предварительное вычисление ваших 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) (я просто догадываюсь здесь, потому что я не знаю много о проблеме, поэтому игнорируйте этот комментарий, если он звучит странно). Если есть какие-либо специальные свойства, опубликуйте их, и мы могли бы предложить дальнейшую оптимизацию.

1 голос
/ 18 мая 2009

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

0 голосов
/ 18 мая 2009 
(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;

}
...