動機
多個請求希望獨佔同一間房,我們希望接受盡可能多的請求。先接受輸入中的第一個請求沒有依據;先接受最短的請求似乎節省時間;先接受最早結束的請求則似乎為後續留下空間。本節證明的是最後一種規則。
貪心算法作出選擇後不再反悔。因此必須說明某個最優解可以保留這個選擇。交換證明透過修改一個最優答案、又不使它變差,提供這樣的依據。隨後還必須準確描述剩餘問題,才能重複論證。
本例說明這兩項證明任務,並不聲稱每個優化問題都有貪心規則。我們會區分「接受數量最多」與「已經無法再加入請求」,也區分請求數量與請求總價值。
定義
定義 8.1.1
(正長度半開區間請求)
輸入是 個請求組成的有限列表,各有不同身份。請求 佔用 ,端點為有限實數,且 ;端點可以為負。兩個請求兼容,是指佔用集合不相交,等價於 或 。因此一個請求可以恰在另一個結束時開始。
可行調度是兩兩兼容的請求子集,按時間先後排列;相鄰請求滿足前者結束不晚於後者開始。其大小是接受的請求身份數量。區間完全相同而身份不同的兩個正長度請求仍衝突。
最大調度的數量最多;極大調度則只是無法在保持可行的前提下再插入一個請求。若剩餘問題至少有一個最大調度可以從某個選擇開始,就稱這個貪心選擇安全。不要求每個最優解都包含它。
已有結束閾值 時,剩餘列表由開始時間至少為 的請求組成。最初尚未選擇請求,沒有閾值;實現時以獨立標誌記錄。把閾值初始化為零,會錯誤排除在零以前結束的請求。
定理/命題
引理 8.1.2
(最早結束可以交換為第一個選擇)
對任意非空剩餘列表,取結束時間最小的請求 ,平局任意處理。該列表存在一個最大調度,以 為第一項。若此前已有固定可行前綴,只要所有剩餘請求都不早於前綴末尾結束時間開始,這個結論仍成立。
定理 8.1.3
(按結束時間掃描使接受數量最大)
按結束時間非遞減排序,任意處理平局,然後掃描一次。接受首項;此後恰在請求開始不早於上一已接受請求的結束時間時接受它。空輸入返回空調度。
所得調度數量最大。比較排序加掃描需要 次精確比較及索引操作;歸併排序實現連同工作空間和輸出需要 個儲存字。
定理 8.1.4
(貪心調度始終不落後)
設貪心調度為 ,任意按時間排列的可行調度為 。對每個 ,貪心調度都存在第 項 ,且 。因此 。比較的是結束時間,不是請求身份或佔用時間總長。
證明思路或證明
交換第一項,同時避免重複身份
證明
(替換最優解的第一項)
從非空剩餘列表中取任意最大調度 。單個請求總可行,所以 至少為一。按 的定義,
若 已在該調度中,它只能位於第一項;否則位於它前面的首項會滿足
矛盾。若 不在其中,把 替換為 。 時,下一請求的開始不早於舊首項結束,因而也不早於 。其餘兼容關係不變; 時沒有後綴需要檢查。新調度的身份仍互異,數量仍為最大值。
若此前有固定前綴, 屬於剩餘列表,故它也不早於前綴最後結束時間開始。交換因此保留整個前綴。結論是存在一個遵從下一選擇的最優解,而不是原最優解唯一。
證明透視
交換究竟保留了哪些條件?
證明完成三項獨立任務,各自依賴不同假設。最早結束給出的不等式保留被替換首項之後的全部請求;與固定前綴的兼容性來自剩餘列表的成員資格,而非最小性;排除 在後面出現的不等式鏈,其嚴格一步用到正長度。沒有正長度, 可能位於最優解較後位置,替換後同一身份會被計算兩次。只說 留下更多時間,只檢查了三項中的第一項。
選定之後,準確識別更小的問題
證明
(剩餘問題的對應與歸納)
接受 後,剩餘問題恰由開始時間至少為 的請求組成。 後的每個可行後綴都在這個列表中;反過來,該列表的每個可行調度都可以接在 後。以 表示最大數量, 表示當前剩餘列表,交換引理及這個對應給出
正長度保證更小的列表不含 自己,請求數量嚴格減少。對剩餘請求數歸納,便證明反覆選擇最早結束者最優。空列表的最優值為零,提供基礎情形。
這說明證明的結構:先證安全選擇,再證精確的剩餘問題對應。只知道最優解具有最優後綴並不夠;很多問題有這個性質,某個貪心首步卻仍然錯誤。後面的最短時長反例正是首步失敗的情形。
旁註
先嘗試推翻貪心規則
證明貪心規則之前,先用兩三個區間嘗試推翻它;下面每個反例最多只需五個區間。能通過小例子的規則,只是交換證明的候選,還不是定理。
為甚麼排序後一次掃描就執行了這個遞歸
證明
(掃描恰好作出剩餘選擇)
被接受請求的結束時間嚴格增加:下一項開始至少等於當前結束,而它自己的結束又嚴格晚於開始。因此,因開始過早而被拒的請求,以後也不會重新符合條件,可以永久丟棄。
任何能接在上一已選請求後的候選,其結束都嚴格晚於當前閾值,也不可能已經被選。掃描排序後的餘項時,遇到的第一個合資格請求,就是所有合資格者中結束最早的;此前被拒者不會重新合資格。因此掃描準確執行已分析的剩餘選擇。同結束時間的任意順序由交換引理保證安全。
另一種證明:與每個可行調度逐項比較
證明
(對競爭調度歸納證明始終不落後)
若比較調度非空, 存在且 ,因為 在整個輸入中最早結束。假設 存在且 ;如果 存在,可行性給出
故 能接在 後。正長度使其結束嚴格晚於 ,因此它不可能是此前已選的貪心請求。仍有合資格且未選的請求,算法不能停止;下一個最早結束選擇 的結束不晚於 。每一步既證明下一項存在,也證明所需不等式。
歸納遍歷比較調度的 項,得 。空比較調度無須歸納,數量界自動成立。
始終不落後的結論給出另一種有用不變量。它避免了一個不完整證明:只在兩邊都有項時比較結束時間,隨後未經證明便假設貪心不會先結束。
概念視角算法
安全選擇比看似合理的局部評分更強
最早結束有用,是因為交換後保留了整個最優後綴。最短時長或最早開始本身沒有這樣的保證。貪心正確性取決於目標、兼容規則與交換性質的結合;直覺上有吸引力的評分不能代替它們。
在明確輸入約定下計算工作量
證明
(排序與掃描的成本)
比較歸併排序反覆拆分列表,再在線性工作量內歸併兩段有序列表;層數為對數量級。掃描時每個請求做一次兼容測試,輸出至多 個身份。因此得到上述時間和儲存界,也包含空輸入的常數工作。若輸入已按結束時間排序,只需線性掃描。
有限實端點採用精確比較。若端點為絕對值至多 的整數,在將尋址作為基本操作的索引陣列模型中,每次端點比較及身份、索引算術可按 位計費。操作次數乘此位長給出算術及索引位成本。這裏沒有引入容差:把準確端點比較換成近似測試,會改變兼容性問題。
例題詳解
例題 8.1.5
(端點相接、負時間與結束平局)
取 、、、、、、、。結束順序為 ,其中 平局可倒轉。
依次接受 、拒絕 、接受 、拒絕 、接受 、拒絕 、接受 、接受 ,得到五項 。若平局中 在 前,則得到同樣五項的 。相鄰結束和開始時間相等可以兼容。定理保證兩者都最大;錯誤地從閾值零開始,就已經會漏掉 。
例題 8.1.6
(最早開始與最短時長都會失敗)
對最早開始規則,取 ,另有四項 、、、。 嚴格最早開始,卻擋住另外四項。只含 的單項調度是極大的,因為無法再加入任何請求,但數量一小於最大值四。
對最短時長規則,取 、、。 時長二,嚴格最短,卻與另外兩項都衝突。先選它再刪除衝突者,只得一項;先 後 可得兩項。局部節省最多時長,並不能保留最優後綴。
例題 8.1.7
(計請求數與最大總價值不同)
、 的價值各為一, 價值十。最早結束規則接受 ,數量二最大,卻只獲價值二;單項 價值十。把 換成 的交換在該步保留數量一,卻降低價值,所以不是保值證明。
這也不意味著應始終選擇價值最高者:令長區間 價值十,三個連續的長度二區間各值四。先選最重者只有十,三項短請求則共十二。本節證明的是單位計數目標;加權優化需要自己的論證。
常見錯誤
反例模式
去掉正長度會改變模型
若允許零長半開區間作為空佔用集合, 與 不相交,兩者在集合不相交的規則下可以同時接受。最早結束先選 ,閾值變為 1,而 的開始 0 較小,於是被拒,只得一項而非兩項。正長度用於給不相交請求排序,也用於從剩餘列表中排除已選請求;本定理明確要求它。
以下錯誤保留模型不變,卻誤讀了定理的內容。
常見錯誤
(閉區間沿用半開區間的比較)
閉區間的端點規則不同: 與 相交。在該模型中,兼容測試必須是嚴格的 或 。換成閉區間卻仍用非嚴格比較 ,會接受互相衝突的請求。
常見錯誤
(極大不是最大,最大也不唯一)
無法再加入請求的調度仍可能遠非最優:第二個例題中的單項調度 是極大的,大小為一,而最大值為四。反過來,最優數量也不決定輸出;第一個例題的結束平局已經給出兩個不同的最優調度。
總結
最早結束選擇安全,因為用它替換最優首項仍保留整個後綴及固定前綴。準確的剩餘對應使歸納成立,排序掃描高效執行這些選擇。始終不落後的另一證明同時保證貪心不會早於任意競爭調度耗盡候選。目標和端點假設都是關鍵。
練習
快速檢查
(給 、、、,分別列出 兩種結束平局順序的貪心輸出。解釋數量為何相同,以及任一輸出是否為唯一最優解。)
利用 與 重疊,為所有可行調度給出上界。
解答 · 答案
先選 ,即使它的時間為負。若 在 前,選 、拒絕 、選 ,得到 ;反之得到 。 在 上重疊,任意可行調度至多取其中一項,再加 ,數量至多三。兩種輸出都達界且不同,因此不唯一。半開約定下,端點相接不衝突。
快速檢查
(有人說:任取請求、刪除所有衝突者,再重複,最後得到極大調度,因此必最優。用例題給出反例,並說明需要證明怎樣的交換結論才能修補這種推理。)
比較極大調度的大小與最大值。
解答 · 答案
先選 ,會刪除其中四項相互兼容的短請求,返回極大單項調度;最優調度卻包含全部四項。要證明貪心選擇正確,必須說明某個最大剩餘調度能在所需的首位包含該選擇,同時保持此前前綴可行。本例中不存在這樣的交換,因為每個含 的調度只有一項。最終無法再添加,不代表比替換選擇後得到的答案更好。
快速檢查
(某個可行競爭調度有七項,貪心已選四項,且 。證明 存在且 ,並解釋正長度的作用。)
先證明 能接在 後。
解答 · 答案
競爭者第五項滿足 ,所以 仍符合條件。正長度給出 ,而此前各貪心項的結束至多為 ,因此 尚未被選。剩餘列表非空,第五個貪心請求存在;最早結束規則給出 。反覆使用此論證,而不是預設兩邊項數相同,才證明一般的始終不落後結論。