algorithm
旅行セールスマン
サーチ…
備考
トラベリングセールスマン問題は、頂点1回につきN
個の頂点を通って移動するための最小コストを求める問題である。頂点i
から頂点j
まで移動するにはコストcost[i][j]
があります。
この問題を解決するアルゴリズムには2種類あります。 厳密アルゴリズムと近似アルゴリズム
厳密アルゴリズム
- ブルートフォースアルゴリズム
- 動的プログラミングアルゴリズム
近似アルゴリズム
追加する
ブルートフォースアルゴリズム
すべての頂点を通るパスは、何らかの方法で頂点を順序付けするのと同じです。したがって、すべての頂点を1回だけ正確に1回移動するための最小コストを計算するには、 N!
1
からN
までの数の順列。
擬似コード
minimum = INF
for all permutations P
current = 0
for i from 0 to N-2
current = current + cost[P[i]][P[i+1]] <- Add the cost of going from 1 vertex to the next
current = current + cost[P[N-1]][P[0]] <- Add the cost of going from last vertex to the first
if current < minimum <- Update minimum if necessary
minimum = current
output minimum
時間の複雑さ
N!
がありますN!
各経路のコストはO(N)
で計算されるので、このアルゴリズムはO(N * N!)
時間で正確な答えを出力します。
動的プログラミングアルゴリズム
パスを(順番に)考慮すると、次のようになります。
(1,2,3,4,6,0,5,7)
とパス
(1,2,3,5,0,6,7,4)
頂点1
から頂点2
、頂点3
までのコストは同じなので、なぜ再計算する必要がありますか?この結果は、後で使用するために保存することができます。
ましょうdp[bitmask][vertex]
、その対応するビット内のすべての頂点を通って移動するの最小コスト表すbitmask
に設定されている1
で終了vertex
。例えば:
dp[12][2]
12 = 1 1 0 0
^ ^
vertices: 3 2 1 0
12
は2進数で1100
を表しているため、 dp[12][2]
は頂点2
で終了するパスを持つグラフの頂点2
と3
を通過することを表します。
したがって、次のアルゴリズム(C ++実装)を持つことができます。
int cost[N][N]; //Adjust the value of N if needed
int memo[1 << N][N]; //Set everything here to -1
int TSP(int bitmask, int pos){
int cost = INF;
if (bitmask == ((1 << N) - 1)){ //All vertices have been explored
return cost[pos][0]; //Cost to go back
}
if (memo[bitmask][pos] != -1){ //If this has already been computed
return memo[bitmask][pos]; //Just return the value, no need to recompute
}
for (int i = 0; i < N; ++i){ //For every vertex
if ((bitmask & (1 << i)) == 0){ //If the vertex has not been visited
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]); //Visit the vertex
}
}
memo[bitmask][pos] = cost; //Save the result
return cost;
}
//Call TSP(1,0)
この行はちょっと混乱するかもしれませんので、ゆっくりと進みましょう:
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);
ここで、 bitmask | (1 << i)
は、bitmaskのi番目のbitmask
を1に設定します。これは、i番目の頂点が訪問されたことを表します。コンマの後のi
は、新しい「最後の」頂点を表す関数呼び出しの新しいpos
を表します。 cost[pos][i]
は、頂点pos
から頂点i
に移動するコストを加算することです。
したがって、この行は、まだ訪問されていない他のすべての頂点に移動する可能な最小値にcost
の値を更新することです。
時間の複雑さ
関数は、 TSP(bitmask,pos)
有する2^N
の値bitmask
とN
の値pos
。各関数は実行にO(N)
時間かかる( for
ループ)。したがって、この実装では、正確な答えを出力するためにO(N^2 * 2^N)
時間がかかります。