巡回セールスマン問題
atcoder abc301 E問題の解説を聞いたのを参考にしてなるべくコンパクトに巡回セールスマン問題をDPでとくプログラムをpython3で書いてみました。
以下が使ったデータです。
点０から出発してすべての点を通って０にもどることを考えています。
4
0 3 4 7
3 0 5 4
4 5 0 3
7 4 3 0
終わったときのｄｐは
[[0, 100, 100, 100],
[0, 100, 100, 100],
[100, 3, 100, 100],
[6, 3, 100, 100],
[100, 100, 4, 100],
[8, 100, 4, 100],
[100, 9, 8, 100],
[12, 9, 8, 100],
[100, 100, 100, 7],
[14, 100, 100, 7],
[100, 11, 100, 7],
[14, 11, 100, 7],
[100, 100, 10, 7],
[14, 100, 10, 7],
[100, 11, 10, 11],
[14, 11, 10, 11]]
となっています。
プログラム
tsp.py
n=int(input())
dist=[[int(i) for i in input().split()] for _ in range(n)]
print(n,dist)
inf=100
n2=1<<n
dp=[[inf]*n for _ in range(n2)]
dp[0][0]=0
#print(dp)
for s in range(n2): # sでビット全探索
for u in range(n): # uが始点
if dp[s][u]==inf: # uが有限値ではないとき
continue
for v in range(n): # vが終点
if ~s>>v&1: # vがsに含まれないとき
dp[s|1<<v][v]=min(dp[s|1<<v][v],dp[s][u]+dist[u][v])
print(dp)