數據集
互動工具採用的六個工作數據與貪心選擇與動態規劃一節的三個區間不同。工作按結束時間排序,佔用半開區間:前一個工作恰好在下一個開始時結束,兩者仍可兼容。調整工作 E 的報酬並觀察表格,不要把前例的數值套進來。
選定最後一項工作,再證明剩下的子問題
有權重的排程不能只看誰最早結束。逐項比較包含與略過的兩種完備情況,填好最優值表,再重建一個相容排程。改變 E 的價值會改變最佳化問題,但不改變區間的幾何關係。
按結束時間排序的六項工作
每項工作佔用 [開始, 結束):包含起點,不包含終點,所以工作可在端點相接。實心起點與空心終點標示半開區間。粗長條表示目前工作;雙外框與 ✓ 表示重建時已選取的工作。虛線框標記第 1 至 p(j) 項工作;它們各自與目前工作相容,但彼此未必相容。
此圖重述下表的區間與目前及已選工作狀態。 目前已重建的工作: 尚未選取任何工作.
| j | 工作 | [s, f) | 價值 | p(j) | 略過:OPT(j−1) | 包含:w_j+OPT(p(j)) | OPT(j) | 本列遞推選擇 | 排程狀態 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 空前綴 | — | 0 | — | |||||
| 1 | A | [0, 2) | 4 | 0 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
| 2 | B | [1, 4) | 10 | 0 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
| 3 | C | [2, 5) | 4 | 1 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
| 4 | D | [4, 6) | 4 | 2 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
| 5 | E | [5, 7) | 9 | 3 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
| 6 | F | [6, 8) | 4 | 4 | 尚未計算 | 尚未計算 | 尚未計算 | 尚未計算 | 尚待重建 |
最早結束的貪婪比較
此處的貪婪法忽略權重,選取 A、C、E。這是可行的比較排程,並不能證明有權重問題的最優性。
A, C, E: 4+4+9=17.
目前已重建的工作: 尚未選取任何工作
- 全部六項工作的最優值
- 尚未得到
- 貪婪排程價值
- 17
- 目前已重建的價值
- 0
- 下一個重建子問題
- 尚未開始重建
步驟 1 / 18: 設定初始值
設定 OPT(0)=0,其餘值尚未知,亦未重建排程。
為何這兩種情況已經足夠
每項工作時長為正,即 s_j<f_j。工作按結束時間由小至大編號。定義 OPT(j) 為第 1 至 j 項工作中,相容子集可取得的最大總價值;允許空子集,故 OPT(0)=0。p(j) 是結束時間不遲於 j 的開始時間的最大較早索引;若不存在則為 0。區間右端不包含在內,故時間相等亦相容。本例 p(1),…,p(6) 為 0,0,1,2,3,4。
考慮只使用第 1 至 j 項工作的最優排程。若它略過 j,價值至多為 OPT(j−1),而該較小前綴的最優排程在此亦可行。若它包含 j,其他已選工作都必須不遲於 j 開始時結束:正時長給出 start_i<finish_i≤finish_j,故較早編號工作不能在 j 結束後才開始。由 p(j) 的最大性,其他工作都在第 1 至 p(j) 項內,其價值至多為 OPT(p(j))。反過來,按結束時間排序保證每個 i≤p(j) 均有 finish_i≤finish_p(j)≤start_j,因此將 j 加到該前綴的最優排程確實相容;空前綴則毋須檢查。兩種都能達到的情況給出 OPT(j)=max(OPT(j−1), w_j+OPT(p(j)))。
每個依賴索引都小於 j。由 OPT(0)=0 開始,以歸納法可證每個已寫入的值均正確。「比較」步驟顯示兩個已知的依賴,尚未提早寫入下一格。本列標示「包含」,只描述該子問題的最優選擇,並不表示該工作一定屬於全部六項工作的最終解。
表格填好後,由 j=6 開始。若包含的候選值嚴格較大,選取 j 並跳至 p(j);否則略過 j,跳至 j−1。不變量為 value(已選工作)+OPT(j)=OPT(6),且每項已選工作均與剩餘前綴第 1 至 j 項中的每項工作相容。包含時以 OPT(j)=w_j+OPT(p(j)) 保留等式;略過時以 OPT(j)=OPT(j−1) 保留等式。索引嚴格下降,故重建必在 0 結束。每次選取後都跳到在它開始前結束的前綴,因此已選工作相容,最後總值達到 OPT(6)。兩候選平手時兩邊皆最優;本圖一律略過,所以只重建一個最優排程,並非列出所有最優解。
對本例六項工作,OPT(6)=max(18,10+wE)。對每個允許的權重,OPT(6)≥10+wE>8+wE,所以最早結束的貪婪法均非最優。wE=9 時,貪婪排程 A,C,E 價值為 17,而 B,E 價值為 19。wE=8 時,B,E 與 B,D,F 均為 18;最後一列平手時略過 F,故重建得到 B,E。wE=4 時,第 5 列本身平手而略過 E,最終解為 B,D,F。平手時採用的選擇,與所有最優排程的集合,是不同的概念。
所示實作逐項掃描較早工作以計算全部 p(j),需 O(n²)。若結束時間已排序,可用二分搜尋在 O(n log n) 內預先求得;若還要排序,排序亦需 O(n log n)。給定 p(j) 後,填表與重建各為 O(n),表格儲存為 O(n)。這些單位成本算術界沒有計入本圖複製狀態及繪製的工作。
即時檢查:為何不能把所有編號不大於 p(j) 的工作都加進來?
該前綴中的工作各自與 j 相容,但它們彼此可能重疊。我們加入的是 OPT(p(j)),即最優相容子集的價值,而非把前綴內所有權重相加。
按閱讀次序列出完整追蹤
- 設定 OPT(0)=0,其餘值尚未知,亦未重建排程。
- j=1 (A), p(1)=0: max(OPT(0)=0, 4+OPT(0)=4). 比較候選值;OPT(j) 尚未寫入。
- j=1 (A), p(1)=0: max(OPT(0)=0, 4+OPT(0)=4). 包含; OPT(1)=4. 這是局部子問題的選擇,尚未重建最終排程。
- j=2 (B), p(2)=0: max(OPT(1)=4, 10+OPT(0)=10). 比較候選值;OPT(j) 尚未寫入。
- j=2 (B), p(2)=0: max(OPT(1)=4, 10+OPT(0)=10). 包含; OPT(2)=10. 這是局部子問題的選擇,尚未重建最終排程。
- j=3 (C), p(3)=1: max(OPT(2)=10, 4+OPT(1)=8). 比較候選值;OPT(j) 尚未寫入。
- j=3 (C), p(3)=1: max(OPT(2)=10, 4+OPT(1)=8). 略過; OPT(3)=10. 這是局部子問題的選擇,尚未重建最終排程。
- j=4 (D), p(4)=2: max(OPT(3)=10, 4+OPT(2)=14). 比較候選值;OPT(j) 尚未寫入。
- j=4 (D), p(4)=2: max(OPT(3)=10, 4+OPT(2)=14). 包含; OPT(4)=14. 這是局部子問題的選擇,尚未重建最終排程。
- j=5 (E), p(5)=3: max(OPT(4)=14, 9+OPT(3)=19). 比較候選值;OPT(j) 尚未寫入。
- j=5 (E), p(5)=3: max(OPT(4)=14, 9+OPT(3)=19). 包含; OPT(5)=19. 這是局部子問題的選擇,尚未重建最終排程。
- j=6 (F), p(6)=4: max(OPT(5)=19, 4+OPT(4)=18). 比較候選值;OPT(j) 尚未寫入。
- j=6 (F), p(6)=4: max(OPT(5)=19, 4+OPT(4)=18). 略過; OPT(6)=19. 這是局部子問題的選擇,尚未重建最終排程。
- F: 略過. 繼續重建子問題 j=5. 目前已重建的工作: 尚未選取任何工作.
- E: 包含. 繼續重建子問題 j=3. 目前已重建的工作: E.
- C: 略過. 繼續重建子問題 j=2. 目前已重建的工作: E.
- B: 包含. 繼續重建子問題 j=0. 目前已重建的工作: B, E.
- 所示排程互相相容,且達到已計算的最優值。 OPT(6)=19; B, E.
這是獨立的原創六項工作例子。所有區間及權重預先已知,工作時長為正;E 的價值為 0 至 16,其餘固定。這是有權重區間排程,並非對所有排程問題或整個課程範圍的宣稱。
前驅索引與遞推式
定義 2.5.1
(前驅索引與前綴最優值)
把工作 按結束時間非遞減排列:。工作 佔用半開區間 ,其中 ,報酬為 。兩個工作的區間不相交時兼容,所以一個工作恰好在另一個開始時結束,兩者仍然兼容。前驅索引 是滿足 的最大 ;若沒有這樣的 ,則 。令 為工作 的相容子集所能得到的最大總報酬,並規定 。
對工作 , 是一個索引:它標示一段可用的前綴,不是報酬,也不代表必須選取該最後工作。E 在時刻 5 開始,C 在 5 結束,因此 。截至 C 的前綴子問題考慮 A、B、C 中的相容子集,並選取報酬最大的子集。
定理 2.5.2
(加權區間遞推式)
對 ,
此外,在工作 之中,與工作 兼容的恰是工作 。
證明
(包含或不包含最後一個工作)
對 ,工作 與 的區間不相交,當且僅當 :另一種可能 會給出 ,不可能成立。若 ,則 ;若 ,則由 的選取知 。因此在 之中與 兼容的恰是 。
再取 的一個最優相容子集 。若 ,則 是 的相容子集,報酬至多為 ,而 的一個最優子集達到這個值。若 ,則 是 的相容子集,所以 的報酬至多為 ;反過來, 的一個最優子集加上 仍相容,並達到這個值。每個相容子集都屬於兩種情況之一,兩個值也都能達到,所以 是兩者的最大值。以 為基礎,對 歸納即涵蓋所有行。
證明透視
為甚麼一個索引可以代表一整組工作
唯一不顯然的一點,是較早的兼容工作構成一段前綴,所以「包含」分支只涉及一個較小的子問題 。這正是用到按結束時間排序之處:它使條件 隨 單調。區間長度為正,即 ,用來排除 的情況。按 與否分類是窮盡的,沒有損失,所以不需要交換論證。歸納得以完結,是因為兩個分支都只涉及更短的前綴,並以 為基礎。兩個分支並列並不影響數值,只影響回溯返回哪一個排程。
因此,排序是方法的一部分,而不是為方便而做的步驟。
反例模式
按開始時間排序會破壞前綴性質
斷言:不論工作以甚麼次序列出,較早的工作中與工作 兼容的總是一段前綴 。按開始時間列出 (報酬 )、(報酬 )和 (報酬 )。滿足 的最大 是 ,所以公式會採用前綴 ,其最大報酬為 (取 )。於是公式報告 ,對應同時含 與 的排程,但兩者重疊,真正的最優值是 。修正方法是按結束時間排序,使 隨 單調,兼容的工作才構成前綴。
閱讀軌跡
例題 2.5.3
(預設報酬:選取 E)
取 。A 至 F 的前驅索引依次為 :例如 D 在 開始,恰是 B 結束之時,這是允許的;F 在 開始,恰是 D 結束之時。表格為 。第 3 行比較 與 ;第 4 行比較 與 ;第 5 行比較 與 ;第 6 行比較 與 。回溯時,第 6 行因 而略過;第 5 行選取 E 並跳至 ;第 3 行略過;第 2 行選取 B 並跳至 。排程 的報酬為 。對 E 的比較是在相應前綴的完整排程之間進行,而不是只拿 E 跟相鄰工作比較。
例題 2.5.4
(報酬為 4:不決定排程的並列)
設 。第 5 行比較 與 :兩個選項都等於 ,軌跡在相等時略過 E。第 6 行比較 與 ,故選取 F,表格為 。回溯時選取 F 並跳至 ;第 4 行因 選取 D 並跳至 ;再選取 B。排程 的報酬為 。在第 5 行選取 E 對該前綴同樣最優,即 ,報酬 ,但 F 與 E 重疊,這個前綴排程無法擴充為整體最優解。中間一行的平手本身不是最終排程。
例題 2.5.5
(沒有前驅與報酬為零)
第 2 行的 ,因為沒有較早的工作在時刻 之前結束。「包含」分支為 ,勝過「不含」分支 ;基礎值 使這種情況不需要特殊處理。現在設 。第 5 行比較 與 ,略過 E;其餘各行與報酬為 時相同,得到 ,報酬 。報酬為零的工作永不被選取:它的「包含」值 不可能超過 ,因為 非遞減,而軌跡只在包含嚴格更好時才選取。
回溯時,選取工作就跳至其前驅,略過則退回上一行;兩種情況都保持餘下前綴的最優值。
常見錯誤
常見錯誤
(把前驅索引當作已選取的工作)
索引 標示的是一段可用的前綴,並不表示工作 被選取。對 E, 使 A、B、C 都可用,但該前綴內最好的排程報酬為 ,只含 B,並不含 C。
常見錯誤
(使用錯誤的端點比較)
數據是半開區間,所以前驅檢驗是 。若共用端點算作衝突,檢驗就要改為 ,表格也會隨之改變。D 在 開始,恰是 B 結束之時。按半開規則,,(工作 B 與 D);按嚴格規則,則 ,因為只有 A 在時刻 之前結束,而 。
練習
快速檢查
(E 的報酬為 9 時,回溯選取哪些工作?總報酬是多少?)
從第 6 行開始,只在包含嚴格更好時才選取工作。
解答 · 答案
第 6 行比較 與 ,略過 F。第 5 行比較 與 ,選取 E 並跳至第 3 行。第 3 行比較 與 ,略過 C。第 2 行比較 與 ,選取 B 並跳至第 0 行。選取的工作為 B 與 E,總報酬為 。
快速檢查
( 是多少?為甚麼是 而不是 ?)
把 F 的開始時間與 D、E 的結束時間比較。
解答 · 答案
F 在 開始。工作 D 佔用 ,在 結束,按半開區間約定兩者兼容,所以 。工作 E 佔用 ,在 結束,與 F 重疊,不可用。因此 。
快速檢查
(E 的報酬至少為多少(取整數),回溯才會選取 E?)
把第 5 行與第 6 行的「包含」值、「不含」值寫成 的函數來比較。
解答 · 答案
第 5 行給出 。在第 6 行,當 時選取 F,此時 E 不會被選取,因為 F 與 E 重疊。 時 ,故選取 F。 時 ,第 6 行平手,略過 F;第 5 行因 而選取 E。報酬更大時情況相同。所以最小的報酬是 。