近似比 — JOVANA Education

當「精確」太昂貴時該怎麼辦

你帶著上一階傳來的壞消息抵達這一階。一旦某問題被證明是NP 困難，地球上沒有人知道一個總能傳回精確最佳解的多項式時間演算法，而且——因為 P 對 NP 問題仍未解決——也沒有人證明這樣的演算法不存在。所以對一個真正 NP 困難的問題（如頂點覆蓋或旅行推銷員），有三條誠實的路。你可以堅持要精確最佳解，並付出可能指數的時間。你可以跑一個快速的啟發式法、然後祈禱它表現不錯，但毫無保證。又或者，你走這一整階要談的那條中間道路：跑一個快速演算法，而它附帶一個可證明的保證，告訴你它的答案最多能離最佳解多遠。

第三條路，正是近似演算法所做的事。它在多項式時間內執行，並帶著一個定理，把它的輸出品質界定在那個未知的最佳解之上。注意它與單純啟發式法的對比：啟發式法在實務上也許極為出色，卻給不了你任何能證明的東西；而近似演算法則用一點點解的品質，換來一個你能寫下來、且對每一個輸入都信得過的保證。記錄這個保證強度的那個數字，就是近似比，而把它弄得分毫不差——包括它的方向慣例與它誠實的限制——正是這第一篇的工作。

在看不見最佳解的情況下定義近似比

核心訣竅來了，值得放慢腳步：這個定義把你的答案，拿去和一個你算不出來的最佳解比較。令 OPT 為某給定實例之真正最佳解的值（成本或收益），令 ALG 為你的演算法在同一實例上傳回的值。對於一個最小化問題（頂點覆蓋想要最少的頂點、旅行推銷員想要最短的路線），若對每一個實例都有 ALG <= c 乘以 OPT，我們就說該演算法是一個 c-近似，其中 c >= 1。因此一個 2-近似承諾 ALG 永遠不超過最小可能值的兩倍——成本至多翻倍，絕不更糟。c 越接近 1，承諾越緊；c = 1 就代表精確。

對於一個最大化問題（背包問題想要最多的價值、最大割想要最多被割斷的邊），不等式翻轉：若對每一個實例都有 ALG >= c 乘以 OPT，演算法就是一個 c-近似，其中 0 < c <= 1。最大化問題的一個 (1/2)-近似保證你至少收集到最佳值的一半。各家教科書的慣例不同——有些把最大化的比值寫成 OPT/ALG >= 某個 >= 1 的數，好讓「比值越大＝越差」與最小化那邊一致——所以閱讀任何資料時，都要先確認不等式指向哪一邊。實質完全相同，翻轉的只是記帳方式。

深層的謎題：你如何對一個未知的 OPT 設界？

停下來，感受一下這個困難。要證明 ALG <= 2 乘以 OPT，你似乎需要 OPT——但計算 OPT 正是你已放棄的那個 NP 困難問題。出路，也是近似中最重要的單一觀念，就是 OPT 的下界（對最大化問題則是上界）。你找出某個能廉價算出、且能證明無論最佳解如何都滿足 L <= OPT 的量 L。接著你證明你的演算法輸出滿足 ALG <= 2 乘以 L。把這些串起來：ALG <= 2L <= 2 乘以 OPT，而 OPT 本身從來不必被算出——它被夾在兩個你掌控的量之間。

經典範例是頂點覆蓋的 2-近似，下一篇會完整展開；這裡只先看論證的形狀。演算法反覆挑出任一條尚未被覆蓋的邊，把它的兩個端點都抓進來。它挑出的那些邊構成一個匹配——沒有兩條共用頂點——而任何合法的頂點覆蓋都必須包含每條被匹配邊的至少一個端點，因此 OPT >= （被匹配邊的數目）。這個不等式就是你那個可計算的下界 L。同時，演算法對每條被匹配邊恰好取了 2 個端點，所以 ALG = 2 乘以（被匹配邊數）= 2L <= 2 乘以 OPT。匹配就是那座鷹架：它是我們看得見、數得出的東西，能從下方釘住 OPT，而我們從不必真的找到 OPT。

want to prove:   ALG  <=  c * OPT     (minimization)

but OPT is NP-hard to compute, so instead:
  1. build a cheap, computable L  with  L <= OPT   (a lower bound on OPT)
  2. relate the algorithm to L:        ALG <= c * L
  3. chain them:               ALG <= c*L <= c * OPT     done.

(maximization: build a cheap U with OPT <= U, show ALG >= c*U)

通用範本：每個近似證明都為 OPT 找一個可計算的替身，並把那個未知的最佳解夾在它與演算法輸出之間。

為何近似比比「它通常有效」更誠實

你已經見過一個沒有這種保證的演算法。對 0/1 背包問題的貪婪法——依「每單位重量價值」由高到低取物——看起來合理、也常常沒問題，但它可以被弄得壞到任意程度：一個被貪婪略過的、又重又極有價值的單品，可能讓它只拿到 OPT 的微小一部分。「看起來在局部最好」從來就不是證明，而在這裡它根本沒有任何最壞情況的倍數。這正是近似比要填補的那道縫。它逼你去直面對手最惡毒的實例，然後要嘛把它界住、要嘛承認你做不到。

兩道誠實檢查，避免近似比被過度推銷。第一，c-近似是最壞情況的天花板，不是預測——界值 2 說的是「絕不超過兩倍」，而非「大約兩倍」。許多 2-近似在多數自然輸入上傳回的就是精確最佳解。第二，近似比可以是緊的（tight）：常常存在一族明確的實例，把 ALG/OPT 一路逼到 c，證明對該演算法而言這份分析無法再改進。一個緊的 2 表示真有某個輸入恰好花了最佳解的兩倍；而一個僅僅被證明出來的 2，私底下也許更好、只是還沒被分析到。當你在彼此競爭的方法間取捨時，知道自己手上是哪一種，至關重要。

一整片保證的疆域，以及穿越這一階的路線

並非每個問題都產出一個常數比值，而這份多樣性正是這個領域之所以豐富的一部分。有些問題容許固定常數：頂點覆蓋拿到 2，而 度量 TSP靠生成樹論證拿到 2、再靠克里斯托菲德斯拿到 1.5（後續有專篇）。有些只容許一個隨規模增長的比值：貪婪集合覆蓋達到約 ln n 的比值，而——令人震撼地——除非 P = NP，這本質上已是任何多項式演算法所能做到的最好。還有些問題是不可近似的：對一般（非度量）TSP，連一個常數倍的近似都會讓你解出一個 NP 完全問題，所以除非 P = NP，否則它不存在。近似比不是一個可以隨意旋轉的旋鈕；它能小到什麼程度，本身就是一個深刻而因問題而異的定理。

第 2 篇從零建起貪婪與組合式近似——把頂點覆蓋的匹配論證完整講透，以及貪婪集合覆蓋的 ln n 比值連同其緊例。
第 3 篇處理度量 TSP：為何三角不等式正是讓它可近似的關鍵、生成樹的 2-近似，以及克里斯托菲德斯那聰明的 1.5。
第 4 篇引入線性規劃鬆弛與捨入——在多項式時間內解一個分數鬆弛，再把它捨入回整數解，同時把損失界住。
第 5 篇抵達最強的保證 PTAS 與 FPTAS：一族能對你選定的任意 epsilon 達成 1 + epsilon 比值的演算法，以更多時間換取更高精度。

自始至終，請握住這篇所安裝的那一個觀念：近似演算法是一個附帶最壞情況證明的多項式時間程序，而那個證明幾乎總是靠「發明一個可計算的替身、從一側困住 OPT」來運作。接下來的每一種技巧——組合式、基於 LP、或基於近似方案——都是建造那個替身、把夾擊收得更緊的、不同且更強大的方式。盯緊每個證明在哪裡找到它對 OPT 的界，整一階讀起來就會像是同一個誠實主題的諸多變奏。