動機
貪心算法作出選擇後不再回頭;動態規劃保留可能有用的替代方案,求解一族相關子問題。兩者都可能有效,但不能靠口號證明。貪心法須證明指定選擇可以出現在某個最優解;動態規劃則須證明狀態記錄了足夠資訊,描述一切相關的後續選擇。
本篇把這些責任明確化。先在區間排程證明局部選擇安全,再改變目標,展示原證明為何失效。加權排程與背包說明如何用遞推式補回失去的資訊。以下輸入均有限,並容許空的可行選取。
定義
定義 2.3.1
(可行性、最優性與交換論證)
最優化問題指定可行解集合及須最大化或最小化的目標。貪心選擇按局部規則挑選下一部分。交換論證證明,可把某個最優解修改成包含貪心選擇,同時保持可行且目標不變差;還須說明選擇後的剩餘問題如何表示。
定義 2.3.2
(動態規劃狀態)
狀態指定一個子問題及其值。遞推式用較小狀態及基本情形表示該值。最優子結構表示可由遞推式所指定子問題的最優解組合出最優解。重疊子問題表示不同遞歸分支需要同一狀態。記憶化按需要計算一次;表列法則按依賴次序計算各狀態。
最優子結構不容許任意丟棄背景。例如禁止重複頂點的路徑問題中,只有當前端點未必足以描述合法後續,因為已用頂點可能影響可行性。狀態須保留影響未來可行性或成本的資訊;但記錄完整歷史又可能產生指數個狀態。設計時須兼顧充分性與狀態數目。
定理 / 命題
定理 2.3.3
(最早結束規則解決無權區間排程)
給定 的區間 ,每次選取剩餘相容區間中最早結束者,可得到數目最多的兩兩不重疊區間。端點可相接:在 結束者與在 開始者相容。按結束時間排序後掃描,時間為 。
定理 2.3.4
(加權區間排程遞推式)
按結束時間非遞減排序,區間權重 非負。令 為小於 且結束時間不晚於 的最大索引;若不存在則為零。若 是前 個區間可達的最大總權重,則
以二分搜尋計算前驅索引後,在精確權重運算為常數時間的模型下,排序及表列總時間為 ,輔助空間為 。
證明思路或證明
證明
(最早結束:交換與剩餘問題)
對貪心定理,令 是剩餘區間中最早結束者, 是某最優排程按時間排列的第一個區間。以 取代 。由 ,該排程所有後續區間均不早於 開始,故也不早於 。替換仍可行,區間數不變,所以存在包含 的最優解。
選 後,只有開始時間不早於 的區間合資格。若包含 的最優解之剩餘部分不是此子問題的最優解,就能把較好剩餘解接到 後面,矛盾。對合資格區間數歸納,空集合顯然,交換及剩餘論證完成每步。實作只須排序一次,按結束次序掃描,當區間開始不早於上個已選區間的結束便接受。相同結束時間可任意打破平手,因為證明只用非嚴格不等式。
證明透視
交換保持的是甚麼
用較早結束的區間取代最優排程第一區間,保持與後面所有區間的相容性,也保持選取數目。貪心證明依靠這兩點。加權目標失去第二點,替代區間可能輕很多。動態規劃透過比較包含與排除兩類,修補這個精確缺口,而非直接承諾交換。
證明
(加權遞推式:排除或包含最後一個區間)
對加權式,依是否包含區間 ,把前 個區間的可行解分兩類。不含者至多為 ,而此值可達。若含 ,其他已選區間必於 或之前結束:其結束時間不晚於 ,而正長度區間不可能放在 後方又在它之前結束。這些合資格的較早區間恰為截至 的前綴,最佳值為 ,接上 可達 。兩類涵蓋全部可能,取最大即證式子。
引用索引都小於 ,所以遞增索引表列合法。樸素遞歸可能反覆求同一索引,儲存每個值可避免重複。前驅已知後,每個狀態只作常數工作,最多 個狀態;排序及二分搜尋給總時間。若權重是長整數,應加入位元運算成本,不能預設常數。
重建一個解,而非只求值
表格記錄最優值,但用戶可能需要實際區間。從 開始,比較 與 。選前者便略過 ,移到 ;選後者便輸出 ,移到 。平手可用一致規則任選。每次索引下降,最多 步終止。遞推式證明保證選中分支可最優完成;倒轉輸出列表即得時間次序。
只有值表未必錯,但只解決求值版本,規格須區分所需輸出。反之,若每個狀態只存一個任意貪心部分排程,就會失去動態規劃用來保證正確的方案比較。
概念視角結構
把加權排程看成最長路徑
取頂點 與兩類邊:長度為零的 ,以及長度為 的 。從 到 的路徑恰好為所選的區間使用第二類邊進入 ,而且要先經過結束時間不晚於 的區間,才會再到達 。因此路徑長度就是一組相容區間的總權重,每組相容區間都對應一條路徑, 就是到 的最長路徑長度。重建的回溯就是把這條路徑倒過來讀。
零一背包與數值狀態參數
命題 2.3.5
(零一背包遞推式)
設物品 的正整數大小為 ,非負價值為 ,容量 為非負整數,每件最多取一次。令 為只用前 件且總大小不超過 的最佳值。基本值 ;由大小為正,。若 ,則 ;否則
證明
(零一背包:排除或包含最後一件物品)
仍把可行解分為不含及包含最後物品。包含時移除它,留下只用較早物品、容量為 的可行解;較差剩餘解可換成最優者。因此每分支可達,也上界所有解。引用第 行至關重要,它防止重複取第 件。
表有 個狀態,需 次算術運算及空間; 時慣寫為 。只求值可用 空間:每件物品按容量遞減更新。處理 時,較小容量仍存前一行值,故包含分支不能重用當前物品。遞增更新會解另一個容許重用的式子。若要重建全部物品,須保留決策或另證重建方法;一行壓縮值不自動包含那些決策。
由二進制 只有對數個位元, 是偽多項式,不是對編碼長度的一般多項式界。若 對該長度為指數,表格也為指數。動態規劃是設計方法,並非多項式時間保證。
另一個問題:恰好裝滿
上面的狀態容許留下空位。若要求總大小恰好為 ,空選便不是每個容量的可行答案。令 為只用前 件、總大小恰為 的子集的最大價值;若不存在這樣的子集,記為 。因此 ,但對每個 都有 。仍假設大小為正整數,按是否選第 件窮盡分類,得到
證明
(恰好裝滿的遞推式)
每個子集恰屬於選或不選一類;從恰好裝滿 的選取中移去第 件,前一行就恰好裝滿 。反過來,每個可達前驅都能構造相應方案;有限價值加上 仍表示不可達。對 歸納,既得到表中數值,也得到不可達狀態。因為不超過 的方案按確切大小分組,。
編程時應先檢查前一狀態能否到達,再做加法;不要直接給有限哨兵加值,以免溢出或誤勝過真實解。
例題 2.3.6
(剩餘容量與無法恰好裝滿)
物品為 與 時,可能的子集大小只有 ,所以恰好大小 不可達;但容量最多為 的最優值是 ,取第一件後還餘兩個單位。恰好大小 可取兩件,得 。價值為零也不能混同於不可達:若只有物品 ,恰好大小 可達且價值為 ,恰好大小 卻不可達。把兩者都初始化為零,就丟失了這個區別。
壓縮成一行時,仍可按容量遞減更新,但不可達項必須先置為 ,加法前亦要檢查前驅是否可達。結果給出最優值或不可達,不會自動給出所選子集。保留每件物品、每個容量的決策(包括可達性和一致的平手規則)才可據此重建;把數值哨兵當作真實選擇可能憑空造出子集。狀態數與對數值 的偽多項式依賴不變。
閱讀依賴圖
可把每個狀態視為頂點,向它依賴的狀態連邊。合法計算次序先放依賴項:加權排程只依賴較小索引,背包只依賴前一行。這種無環結構提供歸納,證明每個表值等於其定義的值。若式子引用自身卻沒有較小狀態,就需要額外推理,不能直接寫迴圈求值。
設計新動態規劃時,先用一句話精確定義一個狀態、指定參數範圍,再從可行解推導各類。接著檢查基本情形、計算次序、狀態數、每狀態工作及重建。這些檢查處理不同錯誤:正確式子可能以錯誤次序實作;正確表格也可能被錯估狀態數。前驅計算等前處理亦可能主導總成本,須一併計入。
例題詳解
反例模式
加入權重後,最早結束法會失效
斷言:最早結束法同樣使總權重最大。取 權重一與 權重一百。最早結束法選擇先結束的 ,並因兩者重疊而阻擋 ,總權重為一;只選 則得一百。無權的交換是把某區間換成較早結束的區間:它保持相容性與區間數目,卻不保持權重。修正方法是加權遞推式,它比較包含與排除兩種情形。此反例指出失效的證明步驟,並非說所有貪心算法在所有加權問題都失敗。
例題 2.3.7
(有實際取捨的加權表)
按結束次序取 權重三、 權重六、 權重四,前驅為 。表為 。重建選第三及第一區間,相接端點相容。只選個別最重者會得到六,而非七。
例題 2.3.8
(壓縮背包的更新方向)
只有一件大小二、價值三的物品,容量四,零一最優值為三。若從全零行遞增更新,先把容量二設為三,再於容量四使用這個新值,便得六,錯誤重用同一物品。遞減更新先處理容量四,讀到容量二的舊零值,正確保留三。
反例模式
按單位大小價值貪心對零一背包失效
一個誘人的規則是按價值與大小之比由大到小取物,只要放得下就取。容量為 ,物品 ,比值依次為 。此規則先取 ,餘下四個單位已放不下任何一件,價值為 ;兩件大小為五的物品卻能一起放入,價值為 。此規則只在物品可以分割時才最優;遞推式處理的是整件取或不取的選擇。
常見錯誤
常見錯誤
(忽略目標的交換論證)
交換論證須保持可行性與目標,並解釋剩餘問題;只說所選區間短或早並不足夠。反例也須符合所有假設,包括正長度及端點約定。
常見錯誤
(把按數值容量建的表當作多項式時間)
按數值容量建表可能隱藏對位元長度的指數依賴。當 時,背包表有 個狀態,而 的二進制編碼只有 位。界 是偽多項式的。
常見錯誤
(壓縮行時沒有追蹤讀取的是哪一行)
空間優化須保持每個讀取值所屬的邏輯行。對只有一件大小二、價值三的物品且容量為四,遞增的原地更新會得到 ,等於把該物品用了兩次;正確值是 。
動態規劃式須有涵蓋所有可行解的上界論證,也須建構能達到每個候選值的解。只數狀態會漏掉轉移工作:代價是狀態數乘以每個狀態的工作量。
總結
貪心排程有效,是因為交換可把最早結束選擇放進最優解而不減少數目。權重破壞此交換,遞推式便保留包含與排除兩種方案。加權排程及零一背包展示狀態意義、依賴、重建,以及多項式與偽多項式的區分。
練習
快速檢查
(用嚴格正長度區間,反駁無權排程「先選最短區間」。)
解答 · 答案
取 。最後一個唯一最短,選它會阻擋另兩個,只得一而非二。半開約定容許前兩區間端點相接。
練習 2.3.9
(區間 的權重依次為 。計算前驅索引、值表與一個最優排程。)
核心
解答(3)
- 1
計算前驅索引
依據: 區間已按結束時間 排序, 是結束時間不晚於 的最大較小索引。
- 2
填寫值表
關鍵一步
- 3
回溯得到最優排程
在狀態四,包含給出 ,所以選區間四並移到 。在狀態二,包含給出 ,所以選區間二並移到 。狀態一則選區間一。這三個互相相容的區間權重為 ,超過單獨一個權重為七的區間。
快速檢查
(若容許負價值但仍可空選,解釋零一背包式為何仍正確。)
解答 · 答案
包含與排除仍分割全部可行解,每個分支仍可達,所以不論價值的正負,遞推式都算出真正的最大值。空選值為零,因此最大化時不必選負價值物品。大小為正只用於基本值 ,以及使 成為嚴格較小的容量,遞減的原地更新尚未覆蓋它。
練習 2.3.10
(面額為一、三、四。說明反覆取最大可用硬幣來湊六並不最優,並為一般的非負目標推出最少硬幣數的遞推式。)
綜合
解答(4)
- 1
否定最大硬幣規則在目標六時的最優性
貪心取四、一、一,用三枚硬幣;三加三只用兩枚。
- 2
定義狀態
令 為湊成總額 所需的最少硬幣數,。因為有面額為一的硬幣,每個目標 都可行。
- 3
按最後一枚硬幣分類
關鍵一步
把剩餘部分換成 的最優解不會增加枚數,而在這樣的最優解後加上該硬幣就達到候選值。因此對 ,
依據: 每個方案的最後一枚硬幣都是某個允許面額 ,剩下目標 。
- 4
按目標遞增的次序計算
每個值只用較小的值,所以算到所需目標只需對該數值目標做線性次數的算術運算;對二進制編碼的目標,這是偽多項式界。