數據集
互動工具採用的六個工作數據與貪心選擇與動態規劃一節的三個區間不同。工作按結束時間排序,佔用半開區間:前一個工作恰好在下一個開始時結束,兩者仍可兼容。調整工作 E 的報酬並觀察表格,不要把前例的數值套進來。
前驅索引與遞推式
定義 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。報酬更大時情況相同。所以最小的報酬是 。