近似演算法

🎯 什麼情境該想到我

當你「確認問題是 NP-hard，但還是得交出一個答案」的時候。
★ 關鍵區分：「近似演算法」有數學保證，「啟發式」沒有。 兩者都有用，但你必須知道自己用的是哪一種。

⚙️ 怎麼用（定義與經典結果）

★ 近似比（approximation ratio）

$\rho ={\max }_{\text{所有實例}}\frac{\text{演算法的解}}{\text{最佳解}}(\text{最小化問題})$

$\rho$-近似演算法：保證對任何輸入，解都在最佳解的 $\rho$ 倍以內。

類別	意思
常數近似	$\rho$ 是常數（如 2-近似）
PTAS	對任意 $\epsilon >0$ 都能做到 $(1+\epsilon )$，時間對 $n$ 是多項式（但可能對 $1/\epsilon$ 是指數）
FPTAS	更強：時間對 $n$ 和 $1/\epsilon$ 都是多項式
不可近似	★ 有些問題連近似都很難（除非 P=NP）。例如一般 TSP 無法在多項式時間內做到任何常數近似

★ 「怎麼可能知道離最佳多遠？我又不知道最佳解」

這是這個領域最漂亮的地方，也是最常被問的：

答案：和「最佳解的下界」比，而不是和最佳解比。

例如頂點覆蓋：任何覆蓋都必須包含每條「極大匹配」邊的至少一端 →
最佳解 $\ge$ 匹配大小。而我們的演算法給出 $2\times$ 匹配大小 → $\le 2\times$ 最佳。

找一個好算的下界，是設計近似演算法的核心技巧。

四個經典結果

① 頂點覆蓋：2-近似

重複：任取一條還沒被覆蓋的邊 (u,v)，★ 把 u 和 v 「兩個都」放進答案

為什麼是 2-近似：選出的這些邊構成一個匹配（互不共用端點），
最佳解必須從每一條這樣的邊裡至少選一個 → 最佳 $\ge k$，而我們選了 $2k$。∎

★ 反直覺的地方：「兩個都拿」比「聰明地只拿一個」有更好的保證。

② 集合覆蓋：$\ln n$-近似（貪婪）

重複：選「還能新蓋住最多未覆蓋元素」的那個集合

這是 貪婪演算法 的經典應用。而且可以證明這個 $\ln n$ 是最優的（除非 P=NP，不可能做得更好）。

③ 滿足三角不等式的 TSP：2-近似（用 MST）

1. 求最小生成樹（見 [[Kruskal 最小生成樹]]）
2. 沿著 MST 做一次 DFS 前序走訪，依序連起來（跳過重複點）

為什麼 ≤ 2：MST $\le$ 最佳迴路（拿掉迴路的一條邊就是一棵生成樹）；
DFS 走訪每條樹邊兩次 $=2\times$MST；三角不等式保證「抄捷徑」不會更長。∎

Christofides 演算法改用「MST + 最小權完美匹配」可做到 1.5-近似。

④ 裝箱：First-Fit Decreasing 約 11/9-近似
先把物品由大到小排序，每個放進第一個放得下的箱子。

★ 近似演算法 vs 啟發式（最重要的區分）

	近似演算法	啟發式（heuristic）
保證	★ 有數學證明的上界	❌ 沒有任何保證
最差情況	已知且有界	可能非常糟
典型表現	⚠️ 常常不如好的啟發式	★ 實務上常常很接近最佳
例子	2-近似頂點覆蓋	模擬退火、遺傳演算法、LKH

★ 一個反直覺但重要的事實：
有保證的近似演算法，在真實資料上往往輸給沒有保證的啟發式。
2-近似的 TSP 解通常比最佳差 15–20%，而 Lin-Kernighan 這類啟發式常常在 1–2% 以內——但它沒有任何保證。

所以實務上的選擇通常是：

• 需要對外承諾品質、或用於計費／合約 → 要有保證 → 近似演算法
• 只要結果夠好 → 啟發式或求解器
• ★ 兩者並用：近似演算法給下界與保證，啟發式給實際答案

★ 實務上最該先考慮的其實是「求解器」

工具	適合
ILP / MIP 求解器（OR-Tools、CBC、Gurobi）	排程、分配、路線、裝箱
CP-SAT（OR-Tools）	★ 組合問題的瑞士刀，排班、排課特別強
SAT 求解器	邏輯約束、相依性求解（套件管理器內部就在用）
專用啟發式庫	TSP 的 LKH、VRP 的 OR-Tools routing

★ 這是實務上最被低估的選項。
與其自己寫一個近似演算法，把問題建模成 ILP/CP 丟給求解器，通常又快又好而且還能給出最佳性證明（gap）。
面試時提出這一點通常比背誦 2-近似證明更有價值。

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 先確認真的需要近似。$n$ 小就暴力、有結構就用特例演算法（見 NP 完備性 的七個策略）。
• ★ 近似比是「最差情況」。2-近似不代表「通常差 2 倍」，通常好得多——但也不保證。
• 三角不等式的前提要檢查。TSP 的 2-近似只在滿足三角不等式時成立（一般 TSP 不可近似）。
  現實中的地理距離滿足，但「機票價格」「轉乘時間」不一定滿足。
• 要量實際品質。小規模時跑暴力解或求解器算出最佳值，量出你的近似解實際差多少——不要只依賴理論保證。
• 啟發式要能重現。隨機化的啟發式要固定 seed，否則無法除錯也無法做 A/B。
• 別把啟發式說成有保證的。這是溝通上的誠實問題——「這個解大概很好」和「這個解保證在 2 倍內」是完全不同的承諾。

🔗 相關工具

• NP 完備性 —— 什麼時候需要走這條路，以及七種策略
• 貪婪演算法 —— 多數近似演算法的骨架
• Kruskal 最小生成樹 —— TSP 2-近似的基礎
• 最大流 —— 對照：一個有多項式精確解的組合問題
• 工具-找對數學模型、工具-演算法設計策略 —— 決策層
• 演算法導論