巡回セールスマン問題

Traveling salesman problem, TSP

都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める組合せ最適化問題である。
wikiより抜粋

NP困難とよばれる問題。多項式時間で解けるアルゴリズムがみつからず計算量的に解くのが困難な問題。
すべての経路を計算する場合、$O(n!)$のため、都市数が20以上の場合、現実的な範囲でなくなる。

解法

bit DP

集合に対する動的計画法のひとつ。$n$個のものに対して$n!$通りの順序の中から最適なものを求めるときに使える。
巡回セールスマン問題で巡回する集合の部分集合Sを巡回する $\mid S \mid!$通りの経路のうち最短のものの距離のうち、最後に頂点vに到達したときのみ考える。
頂点uからvまでの距離を $cost(u,v)$ とすると以下のようになる。
計算量は $O(2^nn^2)$程度になる。

$$dp[S \cup {v}][v] = \min_{u \in S}(dp[S \cup {v}][v], dp[S][u] + cost(u, v))$$

問題

参考