位元遮罩動態規劃與 Held-Karp 旅行推銷員演算法

當狀態是一個集合

本輪前兩篇導覽把動態規劃的狀態設成一段區間或一棵子樹——範圍與樹節點是整齊、井然有序的東西。但有些問題的狀態真真切切是一個子集：推銷員已造訪的城市集合、目前開著的機器集合、已分派到工作的人員集合。子集之間沒有自然的由左至右順序，而 n 個元素上有 2^n 個子集，所以一開始看來，用它們當表的索引根本無望。關鍵的領悟雖小卻有力：n 個項目的一個子集，恰好就是一串 n 個位元；而一串 n 個位元，恰好就是一個介於 0 與 2^n - 1 之間的整數。

於是我們把項目 {0, 1, 2, 3} 的子集 {0, 2, 3} 編碼成位元樣式 1101——位元 i 為 1 正好表示項目 i 在集合中——也就是整數 13。這個技巧，位元遮罩動態規劃，讓一個普通陣列 `dp[mask]` 能為每個子集存一筆值，並以一個普通整數為索引。集合運算化為單一機器指令：聯集是位元 OR、交集是 AND、「項目 i 在不在？」是 `mask & (1<<i)`、加入項目 i 是 `mask | (1<<i)`。暴力法那一輪列舉子集的整套機制，如今在動態規劃表裡有了安身之處。

把旅行推銷員問題誠實地建好

旅行推銷員問題（TSP）問的是：給定 n 座城市與每一對城市之間的距離，找出一條最短的巡迴路線，從某座城市出發、把其餘每座城市恰好造訪一次，再回到出發地。樸素的做法純粹是暴力法：試遍城市的每一種排列。相異的巡迴路線有 (n-1)! 條（固定起點，再排列其餘），而 (n-1)! 長得比 2^n 還快——n = 13 時就已約 4.79 億種排列。我們想做得更好，問題在於這所有排列之間共享了哪些工作。

重疊就在這裡。假設兩條不同的部分路線都從城市 0 出發、都恰好造訪了集合 S = {0, 2, 5, 7} 這些城市、且目前都停在城市 7。那麼把剩下的城市走完並回家的最便宜走法，對兩者是完全相同的，因為「未來」只取決於 還有哪些城市待訪 與 你現在站在哪裡，與你抵達此處所走的順序無關。這正是把動態規劃狀態端到我們面前：一個序對 (S, j)，意為「已造訪的城市集合是 S，而我此刻在城市 j」。兩條具有相同 (S, j) 的部分路線，從此以後可以互換——這正是藏在階乘之中的經典重疊子問題。

Held-Karp：遞迴關係式

令 dp[S][j] 為下述最短路徑的長度：從城市 0 出發、恰好造訪 S 中的城市（S 必須同時包含 0 與 j）、並結束於城市 j。我們會依造訪城市數 |S| 遞增的順序填這張表，這是自然的轉移方向。基底情況是最小的有趣集合：對每個 j，dp[{0, j}][j] = dist(0, j)——從起點直接到 j 的一跳路程。從那裡開始，每一步恰好新增一個新造訪的城市。

dp[{0,j}][j] = dist(0, j)                       # base: start -> j directly

# fill by increasing |S|; j must be in S, k is the previous city
dp[S][j] = min over k in S, k != j, k != 0 of
               dp[S \ {j}][k] + dist(k, j)

# best full tour: close the loop back to city 0
answer = min over j != 0 of dp[FULL][j] + dist(j, 0)

Held-Karp 遞迴關係式。要在造訪過 S 後抵達 j，你必先在某個較早的城市 k，它涵蓋了不含 j 的 S，再走一步 k -> j。

把中間那一行慢慢讀，因為它承載了整個正確性論證。任何以 j 結尾、造訪集合為 S 的最短路徑，必定是從某個緊鄰的前一城市 k 抵達 j 的，而在那最後一跳之前的那一刻，它是一條以 k 結尾、造訪集合恰為「S 去掉 j」的最短路徑。若那較早的一段本身不是最短，我們大可換上一段更便宜的，從而打敗我們所謂的最佳解——矛盾。所以 (S, j) 上的最佳值，是在每一個合法的前驅 k 上取的最小值，內容為「涵蓋不含 j 的 S 而抵達 k 的最佳走法」加上那單一條邊 dist(k, j)。這正是精準陳述的最佳子結構：最佳的整體由最佳的部件組成。

計算成本，並讀出巡迴路線

現在來看價碼，用記憶化那篇導覽教的方式算：（相異狀態數）乘（每個狀態的工作量）。狀態是序對 (S, j)：S 有 2^n 種選擇，而每個 S 之內 j 至多 n 種選擇，所以約 n * 2^n 個狀態。每個狀態的轉移要在至多 n 個前驅 k 上取最小值，是 O(n) 的工作。相乘：O(n^2 * 2^n) 時間，外加表所需的 O(n * 2^n) 空間。和暴力法的 (n-1)! 相比——n = 20 時，Held-Karp 約做 20^2 * 2^20 ~= 4 * 10^8 個基本運算，而 19! 約為 1.2 * 10^17。指數依然健在，但已被一個天文數字般的因子壓垮。

讓位元遮罩編碼真正划算的，是求值順序。如果你照單純遞增的整數順序為各遮罩 S 填 `dp[S]`，那麼每當你計算 dp[S][j] 時，去掉 j 的前驅遮罩是一個嚴格更小的整數——所以它早已填好。完全不需要按 |S| 明確排序；普通的整數順序免費地尊重了依賴關係，因為清掉一個設定位元總會讓數字變小。「少一個元素的集合」與「較小的整數」之間這個微小的巧合，正是位元遮罩動態規劃寫起來如此乾淨的一半原因。

先算出最佳巡迴路線的「長度」：answer = 在各 j 上取 min(dp[FULL][j] + dist(j, 0))，並記住達成它的 j*——那是回家前的最後一座城市。
要取回真正的路線，往回走：在狀態 (FULL, j*) 找出達成 dp[FULL][j*] = dp[FULL \ {j*}][k] + dist(k, j*) 的前驅 k，記下 j*，再移到狀態 (FULL \ {j*}, k) 並重複。
當集合縮到 {0} 時停止；把記下的城市反轉，就得到最佳巡迴路線。一如既往，重建只是沿一條狀態鏈往下走的廉價過程——遠比產生那些數值的填表便宜。

陷阱與誠實的界限

三個陷阱會絆住新手。第一，表是二維的——dp[mask][j]，而非 dp[mask]——因為兩條涵蓋相同集合卻結束於不同城市的路線，未來並不相同；把 j 從狀態裡省掉，你會得到一個快速而無聲錯誤的答案，正是記憶化那篇導覽警告過的漏掉維度的臭蟲。第二，位元操作的差一錯誤：`1 << i` 把一個 1 移到位置 i，而全集是 `(1 << n) - 1`，這是常見的小失誤。第三，常常真正的牆是記憶體而非時間：n = 22 時，long 型別的表 dp[2^22][22] 已達數百 MB，所以你會先撞上 RAM 的上限，再撞上時鐘。

並且讓漸進式保持誠實。O(n^2 * 2^n) 是一個最壞情況的尺度敘述；它對譬如 n = 25 時的絕對速度毫無溢美之詞，那裡光 2^25 就超過 3300 萬，而 n^2 因子又把它乘一遍。Held-Karp 是 TSP 已知最好的「精確」通用方法，但「已知最好的精確」並不等於「快」——面對成千上萬座城市的一整片大陸，你會完全放棄精確，改用啟發式法或近似法。確切知道一個精確指數方法在哪裡不再可用、以及跨過那條線時你拿什麼去交換，與遞迴關係式本身同樣是精通的一部分。