兩個覆蓋問題，都很難
從上一篇起，有一個定義你現在隨身帶著：一個演算法是 alpha 近似的，意思是在每個輸入上，它都回傳一個可行解，其成本在最佳值的 alpha 倍以內——這是一個最壞情況的近似比，而非典型情況的承諾。本篇就把這個想法花在兩個最著名的覆蓋問題、以及馴服它們的兩個貪婪演算法上。兩個問題都是 NP 困難的，所以我們並不奢望拿到確切的最佳解；我們追求的是一個快速、又帶著「我們能證明的保證」的演算法。
首先是頂點覆蓋。給定一張無向圖，一個頂點覆蓋是一組頂點，它碰到每一條邊——對每條邊而言，它的兩個端點至少有一個落在這組頂點裡。我們要的是最小的這樣一組。當複雜度理論在搭建時你就見過它的決定性版本，而那條歸約到頂點覆蓋的論證，正是把它蓋上「NP 困難」這枚章的東西。想像一張博物館平面圖，走廊是邊，你得在某些房間（頂點）派駐警衛，使每條走廊都被它的某一端看著：頂點覆蓋就是「最少的警衛數」。
其次是集合覆蓋，更一般化的猛獸。給你一個有 n 個元素的全集，以及一族子集合，它們合起來能覆蓋一切；你要挑出最少數目的子集合，使它們的聯集仍是整個全集。頂點覆蓋其實是它的一個特例——讓每個頂點對應一個集合（內含它所碰到的那些邊），於是「覆蓋所有邊」就變成「覆蓋這個由邊構成的全集」。所以集合覆蓋至少和頂點覆蓋一樣難，而且我們將看到，它最好的貪婪保證確實更弱。兩個問題、兩個貪婪想法；要學的重點是你挑了哪一種貪婪、以及它的證明為何能收得攏。
頂點覆蓋：失敗的那種貪婪，與管用的那種
直覺的貪婪是反覆抓度數最高的頂點——也就是覆蓋最多「尚未被覆蓋的邊」的那一個——刪掉它的邊，再重複。這感覺天下無敵，但「看起來局部最好」從來都不是證明，而且在這裡它甚至連常數倍都做不到：存在一些圖，這種「最大度數貪婪」會回傳大約最佳值的 (log n) 倍。這正是和 0/1 背包問題一樣的陷阱——一條貌似合理、卻沒有保證的局部規則。所以我們捨棄它，不是因為它從不管用，而是因為它沒有一個可證明的倍率。
底下是那個真正管用的演算法，它的想法妙在「側著走」。不要去選頂點，改去選一條邊。隨便挑一條尚未被覆蓋的邊 (u, v)，把它的兩個端點 u 和 v 都加進你的覆蓋裡，刪掉所有如今被 u 或 v 覆蓋的邊，然後重複，直到沒有邊剩下為止。把兩個端點都加進去看起來很浪費——一個不就夠了嗎？——但這份表面的浪費，恰恰是讓證明能走通的關鍵。你挑的那些邊（每回合一條）構成一個匹配：它們兩兩不共享端點，因為一旦某條邊被選中，它的兩個端點連同它們所有的邊都被移走了。
VertexCoverApprox(G):
C = {} # the cover we build
M = {} # the matching we pick, one edge per round
while G still has an edge:
pick any edge (u, v)
C = C union {u, v} # add BOTH endpoints
M = M union {(u, v)}
delete u, v and all their incident edges from G
return C # |C| = 2 * |M|首先，輸出究竟算不算一個合法的覆蓋？算：迴圈只在沒有邊剩下時才停，而一條邊要消失，只可能是因為它的某個端點被加進了 C，所以每一條原本的邊最終都被碰到了。這個演算法也很快——對邊掃一遍，O(n + m) 的時間，就是你從打基礎時就一直在寫的那種廉價迴圈。可行性與速度是容易的那一半；保證，才是聰明之處藏身的地方。
為什麼它是 2 近似
整個證明都倚靠著一個對最佳值的下界，而這正是這一整階反覆出現的招式：要框出「你比 OPT 高出多少」，你得先有一個你確知不超過 OPT 的東西。在這裡，那個東西就是匹配 M。看看它的那些邊；它們不共享端點。任何頂點覆蓋——包括最佳的那個——都必須包含每條邊的至少一個端點，所以它必須為 M 的每一條邊各花掉至少一個相異的頂點。沒有任何單一頂點能覆蓋兩條匹配邊，因為它們不相交。因此 OPT（最小覆蓋的大小）至少是 |M|。
- 我們回傳的覆蓋是 C，恰有 |C| = 2*|M| 個頂點——每條匹配邊貢獻兩個端點，而匹配邊彼此不相交，所以沒有頂點被重複計算。
- 任何頂點覆蓋對每條匹配邊都得用上至少一個頂點，而這些頂點彼此相異，所以 OPT 至少是 |M|。這就是那個承重的下界。
- 把它們串起來：|C| = 2*|M| <= 2*OPT。所以 C 永遠不超過最佳值的兩倍——在每一個輸入上都成立的二倍保證。
請讀懂剛才發生了什麼，因為這個形狀會在近似法裡反覆出現。我們從未計算 OPT——它是 NP 困難的，我們算不出來。我們把答案拿去和一個夾在「我們」與「OPT」之間的量（|M|）比較：|M| <= OPT <= |C| = 2*|M|。這個匹配，是我們在跑演算法時順手免費搭出來的一張近最佳性憑證。這就是這類證明的藝術：找一個「演算法本身就會遞給你」的 OPT 下界，再證明你的輸出停在它的 alpha 倍以內。
集合覆蓋：以覆蓋量為準的貪婪
對集合覆蓋而言，那個匹配把戲沒有東西可咬，所以我們回到一個誠實的貪婪——而這一次它對得起自己的飯碗。貪婪集合覆蓋的規則是：每一步挑出覆蓋了最多尚未被覆蓋元素的那個集合，把它加進解裡，把那些元素標記為已覆蓋，然後重複，直到一切都被覆蓋為止。這是再自然不過的「每挑一次、撈最多」的啟發式，是貪婪選擇在運作的一個實例。和頂點覆蓋的「最大度數規則」不同，這裡的貪婪選擇確實附帶一個可證明的界限——但比較弱，是個對數倍的界，而看著這道落差浮現，正是本節的重點。
這個分析用到一個乾淨到值得隨身攜帶的「攤付論證」。當貪婪挑了一個覆蓋了 k 個全新元素的集合時，我們把這一個被選中的集合攤到那 k 個元素上，給每個剛被覆蓋的元素一份 1/k 的成本。這樣分攤出去的總成本，正好等於貪婪所挑集合的數目——每個被選中的集合恰好發出 1 單位的成本——所以把所有「每個元素分到的攤付」加總起來，得到的正是貪婪解的大小。接著的把戲，是去框出單一一個元素所收到的攤付。
固定那個隱藏最佳解裡的任一個集合 S，並依貪婪覆蓋它的元素的順序給它們編號——最後被覆蓋的排最前：e_1, e_2, ..., 一路到最後一個。當貪婪正要覆蓋 e_i 時，S 裡的 e_1..e_i 這 i 個元素全都還沒被覆蓋，所以 S 本身就是一個「至少能覆蓋它們 i 個」的可選方案。貪婪總是抓「覆蓋最多」的集合，因此它那一回合至少覆蓋了 i 個新元素，意思是 e_i 被攤到的成本至多 1/i。對 S 的所有元素求和：它的總攤付至多是 1/1 + 1/2 + ... 一路加到它的大小為止，也就是調和數 H_|S|，至多是 H_n（n 是全集大小），而 H_n 大約是 (ln n)。
現在收尾。最佳解用了 OPT 個集合，而全集的每個元素都至少住在其中之一裡面。貪婪付出的整份攤付，至多是「對那 OPT 個最佳集合求和」的攤付總和，每個至多 H_n，所以貪婪解的大小至多是 H_n * OPT——大約 (ln n)*OPT。這就是頭條：貪婪集合覆蓋是一個 H_n 近似，一個大約 (ln n) 倍的保證。它比任何常數成長得慢，但仍然在多項式倍的範圍內接近，而且全出自一條漂亮又簡單的規則。
為什麼一個是常數、另一個是對數
覺得不太對勁是合理的：頂點覆蓋是集合覆蓋的一個特例，可是頂點覆蓋拿到了俐落的 2 倍，一般的集合覆蓋卻只拿到 (ln n)。這沒有矛盾——一個特例本來就可能擁有更多可以利用的結構。頂點覆蓋的恩賜在於，每個「集合」（一個頂點的那些邊）都對著一個大小為二的夥伴：每條邊恰好有兩個端點，所以那個「不相交匹配」的下界才存在。一般的集合覆蓋對於它的集合彼此如何重疊並沒有這種界限，所以那個較弱的調和論證，就是這個貪婪所能承諾的極限了。
退一步，把工具箱收齊。一個貪婪近似需要依序檢查三件事：可行性（輸出是合法解）、執行時間（是多項式）、以及倍率（一個「跑這趟本身就提供出來」的 OPT 下界，拿來框住你的輸出）。頂點覆蓋的證明把那個下界以匹配的形式遞給我們；集合覆蓋的證明則藉由把成本攤到元素上、把它製造出來。接下來幾篇沿用這套食譜、只更換下界：度量型 TSP 倚靠最小生成樹與一條走捷徑的旅程，而再之後，我們會讓一個線性規劃來提供下界，再把它的分數答案捨入回一個整數答案。