最著名的 NP-Hard 問題：精確解的極限在哪、啟發式又能多接近最優

精確解：Held–Karp 位元 DP

狀態設計（上一篇的直接升級）

Hamiltonian 判存在用布林，這裡問最短，把布林換成距離：

\[dp[S][v] = \text{從城 } 0 \text{ 出發、恰好經過集合 } S \text{、目前在 } v \text{ 的最短長度}\]

初始：\(dp[\{0\}][0]=0\)。轉移： \[dp[S\cup\{u\}][u] = \min\bigl(dp[S\cup\{u\}][u],\ dp[S][v] + d(v,u)\bigr)\] 答案：\(\min_{v\neq 0}\ dp[\text{全集}][v] + d(v,0)\)。時間 \(O(2^n n^2)\)、空間 \(O(2^n n)\)。

規模牆

\(n\approx 22\) 是家用電腦的實際極限。但相比 \(n!\) 枚舉（\(n=20\) 時 \(2.4\times10^{18}\)）已是天壤之別，而且 \(O(2^n\,\mathrm{poly})\) 至今仍是一般 TSP 的最佳精確複雜度——60 年沒人打破。

啟發式一：最近鄰（Nearest Neighbor）

從起點開始，每步走向最近的未訪城市，最後回起點。\(O(n^2)\)、三行寫完。品質：平均比最優差 10–25%，最壞可達 \(\Theta(\log n)\) 倍——它會把「順路該撿的城市」留到最後變成昂貴的長跳。

啟發式二：2-opt 局部搜尋

核心動作：拆兩邊、反轉重接

若 \(d(a,c) + d(b,e) < d(a,b) + d(c,e)\)，把 tour 中的 \((a,b)\) 與 \((c,e)\) 拆掉、中段反轉——直觀上是解開一個交叉：

反覆掃描所有 \((i,j)\) 對直到無法改善（局部最優）。每輪 \(O(n^2)\)，通常幾輪收斂。NN 建構 + 2-opt 改善是「兩分鐘寫完、效果驚人」的組合拳：實測小型歐氏實例常直接命中最優（見執行結果）。

手算範例：4 城市

距離矩陣（對稱）：\(d_{01}=10, d_{02}=15, d_{03}=20, d_{12}=35, d_{13}=25, d_{23}=30\)。

所有迴路只有 \((4-1)!/2 = 3\) 條本質不同： \[0\!\to\!1\!\to\!2\!\to\!3\!\to\!0:\ 10+35+30+20 = 95;\quad 0\!\to\!1\!\to\!3\!\to\!2\!\to\!0:\ 10+25+30+15 = \textbf{80};\] \[0\!\to\!2\!\to\!1\!\to\!3\!\to\!0:\ 15+35+25+20 = 95.\] 最優 80。NN 從 0 出發：最近是 1（10），1 的最近未訪是 3（25），再 2（30），回 0（15）——恰好也是 80。NN 不總是這麼幸運，Example 2 就沒中。

完整 C++ 程式

包含：Held–Karp（含 tour 還原）、NN、多起點 NN、2-opt、隨機歐氏實例產生器、與最優的 gap 統計、規模牆實測。編譯：

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

執行結果與解讀

=== Example 1: 4-city worked example ===
Held-Karp optimal = 80.00 (expect 80)  tour: 0-2-3-1-0
Nearest neighbor  = 80.00  tour: 0-1-3-2-0

=== Example 2: NN vs NN+2opt vs optimal (n=12, Euclidean) ===
optimal (Held-Karp): 301.09  (1.32 ms)
nearest neighbor   : 316.19  (+5.01% above optimal)
NN + 2-opt         : 301.09  (+0.00% above optimal, 0.00 ms)

=== Example 3: multi-start nearest neighbor ===
best of 12 starts: 311.10 (start=7, single-start was 316.19)

=== Example 4: the scaling wall ===
n=13 | HK 3.70 ms   (opt=338.65) | NN+2opt 0.01 ms (len=338.65, gap +0.00%)
n=16 | HK 38.10 ms  (opt=335.43) | NN+2opt 0.01 ms (len=335.43, gap +0.00%)
n=19 | HK 407.14 ms (opt=368.26) | NN+2opt 0.06 ms (len=368.26, gap +0.00%)
Held-Karp memory: 2^n * n doubles -> n=25 needs ~6.7 GB. Game over.

實務應用

• 物流路線：UPS 的 ORION 系統每天為 5.5 萬條路線做 TSP 級優化，號稱一年省 3 億美元油錢。

• 製造：PCB 鑽孔、雷射切割、3D 列印噴頭路徑——都是「訪問所有點的最短路」。

• 晶片測試：探針測試順序優化。

• 天文觀測排程：望遠鏡轉動角度最小化的觀測順序。

• 里程碑：Concorde 求解器已精確解出 85,900 城的實例（花了 136 CPU 年）——「NP-Hard」與「特定實例解不出」是兩回事的最佳證明。

練習題

1. 手算 5 城市完全圖（自訂距離）的 Held–Karp 表前兩層（\(|S|=2,3\) 的所有狀態）。

2. 把 2-opt 改成「first improvement」（找到第一個改善就做）vs 現在的「best sweep」，比較收斂速度與最終品質。

3. 實作 Or-opt（把連續 1–3 個城市搬到別處），疊在 2-opt 之後看還能擠出多少。

4. 對 \(n=100\) 隨機歐氏實例：NN、NN+2opt、多起點 NN+2opt 三者的 gap 統計（以多起點 2-opt 最好值當基準）。

5. 挑戰：實作 MST 下界（最優 tour \(\geq\) MST 權重），觀察 2-opt 解與下界的夾擠區間。

小結

延伸閱讀：Applegate et al. The Traveling Salesman Problem: A Computational Study（Concorde 團隊）；Lin & Kernighan (1973)；Karlin, Klein & Oveis Gharan (2021) 打破 Christofides 1.5 界的隨機化演算法。