Разъяснение по вашему алгоритму.
Рекурсивная функция 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, начиная с argmin k (d(k,j) ) = j-1. (Узел, из которого можно достичь j по кратчайшему пути, - j-1). Итак, это эквивалентно туру: 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);
}