巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

どのようにして解を求めればよいのでしょうか? 一番最初に思いつくのが総当たり法です。

都市は全部で4つあり、それぞれの名前を A, B, C, Dとすれば、都市Aを最初に訪問する方法だけでも

と6通りあります。都市が全部で4つある場合は全部で24通り考えなければなりません。都市が全部でn個あるのであれば、n × (n – 1) × (n – 2) × (n – 3) × …… × 2 × 1通りです。nが1増えるたびにそのパターンの数は爆発的に増えていきます。そこで別の方法を考えます。

都市が16以下であれば動的計画法

nが16以下であれば動的計画法が有効です。

ある都市 s からスタートし、集合 S に含まれるすべての都市を訪れ、都市 j に到達する最短路を p(j, S)、その長さを d(j, S) と表記します。都市の集合 S をビット列による表現を用いて表しています。

まず簡単にわかることとしてd(j, {j})があります。このとき集合の要素は j だけです。なのでd(j, {j})は都市 s から都市 j までの距離です。

次に、p(j, S) において j の直前に訪れる頂点を i とします。すると、p(j, S) の頂点 i に到達するまでの部分路は、都市 s からスタートして集合 S – {j} に含まれるすべての都市を訪れ、頂点 i に到達する最短路になっているはずです。従って、d(j, S) は d(i, S – {j}) + (都市 i から都市 j までの距離) の最小値となりです。

集合演算をするにあたりビット演算を用います。集合 S のなかに i番目の都市があるかどうかは S & (1<

動的計画法で巡回セールスマン問題を解くためのクラスを定義します。GetDistanceメソッドは都市間の距離を求めるためのものです。GetSolutionメソッドに都市の座標を渡して処理をおこないます。このとき最短経路と処理にかかる時間も取得できるようにしておきます。

実行結果

この方法だと1秒以内に終わります。

(参考)【paizaラーニング】動的計画法によるTSP