5第五章貪心方法

1、1第五章第五章貪心方法貪心方法25.1 一般方法一般方法5.2 背包問題背包問題5.3 帶有限期的作業(yè)排序帶有限期的作業(yè)排序5.4 最優(yōu)歸并模式最優(yōu)歸并模式5.5 最小生成樹最小生成樹(略略)5.6 單源點最短路徑單源點最短路徑(略略)目錄目錄35.1 一般方法一般方法p方法適用的問題特點方法適用的問題特點p方法的基礎知識方法的基礎知識p方法的求解步驟及核心問題方法的求解步驟及核心問題p方法的抽象化控制方法的抽象化控制p方法的缺點和優(yōu)點方法的缺點和優(yōu)點4p如果有一個機會可以幫助你夢想成真，那么你希如果有一個機會可以幫助你夢想成真，那么你希望哪兩個夢想成真：望哪兩個夢想成真：n1 去巴西看足球世

2、界杯；去巴西看足球世界杯；n2 心儀已久的大學學習；心儀已久的大學學習；n3 環(huán)球旅行；環(huán)球旅行；n4 參觀參觀2014青島世博會現場。青島世博會現場。一個現實世界里的例子一個現實世界里的例子1、2 1、3 1、42、3 2、43、45夢夢想想成成真真的的例例子子貪心方法適用的問題特點貪心方法適用的問題特點p有這樣一類問題：它有有這樣一類問題：它有n個輸入，而它的解就是個輸入，而它的解就是這這n個輸入的某個子集，個輸入的某個子集，這些子集必須滿足某些這些子集必須滿足某些事先給定的條件。事先給定的條件。約束條件約束條件可行解可行解最優(yōu)解最優(yōu)解目標目標函數函數1、2 1、3 1、42、3 2、43

3、、4兩個活動兩個活動個人喜好個人喜好？6基本概念：基本概念：約束條件、可行解、目標函數、最優(yōu)解約束條件、可行解、目標函數、最優(yōu)解A(1)A(2)A(n 1)A(n)B1(1)B1(2)B1(m1)Bk(1) Bk(2)Bk(mk)最優(yōu)解最優(yōu)解 問題有問題有n個輸入，它的解就是這個輸入，它的解就是這n個輸入的某個子集，這個子個輸入的某個子集，這個子集必須滿足某些事先給定的條件即集必須滿足某些事先給定的條件即約束條件約束條件，滿足約束條件的，滿足約束條件的子集稱為該問題的子集稱為該問題的可行解可行解。一般來說可行解不是唯一的，為衡。一般來說可行解不是唯一的，為衡量可行解的優(yōu)劣，以函數的形式給出一定

4、的標準，這些函數稱量可行解的優(yōu)劣，以函數的形式給出一定的標準，這些函數稱為為目標函數目標函數，使目標函數取極值，使目標函數取極值(極大或極小極大或極小)的可行解就稱為的可行解就稱為最最優(yōu)解優(yōu)解。B1是該問題的是該問題的一個可行解一個可行解B1滿足一定滿足一定的約束條件的約束條件B2(1)B2(2)B2(m2)一類問題有一類問題有n個輸入個輸入:Bi是是A的一個子集的一個子集該問題有該問題有k個可行解個可行解該可行解可使該可行解可使 目目標函數取極值標函數取極值7基礎知識基礎知識p貪心方法是指在對問題求解時，總是做出貪心方法是指在對問題求解時，總是做出在當前看來是最好的選擇。在當前看來是最好的選

5、擇。p貪心方法的思想可以追溯到貪心方法的思想可以追溯到1823年年J.C.Warnsdorff 解決馬踏棋盤問題時給解決馬踏棋盤問題時給出的一個著名的算法。出的一個著名的算法。p貪心方法應用的典型問題有背包問題、帶貪心方法應用的典型問題有背包問題、帶有期限的作業(yè)排序、最小生成樹、單源點有期限的作業(yè)排序、最小生成樹、單源點最短路徑等問題。最短路徑等問題。8貪心方法的求解步驟貪心方法的求解步驟 p貪心方法是根據具體的問題：貪心方法是根據具體的問題：n選取一種量度標準；選取一種量度標準；n按此標準對按此標準對n個輸入進行排序；個輸入進行排序； n按該順序一次輸入一個量；按該順序一次輸入一個量；n如果

6、這個輸入量和當前如果這個輸入量和當前該量度意義下該量度意義下的部分最的部分最優(yōu)解加在一起不能產生一個可行解優(yōu)解加在一起不能產生一個可行解，則不把此則不把此輸入加入到這個部分解中。輸入加入到這個部分解中。p這種能夠得到某種量度意義下的最優(yōu)解的這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法就是分級處理方法就是貪心方法貪心方法。9貪心方法設計求解的核心問題貪心方法設計求解的核心問題p貪心方法設計求解的核心問題是選擇能產生問題貪心方法設計求解的核心問題是選擇能產生問題最優(yōu)解的最優(yōu)量度標準。最優(yōu)解的最優(yōu)量度標準。p值得一提的是，把目標函數作為度量標準所得到值得一提的是，把目標函數作為度量標準所得到的解

7、也不一定是問題的最優(yōu)解。的解也不一定是問題的最優(yōu)解。A(1)A(2)A(n)次優(yōu)解次優(yōu)解次優(yōu)解次優(yōu)解最優(yōu)解最優(yōu)解A1(n)A1(1)量度標準量度標準1A2(n)A2(1)量度標準量度標準2Ak(n)Ak(1)量度標準量度標準k10按某種最優(yōu)量度標準從按某種最優(yōu)量度標準從A中中選擇一個輸入，把它賦值給選擇一個輸入，把它賦值給x，并從并從A中消去它。中消去它。Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution, x) then solutionUNION(solution, x) endif r

8、epeat return (solution)End GREEDY算法算法5.1 貪心方法的抽象化控制貪心方法的抽象化控制判斷判斷x是否可以包是否可以包含在解向量中含在解向量中將將x與解向量結合與解向量結合并修改目標函數并修改目標函數11方法的缺點和優(yōu)點方法的缺點和優(yōu)點p缺點：缺點：n不是對所有問題都能得到整體最優(yōu)解。不是對所有問題都能得到整體最優(yōu)解。n需要證明后才能真正運用到題目的算法中。需要證明后才能真正運用到題目的算法中。p優(yōu)點：優(yōu)點：n一旦經過證明成立后，它就是一種高效的算法。一旦經過證明成立后，它就是一種高效的算法。n策略的構造簡單易行。策略的構造簡單易行。n對范圍相當廣泛的許多問題

9、他能產生整體最優(yōu)對范圍相當廣泛的許多問題他能產生整體最優(yōu)解或者是整體最優(yōu)解的近似解。解或者是整體最優(yōu)解的近似解。125.2 背包問題背包問題p問題描述問題描述p背包問題實例背包問題實例p背包問題的貪心算法背包問題的貪心算法p定理定理5.113 極極 大大 化化 pixi 0 xi 1, pi 0 約束條件約束條件 wixi M wi 0, 1 i nn 已知有已知有n種物品和一個可容納種物品和一個可容納M重量的背包，每種重量的背包，每種物品物品i(1 i n)的重量為的重量為wi，假定將物品，假定將物品i的某一部分的某一部分xi放入背包就會得到放入背包就會得到pixi的效益的效益(0 xi 1

10、,1,pi 0) ) ，采用怎，采用怎樣的裝包方法會使裝入背包物品的總效益為最大？樣的裝包方法會使裝入背包物品的總效益為最大？n 問題的形式化描述：問題的形式化描述：問題描述問題描述14(x1, x2, x3) wi xi pixi(1, 2/15, 0) 2028.2(1, 0, 1/5)2028(0, 2/3, 1)2031(0, 1, 1/2)2031.5其中的其中的4個可行解是：個可行解是：有有3個物品個物品n 3，背包能容納的最大重量，背包能容納的最大重量M 20，物品的價值和，物品的價值和重量：重量： (p1, p2, p3) (25,24,15)，(w1,w2,w3) (18,1

11、5,10)背包問題實例背包問題實例考慮下列情況下的背包問題：考慮下列情況下的背包問題：效益值的非增次序效益值的非增次序物品重量的非降次序物品重量的非降次序pi wi比值的非增次序比值的非增次序15p即以目標函數為量度標準即以目標函數為量度標準n該標準使得背包每裝入一件物品就獲得最該標準使得背包每裝入一件物品就獲得最大可能的效益值增量。大可能的效益值增量。n結果是一個次優(yōu)解，原因是背包容量消耗結果是一個次優(yōu)解，原因是背包容量消耗過快過快。(x1,x2,x3) wixi pixi(1,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5(1)按效益值的非增次按效益值的

12、非增次序把物品放到包里。序把物品放到包里。(p1, p2, p3) (25,24,15)；(w1, w2, w3) (18,15,10)。(2)按物品重量的非降按物品重量的非降次序把物品放到包里。次序把物品放到包里。p以容量為量度標準以容量為量度標準n該標準使得背包每裝入一件物品就獲得最該標準使得背包每裝入一件物品就獲得最小可能的容量增量。小可能的容量增量。n結果仍是一個次優(yōu)結果仍是一個次優(yōu)解，原因是容量在慢慢解，原因是容量在慢慢消耗的過程中，效益值卻沒有消耗的過程中，效益值卻沒有迅速的增加。迅速的增加。背包問題的量度標準選擇背包問題的量度標準選擇16p選效益值和容量之比為量度標準選效益值和容

13、量之比為量度標準n每一次裝入的物品使它占用的每一單位每一次裝入的物品使它占用的每一單位 容量獲得當前最大的單位效益容量獲得當前最大的單位效益n結果是一個最優(yōu)解，因為每一單位容量結果是一個最優(yōu)解，因為每一單位容量 的增加將獲得最大的單位效益值。的增加將獲得最大的單位效益值。(3)按按pi wi比值比值的非增的非增次序把物品放到包里。次序把物品放到包里。(p2 w2, p3 w3, p1 w1) (24 15, 15 10, 25 18)(x1,x2,x3) wixi pixi(1,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5(p1, p2, p3)=(25,

14、24,15)；(w1, w2, w3)=(18,15,10)。背包問題的量度標準選擇背包問題的量度標準選擇17算法算法5.2 背包問題的貪心算法背包問題的貪心算法procedure GREEDY-KNAPSACK(P,W,M,X,n)float P(1:n), W(1:n), X(1:n), M, cu; int i, n;X 0; cu M;for i 1 to n do if (W(i) cu) then exit; endif； X(i) 1; cu cu W(i);repeatif (i n) then X(i) cu W(i);endifend GREEDY-KNAPSACK將解向量

15、將解向量X初始化為初始化為0，cu為背包的剩余重量為背包的剩余重量放入物品放入物品i 的一部分的一部分若物品若物品i的重量大于背包的的重量大于背包的剩余重量，則退出循環(huán)剩余重量，則退出循環(huán)若物品若物品i的重量小于等于背包的剩余的重量小于等于背包的剩余容量，則物品容量，則物品i可放入背包內可放入背包內先將物品按先將物品按pi wi比值的非增次序排序比值的非增次序排序(降序降序)18p如果物品事先按照效益值的非增次序或物品重量的非降如果物品事先按照效益值的非增次序或物品重量的非降次序。那么利用算法次序。那么利用算法5.2即可分別即可分別得到量度標準為最優(yōu)得到量度標準為最優(yōu)（使每次效益增量最大或容量

16、消耗最慢）的解。（使每次效益增量最大或容量消耗最慢）的解。(p1,p2,p3) (25,24,15), (w1,w2,w3) (18,15,10)(p2 w2 , p3 w3 , p1 w1 ) (24 15, 15 10, 25 18)輸入參數輸入參數 P (24,15,25)；W (15, 10,18)；M 20；n 3。 初始：初始：X (0, 0, 0)；cu 20。for 循環(huán)部分循環(huán)部分：(1) 15 cu，then x(1) 1，cu cu w(1) 5； (2) 10 cu，then 跳出循環(huán)；跳出循環(huán)；結尾：結尾：x(2) cu w(2) 0.5。輸入參數輸入參數 X (1,

17、 0.5, 0)。運行過運行過程如下程如下19把這個貪心解把這個貪心解X與任一最優(yōu)解與任一最優(yōu)解Y相比較，相比較，如果這兩個解不同，就去找開始不同的第一個如果這兩個解不同，就去找開始不同的第一個xi，然后設法用貪心解的這個然后設法用貪心解的這個xi去去代換代換最優(yōu)解的那個最優(yōu)解的那個yi ，并，并證明最優(yōu)解在分量代換前后的總效益值無任何變化。證明最優(yōu)解在分量代換前后的總效益值無任何變化。反復進行這種代換，直到新產生的最優(yōu)解與貪心解反復進行這種代換，直到新產生的最優(yōu)解與貪心解完全完全一樣一樣，從而證明了貪心解就是最優(yōu)解。，從而證明了貪心解就是最優(yōu)解。最優(yōu)解證明的基本思想最優(yōu)解證明的基本思想20定

18、理定理5.1p如果如果p1 w1 p2 w2 pn wn，則算法，則算法GREEDY-KNAPSACK對于給定的背包問題實例生成一個對于給定的背包問題實例生成一個最優(yōu)解。最優(yōu)解。證明證明: 設設X (x1, , xn )是算法所生成的解。是算法所生成的解。1. 如果所有的如果所有的xi 等于等于1，顯然這個解就是最優(yōu)解。，顯然這個解就是最優(yōu)解。2. 否則，設否則，設j是使是使xj 1的最小下標，由算法可知：的最小下標，由算法可知： 對于對于 1 i j，xi 1； 對于對于 j i n，xi 0； 對于對于 i j，0 xj1。21 3. 若若X不是最優(yōu)解，則必存在一個最優(yōu)解不是最優(yōu)解，則必存

19、在一個最優(yōu)解 Y (y1, , yn)，使得使得 piyi pixi 。 假定假定 wiyiM，設，設k是使得是使得 yk xk的最小下標，的最小下標， 則可以推出則可以推出yk xk成立。成立。4. 現在，假定把現在，假定把 yk 增加到增加到 xk ，那么必須從，那么必須從(yk 1,yn) 中減去同樣多的量，使得所用的總容量仍為中減去同樣多的量，使得所用的總容量仍為M。這。這導致一個新的解導致一個新的解Z (z1, zn)，其中，其中 zi xi，1 i k，并且并且 wi ( yi zi ) wk ( zk yk) k i n三種可能發(fā)生的情況：三種可能發(fā)生的情況：(1)k j；(2)

20、k j；(3)k j225. 因此，對于因此，對于Z有有 pizi piyi (zk yk)pk (yi zi)pi piyi (zk yk)wk pk wk (yi zi)wipi wi piyi (zk yk)wk (yi zi)wipk wk piyi 1 i n所以所以 pizi piyi 成立成立6. 若若 pizi piyi，則，則Y不可能是最優(yōu)解。不可能是最優(yōu)解。 所以所以 pi zi piyi ， 如果如果Z X，則，則X就是最優(yōu)解；就是最優(yōu)解； 否則否則Z X，則重復上面的討論，每次，則重復上面的討論，每次Y中少一個和中少一個和 X不同的值，最終把不同的值，最終把Y轉換成轉換

21、成X，從而證明了，從而證明了X也是最優(yōu)解，也是最優(yōu)解， 證畢。證畢。元素按元素按pi wi非非增次序排列。增次序排列。1 i nk 1 i n1 i n1 i n1 i nk 1 i nk 1 i n23定理定理5.1證明總結證明總結p分析貪心解的形式分析貪心解的形式p假設最優(yōu)解假設最優(yōu)解p比較貪心解和最優(yōu)解比較貪心解和最優(yōu)解p重新構造最優(yōu)解重新構造最優(yōu)解p證明重新構造的最優(yōu)解與貪心解相同證明重新構造的最優(yōu)解與貪心解相同245.3 帶有限期的作業(yè)排序帶有限期的作業(yè)排序n問題描述問題描述n帶限期的作業(yè)排序算法帶限期的作業(yè)排序算法n定理定理5.2n定理定理5.3n算法算法5.4n算法算法5.525

22、問題描述問題描述p假定只能在一臺機器上處理假定只能在一臺機器上處理n個作業(yè)，個作業(yè)， 每個作業(yè)均每個作業(yè)均可在單位時間內完成；又假定每個作業(yè)可在單位時間內完成；又假定每個作業(yè)i都有一個都有一個截止期限截止期限di 0(di是整數是整數)，當且僅當作業(yè)，當且僅當作業(yè)i在它的期在它的期限截止之前被完成時獲得限截止之前被完成時獲得pi 0的效益。的效益。p該問題的一個可行解是這該問題的一個可行解是這n個作業(yè)的一個子集合個作業(yè)的一個子集合J，J中的每個作業(yè)都能在各自的截止期限之前完成，中的每個作業(yè)都能在各自的截止期限之前完成，可行解的效益值是可行解的效益值是J中這些作業(yè)的效益之和中這些作業(yè)的效益之和

23、pj 。具有最大效益值的可行解就是最優(yōu)解具有最大效益值的可行解就是最優(yōu)解。限制條件限制條件目標函數目標函數26形式化描述形式化描述目標函數：目標函數： 約束條件：作業(yè)約束條件：作業(yè) j 的處理時間的處理時間 tj dj，dj 0，pj 0， 1 j n Jjjp27有有4個作業(yè)個作業(yè)n 4；(p1, p2, p3, p4) (100, 10, 15, 20)；(d1, d2, d3, d4) (2, 1, 2, 1)；可行解可行解J處理順序處理順序效益值效益值 pj （1）1100（2）210（3）315（4）420 （1，3） 1, 3 或或 3, 1 115 （1，2） 2，1 110 （

24、1，4） 4，1 120 （2，3） 2，3 25 （3，4） 4，3 35例例5.228帶限期的作業(yè)排序算法的實現思想帶限期的作業(yè)排序算法的實現思想p為得到最優(yōu)解，貪心策略應制定一個量度標準，為得到最優(yōu)解，貪心策略應制定一個量度標準，使得所選擇的下一個作業(yè)在這種量度下達到最優(yōu)。使得所選擇的下一個作業(yè)在這種量度下達到最優(yōu)。p選擇目標函數選擇目標函數 pj作為量度標準作為量度標準，使下一個要計入，使下一個要計入的作業(yè)是滿足的作業(yè)是滿足J是一個可行解是一個可行解的限制條件下使的限制條件下使 pj得到最大增加的作業(yè)，只需將各作業(yè)按效益得到最大增加的作業(yè)，只需將各作業(yè)按效益pi降序降序排列即可，即：排

25、列即可，即：p1 p2 pn .J中的每個作業(yè)中的每個作業(yè)都能在各自的截都能在各自的截止期限之前完成。止期限之前完成。29算法算法5.3 帶限期的作業(yè)排序算法描述帶限期的作業(yè)排序算法描述procedure GREEDY_JOB(D, J, n)/ 作業(yè)按作業(yè)按p1 p2 pn的次序輸入；它們的期限值的次序輸入；它們的期限值D(i) 1，1 i n，n 1。J是在它們的截止期限前完成是在它們的截止期限前完成的作業(yè)的集合。的作業(yè)的集合。/ J1 for i 2 to n do if (J i的所有作業(yè)都能在它們的截止期限前完成的所有作業(yè)都能在它們的截止期限前完成 ) then J J i endi

26、frepeatend GREEDY_JOB算法中最關鍵的一步算法中最關鍵的一步30兩個問題兩個問題p算法算法5.3所描述的貪心方法是否能提供一個所描述的貪心方法是否能提供一個最優(yōu)解？最優(yōu)解？p對于給定的作業(yè)集合對于給定的作業(yè)集合J，如何確定它是否是，如何確定它是否是可行解？可行解？31定理定理5.2p對于作業(yè)排序問題用算法對于作業(yè)排序問題用算法5.3所描述的貪心方法總是所描述的貪心方法總是得到一個最優(yōu)解。得到一個最優(yōu)解。p證明思路：證明思路：nJ是貪心方法求出的作業(yè)集合，是貪心方法求出的作業(yè)集合，I是一個最優(yōu)解的作業(yè)集合。是一個最優(yōu)解的作業(yè)集合?？梢宰C明可以證明J和和I具有相同的效益值，從而具

27、有相同的效益值，從而J也是最優(yōu)解。也是最優(yōu)解。n證明證明I J。IJaba是使得是使得a J且且a I的的一個最高效益值的作業(yè)一個最高效益值的作業(yè)由貪心方法可知，對于在由貪心方法可知，對于在I中中又不在又不在J中的所有作業(yè)中的所有作業(yè)b，都有，都有pa pb。這是因為，若。這是因為，若pb pa,則則貪心方法會先于貪心方法會先于a考慮考慮b，并把，并把b計入到計入到J中去。中去。32n設設SJ和和SI分別是分別是J和和I的可行調度表。令調度表中相同作的可行調度表。令調度表中相同作業(yè)在相同的時間片執(zhí)行。具體方法如下：業(yè)在相同的時間片執(zhí)行。具體方法如下： SJ: .i.k.SI: i. t t S

28、J: .ki.SI: i. t t SJ: .i.SI: .i.k. t t SJ: .i.SI: .k.i. t t n用用J中作業(yè)中作業(yè)a替換掉替換掉I中同時間片調用的作業(yè)中同時間片調用的作業(yè)b，得到作業(yè)集，得到作業(yè)集合合I I b a的一個可行調度表。顯然，的一個可行調度表。顯然，I的效益值不的效益值不小于小于I的效益值，并且的效益值，并且I比比I少一個與少一個與J不同的作業(yè)。不同的作業(yè)。n重復應用上述轉換，使重復應用上述轉換，使I在不減效益值得情況下轉換成在不減效益值得情況下轉換成J，因此因此J也必定是最優(yōu)解，證畢。也必定是最優(yōu)解，證畢。33確定作業(yè)集合確定作業(yè)集合J是否是可行解是否是

29、可行解p假定假定J中有中有k個作業(yè)，檢驗個作業(yè)，檢驗J的所有可能的排列的所有可能的排列ni1, i2, , ik是是J中作業(yè)的一種排列中作業(yè)的一種排列;n完成作業(yè)完成作業(yè)ij的最早時間是的最早時間是j，1 j n；n若排列中每個作業(yè)的若排列中每個作業(yè)的dij j，則，則 是一個允許的調是一個允許的調度序列，度序列，J是一個可行解；否則，檢驗其他排列是一個可行解；否則，檢驗其他排列形式。形式。檢驗一種特殊的排列：檢驗一種特殊的排列：按期限的非降次序。按期限的非降次序。34一個例子一個例子 (p1, p2 , p3, p4) (100, 10, 15, 20)， (d1, d2, d3, d4)

30、(2, 1, 2, 1) ：d2 d4 d1 d3J 1, 4 處理次序：處理次序：4, 1 , J是一個可行解是一個可行解J 2, 3 處理次序：處理次序：2, 3 , J是一個可行解是一個可行解J 2, 4 處理次序：處理次序： 2, 4 , 但是作業(yè)但是作業(yè)4違反它的期限，違反它的期限，所以所以J不是一個可行解不是一個可行解35定理定理5.3p設設J是是k個作業(yè)的集合，個作業(yè)的集合，i1,i2,ik是是J中作中作業(yè)的一種排列，它使得業(yè)的一種排列，它使得di1 di2dik。J是是一個可行解，當且僅當一個可行解，當且僅當J中的作業(yè)可以按中的作業(yè)可以按照照 的次序而又不違反任何一個期限的情的

31、次序而又不違反任何一個期限的情況來處理。況來處理。36證明思想證明思想p如果如果J中的作業(yè)可以按照中的作業(yè)可以按照 的次序而又不違反任的次序而又不違反任何一個期限，則何一個期限，則J是一個可行解。是一個可行解。p若若J是可行解，則必存在是可行解，則必存在 r1,r2,rk，使得，使得drj j， 1 j k。n假設假設 ，令，令a是使得是使得ra ia的最小下標。的最小下標。n設設rb ia，顯然，顯然b a。n在在 中交換中交換ra與與rb的位置，產生新的可行排列的位置，產生新的可行排列 ”。p連續(xù)使用這種方法，就將連續(xù)使用這種方法，就將 轉換成轉換成 且不違反且不違反任何一個期限。任何一個

32、期限。 : ra. : ia .rb. ” : rb. : ia .ra.ra延后執(zhí)行延后執(zhí)行是否可行？是否可行？drb dia dra37p首先將作業(yè)按首先將作業(yè)按p1 p2 pn排序，將作業(yè)排序，將作業(yè)1存入數組存入數組J中，然后處理作業(yè)中，然后處理作業(yè)2到作業(yè)到作業(yè)n。p假設已處理了假設已處理了i 1個作業(yè)，其中有個作業(yè)，其中有k個作業(yè)已存入個作業(yè)已存入J(1), J(2),J(k)中，且中，且DJ(1) DJ(2) DJ(k)。p現在處理作業(yè)現在處理作業(yè)i，判斷，判斷J i是否可行，即，是否能找到是否可行，即，是否能找到一個適當的位置一個適當的位置r，滿足如下條件：，滿足如下條件：nD

33、l l， r 1 l k；nDJ(r) Di；nDi r；p若找到，則進行如下處理：若找到，則進行如下處理：n位置位置r 1k共共k r個作業(yè)依次后移一個位置，即延遲一個單位個作業(yè)依次后移一個位置，即延遲一個單位時間再處理；時間再處理；n作業(yè)作業(yè)i插入到插入到r 1位置，即，在位置，即，在r時間片處理；時間片處理；類似于直接插入類似于直接插入法對期限值進行法對期限值進行非降次序排列。非降次序排列。根據定理根據定理5.3，帶有限期的作業(yè)排序問題可如下處理：帶有限期的作業(yè)排序問題可如下處理：38J0 J1 J2 J3 J4 J50312J0 J1 J2 J3 J4 J501012345p20151

34、051d0231442實例：實例：n 5，(p1, p2, p3, p4, p5) (10, 1, 15, 20, 5) (d1, d2, d3, d4, d5) ( 1, 4, 3, 2, 4)J0 J1 J2 J3 J4 J50122134Dl l, r 1 l k；DJ(r) Di；Di r；39procedure JS(D, J, n, k) integer D(0:n), J(0:n), i, k, n, r; D(0) J(0) 0; k1; J(1) 1; for i2 to n do r k; while ( D(J(r) D(i) and D(J(r) r ) do rr 1

35、 repeat if ( D(J(r) D(i) and D(i) r ) then for lk to r 1 by 1 do J(l 1)J(l); repeat J(r 1) i ; kk 1； endif repeatend JS從從D(J(k)到到 D(J(1)依依次與次與D(i)比較來尋找比較來尋找插入位置插入位置r的過程的過程 滿足條件表滿足條件表示找到插入示找到插入位置位置r實現作業(yè)實現作業(yè)r 1到到作業(yè)作業(yè)k依次往后依次往后移動一個位置移動一個位置 將作業(yè)將作業(yè)i插入到插入到r 1位置位置算法算法5.4 帶有限期的作業(yè)排序的貪心算法帶有限期的作業(yè)排序的貪心算法40D(0) J

36、(0) 0; k 1; J(1) 1; for循環(huán)循環(huán)(i 2時時) r k 1; while (D(J(r) D(i)andD(J(r) r) 條件不滿足，不執(zhí)行循環(huán)條件不滿足，不執(zhí)行循環(huán) if ( D(J(r) D(i) and D(i) r ) then for i 1 to r 1 2 by 1 do 不執(zhí)行循環(huán)不執(zhí)行循環(huán) J(2) i 2 ; k k 1 2; J(0) J(1) J(2) J(3) J(4) J(5)01012345p20151051d0231442實例：實例：n 5, (p1, p2, p3, p4, p5) (10, 1, 15, 20, 5) (d1, d2,

37、 d3, d4, d5) ( 1, 4, 3, 2, 4)41k 2; for循環(huán)循環(huán)(i 3時時) r k 2; while (DJr Di and DJr r) 執(zhí)行兩次循環(huán)后執(zhí)行兩次循環(huán)后 r 0 if ( DJr Di and Di r ) then for i 2 to r 1 1 by 1 do 執(zhí)行執(zhí)行2次次 J3 J2; J2 J1; J1 i 3 ; k k 1 3; J0 J1 J2 J3 J4 J5012213k 3; for循環(huán)循環(huán)(i 4時時) r k 3; while (DJr Di and DJr r) 條件不滿足，不執(zhí)行循環(huán)條件不滿足，不執(zhí)行循環(huán) if ( DJ

38、r Di and Di r ) then for i 3 to r 1 4 by 1 do 不執(zhí)行循環(huán)不執(zhí)行循環(huán) J4 i 4 ; k k 1 4; 4012345p20151051d02314442k 4; for循環(huán)循環(huán)( i 5時時) r k 4; while (DJr DiandDJr r) 條件不滿足，不執(zhí)行循環(huán)條件不滿足，不執(zhí)行循環(huán) if ( DJr Di and Di r )條件不滿足條件不滿足作業(yè)作業(yè)5不能插入不能插入 J0 J1 J2 J3 J4 J503124012345p20151051d02314443算法算法5.4的時間復雜度的時間復雜度p算法算法JS有兩個賴以測量其

39、時間復雜度的參數：有兩個賴以測量其時間復雜度的參數：作作業(yè)數業(yè)數 n 和包含在解和包含在解J中的作業(yè)數中的作業(yè)數 s p內層的內層的while循環(huán)至多循環(huán)循環(huán)至多循環(huán)k次，插入作業(yè)次，插入作業(yè) i 要執(zhí)行要執(zhí)行時間為時間為 (k r)p外層外層for循環(huán)共執(zhí)行循環(huán)共執(zhí)行(n 1)次次p如果如果s是是k的終值，即的終值，即s是最后所得解的作業(yè)數，則是最后所得解的作業(yè)數，則JS算法所需要的總時間為算法所需要的總時間為 (sn)p由于由于s n，所以，所以JS算法的時間復雜度為算法的時間復雜度為 (n2)44一種更快的作業(yè)排序算法一種更快的作業(yè)排序算法p算法思想算法思想n對作業(yè)對作業(yè)i分配時間時，分

40、給它一個時間片，在這個時間片分配時間時，分給它一個時間片，在這個時間片里作業(yè)里作業(yè)i能完成。時間片是一個時間范圍，在考慮已經分能完成。時間片是一個時間范圍，在考慮已經分配的時間片的基礎上，時間上界應盡可能的取大配的時間片的基礎上，時間上界應盡可能的取大(可能的可能的話盡量將作業(yè)向后排話盡量將作業(yè)向后排)。p算法的非形式化描述算法的非形式化描述n如果如果J是作業(yè)的可行子集，可使用下述規(guī)則來確定是作業(yè)的可行子集，可使用下述規(guī)則來確定J中每個中每個作業(yè)的處理時間：若還沒給作業(yè)作業(yè)的處理時間：若還沒給作業(yè)i分配處理時間，則分給分配處理時間，則分給它時間片它時間片 1, ，其中其中 應盡量取大，且該時間

41、片是空應盡量取大，且該時間片是空的。若正在被考慮的作業(yè)的。若正在被考慮的作業(yè)i不存在這樣的不存在這樣的 ，則這個作業(yè)就則這個作業(yè)就不能計入不能計入J中。中?？梢园芽梢园袹S的計算時間由的計算時間由 (n2)降低到數量級接近于于降低到數量級接近于于 (n)。45i12345pi20151051di22133可行解可行解J已分配的時間片已分配的時間片考慮的作業(yè)考慮的作業(yè)分配動作分配動作無無1分配分配1, 211, 22分配分配0, 11, 20, 1 1, 23舍棄舍棄1, 20, 1 1, 24分配分配2, 31, 2, 40, 1 1, 2 2, 35舍棄舍棄如何得到如何得到 ？快速作業(yè)排序實

42、例快速作業(yè)排序實例461.存在存在n個作業(yè)，每個作業(yè)花費一個單位時間，因此只需考慮個作業(yè)，每個作業(yè)花費一個單位時間，因此只需考慮時間片時間片i 1,i，1 i b，b minn, maxdi 例如：例如：10個作業(yè)，作業(yè)的截止期中最大值是個作業(yè)，作業(yè)的截止期中最大值是5，只需考慮時間段，只需考慮時間段0,5 5個作業(yè)，作業(yè)的截止期中最大值是個作業(yè)，作業(yè)的截止期中最大值是10，同樣只需考慮時間段，同樣只需考慮時間段0,52.對于任一期限對于任一期限i，設，設ni是滿足是滿足ni i且且ni 1,ni為空的最大整數為空的最大整數 3.引進一個虛構的期限值引進一個虛構的期限值0和時間片和時間片 1,

43、0 若期限值若期限值i j，但，但ni nj，設，設i j表明時間表明時間i 1, j是滿的，所以期限值為是滿的，所以期限值為i 1, i 2, , j的作業(yè)都有可能分到的作業(yè)都有可能分到ni 1, ni時間片時間片4.對于每個期限值對于每個期限值i，用，用F(i)表示當前最接近的空時間片，即表示當前最接近的空時間片，即 F(i) ni . 開始時，時間片都為空，開始時，時間片都為空，F(i) i.思想：將期限值表示成集合，使得確定思想：將期限值表示成集合，使得確定 的時間減小的時間減小算法算法5.5設計思想設計思想476.期限值按可以分配到的時間片被分成不同集合，期限值按可以分配到的時間片被

44、分成不同集合，初始有初始有b 1個集合。個集合。7.使用集合的樹表示法，把每個集合表示成一棵樹，使用集合的樹表示法，把每個集合表示成一棵樹，根結點就認為是這個集合。根結點就認為是這個集合。P(i)把期限值把期限值i鏈接到它鏈接到它的集合樹。開始時的集合樹。開始時P(i) 1，0 i b.8.判斷作業(yè)判斷作業(yè)i的可用空時間片，即找的可用空時間片，即找minn,di的根的根j，若若F(j) 0，說明有時間片可以分配，則，說明有時間片可以分配，則 F(j)是最接是最接近的時間片。近的時間片。9.標識標識F(j)被占用：以被占用：以j為根的集合樹與包含期限為根的集合樹與包含期限F(j) 1的集合樹合并

45、，的集合樹合并，F(j)更新。更新。算法算法5.5設計思想設計思想48pF(i)：期限：期限i能分配到的時間片，初始化為能分配到的時間片，初始化為ipP(i)： 期限期限i的父結點，初始化為的父結點，初始化為 1p對于當前考慮的作業(yè)對于當前考慮的作業(yè)i 作業(yè)作業(yè)i的期限的期限D(i)所在的集合所在的集合 FIND(D(i)j j是否已被分配是否已被分配 F(j)是否為是否為0 若若F(j)不為不為0，則，則給作業(yè)給作業(yè)i分配時間片分配時間片F(j)并并做標記做標記集合的變化集合的變化：j所在的集合和前面的集合所在的集合和前面的集合l合并合并線性表的變化線性表的變化： 對對F(j)重新賦值為重新

46、賦值為F(l)的值的值算法算法5.5設計思想設計思想49p初始初始np1 p2 pnnb minn,maxdjnF(i) inP(i) 1p依次檢驗每個作業(yè)依次檢驗每個作業(yè)wn尋找尋找D(w)所在樹的根節(jié)點所在樹的根節(jié)點jn如果如果F(j) 0， F(j)時間片可以分配給作業(yè)時間片可以分配給作業(yè)w ，因此，將，因此，將w并入到解集合并入到解集合J中，中，n尋找尋找F(j) 1所在樹的根節(jié)點所在樹的根節(jié)點l，將，將l和和j所在的兩個樹合并所在的兩個樹合并到一起。到一起。nF(j) F(l)算法算法5.5設計思想設計思想jFIND(min(n, D(w)kk 1;J(k)w;lFIND(F(j)

47、1);call UNION(l,j);50Procedure FJS(D,n,b,k.J)/作業(yè)已按作業(yè)已按p1 p2 pn被排序，被排序，b minn,maxD(i)./找最優(yōu)解找最優(yōu)解J=J(1),J(k) integer b,D(0:n),J(0:n),F(0:b),P(0:b)for i 0 TO b DO F(i)i ; P(i) 1 ;repeatk0for i1 TO n DO jFIND(min(n,D(i) ; if F(j) 0 then kk 1; J(k) i ; lFIND(F(j) 1) UNION(l, j); F(j)F(l) endifrepeatend FJ

48、S 作業(yè)作業(yè)i的期限值所的期限值所在的集合的根在的集合的根可以給作業(yè)可以給作業(yè)i分配時間片分配時間片標識標識F(j)被占用被占用算法算法5.5 作業(yè)排序的一個更快算法作業(yè)排序的一個更快算法51考慮考慮作業(yè)作業(yè)樹樹J無無 0 1 2 3 4 5 6 7-10-11-12-13-14-15-16-170 1 2 3 3 5 6 7-10-11-12-2334-15-16-1710 1 1 3 3 5 6 7-10-2112-2334-15-16-171,2F(0)(1) (2) (3) (4) (5) (6) (7)例：設例：設n=7，(p1, ,p7) (35,30,25,20,15,10,5)

49、 (d1,d7) (4,2,4,3,4,8,3) 1252考慮考慮作業(yè)作業(yè)樹樹J0 1 1 1 3 5 6 7-10-4112-15-16-1713341,2,3 0 0 1 1 3 5 6 710-5112-15-16-1713341,2,3,4F(0)(1) (2) (3) (4) (5) (6) (7)(p1, ,p7) (35,30,25,20,15,10,5) (d1,d7) (4,2,4,3,4,8,3)3453考慮考慮作業(yè)作業(yè)樹樹J10-5112-15-16-1713140 0 1 1 3 5 6 71,2,3,40 0 1 1 3 5 6 610-5112-15-2667133

50、41,2,3,4,60 0 1 1 3 5 6 6 同上同上F(0)(1) (2) (3) (4) (5) (6) (7)最優(yōu)解最優(yōu)解J 1,2,3,4,6，處理次序，處理次序4,2,3,1,6，效益值，效益值120(舍棄舍棄)567(舍棄舍棄)(p1, ,p7) (35,30,25,20,15,10,5) (d1,d7) (4,2,4,3,4,8,3)545.4 最優(yōu)歸并模式最優(yōu)歸并模式將兩個分別包含將兩個分別包含n個和個和m個記錄的個記錄的已排序已排序文件文件歸并歸并成成一個包含一個包含(n m)個記錄的排序文件個記錄的排序文件, 時間為時間為 (n m)1460357901345679文

51、件文件1：n 3文件文件2：m 5若待歸并的文件數大于若待歸并的文件數大于2，如何處理呢？，如何處理呢？55例例: 將將4個文件個文件X1,X2,X3,X4進行歸并進行歸并, 有不同的歸并方式：有不同的歸并方式：X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y35.4 最優(yōu)歸并模式最優(yōu)歸并模式n個文件歸并個文件歸并, 有多種歸并方式，需要的時間也不同。有多種歸并方式，需要的時間也不同。56歸并的計算時間歸并的計算時間,即記錄比較和移動的時間。即記錄比較和移動的時間。問題問題: 如何確定一個把如何確定一個把n個個已排序已排序文件歸并在一起的最文件歸并在一起的最優(yōu)方法，即需要時間最少的方法。

52、優(yōu)方法，即需要時間最少的方法。n 3，長度分別為，長度分別為30,20,10Y1Y35060記錄移動的總次數記錄移動的總次數: 50 60 110X1X2X330 20 10Y1Y2X130X2X3 20 103060記錄移動的總次數記錄移動的總次數: 30 60 90最優(yōu)最優(yōu)5.4 最優(yōu)歸并模式最優(yōu)歸并模式57量度標準：量度標準：每一步都歸并尺寸比較小的兩個文件每一步都歸并尺寸比較小的兩個文件例例: 有五個文件長度分別是有五個文件長度分別是(F1,F5) (20, 30,10, 5, 30)5F410F315Z120F130F230F560Z335Z295Z4這種模式稱這種模式稱二路歸并模式

53、二路歸并模式 用用二元歸并樹二元歸并樹來表示來表示葉結點稱葉結點稱外部結點外部結點表示已知的文件表示已知的文件內部結點內部結點, 每個內部結點每個內部結點有兩個兒子有兩個兒子, 表示它是由表示它是由兩個文件歸并而得到的兩個文件歸并而得到的5.4 最優(yōu)歸并模式最優(yōu)歸并模式585F410F315Z120F130F230F560Z335Z295Z4帶權外部路徑長度帶權外部路徑長度 如果如果di表示從根到代表文件表示從根到代表文件Fi的外部結點的距離，的外部結點的距離， qi表示文件表示文件Fi的長度的長度(即記錄數即記錄數)，則這棵二元歸并樹，則這棵二元歸并樹 的記錄移動總量是：的記錄移動總量是：

54、diqi ( i 1,2,n) 一個最優(yōu)二路歸并模式一個最優(yōu)二路歸并模式 與一棵具有最小外部路徑與一棵具有最小外部路徑 的二元樹相對應的二元樹相對應計算實例中的記錄移動總量計算實例中的記錄移動總量 diqi 5 3 10 3 20 2 30 2 30 2 2055.4 最優(yōu)歸并模式最優(yōu)歸并模式59生成二元歸并樹算法生成二元歸并樹算法 算法把算法把n個樹的表個樹的表L作為輸入作為輸入, 樹中的每一個結點有樹中的每一個結點有三個信息段三個信息段( LCHILD,RCHILD,WEIGHT ) 起初起初L中的每一棵樹正好是一個結點中的每一棵樹正好是一個結點, 即外部結點即外部結點, 結點的結點的LC

55、HILD和和RCHILD信息段都為信息段都為0, 而而WEIGHT信息段的值就是已知文件的長度。信息段的值就是已知文件的長度。 算法運行時算法運行時, 對于對于L中的任何一棵具有根結點中的任何一棵具有根結點T的樹的樹, WEIGHT(T)表示要歸并的文件的長度。表示要歸并的文件的長度。 WEIGHT(T) 樹樹T中外部結點的長度和中外部結點的長度和5.4 最優(yōu)歸并模式最優(yōu)歸并模式60procedure TREE(L, n)for I 1 to n 1 do call GETNODE(T); LCHILD(T)LEAST(L); RCHILD(T)LEAST(L); WEIGHT(T)WEIGH

56、T(LCHILD(T) WEIGHT(RCHILD(T) call INSERT(L,T);repeatreturn (LEAST(L);end TREE構造一個新結點構造一個新結點 作作為當前樹的根結點為當前樹的根結點找出找出L中一棵中一棵WEIGHT最小的樹，把它作為新最小的樹，把它作為新結點的左子樹，然后在結點的左子樹，然后在L中將這棵樹刪除中將這棵樹刪除把根為把根為T的樹插的樹插入到表入到表L中中新結點的新結點的WEIGHT信息信息段的值等于左、右子樹段的值等于左、右子樹的的WEIGHT之和之和最后留在表最后留在表L中的樹就是歸并中的樹就是歸并樹，將它作為結果返回樹，將它作為結果返回5

57、.4 最優(yōu)歸并模式最優(yōu)歸并模式61例例: 有有6個文件個文件, 長度分別為長度分別為: 2 , 3 , 5 , 7 , 9 , 13, 算法算法TREE如何工作？如何工作？23初始初始, 表表L中有中有6棵樹棵樹,每棵樹只有一個結點每棵樹只有一個結點,分別代表分別代表6個文件個文件i 1, 先產生一個新結點先產生一個新結點(內結點內結點), 從從L的的6棵樹中找出棵樹中找出WEIGHT值值最小的樹最小的樹,作為新結點的左子樹作為新結點的左子樹, 再從剩余再從剩余5棵樹中找出棵樹中找出WEIGHT最小的樹最小的樹,作為新結點的右子樹作為新結點的右子樹, 新結點的新結點的WEIGHT的值等于左、的

58、值等于左、右子樹右子樹WEIGHT值之和值之和, 表表L中還有中還有5棵樹棵樹2351379表表L:i 1，表，表L：5137955.4 最優(yōu)歸并模式最優(yōu)歸并模式62i 2，先產生一個新結點，從，先產生一個新結點，從L的棵樹中找出的棵樹中找出WEIGHT值為值為5的的樹，作為新結點的左子樹，再在剩余樹，作為新結點的左子樹，再在剩余4棵樹找出棵樹找出WEIGHT值為值為5的樹，作為新結點的右子樹，新結點的的樹，作為新結點的右子樹，新結點的WEIGHT的值等于左、的值等于左、右子樹右子樹WEIGHT值之和，表值之和，表L中還有中還有4棵樹棵樹235i 2，表，表L：51379i 3，先產生一個新結

59、點，從，先產生一個新結點，從L的棵樹中找出的棵樹中找出WEIGHT值為值為7的的樹，作為新結點的左子樹，再在剩余樹，作為新結點的左子樹，再在剩余4棵樹找出棵樹找出WEIGHT值為值為9的樹，作為新結點的右子樹，新結點的的樹，作為新結點的右子樹，新結點的WEIGHT的值等于左、的值等于左、右子樹右子樹WEIGHT值之和，表值之和，表L中還有中還有3棵樹棵樹102355101379165.4 最優(yōu)歸并模式最優(yōu)歸并模式i 3，表，表L：632355101379167916232355101323395.4 最優(yōu)歸并模式最優(yōu)歸并模式i 4，表，表L：i 5，表，表L：64二元歸并樹算法的計算時間二元歸

60、并樹算法的計算時間 主循環(huán)執(zhí)行主循環(huán)執(zhí)行n 1次次 如果如果L中中WEIGHT的值按升序排列的值按升序排列, 則則LEAST(L)只需要只需要 (1)的時間的時間 INSERT(L,T)在在 (n)時間內被執(zhí)行時間內被執(zhí)行 因此因此二元歸并樹二元歸并樹算法的計算是總量為算法的計算是總量為: (n2) 若若L表示成一個表示成一個min-堆的情況，堆的情況， INSERT(L,T) 和和LEAST(L) 可在可在log(n)時間內完成，算法的時間為時間內完成，算法的時間為 (nlogn)v定理定理3.4: 若若L最初包含最初包含n 1個單各結點的樹，這些個單各結點的樹，這些樹有樹有WEIGHT值為