第三部分：計算複雜度¶

< 上一題：NP 證明 | 返回目錄 | 返回總結 >

場景：伺服器選址問題¶

SearchX 要在全球部署資料中心。每個城市都有潛在用戶，但不可能每個城市都建機房。

目標：選最少的城市建機房，讓每個用戶都能連到**某個**機房。

這是 NP-Complete 的 Set Cover 問題。但客戶等不了，你需要一個「夠好」的解。

「找不到最佳解，那近似解呢？離最佳有多遠？」

第 8 題：伺服器選址 - 近似演算法¶

當問題是 NP-Hard，我們退而求其次：找一個**有品質保證**的近似解。

(a) 近似比的定義¶

3 分 ・大三

你需要知道：如何衡量近似演算法的品質？

題目：

定義近似比（Approximation Ratio）
什麼是 $\alpha$-approximation algorithm？
為什麼近似比很重要？

解答

1. 近似比：

對於最小化問題： $$\alpha = \frac{\text{演算法解}}{\text{最佳解}} \ge 1$$

對於最大化問題： $$\alpha = \frac{\text{最佳解}}{\text{演算法解}} \ge 1$$

2. $\alpha$-approximation：

演算法 $A$ 是 $\alpha$-approximation 若對**所有**輸入： $$\frac{A(I)}{\text{OPT}(I)} \le \alpha$$

3. 重要性：

有保證：不只是「通常不錯」，是「一定不超過最佳的 $\alpha$ 倍」
效率：通常是多項式時間
實用：真實世界中，2 倍最佳解往往夠用

近似比	含義
1	最佳解（通常不可能）
2	最多是最佳的 2 倍
$O(\log n)$	隨輸入大小緩慢增長

(b) Vertex Cover 的 2-近似¶

4 分 ・大三（考古題 113 Q13）

你需要知道：最經典的近似演算法

題目：

設計 Vertex Cover 的 2-approximation 演算法並證明近似比。

解答

演算法：Maximal Matching

def vertex_cover_approx(G):
    cover = set()
    edges = set(G.edges())

    while edges:
        # 任意選一條邊
        (u, v) = edges.pop()
        # 把兩端都加入 cover
        cover.add(u)
        cover.add(v)
        # 移除所有與 u 或 v 相連的邊
        edges = {e for e in edges if u not in e and v not in e}

    return cover

正確性：每條被選的邊，兩端都加入 cover，所以所有邊都被覆蓋。

近似比證明：

設演算法選了 $k$ 條邊，則 $|C| = 2k$（每條邊貢獻 2 個頂點）。

關鍵觀察：這 $k$ 條邊沒有共同端點（Matching）。

因此，最佳解**至少**要選 $k$ 個頂點來覆蓋這 $k$ 條邊。

\[\text{OPT} \ge k\]

\[\frac{|C|}{\text{OPT}} = \frac{2k}{\text{OPT}} \le \frac{2k}{k} = 2\]

時間複雜度：$O(|E|)$

© Set Cover 的貪心近似¶

4 分 ・大三

你需要知道：貪心法的近似保證

題目：

Set Cover：給定全集 $U$ 和若干子集 $S_1, \ldots, S_m$，選最少子集使聯集等於 $U$。

設計貪心演算法並分析近似比。

解答

貪心演算法：

def set_cover_greedy(U, sets):
    cover = []
    uncovered = set(U)

    while uncovered:
        # 選覆蓋最多未覆蓋元素的集合
        best = max(sets, key=lambda s: len(s & uncovered))
        cover.append(best)
        uncovered -= best

    return cover

近似比分析：

設 $|U| = n$，最佳解用 $k$ 個集合。

引理：第 $i$ 次迭代後，剩餘元素 $\le n(1 - 1/k)^i$

證明： - 每次迭代，最佳解的某個集合至少覆蓋「剩餘的 $1/k$」 - 貪心選的至少和它一樣好 - 所以剩餘減少至少 $1/k$ 的比例

迭代 $k \ln n$ 次後： $$n(1 - 1/k)^{k \ln n} \le n \cdot e^{-\ln n} = 1$$

近似比：$O(\ln n)$（或更精確地，$H_n = 1 + 1/2 + \cdots + 1/n$）

這是最佳的嗎？

是的！除非 P = NP，Set Cover 沒有 $(1-\epsilon) \ln n$ 的近似演算法。

(d) 無法近似的問題¶

3 分 ・大三

你需要知道：不是所有 NP-Hard 問題都有好的近似

題目：

說明為什麼有些問題很難近似。

解答

例子：一般 TSP

Claim：除非 P = NP，一般 TSP 沒有任何常數近似比。

證明（反證法）：

假設有 $\alpha$-approximation 演算法 $A$。

從 Hamiltonian Path 問題構造 TSP： - 如果原圖有邊 $(u,v)$，權重 = 1 - 如果原圖沒邊，權重 = $\alpha n + 1$

若有 Hamiltonian Path： - 最佳 TSP = $n$ - $A$ 輸出 $\le \alpha n$

若沒有 Hamiltonian Path： - 任何 tour 至少用一條權重 $\alpha n + 1$ 的邊 - 所以 $A$ 輸出 $> \alpha n$

用 $A$ 可以判斷 Hamiltonian Path！矛盾。

但是：Metric TSP（滿足三角不等式）有 1.5-近似（Christofides 演算法）。

近似難度分類：

問題	最佳近似比
Vertex Cover	2（可能最佳）
Set Cover	$\Theta(\ln n)$
Metric TSP	1.5
General TSP	無常數近似
Clique	$n^{1-\epsilon}$ 無法達成

(e) 隨機化近似演算法¶

3 分 ・大三

你需要知道：隨機化可以幫助近似

題目：

說明 MAX-3-SAT 的隨機化近似演算法。

解答

問題：給定 3-SAT 公式，最大化滿足的子句數。

隨機演算法：每個變數獨立隨機設為 TRUE/FALSE（各 50%）。

分析：

對於一個有 3 個文字的子句： - 不被滿足的機率 = $(1/2)^3 = 1/8$ - 被滿足的機率 = $7/8$

設有 $m$ 個子句，期望滿足 $7m/8$ 個。

最佳解最多 $m$ 個，所以：

\[\text{期望} = \frac{7m}{8} \ge \frac{7}{8} \cdot \text{OPT}\]

這是一個 8/7-approximation！

去隨機化：可以用 Method of Conditional Expectations 把隨機演算法轉成確定性演算法。

(f) 近似演算法總結¶

3 分 ・大三

你需要知道：什麼時候用什麼技術？

題目：

總結近似演算法的設計技術。

解答

常見技術：

技術	適用場景	例子
貪心	每步最佳選擇有保證	Set Cover, Vertex Cover
線性規劃放鬆	整數規劃問題	Set Cover, Facility Location
隨機化	期望分析有保證	MAX-SAT
局部搜尋	可改進解	MAX-CUT
動態規劃	FPTAS	Knapsack

近似類別：

類別	定義	例子
PTAS	對任何 $\epsilon > 0$，有 $(1+\epsilon)$-近似	Knapsack
FPTAS	PTAS + 時間是 $1/\epsilon$ 的多項式	Knapsack
APX	有常數近似比	Vertex Cover
Log-APX	有 $O(\log n)$ 近似比	Set Cover

實務建議：

先確認問題的近似難度（有無 hardness result）
選擇匹配的技術
簡單的貪心通常是好的起點
必要時用隨機化或 LP 放鬆

第 8 題小結：你的近似演算法工具箱¶

「NP-Hard 怎麼辦？」
    │
    ├─► (a) 近似比定義
    │       → 解/最佳 ≤ α
    │
    ├─► (b) Vertex Cover
    │       → Maximal Matching = 2-近似
    │
    ├─► (c) Set Cover
    │       → 貪心 = O(ln n)-近似
    │
    ├─► (d) 近似難度
    │       → 有些問題無法近似
    │
    ├─► (e) 隨機化
    │       → MAX-3-SAT: 7/8-近似
    │
    └─► (f) 技術總結
            → 貪心、LP、隨機化

近似演算法對照表：

問題	近似比	技術	是否最佳
Vertex Cover	2	Maximal Matching	可能
Set Cover	$H_n \approx \ln n$	貪心	是
Metric TSP	1.5	Christofides	未知
MAX-3-SAT	⅞	隨機化	是
Knapsack	FPTAS	動態規劃	是

選擇策略：

NP-Hard 問題
      │
      ▼
有常數近似？───是───► APX 技術（貪心、LP）
      │
      否
      ▼
有 log n 近似？───是───► 貪心（Set Cover 型）
      │
      否
      ▼
無法近似？───是───► 啟發式、特殊情況
      │
      否
      ▼
PTAS/FPTAS？───是───► DP + 縮放技術

< 上一題：NP 證明 | 返回目錄 | 返回總結 >

近似比	含義
1	最佳解（通常不可能）
2	最多是最佳的 2 倍
\(O(\log n)\)	隨輸入大小緩慢增長

類別	定義	例子
PTAS	對任何 \(\epsilon > 0\)，有 \((1+\epsilon)\)-近似	Knapsack
FPTAS	PTAS + 時間是 \(1/\epsilon\) 的多項式	Knapsack
APX	有常數近似比	Vertex Cover
Log-APX	有 \(O(\log n)\) 近似比	Set Cover