跳轉到

8.1 近似演算法與近似比#

概念說明#

近似演算法（Approximation Algorithm）是多項式時間演算法，其輸出保證與最佳解的差距不超過某個因子。對最大化問題，定義近似比 ρ 為「最佳解 / 演算法解」，對最小化問題為「演算法解 / 最佳解」；ρ = 1 即精確解，ρ 越接近 1 越好。這個保證是對所有實例成立的數學定理，而不是平均值——這正是近似演算法與啟發式的本質區別。

三個經典例子勾勒出這個領域的光譜：

  1. 頂點覆蓋 2-近似：貪婪選邊的兩端點，證明可得 ρ = 2，極簡且優雅。
  2. TSP 的 Christofides 演算法：當距離滿足三角不等式時，利用最小生成樹與最小權完美匹配，保證 ρ = 1.5——四十多年來無人能改進（2020 年代有 1.5 - ε 的小幅突破）。
  3. 一般 TSP 無常數近似：若不要求三角不等式，任何常數倍近似都意味著 P = NP（因為可藉此判斷漢米爾頓迴路）。

近似比還有一個深刻面向：近似難度（hardness of approximation）。某些問題可以證明「存在 ε > 0，除非 P = NP，否則不存在 (1+ε)-近似演算法」，例如一般圖的最大集團幾乎不可近似（n^(1-ε) 下界）。PCP 定理是這些結果的基石，它把「優化困難」轉譯成「驗證困難」，是現代複雜度理論最深刻的成就之一。

演算法步驟（頂點覆蓋 2-近似）#

  1. C ← 空集合；E' ← 所有邊。
  2. 當 E' 非空：任取一條邊 (u, v)，把 u、v 加入 C。
  3. 刪除 E' 中所有與 u 或 v 相連的邊。
  4. 輸出 C。

正確性證明草稿：每輪選中的邊 (u, v) 彼此互不相交（匹配）；任何頂點覆蓋必須含每條匹配邊的至少一端，故 OPT ≥ 匹配數；而 |C| = 2 × 匹配數 ≤ 2·OPT。

Python 程式碼範例#

import networkx as nx

def vertex_cover_2approx(edges):
    """頂點覆蓋 2-近似：O(m)"""
    cover, used = set(), set()
    for u, v in edges:
        if u not in cover and v not in cover and \
           (u, v) not in used:
            cover |= {u, v}
            used.add((u, v))
    return cover

def metric_tsp_double_tree(pts):
    """歐氏 TSP 的 2-近似：最小生成樹兩倍走訪"""
    n = len(pts)
    d = lambda a, b: ((pts[a][0]-pts[b][0])**2 +
                      (pts[a][1]-pts[b][1])**2) ** 0.5
    # Prim 最小生成樹
    mst, seen = [], {0}
    while len(seen) < n:
        best = min(((d(u, v), u, v)
                    for u in seen for v in range(n)
                    if v not in seen))
        mst.append((best[1], best[2])); seen.add(best[2])
    # 樹的兩倍 + 走短路（preorder 遍歷即得 2-近似）
    adj = {i: [] for i in range(n)}
    for u, v in mst:
        adj[u].append(v); adj[v].append(u)
    tour, stack, visited = [], [0], set()
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u); tour.append(u)
        stack.extend(reversed(adj[u]))
    length = sum(d(tour[i], tour[(i+1) % n])
                 for i in range(n))
    return tour, length

# 用 networkx 的精確最小頂點覆蓋（小圖）比對近似品質
edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(0,2)]
G = nx.Graph(edges)
approx = vertex_cover_2approx(edges)
exact = nx.algorithms.approximation.min_weighted_vertex_cover(G)
print("近似:", approx, "networkx 近似:", exact)

pts = [(0,0),(2,3),(5,1),(6,4),(1,5),(3,6)]
print(metric_tsp_double_tree(pts))

複雜度分析#

  • 頂點覆蓋 2-近似：O(m) 時間，ρ = 2；且已證明除非 P = NP，不存在 ρ < 1.36 的近似——真相落在 [1.36, 2] 之間。
  • 雙樹 TSP：MST O(n²) + 遍歷 O(n)，總計 O(n²)，ρ = 2；Christofides 額外做最小權完美匹配 O(n³)，ρ = 1.5。
  • 一般原則：能寫成整數線性規劃的問題，其 LP 鬆弛解常給出自然近似（頂點覆蓋 LP 的整數性落差恰為 2）。
  • 近似難度：PCP 定理 ⟹ MAX-3SAT 除非 P = NP 無法 1.0136-近似；集團問題則幾乎不可近似。

練習#

  1. 生成隨機圖（n = 20，邊密度 0.3），比較 2-近似與暴力精確解的比值，統計 50 次實驗的平均近似比。
  2. 證明：把 2-近似演算法中的「選邊兩端」改成「選邊一端」不能保證任何近似比，並構造反例。
  3. 實作 Christofides 演算法中的最小權完美匹配（可用 networkx 的 min_weight_matching），與雙樹演算法比較在歐氏實例上的路徑長。