部分集合DPで履歴を圧縮する

訪れた順を全部覚えると N! 通り。訪問済み集合と最後の頂点だけで今後が決まるなら、状態をまとめられます。

言語：Python / 計算量：O(2^N N²)、メモリ O(2^N N)

前提：ビット全探索で部分集合を列挙 / DPは「同じ続きをまとめる」

考え方

1. dp[mask][v] は訪問集合mask、最後vの最小コスト。
2. 未訪問uへ移動して mask
3. (1<<u) を更新。
4. 到達不能を∞にし、始点だけ初期化します。

具体例

3頂点で0→1=2、1→2=3、0→2=9、2→1=1なら、0から全頂点を訪れる最短経路は0→1→2の5です。

実装

c=[[0,2,9],[2,0,3],[9,1,0]];n=3
dp=[[float("inf")]*n for _ in range(1<<n)];dp[1][0]=0
for mask in range(1<<n):
    for v in range(n):
        for u in range(n):
            if not(mask>>u&1):
                nm=mask|1<<u
                dp[nm][u]=min(dp[nm][u],dp[mask][v]+c[v][u])
print(min(dp[-1]))

注意する条件

「訪問した集合」だけでは足りず、最後の頂点が必要です。N=20でもPythonの二次元配列はメモリに注意。

確認問題

例の全頂点を訪れる最短経路のコストは？

実装課題

N と N×N の非負コスト行列。頂点0から全頂点をちょうど1回ずつ訪れる最小コスト。最後に0へ戻らない。1≤N≤12、c≤10^6。

入力:
3
0 2 9
2 0 3
9 1 0
出力:
5

n=int(input());c=[list(map(int,input().split())) for _ in range(n)]
dp=[[float("inf")]*n for _ in range(1<<n)];dp[1][0]=0
for mask in range(1<<n):
    for v in range(n):
        if dp[mask][v]==float("inf"):continue
        for u in range(n):
            if not(mask>>u&1):
                nm=mask|1<<u;dp[nm][u]=min(dp[nm][u],dp[mask][v]+c[v][u])
print(min(dp[-1]))

読了の記録・下書き・メモへ