Как вычислить оптимальные пути для биллингового тура коммивояжера?

ОБНОВЛЕНО

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

(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 ))

Теперь это начинает иметь смысл, за исключением части C. Как я могу определить минимальное значение k? Я полагаю, это означает, что вы можете перебирать все возможные значения k и просто хранить минимальный результат (l (k, i) + dist (pk, pj)?

Да, определенно проблема, которую я учил в школе. Мы изучаем битонные туры для проблемы коммивояжера.

В любом случае, скажем, у меня есть 5 вершин {0,1,2,3,4}. Я знаю, что мой первый шаг - сортировать их по порядку увеличения x-координат. Оттуда я немного смущен тем, как это будет сделано при динамическом программировании.

Я читаю, что я должен проверять список отсортированных узлов и поддерживать оптимальные пути для обеих частей (начальный путь и путь возврата). Я смущен тем, как я буду рассчитывать эти оптимальные пути. Например, как я узнаю, должен ли я включать данный node в исходный путь или путь возврата, поскольку он не может быть в обоих (кроме конечных точек). Возвращаясь к Фибоначчи в динамическом программировании, вы в основном начинаете свой базовый случай и прокладываете себе путь вперед. Я предполагаю, что я спрашиваю, как я начну с проблемы с битоническим коммивояжером?

Для чего-то вроде чисел Фибоначчи, приближенное динамическое программирование совершенно ясно. Тем не менее, я не знаю, насколько я просто плотный или что, но я довольно запутан, пытаясь обернуть голову этой проблемой.

Спасибо, что посмотрели!

ПРИМЕЧАНИЕ. Я не ищу полные решения, но, по крайней мере, некоторые полезные советы, чтобы начать работу. Например, если бы это была проблема Фибоначчи, можно было бы проиллюстрировать, как вычисляются первые несколько чисел. Пожалуйста, дайте мне знать, как я могу улучшить этот вопрос.

Ответ 1

Разъяснение вашего алгоритма.

Рекурсивная функция l(i,j) должна вычислять минимальное расстояние битового обхода i -> 1 -> j, посещающего все узлы, которые меньше, чем i. Итак, решение исходной проблемы будет l(n,n)!

Важные замечания:

мы можем предположить, что узлы упорядочены по их координате x и помечены соответствующим образом (p1.x < p2.x < p3.x ... < pn.x). Если они не были заказаны, мы могли бы отсортировать их в O(nlogn) время.
l(i,j) = l(j,i). Причина в том, что в lhs у нас есть тур i ->...-> 1 -> ... -> j, который является оптимальным. Однако при прохождении этого маршрута в обратном направлении мы получим такое же расстояние и не сломаем битоническое свойство.

Теперь простые случаи (обратите внимание на изменения!):

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj ) = dist(1,2)

Здесь у нас следующий тур: 1->1->...->2. Тривиально это эквивалентно длине пути 1->...->2. Поскольку точки упорядочены по их координате .x, между 1 и 2 нет точки, поэтому соединяющая их прямая линия будет оптимальной. (Выбор любого количества других точек для посещения до 2 приведет к более длинному пути!)

(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)

В этом случае j-1 должен находиться на части пути 1 -> ... -> j, поскольку деталь i -> ... -> 1 не может содержать узлы с индексом больше, чем i. Поскольку все узлы в пути 1 -> ... -> j расположены в порядке возрастания индекса, между j-1 и j не может быть ни одного. Итак, это эквивалентно туру: i -> ... -> 1 -> .... -> j-1 -> j, что эквивалентно l(i,j-1) + dist(pj-1,pj)!

И, наконец, самое интересное:

(c) When i = j - 1 or i = j, min 1<=k<i (l(k; i) + dist(pk; pj ))

Здесь мы знаем, что нам нужно добраться от i до 1, но нет никакой подсказки о развороте назад! Ключевая идея здесь заключается в том, что мы должны думать об узле непосредственно перед j на нашем обратном маршруте. Это может быть любой из узлов от 1 до j-1! Предположим, что этот узел k. Теперь у нас есть тур: i -> ... -> 1 -> .... -> k -> j, верно? Стоимость этого тура l(i,k) + dist(pk,pj).

Надеюсь, ты понял.

Реализация.

Вам понадобится двумерный массив скажем BT[1..n][1..n]. Пусть i будет индексом строки, j будет индексом столбца. Как мы должны заполнить эту таблицу?

В первой строке мы знаем BT[1][1] = 0, BT[1][2] = d(1,2), поэтому у нас остались только индексы i,j, которые попадают в категорию (b).

В оставшихся строках мы заполняем элементы от диагонали до конца.

Вот пример кода C++ (не тестировался):

void ComputeBitonicTSPCost( const std::vector< std::vector<int> >& dist, int* opt ) {
  int n = dist.size();
  std::vector< std::vector< int > > BT;
  BT.resize(n);
  for ( int i = 0; i < n; ++i )
    BT.at(i).resize(n);

  BT.at(0).at(0) = 0;  // p1 to p1 bitonic distance is 0
  BT.at(0).at(1) = dist.at(0).at(1);  // p1 to p2 bitonic distance is d(2,1)

  // fill the first row
  for ( int j = 2; j < n; ++j )
    BT.at(0).at(j) = BT.at(0).at(j-1) + dist.at(j-1).at(j);

  // fill the remaining rows
  int temp, min;  
  for ( int i = 1; i < n; ++i ) {
    for ( int j = i; j < n; ++j ) {
      BT.at(i).at(j) = -1;
      min = std::numeric_limits<int>::max();
      if ( i == j || i == j -1 ) {
        for( int k = 0; k < i; ++k ) {
          temp = BT.at(k).at(i) + dist.at(k).at(j);
          min = ( temp < min ) ? temp : min;
        }        
        BT.at(i).at(j) = min;        
      } else {
        BT.at(i).at(j) = BT.at(i).at(j-1) + dist.at(j-1).at(j);
      }
    }
  }

  *opt = BT.at(n-1).at(n-1);
}

Ответ 2

Хорошо, ключевые понятия в решении динамического программирования:

вы предварительно вычислите меньшие проблемы.
У вас есть правило, позволяющее объединить более мелкие проблемы, чтобы найти решения для больших проблем.
у вас есть известное свойство проблем, которые позволяют вам доказать, что решение действительно оптимально в некоторой степени оптимальности. (В этом случае кратчайший.)

Существенное свойство биттонического тура состоит в том, что вертикальная линия в системе координат пересекает сторону замкнутого многоугольника не более двух раз. Итак, что такое битонический тур ровно на два очка? Ясно, что любые две точки образуют (вырожденный) битонический тур. Три точки имеют две битонные туры ( "по часовой стрелке" и "против часовой стрелки" ).

Теперь, как вы можете предварительно вычислить различные более мелкие битонные туры и объединить их, пока не включите все пункты и до сих пор будете битоническим туром?

Хорошо, вы на ривере с обновлением. Но теперь, в динамическом программном решении, что вы делаете с работой снизу вверх: предварительно вычислите и memoize (не "запоминать" ) оптимальные подзадачи.