Held-Karp 旅行推銷員演算法（Held-Karp TSP algorithm）
/ held karp /
旅行推銷員問題（TSP）要找最短的巡迴：從一個家城出發，恰好拜訪其他每個城市一次，再回到家。暴力法嘗試城市的所有 (n-1)! 種排序，即使只有 15 個城市也慢得驚人。Held-Karp 演算法是經典的動態規劃攻法：它仍需指數時間，但把階乘成長換成小得多的 2^n 成長，使原本無望的 15 城問題變得輕鬆、20 城問題成為筆電就能算的事。
關鍵體會是：要延伸一條部分巡迴路徑，你不需要記住拜訪城市的整個順序——你只需兩件事：你已拜訪了哪些城市（一個子集，存成位元遮罩），以及你目前身在哪個城市。關於你將如何完成巡迴的一切，都只取決於這兩個事實，於是許多不同的拜訪順序便壓縮成一個狀態。定義 dp[mask][i] 為「從家城出發、恰好拜訪 mask 中那組城市、並結束於城市 i（i 在 mask 中）」的最短路徑長度。基底情況是 dp[{home, j}][j] = dist(home, j)。轉移：要抵達 dp[mask][i]，你是從 mask 中某個前一個城市 j（j 不等於 i）來的，所以 dp[mask][i] = 在 j 上取 dp[去掉 i 的 mask][j] + dist(j, i) 的最小值。最終巡迴長度是在 i 上取 dp[全集][i] + dist(i, home) 的最小值。
共有 2^n 個子集乘以 n 個結束城市，故 O(2^n 乘以 n) 個狀態，每個需 O(n) 工作來考慮所有前驅，給出 O(2^n 乘以 n^2) 時間、O(2^n 乘以 n) 空間。這是指數的——TSP 是 NP 困難的，沒有已知的多項式演算法——但它遠勝 O(n!)，且可證明是精確的、而非近似。通常擋住你的是空間而非時間：儲存 2^n 乘以 n 個數字在 n = 20 附近還行，到 n = 30 就無望了。對更大的實例，人們改用近似演算法（如度量情形下的 Christofides）或分支定界法；Held-Karp 則是在小輸入上取得精確最佳解的黃金標準。
四個城市，home = 0。要算 dp[{0,1,2}][2]（已拜訪 0、1、2，現在在 2），你可能從 1 來：dp[{0,1}][1] + dist(1,2)。dp[{0,1}][1] = dist(0,1)。故 dp[{0,1,2}][2] = dist(0,1) + dist(1,2)。再比較各個全集項 dp[{0,1,2,3}][i] + dist(i,0)，找出最佳的封閉巡迴。
狀態 = （已拜訪城市集合，目前城市）；除此之外的路徑順序無關緊要。
Held-Karp 是精確且指數的，並非繞過 NP 困難的漏洞：它只是把 O(n!) 壓到 O(2^n 乘以 n^2)。它的記憶體高牆（2^n 個項）通常比時間先碰到，把實用上限壓在 n = 20 附近。