FLYING

/* TODO: 気の利いた説明を書く */

動的計画法による巡回セールスマン問題の解法

都市数が20以下ぐらいであれば、動的計画法を使ってTSPの厳密解を求めることが可能。その概要は以下の通り。

state を「到達した都市の状態を表すビット列」、cost[state][i] を「都市 i を訪れて状態 state になったときの最小コスト」とすると、

  1. cost を十分に大きな値で初期化する
  2. 最初に訪れる都市のコストを 0 で初期化する
  3. 以下のステップを全ての state 及び都市に対して実行
    • state において、到達済みの都市 i から出発して、未到達の都市 j に向かうコストを算出
    • 上で算出したコストが cost[state|(1<<j)][j] よりも小さければコストを更新
  4. cost[(1<<都市数)-1][] のうち、最小のものが求めるコストとなる

ここでは最小コストだけを求める場合を例にとったが、cost を更新するときに、移動元の都市の番号を保存しておけば、後から最短経路を辿ることもできる。