TSP(巡回セールスマン問題）をメモ化再帰(bitDP)で解く

TSPのオンラインジャッジ

TSPとは、最短のハルミトン閉路を求める問題。指数時間のアルゴリズムしか知られていない。

解法

✔︎愚直解

まずは愚直に全探索することを考える。

例えばやり方として、頂点の順列(permutation)を全列挙して、その通りに辺の長さを足していく。

とても簡単でわかりやすい。

しかし、順列の組み合わせは(N-1)!個(Nは頂点数）なので、N = 8くらいまでしか現実的な時間内に解くことができない。

✔︎メモ化

愚直解のやり方から高速化することを考える。

実は、愚直なやり方は余計な計算をしている部分が非常に多い。

f:id:dalekspritner:20180927223811p:plain

上図の頂点１からスタートして、頂点１に戻ってくる場合を考える。

たとえば図のように、１、２、３、８の頂点を複数の方法で経由して頂点７まできた時、残りの最短の道順はどうなるかというと、実は同じ経路になる。

つまり頂点集合Sの部分集合S’を通って頂点vにいるとき、後の最短経路長は同じ値になるので、状態数は2ˆN * N通りしかない。

よって

dp[S’][v] ... S’を通ってvにいる時の後に通る最短経路長

という状態をメモしてあげれば、計算量をO(N!)からO(2ˆN * Nˆ2)に落とすことができる。

これならN=16くらいまでなら現実的な時間内で解くことができる。

漸化式っぽくすると

dp[S’][v] は S’ = Sのとき0（もういくところがないため）

それ以外の時 min(dp[S’ & u][u] + dist[v][u], dp[S'][v])

uはvからたどり着くことができて、まだ行っていない(S’に含まれない）頂点。

あとはdp[0][start]から深さ優先探索で再帰的に解くことができる。

最後に頂点集合の管理方法として便利なのが、bitとして管理する方法。

bitについては、以下が個人的に参考になる。

実装

本質的な部分はDFS関数の中。

参考になる良書たち↓

アウトプットは砕けない