貪心算法逐步作出局部最優的選擇,並且從不修改已作的選擇。許多看似合理的貪心規則其實是錯的,所以真正有用的能力不是設計規則,而是證明規則。標準的證明技巧是交換論證:取任意一個最優解,說明它可以一步步改造成與貪心選擇一致的解,而且不會變差。最小生成樹一節中的割性質就是一個例子;本節把這個方法單獨抽出來,應用於另外兩個問題。貪心算法與動態規劃都依賴最優子結構,但貪心算法只承諾於單一個子問題,而不是比較多個子問題,交換論證正是用來證明這個承諾是合理的。
1. 證明模式
定義 19.1.1
(貪心選擇性質與最優子結構)
設問題要求在可行解中使目標函數最小或最大。貪心算法依固定規則挑選元素。要證明它正確,需證明兩個性質。
- 貪心選擇性質。 對每個實例,都存在一個包含貪心選擇的最優解。
- 最優子結構。 固定貪心選擇之後,包含它的最優解的其餘部分,是同類型的較小實例的最優解。
然後對實例大小作歸納,即可證明貪心算法最優:它作出與某個最優解一致的選擇,由歸納假設最優地解決較小的實例,兩部分合起來是最優的。工作的核心是性質 1,並以交換來證明:設 是不含貪心選擇 的最優解,構造包含 且不比 差的 。只證明算法的輸出可行,或在若干例子上最優,都不算證明。
第二種形式是針對排序問題的相鄰交換論證:說明在任何次序中,交換違反貪心規則的兩個相鄰項目不會令目標變差,而當違反是嚴格的時,目標嚴格改善。
2. 區間調度
定義 19.1.2
(相容請求與區間調度)
問題。 給定 個請求,請求 佔用半開區間 ,。選出最大的兩兩相容的請求集合,相容指區間互不相交。使用半開區間意味著 與 相容。
貪心規則(最早結束時間)。 在與已選請求相容的請求中,反覆選取結束時間最小的一個。
sort requests by f (ties broken arbitrarily)
last = -infinity; chosen = []
for each request i in this order:
if s_i >= last:
append i to chosen
last = f_i
return chosen
由於請求按結束時間遞增處理,當前請求 與所有已選請求相容,當且僅當 最近選取的請求的結束時間(它也是迄今最大的結束時間)。
定理 19.1.3
(最早結束時間的最優性)
該算法返回一個大小最大的相容請求集合。
證明
(交換第一個請求)
對請求數作歸納。沒有請求時顯然成立。令 為第一個被選取的請求,它的結束時間在所有請求中最小(若有並列,任取一個)。
貪心選擇性質。 設 為最優集合,其區間按開始時間(由於互不相交,等同於按結束時間)排序為 。因為 的結束時間全局最小,。若 無需改動。否則令 。 的結束不遲於 ,而 的結束不遲於 的開始,所以 與 相容。因此 相容且 ,故它也是最優的,並包含 。
子結構。 令 為滿足 的請求集合,即恰好與 相容的請求。任何包含 的相容集合,都是 加上 的一個相容子集。若 不是 的最大相容子集,把它換成更大的,就得到包含 的更大相容集合,與 的最優性矛盾。所以 是 的最優解。
選取 之後,算法恰好等於在 上執行同一算法,因為它會跳過開始於 之前的請求,而其餘請求仍按結束時間排列。由歸納假設,它返回 的最優集合,加上 即得 ,也就是最優值。
證明透視
結束時間規則在交換中的位置
這個證明只有一步不是例行的:把 換成 。這一步所需的每個事實都在確定的位置使用。第一, 成立,僅僅因為 的結束時間在所有請求中最小;貪心規則只在這裏用到。第二,最優解的區間兩兩不相交,所以 ;把兩個不等式連起來得 ,而 的開始時間都不早於 ,所以同一個界對它們也成立。第三,子結構一步把交換後的最優解 變成較小實例 的最優解。
去掉第一個事實,交換就失敗。對「最早開始」的選擇 與 ,,所以 與 相撞。論證之所以能收尾,是因為 不含 (),所以 的請求比原實例少,歸納假設可以使用。
複雜度。 排序主導:,掃描為 。
反例模式
最早開始與最短請求都不是最優
聲稱:每次選開始最早的請求,或選最短的請求,總能得出最大的相容集合。兩個說法都是錯的。對 、、,「最早開始」規則選 ,它與其餘兩個都重疊,所以只得 1 個請求,而 相容,有 2 個。對 、、,長度為 ,「最短請求」規則選 ;它與 在 重疊,與 在 重疊,結果只有 1 個請求,而 與 相容,因為 與 不相交。修正方法是結束時間規則:在第一個實例中,它選 再選 ;在第二個實例中,它選 (結束於 5),跳過 (開始 ),再選 (開始 )。
3. 例題:區間調度
例題 19.1.4
(八個請求的最早結束時間調度)
請求(半開區間):A 、B 、C 、D 、E 、F 、G 、H 。按結束時間排序:A(4)、B(5)、C(6)、D(7)、E(9)、F(9)、G(10)、H(11)。
- A:,選取;last 。
- B:開始 ,跳過。C:開始 ,跳過。
- D:開始 ,選取;last 。
- E:開始 ,跳過。F:開始 ,跳過。G:開始 ,跳過。
- H:開始 ,選取;last 。
結果為 ,大小為 3。由定理,不存在含四個請求的相容集合。作為對比,「最早開始」規則先選 C(開始於 0),然後選第一個開始於 6 或之後的請求,即 G,其後沒有開始於 10 或之後的請求(H 開始於 8):只得兩個請求,嚴格較差。
例題 19.1.5
(首尾相接的區間與並列的結束時間)
取 、、、。結束時間為 ,所以 與 並列。按次序 :選 (last );跳過 (開始 );選 (開始 ,因為 與 不相交);跳過 (開始 )。結果為 。按次序 ,同樣的步驟得 。兩個輸出是大小同為 的不同集合,這與定理並不矛盾:定理確定的是答案的大小,而不是集合本身。並列時的選擇不影響後續步驟,因為 與 的結束時間同為 。
4. 最小化加權完成時間
定義 19.1.6
(完成時間與加權完成時間)
問題。 項工作在單一機器上逐項執行,無空隙,從時間 0 開始。工作 的處理時間為 ,權重為 。在某個次序中,工作 的完成時間 是直至並包括它在內的所有工作的處理時間之和。要最小化 。
貪心規則(Smith 規則)。 按比值 不遞減的次序處理工作。
引理 19.1.7
(相鄰交換)
設工作 與 在某個排程中相鄰, 緊接在 之前,這一對從時間 開始。交換兩者使目標函數(交換前減交換後)恰好改變 ,其他工作的完成時間不變。
證明
(只有被交換的一對改變)
兩項工作無論次序如何,都佔用同一個區間 ,所以其他工作的完成時間不變。交換前,這一對的貢獻為 ;交換後為 。相減時,、 與 互相抵消,剩下 。
由於 , 當且僅當 。
定理 19.1.8
(Smith 規則最優)
任何按 不遞減排列的次序都使 最小,而且所有這類次序的成本相同。
證明
(消除相鄰逆序)
令 為最優次序(排列只有有限個,最優次序必存在)。若它含有相鄰一對 滿足 (嚴格逆序),交換它們由引理使成本嚴格下降,與最優性矛盾。所以 沒有相鄰的嚴格逆序,即相鄰比值不遞減,由傳遞性整個次序按比值不遞減。任何兩個按比值不遞減的次序,只相差於比值相等的工作之間的排列;交換比值相等的相鄰工作,由引理使成本改變 ,而比值相等的各塊的任何排列都是一連串這樣的交換。所以所有不遞減次序的成本都等於 的成本,即最優值。
證明透視
為甚麼局部交換能得出整體最優
引理純屬局部:它只計算一次相鄰交換的得失。使它變成整體結論的一步,是把 取為最優次序;由於排列只有有限個,最優次序必存在。矛盾出現在「嚴格」二字:嚴格逆序 給出嚴格為正的節省量 ,所以 還能改進。 用來把 的正負化為比值的比較;若有權重為零,比值就不能反映正負。沒有相鄰的嚴格逆序,就表示比值數列不遞減;此時只有比值相等的各塊可以自由排列,而每次交換的節省量恰為 ,所以所有這類次序的成本相同。
5. 例題:Smith 規則
例題 19.1.9
(三項工作的 Smith 規則)
工作: 的 ,比值 ; 為 ,比值 ; 為 ,比值 。Smith 次序為 ,完成時間為 ,成本 。
逐一檢查全部六個次序可確認它最優。:完成時間 ,成本 。:,成本 。: 於 1, 於 4, 於 6:。:14。: 於 2, 於 5, 於 6:。: 於 2, 於 3, 於 6:。最小值為 14。
6. 常見錯誤
反例模式
權重最大優先並不最優
聲稱:按權重不遞增處理工作,可使 最小。取工作 與 。先做 :、,成本 。先做 :、,成本 。所以按權重優先的次序並不最優。兩者的比值為 與 ,Smith 規則先做 ,與成本比較的結果一致。修正方法是使用比值 ,而不是只看權重。
常見錯誤
(可行或在例子上最優都不是證明)
貪心規則必須對每個實例證明最優。只證明輸出可行,或只在少數實例上最優,既不能確立貪心選擇性質,也不能確立最優子結構。上面的「最早開始」與「最短優先」規則的輸出必然可行,也看似自然,卻都會失敗。
常見錯誤
(交換後離開了可行解的範圍)
交換必須從任意一個最優解 出發,而不是從貪心解出發,並且必須驗證改造後的解可行。在區間調度中,把 換成 之所以可行,是因為 ,而其餘區間都開始於 之後。結果不可行的交換甚麼也證明不了。
常見錯誤
(Smith 規則的比值方向與並列情況)
Smith 規則按 不遞減排序,等價於按 不遞增;方向相反會把又長又輕的工作排在前面。比值相等的工作在這裏可以任意排列,因為交換它們使成本改變 。在其他貪心問題中,並列可能有影響,所以要說明對並列情況聲稱了甚麼。
練習
快速檢查
(對 、、、、、 應用最早結束時間調度。)
先按結束時間排序。
解答 · 答案
按結束時間排序:(2)、(3)、(5)、(7)、(9)、(10)。選 ;last 。 開始於 ,跳過。 開始於 ,選取;last 。 開始於 ,跳過。 開始於 ,選取;last 。 開始於 ,跳過。所選集合為 ,共 3 個請求。
快速檢查
(給出一個三請求的實例,使「最早開始優先」不是最優。)
讓其中一個請求很長。
解答 · 答案
取 、、。最早開始選 ,它與另外兩個都重疊,得 1 個請求。集合 相容,有 2 個請求。
練習 19.1.10
(按 Smith 規則排列工作 :、、、,並計算成本。說明兩種合法的並列次序成本相同。)
核心
解答(3)
- 1
計算比值並排序
比值 為 、、、。不遞減次序為:先是比值 1 的 ,然後是比值 2 的 與 (任一次序),最後是 。
- 2
第一種並列次序的成本
次序 的完成時間為 ,所以
依據: 完成時間是處理時間的累計和。
- 3
另一種並列次序的成本與比較
次序 的完成時間為 ,成本為 。兩種並列次序的成本都是 46。
快速檢查
(利用 Smith 規則說明:要使處理時間為 的工作的完成時間總和最小,應先做最短的工作,並計算最小值。)
所有權重均為 1。
解答 · 答案
所有權重為 1 時,比值 ,所以 Smith 規則按處理時間不遞減排序:。完成時間為 ,總和為 。作為對比,次序 的完成時間為 ,總和 。