澄清你的算法。
递归函数应该计算访问所有小于 的节点的双调旅行的l(i,j)最小距离。因此，最初问题的解决方案将是！i -> 1 -> jil(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之间没有点，所以连接它们的直线将是最优的。（选择之前访问的任意数量的其他点会导致路径更长！）122
(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之间不能没有。所以，这相当于 tour: ，相当于!j-1ji -> ... -> 1 -> .... -> j-1 -> jl(i,j-1) + dist(pj-1,pj)
Anf 最后有趣的部分来了：
(c) When i = j - 1 or i = j, min 1<=k<i (l(k; i) + dist(pk; pj ))
在这里，我们知道我们必须从ito 1，但没有关于后向扫描的线索！j这里的关键思想是我们必须在我们的反向路线上考虑之前的节点。它可能是从1到的任何节点j-1！让我们假设这个节点是k。现在我们有一个游览：i -> ... -> 1 -> .... -> k -> j，对吧？这次旅行的费用是l(i,k) + dist(pk,pj)。
希望你明白了。
执行。
您将需要一个二维数组 say 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);
}