加權區間排程:子問題必須排除衝突
在無權重的問題中,選擇最早完成的活動可以令互相相容的活動數目達到最大,但未必能令總回報達到最大。只要我們找出選擇某項活動後剩下的較小問題,動態規劃便能奏效。
1. 訂明排程模型
共有 n 項活動。活動 i 佔用半開區間 [s_i,f_i),其中 s_i<f_i,並帶有回報 w_i。回報可以相加,而甚麼都不選的回報為零。輸入按完成時間排序,這樣每個相容的前綴都可以被識別出來。
定義 7.1.1
(加權區間排程與前驅下標)
若兩項活動所佔用的區間互不重疊,則稱它們為相容;一項活動恰好在另一項開始時完成是容許的。問題要求找出一組兩兩相容、總回報最大的活動,空集的回報為 。將活動按完成時間的非遞減次序排列,並以確定的方式處理同值情況,然後依此次序編號為 。
- 前驅下標 是滿足 的最大下標 ;若不存在這樣的下標,則為 。
- 是只從首 項活動中選出相容集合所能得到的最大總回報,並設 。
定理 7.1.2
(前驅遞推式)
設活動已按完成時間的非遞減次序編號,且 ,回報 為任意實數。則對 ,
證明
(排除活動 i 或包含活動 i)
設 為 的所有相容子集所組成的族(包括空集),所以 就是 上總回報的最大值。按是否選取 將 分成兩類。
不含 的集合恰好就是 的成員,因此它們的最佳回報為 。
現取 。由排序可知 ,而 ,故 :活動 不可能在 或之後才開始。所以 與 相容,當且僅當 在 或之前完成,即 。集合 正是前綴 :若 ,則 ;若 ,則 ,因為 是具有該性質的最大下標。
因此,含 的集合相容,當且僅當它具有 的形式,其中 。其回報為 ,所以這類集合的最佳回報是 ,而且可以達到。 中每個集合恰好屬於兩類之一,兩個值都能達到,所以 是兩者中較大的一個。回報為負數也不構成問題:空集既屬於 ,也屬於 ,所以兩個分支都不會被迫蒙受損失。
遞推式只在位置 和 讀取表格,因此可以依 的次序填表。單靠排序並不能解決問題;排序的作用是令相容的活動構成一個前綴。
證明透視
各項假設在遞推式中的作用
這個論證只有一個結構性的步驟:包含 的排程與前綴 的排程,可以透過加入或移除 一一對應。三項假設使這個對應成立。
第一,按完成時間排序,使每個 都有 。第二,區間長度為正,即 。兩者合起來排除了下標較小的活動從右方與 相容的唯一方式,即在 或之後才開始,於是與 相容就化為單一測試 。第三,由於完成時間非遞減,這個測試把 以下的下標切成一個前綴,所以只用一個數 就能概括所有衝突。
論證隨後便告完成:被移除的 本身就是前綴內任意的相容集合,所以 正是所需的量;而兩個互相窮盡的情況的最大值,就是兩個情況的值中較大者。去掉排序的假設,第一點和第三點便會失效;最後一節的反例顯示遞推式會給出錯誤的值。
概念視角結構
把遞推式看成最長路徑
取節點 ,並為每個節點 設兩種入邊:邊 ,權重為 (略過活動 );邊 ,權重為 (選取它)。每條邊都向前,所以這個圖無環,節點可以按遞增次序處理。從節點 出發的最長路徑距離 滿足 及 ,這正是 的遞推式。從 到 的一條路徑對應於它所使用的選取邊所屬的活動集合:若路徑選取了 ,之後又選取 ,則它必先到達節點 ,所以 ,兩者相容。反過來,每個相容集合都給出這樣的一條路徑。重構就是沿著每個最大值所取的邊往回走。
2. 詳解例子
例題 7.1.3
(含邊界相等情況的五項活動)
以下活動已按完成次序排列。計算每個前驅時,須將先前活動的完成時間與目前活動的開始時間比較,並包括相等的情況。
i | 區間 | 回報 | p(i) | OPT(i) |
|---|---|---|---|---|
| 1 | [1,3) | 5 | 0 | 5 |
| 2 | [2,5) | 6 | 0 | 6 |
| 3 | [4,6) | 5 | 1 | 10 |
| 4 | [6,7) | 4 | 3 | 14 |
| 5 | [5,8) | 11 | 2 | 17 |
例如,活動 4 可以接在活動 3 之後,因為 6 <= 6。在活動 5,不包含它得 14,包含它則得 11+OPT(2)=17,所以選擇 5,並在下標 2 繼續。在 2,包含它得 6,不包含它得 5,所以選擇 2。被選中的區間 [2,5) 和 [5,8) 的總回報為 17。前驅是一個下標,而不是先前某項活動的總回報。
要重構一個排程,從 i=n 開始。若 w_i+OPT(p(i)) > OPT(i-1),則選擇 i 並設 i=p(i);否則設 i=i-1。遇到相等時,此策略會略過 i,得出其中一個有效的最佳解;若在相等時選擇 i,只要重構隨後在 p(i) 繼續,亦同樣有效。若需要按時間先後排列,最後把選中的下標倒序即可。
例題 7.1.4
(負回報與空排程)
取已按完成時間排序的活動:[0,2) 回報 、[1,3) 回報 、[3,5) 回報 。前驅:活動 1 的 p(1)=0;活動 2 在 1 開始,但活動 1 在 2 才完成,所以 p(2)=0;活動 3 在 3 開始,而活動 2 在 3 完成,所以 p(3)=2。
各值:OPT(1)=max{0, -4+0}=0,OPT(2)=max{0, 2+0}=2,OPT(3)=max{2, -1+OPT(2)}=max{2,1}=2。重構:在 3,-1+2=1 不大於 OPT(2)=2,所以略過而移到 2;在 2,2+0=2>OPT(1)=0,所以選擇 2 並跳到 0。最佳解是只選單一活動 [1,3),回報為 2。若所有回報皆為負數,每次包含測試都會失敗,重構便會得出回報為 0 的空排程,這就是邊界情況 OPT(0)=0 的作用。
例題 7.1.5
(以二分搜尋計算 p(i))
沿用第一個例子的完成時間 3,5,6,7,8,計算 p(5),其中 s_5=5。我們要在 0..4 中找出滿足 f_j <= 5 的最大 j,並視 j=0 為必然可接受。維持一個已知包含答案的區間 [lo,hi],起始為 lo=0、hi=4;當 lo<hi 時,探測 mid=ceil((lo+hi)/2),若 f_mid <= s_i 則設 lo=mid,否則設 hi=mid-1。
探測 mid=2:f_2=5<=5,所以 lo=2。探測 mid=3:f_3=6>5,所以 hi=2。區間為 [2,2],故 p(5)=2,與表格相符。兩個極端情況幾乎不用探測:i=1 時區間為 [0,0],立即得 p(1)=0;i=2(s_2=2)時,探測 mid=1 得 f_1=3>2,所以 hi=0,p(2)=0。每個前驅約需 log2 i 次探測。
3. 成本與一個邊界陷阱
排序的成本為 O(n log n)。由於完成時間已經排序,可以在前綴 1,...,i-1 中以二分搜尋找出最右邊、完成時間至多為 s_i 的活動,每個前驅花 O(log n),總共 O(n log n)。填表與重構各需 O(n),而表格、前驅陣列及輸出共使用 O(n) 空間。這些結論假設對所給數值的比較與算術運算均為常數時間。為每個前驅向後逐一掃描同樣正確,但成本可能達到 Theta(n^2)。
若改為規定當一個端點等於另一個端點時區間即屬衝突,則相容性測試變成 f_j < s_i;前驅陣列和答案都可能隨之改變。遞推式必須配合問題本身的規則,而不是某個未經說明的慣例。
常見錯誤
(容許端點相接時卻用了嚴格不等式)
若模型容許 [a,b) 與 [b,c) 同時被選,卻寫成 f_j < s_i,前綴便會縮短。在第一個詳解例子中,這會令 p(4)=2 而非 3,因為 f_3=6 不再被接受;於是 OPT(4)=max{10, 4+6}=10 而非 14,p(5) 變成 1,最終答案由 17 降至 16。測試必須根據所訂明的相容規則來選擇。
常見錯誤
(把 i-1 當作前驅)
排序使活動 i-1 不遲於 i 完成,但它仍可能與 i 重疊。在第一個例子中,[6,7)(活動 4)與 [5,8)(活動 5)重疊,所以 w_5+OPT(4)=25 不是任何排程的值。正確的前驅是 p(5)=2,它略過所有與活動 5 衝突的活動。
表格同樣依賴輸入的次序,下面的例子說明這一點。
反例模式
遞推式需要按完成時間排序的輸入
假設活動按以下次序列出:活動 1 為 [2,4),回報 5;活動 2 為 [0,1),回報 3,因此完成時間 4 與 1 並非非遞減。沿用同一定義,p(2) 是滿足 f_j<=0 的最大 j<2;由於 f_1=4,得 p(2)=0。於是 OPT(1)=5,OPT(2)=max{5, 3+OPT(0)}=5。但區間 [0,1) 與 [2,4) 互不相交,所以真正的最佳值是 5+3=8。活動 1 與活動 2 相容,但在時間上位於其後,而測試 f_j<=s_i 只能偵測在活動 i 開始前完成的活動。按完成時間排序後,[0,1) 在前、[2,4) 在後,於是 p(2)=1,遞推式得出 max{3, 5+3}=8。
快速檢查
(按完成時間排序的活動為 [0,4) 回報 2、[3,5) 回報 3,以及 [4,7) 回報 1。計算 p(1),p(2),p(3) 與 OPT(1),OPT(2),OPT(3)。)
將每個完成時間與目前活動的開始時間比較,並容許相等。
解答 · 答案
p(1)=0。活動 2(開始時間 3):f_1=4>3,所以 p(2)=0。活動 3(開始時間 4):f_2=5>4,但 f_1=4<=4,所以 p(3)=1。於是 OPT(1)=2,OPT(2)=max{2, 3+0}=3,OPT(3)=max{3, 1+OPT(1)}=max{3,3}=3。相等的情況顯示有兩個最佳排程 {2} 與 {1,3},回報同為 3。
練習:重疊的活動
快速檢查
(考慮以下活動:[1,3),回報 4;[3,4),回報 4;以及 [2,5),回報 9。求最佳回報,並解釋為何在帶權回報的情況下,反覆選擇最早完成的活動並不足夠。)
比較總回報之前,先列出哪些活動對互相相容。
解答 · 答案
按完成次序,首兩項活動互相相容,總回報為 8。第三項與它們每一項都重疊,單獨選擇可得 9,因此最佳值為 9。最早完成選擇法會選取首兩項,得到 8;這條貪心規則優化的是另一個目標,即活動的數目,而不一定是總回報。
練習:五項按完成時間排序的活動
快速檢查
(已按完成時間排序的活動為:[0,2) 回報 3、[1,3) 回報 5、[2,4) 回報 4、[3,5) 回報 4,以及 [4,6) 回報 3。計算 p、動態規劃的值,以及一個最佳排程。)
先計算 p,再由左至右填表。
解答 · 答案
前驅陣列為 [0,0,1,2,3]。由 OPT(0)=0 開始,各值依次為 3,5,7,9,10:例如第五項活動給出 3+OPT(3)=10,大於 OPT(4)=9。選擇 5,然後選擇 3,因為 4+OPT(1)=7>OPT(2)=5,再選擇 1。區間 [0,2)、[2,4)、[4,6) 只在端點相接,總回報為 3+4+3=10。這個重構過程沿用了證明中所用的「包含/不包含」兩個選項。