寫程式的人遲早會撞到一種牆：問題明明「聽起來很簡單」，程式卻怎麼寫都跑不完。 例如「把 40 個包裹分給兩台車，讓兩台車的重量儘量平均」——聽起來像小學數學， 但暴力枚舉有 \(2^{40} \approx 10^{12}\) 種分法；再快的電腦，指數成長都能讓它跪下。

這面牆有個名字，叫 NP-Hard。本教材用白話回答三個問題：

1. 這面牆是什麼？—— P、NP、NP-Complete、NP-Hard 到底在說什麼？ （第 1–4 章，全部用比喻與例子講，數學符號降到最低）

2. 撞牆之後怎麼辦？—— 四條實戰出路：聰明的暴力（精確解）、 有品質保證的妥協（近似演算法）、賭運氣但通常很準（啟發式）、 以及「先檢查你的問題是不是特例」（回到 P）。（第 5–9 章）

3. 真實世界怎麼與 NP 共處？—— 晶片驗證、物流路線、排班、 密碼學，每天都在跟 NP-Hard 問題打交道，而且活得很好。（第 10 章）

為什麼有些問題「算不動」？

兩種成長速度：多項式 vs. 指數

演算法的核心貨幣是時間隨輸入大小的成長速度。同樣是「變慢」， \(n^2\) 跟 \(2^n\) 是兩個完全不同的世界：

假設電腦每秒做 \(10^9\) 次運算：\(n=100\) 時 \(n^3\) 只要 0.001 秒， 而 \(2^n\) 要 \(10^{13}\) 年——宇宙年齡的一千倍。這就是為什麼理論界把 「多項式時間（polynomial time）」當作「有效率、可實用」的分界線： 多項式再大也追得上，指數永遠追不上。

枚舉的詛咒：組合爆炸

很多實際問題的「候選解」數量是指數級的：

• 40 個物品「選或不選」：\(2^{40} \approx 10^{12}\) 種組合。

• 20 個城市的巡迴順序：\(19! \approx 10^{17}\) 條路線。

• 100 個布林變數的真假指派：\(2^{100} \approx 10^{30}\) 種。

這些問題有個共同特徵：檢查一個候選解對不對很快（把路線長度加一加、 把公式代入驗證），但候選解多到不可能全部看完。 「驗證容易、求解疑似困難」——這正是 NP 理論要形式化的現象。

一個具體例子：拼圖 vs. 檢查拼圖

於是自然冒出一個看似天真、實則是電腦科學最深的問題：

這就是價值一百萬美元的 P vs. NP 問題（第 2 章）。

P、NP、NP-Complete、NP-Hard 白話定義

先說清楚：我們談的是「決策問題」

複雜度理論的標準舞台是決策問題（decision problem）——答案只有「是／否」的問題。

• 優化版：「最短的巡迴路線是多長？」

• 決策版：「存在長度 \(\leq K\) 的巡迴路線嗎？」

兩者實務上等價（用二分搜尋 \(K\) 就能從決策版逼出優化版）， 但理論上用決策版比較乾淨。下文的 P、NP 都是「決策問題的集合」。

P：解得快

排序、最短路徑、最小生成樹、二分圖匹配、質數判定、2-SAT——都在 P。 白話：P = 我們已經知道怎麼有效率解決的問題。

NP：驗得快

NP-Complete：NP 裡最難的一批

白話：NP-Complete 問題是 NP 世界的「萬能鑰匙孔」—— 任何 NP 問題都能翻譯成它。因此只要任何一個 NP-Complete 問題 找到多項式解法，整個 NP 全部瞬間變成 P，世界改寫（\(P = NP\)）。 反過來，只要你相信 \(P \neq NP\)，那所有 NP-Complete 問題都沒有多項式解法。

NP-Hard：至少跟 NP-Complete 一樣難

例如「TSP 優化版（求最短巡迴）」是 NP-Hard：它不是是／否問題， 嚴格說不在 NP 裡，但它顯然不比決策版容易。 極端例子如停機問題（Halting Problem）也是 NP-Hard——它根本不可計算。

一張圖看懂四個類別

P vs. NP：百萬美元懸案

「\(P = NP\) 嗎？」是克雷數學研究所七大千禧年大獎難題之一， 懸賞一百萬美元，至今（2026 年）仍未解決。學界壓倒性地相信 \(P \neq NP\) ——「找解」本質上就是比「驗解」難——但沒有人能證明。 已知的證明技巧（相對化、自然證明）都被證明「不足以」解決這題， 這也是它難的原因之一。

歸約：難度的「翻譯機」

歸約的白話意思

Cook–Levin 定理：第一把萬能鑰匙

白話：任何 NP 問題的「驗證過程」都能被編碼成一條巨大的布林公式， 使得「公式可滿足 \(\iff\) 原問題答案為是」。 這是史上第一個被證明的 NP-Complete 問題——有了第一個， 之後只要「已知 NPC 問題 \(\leq_p\) 新問題」，新問題就也是 NPC。 Karp 在 1972 年一口氣用歸約證明了 21 個經典問題都是 NPC，開啟了整個領域。

經典歸約鏈

箭頭 \(A \to B\) 表示「\(A\) 歸約到 \(B\)，因此 \(B\) 也是 NP-Complete」。 所有 NPC 問題彼此都可互相歸約——它們是同一種難的不同化身。

體驗一個歸約：Independent Set \(\leq_p\) Vertex Cover

這是最漂亮的入門歸約，一行就講完：

直覺：獨立集內部沒有任何邊，所以每條邊至少有一端在集合外—— 集合外的點恰好「覆蓋」了所有邊。翻譯程式只需要把 \(k\) 換成 \(n-k\)， 顯然是多項式時間。兩題難度綁定，一起難、一起easy。

經典 NP-Complete 問題圖鑑

以下每個問題都給：白話定義、一句話記憶點、真實應用。 它們是面試、競賽與論文中的常客。

邏輯類

SAT（布林可滿足性）

給一條布林公式，如 \((x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3)\)， 問：有沒有一組真假指派讓整條公式為真？ 記憶點：NPC 的始祖（Cook–Levin）。 應用：晶片等價性驗證、軟體模型檢查、排程。

3-SAT

限制每個子句恰好 3 個文字的 SAT。依然 NPC， 且因為結構整齊，是最常拿來當歸約起點的問題。 （對照：2-SAT 每子句 2 個文字，卻掉回 P——見第 9 章。）

圖論類

Vertex Cover（頂點覆蓋）

選最少的頂點，使每條邊至少有一端被選中。 比喻：在每條走廊都看得到的位置裝最少的監視器。 應用：感測器佈點、測試案例挑選。

Independent Set（獨立集）

選最多的頂點，任兩個都不相鄰。 比喻：宴會排座位，互相有過節的人不能同桌。 與 Vertex Cover 互補（\(S\) 獨立 \(\iff V \setminus S\) 覆蓋）。

Clique（最大團）

找最大的「彼此全認識」子圖。 應用：社群偵測、蛋白質交互作用分析。 與 Independent Set 在補圖上等價。

Graph Coloring（圖著色，\(k \geq 3\)）

用 \(k\) 種顏色塗頂點，相鄰不同色。 應用：排課／排考（衝突的課不同時段）、 編譯器暫存器配置、無線頻譜分配。 注意 \(k=2\)（二分圖判定）在 P。

Hamiltonian Path / Cycle

一條「恰好經過每個頂點一次」的路徑／迴圈。 對照組：歐拉路徑（每條邊恰一次）在 P！ 一字之差，難度天壤之別。

數字與組合類

Subset Sum（子集和）

一堆整數裡，能否挑出一個子集恰好加到目標值 \(T\)？ 應用：對帳（哪幾筆交易加起來是這個總額？）。

Partition（分割）

能否把一堆數分成總和相等的兩半？是 Subset Sum 取 \(T = \text{總和}/2\) 的特例，仍 NPC。 比喻：兩台貨車載重平均。

0/1 Knapsack（背包，決策版）

容量 \(W\) 的背包、每件物品有重量與價值，能否裝出價值 \(\geq V\)？ 重要註腳：有 \(O(nW)\) 的 DP——但這是偽多項式（見第 6 章），不與 NPC 矛盾。

Bin Packing（裝箱）

把不同大小的物品裝進容量固定的箱子，最少用幾箱？ 應用：貨櫃裝載、雲端虛擬機配置、廣告版位。

Set Cover（集合覆蓋）

給一堆集合，選最少個把全集蓋滿。 應用：選最少的測試涵蓋所有功能、消防站選址。

路徑類

TSP（旅行推銷員）

訪問每個城市恰一次並回到起點，總距離最短。 決策版 NPC；優化版 NP-Hard。 應用：物流配送、電路板鑽孔路徑、基因定序排程。

速查表

撞牆之後的四條路

證明（或強烈懷疑）你的問題是 NP-Hard 之後，不代表舉手投降。 實務上有四條路，後面四章各講一條：

路 1：精確解——聰明的暴力

精確解仍是指數時間，但透過剪枝與記憶化， 實務可解的規模遠比天真枚舉大。所有程式碼見第 11 章。

回溯 + 剪枝：N-Queens

回溯法（backtracking）＝深度優先枚舉＋「一發現不可行就立刻退回」。 N-Queens（在 \(n \times n\) 棋盤放 \(n\) 個互不攻擊的皇后）是教科書範例：

• 逐列放置：每列恰一個皇后，衝突只需檢查「直行、兩條對角線」。

• 用三個布林陣列，\(O(1)\) 判斷衝突；一衝突整棵子樹直接跳過。

實測：\(n=8\) 得 92 解、\(n=10\) 得 724 解，瞬間完成—— 剪枝把 \(8^8 \approx 1600\) 萬的枚舉空間砍到只剩幾千個節點。

DPLL：SAT 求解器的雛形

DPLL（Davis–Putnam–Logemann–Loveland, 1962）＝回溯＋兩條關鍵推理：

• 單元傳播（unit propagation）：某子句只剩一個未定文字時，它被迫為真——連鎖反應常能瞬間定下大量變數。

• 提早偵測矛盾：出現空子句立刻回溯。

現代工業 SAT solver 的核心 CDCL（Conflict-Driven Clause Learning） 就是 DPLL 加上「從衝突中學出新子句、非時序回跳」等強化， 實務能處理數百萬變數的實例（第 10 章）。

偽多項式 DP：Knapsack 與 Subset Sum

Knapsack 有經典 DP：\(dp[c] =\) 容量 \(c\) 下的最大價值，時間 \(O(nW)\)。 「咦？這不是多項式嗎？」——不是。

Meet-in-the-Middle：\(2^n \to 2^{n/2}\)

Subset Sum 在值域巨大時 DP 失效，但可以對半分： 枚舉左半所有子集和（\(2^{n/2}\) 個）、右半也枚舉並排序， 再對每個左半的和二分搜尋「互補值」。 \(n=40\) 時從 \(10^{12}\) 降到約 \(2 \times 10^6\)——瞬間可解。 空間換時間的經典。

位元壓縮 DP：Hamiltonian 與 TSP（Held–Karp）

用一個整數的位元表示「已拜訪的城市集合」：

\[dp[\text{mask}][v] = \text{走過集合 mask、目前在城市 } v \text{ 的最短距離}\]

轉移即嘗試下一個未拜訪城市。時間 \(O(n^2 2^n)\)、空間 \(O(n 2^n)\)—— \(n=20\) 約 4 億次運算，秒級可解。比 \(n!\) 枚舉快了 \(10^{11}\) 倍。 這是「指數但聰明」的代表作：實測 4 城市經典例最佳解 80，正確。

分支限界與 FPT：Vertex Cover

「覆蓋數 \(\leq k\)？」有個優雅的二分支：任取一條邊 \((u,v)\)， u 或 v 必有一個要選——分兩支遞迴，深度最多 \(k\)。 時間 \(O(2^k \cdot \text{poly}(n))\)：對輸入大小指數在 \(k\) 上， \(n\) 再大、只要 \(k\) 小就跑得動。這叫參數化複雜度／FPT （Fixed-Parameter Tractable），是理論界對付 NP-Hard 的第五條暗路。 （目前最好的 Vertex Cover FPT 約 \(O(1.25^k + kn)\)。）

路 2：近似演算法——妥協，但有收據

近似比：品質保證書

白話：我不給你最好的，但白紙黑字保證離最好差不到 \(\alpha\) 倍。 這跟啟發式的差別就在這張「收據」。

Vertex Cover 的 2-近似：漂亮到不像話

1. 隨便找一條還沒被覆蓋的邊 \((u,v)\)，兩個端點都選。

2. 刪掉所有被覆蓋的邊，重複直到沒有邊。

為什麼是 2-近似？我們選的邊彼此不共點（是一組匹配）， 最優解對每條這種邊至少要選 1 個端點，我們選了 2 個—— 所以最多是最優的 2 倍。三行演算法、一行證明。 （實測：5 邊小圖輸出 4 個點，OPT 為 2，正好卡在保證線上。）

Set Cover 的貪婪 \(\ln n\)-近似

每一輪選「能新覆蓋最多元素」的集合，直到蓋滿。 可證明近似比為 \(H_n \approx \ln n\)，而且（除非 \(P = NP\)） 沒有演算法能做得更好——貪婪就是極限。 實務中它常遠比理論保證好。

Bin Packing 的 First-Fit Decreasing

物品由大到小排序，逐一放進「第一個放得下的箱子」。 保證用箱數 \(\leq \frac{11}{9} OPT + 1\)。 直覺：大物品先卡位，小物品填縫，浪費不會太多。 實測 10 件物品用 5 箱，正好等於下界 \(\lceil \text{總體積} \rceil\)——碰到最優。

Metric TSP：MST 2-近似與 Christofides 1.5-近似

當距離滿足三角不等式（繞路不會更近）時：

• MST 2-近似：造最小生成樹 → 沿樹走一圈（每邊走兩次）→ 跳過重複城市（shortcut）。因為 \(MST \leq OPT\)， 繞兩圈 \(\leq 2 \cdot OPT\)。

• Christofides 1.5-近似：MST ＋ 奇度數頂點間的最小完美匹配 → 歐拉迴路 → shortcut。近似比 1.5，懸了 45 年後 才在 2020 年被改進了 \(10^{-36}\) 那麼一點——理論突破，實務不變。

路 3：啟發式——沒有保證，但實務常勝

建構式啟發：最近鄰

TSP 的最近鄰法：每次走向「還沒去過的最近城市」。 快（\(O(n^2)\)）、直覺，但品質平平（典型離最優 10–25%）， 常拿來當起始解。

局部搜尋：2-opt

拿到一條路線後，反覆嘗試「把路線中某一段反轉」—— 等價於把兩條交叉的邊解開——只要變短就採用，直到無法改善。

我們的實測（12 城市隨機點）：最近鄰起手後 2-opt 收斂， 離 Held–Karp 精確解仍有 4.5% 差距——這示範了局部搜尋會卡在 局部最優：附近沒有更好的解，但全域還有。

跳出局部最優：模擬退火與其他

• 模擬退火（Simulated Annealing）：偶爾接受變差的解， 接受機率隨「溫度」下降——早期亂跳探索、後期收斂精修。 靈感來自金屬退火。

• 禁忌搜尋（Tabu Search）：記住最近走過的解，禁止走回頭路。

• 遺傳演算法（Genetic Algorithm）：一群解互相「交配＋突變」，優勝劣汰。

• 蟻群演算法（Ant Colony）：用「費洛蒙」累積好路徑的記憶。

這些統稱 metaheuristics：不保證品質、不保證收斂時間， 但工程實務上經常是「效果最好的那個」。

工業級現實：solver 比你想的強大

• TSP：精確 solver Concorde（分支切割法）已解出 85,900 城市的最優解；啟發式 LKH（Lin–Kernighan–Helsgaun） 對數萬城市常在最優 0.02% 之內，秒級完成——物流業的日常主力。

• SAT：CDCL solver（MiniSat、Kissat 等）處理百萬變數等級的 硬體驗證實例；晶片業每天靠它檢查電路等價性。

• 通用建模：ILP solver（Gurobi、CPLEX）、 Google OR-Tools（CP-SAT）讓你「描述問題、不寫演算法」。

路 4：特例回到 P——先檢查你的問題長什麼樣

NP-Hard 是對最壞情況、一般形式的判決。 你手上的實例常常有特殊結構，讓問題整個掉回 P。

2-SAT：一字之差，天壤之別

3-SAT 是 NPC，但每子句只有兩個文字的 2-SAT 可以線性時間解：

• 子句 \((a \lor b)\) 改寫成兩條蘊含：\(\neg a \Rightarrow b\)、\(\neg b \Rightarrow a\)。

• 把每個變數拆成「真、假」兩個節點，蘊含變成有向邊，建出蘊含圖。

• 跑 SCC（強連通分量，見圖論教材 Tarjan）： 若某變數 \(x\) 與 \(\neg x\) 落在同一分量 → 矛盾，UNSAT； 否則依分量的拓撲序即可讀出一組解。

為什麼 3 個文字就不行？因為 \((a \lor b \lor c)\) 無法寫成單純的 「一個假就逼另一個真」——蘊含結構崩掉了。 難與易的分界線常常細得驚人。

其他常見的「掉回 P」情境

真實世界如何與 NP 共處

密碼學：把「難」當成資產

NP-Hard 不全是壞消息——現代密碼學依賴「某些問題難解」： RSA 靠大整數分解難、離散對數系統靠指數難。 如果 \(P = NP\) 且演算法實用，這些防線一夜蒸發。 「難」在這裡是保護你銀行帳戶的城牆。 （註：分解質因數目前未被證明 NP-Complete， 它是「疑似不在 P、也疑似不是 NPC」的中間地帶，也是量子電腦 Shor 演算法能攻破的原因。）

晶片與軟體驗證：SAT solver 的主場

驗證兩個電路等價、驗證程式不會進入危險狀態，都被編碼成 SAT。 CDCL solver 例行處理數百萬變數的實例； 從 CPU 設計、作業系統驗證到數學定理的機器證明， SAT 被稱為電腦科學「安靜的革命」。

物流與路線：TSP/VRP 的日常

外送平台、貨運公司每天解的就是 TSP 與它的加強版 VRP（多車、時間窗、容量）。 實務配方：LKH 這類 heuristic 起手 + 局部搜尋精修， 數萬個點在幾秒內得到離最優 1% 內的路線； 需要保證時用 Concorde 這類精確 solver 處理較小的實例。

排程與資源分配

• 排課／排班：本質是圖著色＋各種限制， 實務用 CP-SAT / ILP solver 建模求解。

• 編譯器暫存器配置：變數衝突圖著色， LLVM 等用啟發式（圖著色 + spill）。

• 雲端資源打包：把 VM 塞進最少的實體機 = Bin Packing， 資料中心的省電核心邏輯。

• 頻譜分配：基地台頻率互擾 = 著色問題。

生物資訊與其他

蛋白質結構比對、基因組重組距離、系統發生樹重建， 多數是 NP-Hard，靠啟發式與近似撐起整個領域。 連遊戲設計都有份——數獨（一般化）、踩地雷（一般化）、 俄羅斯方塊（離線版）都被證明 NP-Complete。

完整 C++ 實作

本章提供一份完整、可直接編譯執行的 C++17 程式碼， 涵蓋全書 13 個演算法。此程式碼已實際以 g++ -std=c++17 -O2 -Wall -Wextra 編譯並執行驗證通過。

編譯與執行

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

原始碼

執行輸出（節錄）

1. N-Queens: n=4 -> 2 | n=8 -> 92 | n=10 -> 724 solutions
2. DPLL SAT: formula A: SAT  model: x1=1 x2=0 x3=1
             formula B (x & ~x): UNSAT
3. Subset Sum {3,34,4,12,5,2}: sum=9 -> yes | sum=30 -> no
4. Knapsack W=50 -> best value = 220 (expect 220)
5. Coloring: K4 3-color no / 4-color yes | C5 2-color no / 3-color yes
6. Hamiltonian: path graph yes | star graph no
7. TSP Held-Karp 4-city -> optimal = 80 (expect 80)
8. Vertex Cover branching: k=1 no | k=2 yes
9. VC 2-approx: size=4 (OPT=2, bound 2*OPT=4)
10. Set Cover greedy: S0 S3 (count=2)
11. Bin Packing FFD: bins used = 5 (= lower bound)
12. TSP 12 cities: NN 3574.4 -> 2-opt 3574.4 vs exact 3420.5 (gap 4.5%)
13. 2-SAT: formula C SAT (x0=1 x1=1 x2=1) | formula D UNSAT

練習題

觀念題

1. 用自己的話解釋：為什麼「NP」不是「非多項式」的意思？

2. 你朋友宣稱：「我證明了 Sudoku（一般化 \(n^2 \times n^2\)）有多項式解法。」 如果他是對的，對整個 NP 世界意味著什麼？

3. 為什麼「TSP 優化版」通常說是 NP-Hard 而不說 NP-Complete？

4. Knapsack 有 \(O(nW)\) 的 DP，為什麼它仍是 NP-Complete？ 「偽多項式」的「偽」在哪裡？

5. 證明：\(S\) 是獨立集 \(\iff V \setminus S\) 是頂點覆蓋。 並由此說明兩個問題的難度為何綁在一起。

實作題

1. 修改 N-Queens 程式，輸出一組具體解（而不只是計數）。

2. 把 Subset Sum 的 DP 改成同時輸出「選了哪些數」。

3. 為 DPLL 加上「純文字消去」（pure literal elimination）： 若某變數在所有子句中只以同一極性出現，直接賦值。

4. 用 Held–Karp 的 \(dp\) 表回溯出實際的最短巡迴路線。

5. 實作模擬退火版 TSP，跟 2-opt 比較誰更接近 Held–Karp 精確解。

6. 實作「度量 TSP 的 MST 2-近似」（提示：用圖論教材的 Prim + DFS 走訪 + shortcut），實驗它實際離最優多遠。

7. 把「排課問題」（\(n\) 門課、衝突表、\(k\) 個時段）建模成圖著色， 用回溯求解；再試著加上「先著色度數最大的點」的排序啟發，觀察加速。

挑戰題

1. 證明 Partition \(\leq_p\) Bin Packing 決策版（提示：兩個容量恰好的箱子）。

2. 寫一個 3-SAT 隨機實例產生器，觀察「子句數/變數數」比值 在 4.27 附近時 DPLL 突然變慢的相變現象。

3. 研究 Vertex Cover 的核心化（kernelization）： 先套用「度數 \(> k\) 的點必選」規則，再分支，能快多少？

總結與延伸閱讀

全書速查表

學習路徑建議

1. 先會分類：拿到問題能判斷「這是不是經典 NPC 的偽裝」。 （多看第 4 章圖鑑，面試中「認出題型」值一半分數。）

2. 掌握三個精確技巧：回溯剪枝、偽多項式 DP、位元壓縮 DP—— 競賽與面試的主力。

3. 記住三個近似經典：VC 的 2、Set Cover 的 \(\ln n\)、 Metric TSP 的 1.5——連證明一起記，很短。

4. 學會用 solver：把問題編成 SAT / ILP 是現代工程師的核心能力。

5. 深入理論（選修）：歸約證明、PCP 定理與不可近似性、 參數化複雜度、平均情況複雜度。

延伸閱讀

• Computers and Intractability（Garey & Johnson）—— NP-Complete 的聖經，附 300+ 問題圖鑑。

• Introduction to Algorithms（CLRS）第 34–35 章—— NP-Completeness 與近似演算法的標準教材。

• Algorithm Design（Kleinberg & Tardos）第 8、10–12 章—— 歸約與近似講得最好懂的一本。

• Approximation Algorithms（Vazirani）——近似演算法專書。

• Parameterized Algorithms（Cygan et al.）——FPT 專書。

• In Pursuit of the Traveling Salesman（William Cook）—— TSP 的科普史，Concorde 作者親筆。

• The Silent (R)evolution of SAT（CACM）——現代 SAT solver 綜述。

• Clay Mathematics Institute：P vs NP 千禧年大獎題官方頁面。