每個點恰好經過一次：用位元把「走過哪些點」壓成一個整數，\(n!\) 變 \(2^n\)

核心技術：狀態壓縮 DP

暴力的絕望與 DP 的救贖

枚舉所有拜訪順序是 \(O(n!)\)：\(n=18\) 時 \(18!\approx 6.4\times10^{15}\)，宇宙熱寂前跑不完。關鍵觀察：

狀態設計

用 \(n\) 位元整數 \(S\) 表示走過的點集（第 \(i\) 位 = 點 \(i\) 走過沒）：

\[dp[S][v] = \text{「存在一條恰好走過 } S \text{、結尾在 } v \text{ 的路徑」（布林）}\]

初始：\(dp[\{v\}][v] =\) 真（單點路徑）。 轉移： \[dp[S \cup \{u\}][u] \;\mathrel{|}= \; dp[S][v] \ \land\ (v,u)\in E \ \land\ u\notin S\] 答案：存在 \(v\) 使 \(dp[\text{全集}][v]\) 為真。時間 \(O(2^n n^2)\)、空間 \(O(2^n n)\)。

三個實用細節

• 路徑還原：記 \(parent[S][v]\) = 轉移來源點，從終點沿 \(S \setminus \{v\}\) 倒著走回去。

• 找 Cycle：固定起點 0（環從哪開始都一樣），DP 只從 \(dp[\{0\}][0]\) 起跑；最後檢查結尾 \(v\) 與 0 有邊。

• 位元技巧：鄰接表也存成 bitmask，「\(v\) 的未走訪鄰居」= adj[v] & ~S，配合 __builtin_ctz 逐位取出。

手算範例

菱形圖：邊 \(0\!-\!1,\ 0\!-\!2,\ 1\!-\!2,\ 1\!-\!3,\ 2\!-\!3\)。求 0 出發的 Hamiltonian Path：

\(dp[1111][3]\) 為真 \(\Rightarrow\) 存在，如 \(0\to1\to2\to3\)（用邊 \(0\!-\!1,1\!-\!2,2\!-\!3\)）。又 \(3\) 與 \(0\) 無邊，檢查其他結尾……\(dp[1111][1]\)：路徑 \(0\to2\to3\to1\)，而 \(1\!-\!0\) 有邊 \(\Rightarrow\) Hamiltonian Cycle 也存在：\(0\to2\to3\to1\to0\)。

完整 C++ 程式

包含：bitmask DP（Path 與 Cycle、含還原）、鏈+弦、立方體圖 \(Q_3\)（環 = 3 位元 Gray code）、Petersen 圖（著名的有 Path 無 Cycle）、\(n=18\) 效能展示。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o hamiltonian_path hamiltonian_path.cpp

執行結果與解讀

=== Example 1: path exists, cycle doesn't ===
Hamiltonian path : 4 -> 3 -> 2 -> 1 -> 0
Hamiltonian cycle: none

=== Example 2: cube graph Q3 ===
Hamiltonian path : 7 -> 5 -> 4 -> 6 -> 2 -> 3 -> 1 -> 0
Hamiltonian cycle: 0 -> 4 -> 5 -> 7 -> 6 -> 2 -> 3 -> 1 -> 0
(cycle = 3-bit Gray code!)

=== Example 3: Petersen graph (famous non-Hamiltonian) ===
Hamiltonian path : 7 -> 5 -> 8 -> 6 -> 9 -> 4 -> 3 -> 2 -> 1 -> 0
Hamiltonian cycle: none

=== Example 4: bitmask DP vs factorial enumeration ===
n=18: path FOUND in 50.7 ms (DP states with value=1: 534587)
compare: 18! = 6,402,373,705,728,000 permutations
         2^18 * 18^2 = 84,934,656 DP transitions
path: 16 -> 3 -> 15 -> 2 -> 12 -> 10 -> 4 -> 7 -> 13 -> 6 -> 17 -> 8 -> 14 -> 11 -> 9 -> 1 -> 5 -> 0

與 TSP 的關係

Hamiltonian Path 是 TSP 的「存在版」：TSP 問最短的走訪路線，這裡只問有沒有。把 \(dp\) 的布林值換成「最短距離」，轉移的 OR 換成 min，就得到下一篇的 Held–Karp 演算法——同一個狀態設計，兩道經典問題。

實務應用

• 基因組定序：把 DNA 片段重疊圖走一遍恰好一次以重建序列（實務多轉成 Euler 路徑模型的 de Bruijn 圖，正因 Hamiltonian 太難）。

• 電路布線與鑽孔：PCB 鑽孔機走訪每個孔位一次的路線規劃。

• 解謎：騎士巡遊（Knight’s Tour）= 棋盤跳躍圖的 Hamiltonian Path；許多一筆畫遊戲的本體。

• Gray code 與硬體：旋轉編碼器、K-map 化簡的排序都依賴 \(Q_n\) 的 Hamiltonian 結構。

練習題

1. 手算 \(K_4\)（完全圖）的 \(dp\) 表，數出 Hamiltonian Cycle 的數量（提示：\((4-1)!/2 = 3\)）。

2. 把程式改成計數版本：有幾條不同的 Hamiltonian Path？（布林 OR 改加法。）

3. 加一個優化：若圖不連通或存在度 0 的點，直接回報不存在。實測隨機稀疏圖的加速。

4. 實作「指定起點 \(s\) 與終點 \(t\)」的 Hamiltonian Path 判定。

5. 挑戰：\(5\times5\) 棋盤的騎士巡遊——建跳躍圖後用本程式找 Path（提示：\(n=25\) 需要 uint32_t 以上的 mask 與大量記憶體，想想怎麼分治或改用回溯 + Warnsdorff 啟發式）。

小結

延伸閱讀：Held & Karp (1962)、Bellman (1962) 同年獨立提出此 DP；Dirac／Ore 定理（度數夠大保證 Hamiltonian）；Björklund (2010) \(O(1.657^n)\) 的代數突破。