アルゴリズムの説明。
再帰関数は、より小さいすべてのノードを訪問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は最適なツアーがあるからです。ただし、このルートを逆方向にトラバースすると、同じ距離が得られ、bitonic プロパティが壊れることはありません。
簡単なケース (変更点に注意してください!):
(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ためです。パス内のすべてのノードはインデックスの昇順であるため、 と の間にノードが存在しない場合があります。したがって、これは tour:と同等であり、これは!と同等です。i -> ... -> 1i1 -> ... -> jj-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 ))
iここで、 からまで取得する必要があることはわかっていますが1、後方スイープに関する手がかりはありません! jここでの重要なアイデアは、逆方向のルートの直前のノードを考えなければならないということです。1からまでのノードのいずれかj-1です。このノードが であると仮定しましょうk。では、ツアーを始めましょう:i -> ... -> 1 -> .... -> k -> jですよね? このツアーの料金は ですl(i,k) + dist(pk,pj)。
あなたがそれを手に入れたことを願っています。
実装。
たとえば、2次元配列が必要になります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);
}