読者です 読者をやめる 読者になる 読者になる

FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

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

c/c++ memo

都市数が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 を更新するときに、移動元の都市の番号を保存しておけば、後から最短経路を辿ることもできる。