巡回セールスマン問題
Traveling Salesman Problem TSP
問題
$ N 個の都市を$ 1 回ずつ通る最短ルートやその距離を求める問題。
始点には戻る、距離はユークリッド距離が典型な気がする
典型
応用
見かけ次第追記したい
解法
dp [ 通過済みの都市 ] [ 最後にいた都市 ] として bitDP 通過状況$ b, 終点$ i について昇順に見て、$ i からたどり着ける都市 $ j について、
$ \mathrm{dp}[b \cup j][j] = \min(\mathrm{dp}[b \cup j][j], \mathrm{dp}[b][i] + \mathrm{cost}(i, j))
と更新していく。都市の数$ Nに対して計算量$ \Omicron(N^22^N)
DPの初期化
$ [0][0]=0 , それ以外$ =\mathrm{INF}