Day 011-Q4 | ハミルトン路・巡回セールスマン (bitDP)

問題

$N$ 都市と各都市間の移動コスト $d[i][j]$ が与えられる。都市 $0$ を出発して全都市を ちょうど1回ずつ 訪問し、都市 $0$ に戻る最小コストを求めよ（巡回セールスマン問題 / TSP）。

入力形式

N
d[0][0] d[0][1] ... d[0][N-1]
...（N行）

制約

$2 \le N \le 20$

$0 \le d[i][j] \le 10^9$

$d[i][i] = 0$

入出力例

入力例 1

出力例 1

説明: $0 \to 1 \to 3 \to 2 \to 0$: $2+4+8+15=29$... 最適経路は $0\to3\to1\to2\to0$: $10+3+7+9=29$... （実際は 21 になる最適経路がある）

ヒント (段階的開示)

ヒント1: 方向性

$N!$ の全順列は $N=20$ で約 $2.4 \times 10^{18}$。bitDP（Held-Karp アルゴリズム） を使うと $O(2^N \times N^2)$ で解ける。

ヒント2: アプローチ

dp[S][v] = 訪問済み都市の集合が $S$（ビット集合）であり、現在いる都市が $v$ のときの最小コスト。
初期化: dp[1<<0][0] = 0（都市0にいて都市0のみ訪問済み）
遷移:

dp[S | (1<<u)][u] = min(dp[S | (1<<u)][u], dp[S][v] + d[v][u])

ただし $u \notin S$。

ヒント3: 誘導

INF = float('inf')
dp = [[INF] * N for _ in range(1 << N)]
dp[1][0] = 0  # (S=0001, v=0) = 0

for S in range(1 << N):
    for v in range(N):
        if dp[S][v] == INF:
            continue
        if not (S >> v & 1):
            continue
        for u in range(N):
            if S >> u & 1:
                continue
            ns = S | (1 << u)
            dp[ns][u] = min(dp[ns][u], dp[S][v] + d[v][u])

ans = min(dp[(1<<N)-1][v] + d[v][0] for v in range(N))

模範解答 (Python)

import sys
input = sys.stdin.readline
INF = float('inf')

def main():
    N = int(input())
    d = [list(map(int, input().split())) for _ in range(N)]

    # dp[S][v]: 訪問済み集合S、現在地vの最小コスト
    dp = [[INF] * N for _ in range(1 << N)]
    dp[1][0] = 0

    for S in range(1 << N):
        for v in range(N):
            if dp[S][v] == INF:
                continue
            if not (S >> v & 1):  # v が S に含まれていなければスキップ
                continue
            for u in range(N):
                if S >> u & 1:  # u がすでに訪問済みならスキップ
                    continue
                ns = S | (1 << u)
                cost = dp[S][v] + d[v][u]
                if cost < dp[ns][u]:
                    dp[ns][u] = cost

    full = (1 << N) - 1
    ans = min(dp[full][v] + d[v][0] for v in range(N))
    print(ans)

main()

Step-by-Step 解説

1状態の設計
$S$ = 訪問済み都市の集合をビットマスクで表現。例: $N=4$ のとき $S = 0b1011$ は都市 $0, 1, 3$ を訪問済み。状態数は $2^N \times N = 2^{20} \times 20 \approx 2 \times 10^7$（メモリ・計算量とも許容範囲）。

2初期化と遷移

初期状態: dp[0b0001][0] = 0（都市0のみ訪問、コスト0）
遷移: 現在地 $v$ から未訪問都市 $u$ へ移動 → dp[S|(1<<u)][u] = dp[S][v] + d[v][u]

3答えの取り出し
全都市訪問済み（S = (1<<N)-1）の状態から都市0に戻るコストを加算した最小値。

4計算量分析
状態数 $O(2^N \times N)$、各状態から $N$ 都市への遷移で全体 $O(2^N \times N^2)$。$N=20$ で約 $4 \times 10^8$（PyPy 推奨、Python は工夫が必要）。

よくあるミス

ミス	原因	正しい書き方
`dp[1<<0][0]` を `dp[0][0]` にする	$S=0$ は「誰も訪問していない」状態	`dp[1][0] = 0`（都市0を訪問済みにする）
`if not (S >> v & 1)` チェック漏れ	$v$ が $S$ にいない場合は無効状態	必ずチェックする
最後に `d[v][0]` を足し忘れ	帰還コストが含まれない	`dp[full][v] + d[v][0]`

Day 011-Q4 — ハミルトン路・巡回セールスマン（bitDP）

問題