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

Хорошо, это скорее дополнительный вопрос: Как вычислить оптимальные пути для тура коммивояжера 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

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


java recurrence algorithm dynamic-programming
person Mr. Shickadance    schedule 17.05.2009    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

person hhafez    schedule 17.05.2009
comment
+1 за вывод вычисления расстояния за пределы цикла. компилятор Java не сможет сделать это сам, если не сможет доказать, что функция dist не может измениться. Поскольку dist предположительно ищет расстояние в массиве (который является изменяемым), я не думаю, что какой-либо текущий компилятор сможет это доказать. - person mikera; 05.03.2012

arrow_upward
1
arrow_downward

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

person Imaskar    schedule 17.05.2009