為甚麼要近似
前面幾節說明,許多優化問題是 NP 困難的,目前沒有已知的多項式時間算法能對所有輸入求出最優解。除非這些問題都能在多項式時間內精確求解,否則必須有所取捨。近似算法放棄的是最優性,而不是可證明性:它在每個輸入上都以多項式時間運行,並附帶一個已證明的界,說明答案與最優值最多相差多少。本節介紹兩種基本的證明技巧。第一種把算法的輸出與一個容易計算的最優值下界(極大匹配)作比較;第二種把總成本分攤到被覆蓋的元素上,再與最優值比較(貪心集合覆蓋)。本節假定讀者已掌握本章前幾節關於圖和 NP 困難的定義。
定義
定義 4.6.1
(近似比)
極小化型的優化問題為每個輸入 指定一族可行解,每個可行解有非負成本; 表示可行解的最小成本。算法 稱為 -近似算法( 為常數),是指在每個輸入 上,它以輸入大小的多項式時間運行,輸出一個可行解,並且輸出的成本 滿足
比值 也可以依賴輸入規模,本節後半部分便是如此。近似比是對所有輸入成立的陳述,所以算法在某些輸入上碰巧得到最優解並不能證明甚麼;而它在某個輸入上表現欠佳,只能給出其真實近似比的下界。
定義 4.6.2
(頂點覆蓋、匹配與極大匹配)
設 為有限無向圖。頂點覆蓋是集合 ,使每條邊至少有一個端點在 中。最小頂點覆蓋問題要求大小最小的頂點覆蓋。匹配是邊集 ,其中任意兩條邊沒有公共端點;若無法從 中再加入任何一條邊而保持匹配性質,則稱 極大。極大比最大要弱:極大匹配不能再擴充,但別處仍可能存在更大的匹配。
定義 4.6.3
(集合覆蓋與調和數)
在最小集合覆蓋問題中,給定有限全集 ()及集合 ,它們的並集為 。覆蓋是一組指標 使 ,其成本為 。第 個調和數為 ;因為對 有 ,所以 。
以極大匹配求頂點覆蓋
算法反覆取一條未被覆蓋的邊,把它的兩個端點都放入覆蓋。
APPROX-VERTEX-COVER(G):
C = empty set; M = empty set
while G still has an edge uv:
add u and v to C; add uv to M
delete u, v and every edge incident to u or v from G
return C
定理 4.6.4
(頂點覆蓋的二近似)
對任意圖 ,算法在 時間內終止,集合 是極大匹配,輸出 是頂點覆蓋且 ,並且
證明
(以極大匹配得到二近似)
每次迭代至少刪去邊 ,所以迴圈至多執行 次。使用鄰接表並為每個頂點設一個標記,每次迭代的時間與被刪去的邊數成正比再加一個常數,因此得到上述總時間。
當 加入 時,所有與 或 相連的邊都被刪去,所以之後加入 的邊不會再用到 或 。因此 中的邊兩兩不相交,。只有圖中不再有邊時迴圈才結束; 的每條邊要麼被加入 ,要麼因為含有已在 中的端點而被刪去。所以每條邊都有端點在 中, 是頂點覆蓋。若結束時還有邊可加入 ,這條邊的兩個端點都不在 中,與上面的結論矛盾;所以 是極大的。
關於最優性,設 為最小頂點覆蓋。 的每條邊都有端點在 中,而不同的邊有不同的端點,所以 至少含有 個不同的頂點:。因此 。
這個證明體現了一個一般模式:把一個可在多項式時間內算出的最優值下界()與輸出的成本作比較。算法本身無須知道 。
概念視角組合
頂點覆蓋是特殊的集合覆蓋
由 構造一個集合覆蓋輸入:全集為 ,每個頂點 對應集合 ,即與 相連的所有邊。集合 是頂點覆蓋,當且僅當 ,所以頂點覆蓋就是這個輸入的覆蓋,成本也相同。每個元素(邊)恰好屬於兩個集合。匹配是一族兩兩不屬於同一集合的元素,所以任何覆蓋都要為每個元素各用一個不同的集合;這正是 的另一種說法。取匹配邊的兩個端點,就是取所有含該元素的集合。
貪心集合覆蓋
貪心規則是反覆選取含有最多尚未覆蓋元素的集合。
GREEDY-SET-COVER(U, S_1..S_m):
R = U; J = empty list
while R is not empty:
choose j maximizing |S_j intersect R| (break ties by smallest index)
append j to J; R = R minus S_j
return J
定理 4.6.5
(貪心集合覆蓋的調和數保證)
設 為覆蓋的最小大小。貪心算法返回的覆蓋大小至多為 。
證明
(貪心集合覆蓋的調和數界)
終止性:由於所有集合的並集為 ,只要 ,就有某個集合與 相交,所以每次迭代至少移走一個元素,迴圈至多 次後以 結束;因此 是覆蓋。
關鍵引理。 若仍有 個元素未被覆蓋,則某個集合至少含其中 個。事實上,由 個集合組成的最優覆蓋覆蓋全部 個剩餘元素,所以這 個集合含有的剩餘元素(按重數計)至少有 個,由鴿籠原理,其中一個至少含 個。貪心所選集合的新元素數不少於該集合的。
分攤。 每當貪心選取一個覆蓋 個新元素的集合,就給這 個元素各標價格 。所有價格之和等於所選集合的個數。把元素按被覆蓋的次序排成 (同一次迭代覆蓋的元素任意排序)。在 被覆蓋的那次迭代開始時, 都尚未被覆蓋,所以 。由關鍵引理,貪心覆蓋了 個新元素,於是
對 求和,得 。
證明透視
為甚麼價格能把計數變成求和
證明把所選集合的個數轉成對元素求和:給每個新覆蓋的元素定價 ,總價格就等於 ,於是可以逐個元素證明上界。不顯而易見的一步是元素的排列次序。無論同一次迭代內怎樣排序, 仍有 ,因為這只用到「在該次迭代開始時 都尚未被覆蓋」。
最優值 只在一處出現,就是關鍵引理的鴿籠步驟,而且只作為「覆蓋剩餘元素的最優覆蓋最多需要幾個集合」的上界;這正是貪心已經移走一些元素之後論證仍然成立的原因。界 相加得 ,證明就此完結。沒有關鍵引理的話,每個元素的價格都可能高達 ,只能得到毫無用處的界 。
例題
例題 4.6.6
(六個頂點的路徑上的頂點覆蓋)
設 為路徑 ,邊為 。按所列次序取邊運行算法。取 :把 放入 ,刪去 。剩下的第一條邊是 :把 放入 ,刪去 。接著是 :把 放入 。此時 ,,故 。集合 覆蓋 (靠 )、(靠 )和 (靠 ),所以 ;又 ,故 ,這個次序下的比值恰為 。
結果取決於選邊次序。若第一條邊取 (刪去 ),再取 (刪去 ),則 ,,。兩種輸出都符合定理。
例題 4.6.7
(貪心集合覆蓋未必最優)
設 ,,,。貪心首先選 (四個新元素,其餘集合各三個)。此時 ; 覆蓋 , 覆蓋 ,各有一個新元素;平手時取 。然後 ,選 。貪心返回三個集合。而僅 已覆蓋 ,所以 ,輸出是最優值的 倍。定理只保證 ,即 ,與 一致。
例題 4.6.8
(此算法的因子 2 不能改進)
設 為完全二分圖,兩側 各有 個頂點。 的每個極大匹配都是完美匹配:若 和 中各有一個未匹配的頂點,它們之間的邊就可以加入。所以算法總是輸出全部 個頂點。單是 已是頂點覆蓋(每條邊都有端點在 中),所以 。由定理 ,故 ,輸出恰為最優值的兩倍,對每個 都如此。因此這個算法的分析是緊的。
常見錯誤與細節
常見錯誤
(把近似比當成結構上的相似)
-近似是對成本的最壞情況保證,並不保證輸出與最優解相似:六個頂點路徑的例題中,兩個輸出所用的頂點不同,兩者都不必與最優覆蓋相似。
反例模式
每條匹配邊只取一個端點
一個誘人的捷徑是每條匹配邊只取一個端點,這樣覆蓋的大小會減半。在路徑 上, 是極大匹配:唯一的另一條邊 與這兩條邊都有公共端點。若選 和 ,邊 就沒有被覆蓋,所以這個捷徑不成立。必須取兩個端點:極大性只說明 以外的每條邊都接觸某個已匹配的頂點,而要覆蓋那條邊,無論它接觸的是哪一個端點,這個已匹配的頂點都必須在 中。
常見錯誤
(極大匹配與最大匹配)
匹配必須是極大的,覆蓋才有效,但不必是最大的。不等式 對每個匹配 都成立,所以證明對算法碰巧構造出的極大匹配同樣適用。
常見錯誤
(剩餘元素的最優值)
在集合覆蓋的分析中, 是原輸入的最優值。選了一些集合之後,對尚未覆蓋的元素而言,剩餘的最優值至多為 ,但可能更小;關鍵引理只需要上界 ,而這個方向是成立的。
調和數的界依賴 ,所以不是常數因子保證;本節也沒有說明它是否是最好的可能值。
練習
快速檢查
(在頂點為 、邊為 的五邊形上,按此次序取邊運行頂點覆蓋算法。列出 和 ,並求 。)
圈上每個頂點至多覆蓋兩條邊。
解答 · 答案
取 :把 放入 ,刪去 。剩下 。取 :放入 ,刪去 。再沒有邊。所以 ,,大小為 。頂點覆蓋至少需要 個頂點,因為每個頂點至多覆蓋五條邊中的兩條;而 覆蓋 (靠 )、(靠 )和 (靠 )。所以 ,比值為 。
練習 4.6.9
(設 為圖 的任意匹配。證明 的每個頂點覆蓋至少有 個頂點,並說明為甚麼單靠這個不等式不能推出頂點覆蓋算法的輸出至多有 個頂點。)
核心
解答(3)
- 1
為每條匹配邊選出一個在覆蓋中的端點
設 為頂點覆蓋。對 的每條邊,選一個屬於 的端點。
依據: 頂點覆蓋在每條邊上都有端點,當然也在 的每條邊上有。
- 2
證明所選的端點互不相同
關鍵一步
中兩條不同的邊沒有公共端點,所以它們給出不同的頂點。因此 至少含有 個頂點。
依據: 匹配中的邊沒有公共端點。
- 3
與算法的輸出比較
這個不等式只給出 的下界 。算法的輸出有 個頂點,大於 ,並且可以大於 :在六個頂點的路徑例題中, 而 。
練習 4.6.10
(設 ,,,,,。運行貪心集合覆蓋(平手時取下標最小者),並證明其輸出是最優的。)
核心
解答(3)
- 1
運行貪心算法
是最大的集合,故取 ;此時 。新元素: 給出 (3 個), 給出 (2 個), 給出 (2 個), 給出 (2 個)。取 ;此時 ,第一個含 的集合是 。輸出為 ,共三個集合。
- 2
證明沒有兩個集合能覆蓋
關鍵一步
各集合的大小為 。兩個集合要覆蓋 ,大小之和至少為 。不含 時,最大的和是 。含 時,另一個集合的大小必須為 ,即 或 ;但 ,,所以這些配對至多覆蓋 個元素。
依據: 下界 與貪心的輸出相等。
- 3
得出最優性
因此 ,而貪心只用了 個集合,所以 ,貪心在這裏是最優的。
快速檢查
(在貪心集合覆蓋未必最優的例題中(,,,),按元素被覆蓋的次序寫出每個元素的價格,驗證價格之和等於所選集合的個數,並對每個 驗證 。)
貪心依次選 、、,而 。
解答 · 答案
貪心選 ,以價格 覆蓋 ;然後用 以價格 覆蓋 ,用 以價格 覆蓋 。總和為 ,等於所選集合的個數。當 , 時, 的界 依次為 。價格 分別不超過 ,所以六個不等式都成立;例如 時 , 時 。
快速檢查
(設一個有 個頂點的圖,其邊恰好構成 條邊的完美匹配(沒有其他邊)。證明頂點覆蓋算法輸出的覆蓋恰有 個頂點,並求 。)
利用下界 。
解答 · 答案
圖的每條邊都與其他邊不相交,所以取一條邊只刪去這一條邊,算法取遍全部 條邊:。每個頂點覆蓋都需要在這 條不相交的邊中各取一個頂點,所以 ;每條邊取一個端點即得大小為 的覆蓋。故 ,,達到定理所允許的最壞情況。