動的計画法による巡回セールスマン問題の解法
都市数が20以下ぐらいであれば、動的計画法を使ってTSPの厳密解を求めることが可能。その概要は以下の通り。
state を「到達した都市の状態を表すビット列」、cost[state][i] を「都市 i を訪れて状態 state になったときの最小コスト」とすると、
- cost を十分に大きな値で初期化する
- 最初に訪れる都市のコストを 0 で初期化する
- 以下のステップを全ての state 及び都市に対して実行
- state において、到達済みの都市 i から出発して、未到達の都市 j に向かうコストを算出
- 上で算出したコストが cost[state|(1<<j)][j] よりも小さければコストを更新
- cost[(1<<都市数)-1][] のうち、最小のものが求めるコストとなる
ここでは最小コストだけを求める場合を例にとったが、cost を更新するときに、移動元の都市の番号を保存しておけば、後から最短経路を辿ることもできる。