ビットDP（巡回セールスマン TSP）
訪問済みの都市集合をビット列で表し、Held–Karp の漸化式 dp[S][v] を 1 都市ずつ埋めて最短巡回路を復元します。
6
7
速度
状態数 2ⁿ × n
—
埋めた dp エントリ
—
現在の集合 S
—
最短巡回路長
—
dp[S][v] = min over u∈S\{v} ( dp[S\{v}][u] + dist(u, v) )
都市の地図（都市0=スタート赤・最短巡回路を緑で復元） ドラッグで移動
dp 表（行=訪問集合 S, 列=現在都市 v）／橙=埋まった, 青=計算中
巡回セールスマン問題（TSP）は「全都市をちょうど 1 回ずつ訪れて出発点に戻る最短経路」を求める問題です。素朴に全順列を試すと
ビットDP（Held–Karp 法）は「どの都市を訪問済みか」を n ビットの集合
計算量は
(n−1)! 通りで爆発します。ビットDP（Held–Karp 法）は「どの都市を訪問済みか」を n ビットの集合
S で表し、dp[S][v] =「集合 S の都市を訪れて今 v にいるときの最短距離」を小さい集合から順に埋めます。ビットが 1 つ立つ＝都市を 1 つ追加、という遷移です。計算量は
O(2ⁿ · n²)。全順列の O(n!) より圧倒的に速い一方、状態数 2ⁿ がメモリを食うので n を上げると一気に重くなる ── スライダーで体感しましょう。
いま何が起きている？
ここがポイント
- 状態 = 集合 + 現在地 ── 「訪問済み都市の集合 S」と「今いる都市 v」だけで未来が決まる（経路の途中の順序は忘れてよい）。
- ビットが集合を表す ──
Sの第 i ビットが 1 なら都市 i は訪問済み。集合演算が|・&の高速ビット演算になる。 - 小さい集合から埋める ──
dp[S][v]は「v を最後に追加する直前のdp[S\{v}][u]」から計算。だから集合サイズ昇順（=Sの値の昇順）に処理できる。 - 2ⁿ の壁 ── n!よりずっと速い
O(2ⁿn²)でも、n を 1 増やすと状態数は倍。n≈20 前後が実用限界。