2015算法第五章貪心方法

1、第5章 貪心方法吉林大學(xué)計(jì)算機(jī)學(xué)院谷主要內(nèi)容p 5.1 一般方法p 5.2 背包問題p 5.3 帶有限期的作業(yè)排序p 5.4 最優(yōu)歸并模式p 5.5 最小生成樹(略)p 5.6 單源點(diǎn)最短路徑(略)5.1 一般方法p 方法適用的問題特點(diǎn)p 方法的基礎(chǔ)知識(shí)p 方法的求解步驟及p 方法的抽象化p 方法的缺點(diǎn)和優(yōu)點(diǎn)問題3一個(gè)現(xiàn)實(shí)世界里的例子p 如果有一個(gè)機(jī)會(huì)可以幫助你夢(mèng)想成真，那么你希望哪兩個(gè)夢(mèng)想成真：ü 1 到埃及看金字塔；ü 2 參觀布達(dá)拉宮；ü 3 游覽意大利時(shí)尚之都；ü 4 觀賞西班牙斗牛表演。1、21、32、31、42、43、44貪心方法適用的問題特

2、點(diǎn)p 有這樣一類問題：它有n個(gè)輸入，而它的是這n個(gè)輸入的某個(gè)子集，這些子集必須滿足某些事先給定的條件。約束條件兩個(gè)活動(dòng)可行解1、21、32、31、42、43、4目標(biāo)函數(shù)最優(yōu)解個(gè)人喜好5？基本概念：約束條件、可行解、目標(biāo)函數(shù)、最優(yōu)解問題有n個(gè)輸入，它的是這n個(gè)輸入的某個(gè)子集，這個(gè)子集必須滿足某些事先給定的條件即約束條件，滿足約束條件的子集稱為該問題的可行解。一般來(lái)說(shuō)可行解不是唯一的，為衡量可行解的優(yōu)劣，以函數(shù)的形式給出一定的標(biāo)準(zhǔn)，這些函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取極值(極大或極小)的可行優(yōu)解。稱為最一類問題有n個(gè)輸入:最優(yōu)解B1滿足一定的約束條件該可行解可使目標(biāo)函數(shù)取極值B 是該問題的1一個(gè)可行

3、解6該問題有k個(gè)可行解Bk(1)Bk(2)Bk(mk)B2(1)B2(2)B2(m2)B1(1)B1(2)B1(m1)A(1)A(2)A(n-1)A(n)基礎(chǔ)知識(shí)p 貪心方法是指在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。p 貪心方法的思想可以追溯到1823年J.C.Warnsdorff 解決馬踏棋盤問題時(shí)給出的一個(gè)著名的算法。p 貪心方法應(yīng)用的典型問題有背包問題、帶有期限的作業(yè)排序、最小生成樹、單源點(diǎn)最短路徑等問題。7貪心方法的求解步驟p 貪心方法是根據(jù)具體的問題：ü 選取一種量度標(biāo)準(zhǔn)；ü 按此標(biāo)準(zhǔn)對(duì)n個(gè)輸入進(jìn)行排序；ü 按該順序一次輸入一個(gè)量；ü

4、 如果這個(gè)輸入量和當(dāng)前該量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加入到這個(gè)部分。p 這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法就是貪心方法。8貪心方法設(shè)計(jì)求解的問題¼¼量度標(biāo)準(zhǔn)k量度標(biāo)準(zhǔn)1量度標(biāo)準(zhǔn)2次優(yōu)解最優(yōu)解次優(yōu)解p 貪心方法設(shè)計(jì)求解的問題是選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)。p 值得一提的是，把目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所得到的不一定是問題的最優(yōu)解。9Ak(1)¼Ak(n)A2(1)¼A2(n)A1(1)¼A1(n)A(1)A(2)A(n)算法5.1 貪心方法的抽象化 按某種最優(yōu)量度標(biāo)準(zhǔn)從A中選擇一個(gè)輸入，把它賦值給x

5、，并從A中消去它。Procedure GREEDY(A,n)solution¬Æx是否可以包含在解向量中return (solution)將x與解向量結(jié)合并修改目標(biāo)函數(shù)End GREEDY10for i¬1 to n doif FEASIBLE(solution, x)thensolution¬UNION(solution, x) endifrepeatx¬SELECT(A)方法的缺點(diǎn)和優(yōu)點(diǎn)p 缺點(diǎn)：ü 不是對(duì)所有問題都能得到整體最優(yōu)解。ü 需要證明后才能真正運(yùn)用到題目的算法中。p 優(yōu)點(diǎn)：ü 一旦經(jīng)過證明成立后，它

6、就是一種高效的算法。ü 策略的構(gòu)造簡(jiǎn)單易行。ü 對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。115.2背包問題p 問題描述p 背包問題實(shí)例p 背包問題的貪心算法p 定理5.112問題描述n 已知有n種物品和一個(gè)可容納M重量的背包，每種物品i(1£i£n)的重量為wi，假定將物品i的某一部分xi 放入背包就會(huì)得到pixi的效益(0£xi£1,pi>0) ，采用怎樣的裝包方使裝入背包物品的總效益為最大？n 問題的形式化描述：13極大化å pixi0£xi£1, pi >0約

7、束條件 å wixi £Mwi >0, 1£i £n背包問題實(shí)例考慮下列情況下的背包問題：有3個(gè)物品n=3，背包能容納的最大重量M=20，物品的價(jià)值和重量： (p1, p2, p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)效益值的次序其中的4個(gè)可行解是：物pi/wi比值的14次序品重量的非降次序(x1, x2, x3)S wi xiS pixi(1, 2/15, 0)2028.2(1, 0, 1/5)2028(0, 2/3, 1)2031(0, 1, 1/2)2031.5背包問題的量度標(biāo)準(zhǔn)選擇åwixi20202

8、0åpixi28.23131.5(x1,x2,x3)(1,2/15,0)(0,2/3,1)(0,1,1/2)(p1, p2, p3)=(25,24,15)；(w1, w2, w3)=(18,15,10)。即以目標(biāo)函數(shù)為量度標(biāo)準(zhǔn)p(1)按效益值的次該標(biāo)準(zhǔn)使得背包每裝入一件物品就獲得最大可能的效益值增量。ü序把物品放到包里。結(jié)果是一個(gè)次優(yōu)解， 過快。是背包容量消耗ü以容量為量度標(biāo)準(zhǔn)n 該標(biāo)準(zhǔn)使得背包每裝入一件物品就獲得最小可能的容量增量。p(2)按物品重量的非降次序把物品放到包里。n 結(jié)果仍是一個(gè)次優(yōu)解，是容量在慢慢消耗的過程中，效益值卻沒有迅速的增加15。背包問題的

9、量度標(biāo)準(zhǔn)選擇åwixi202020åpixi28.23131.5(x1,x2,x3)(1,2/15,0)(0,2/3,1)(0,1,1/2)(p1, p2, p3)=(25,24,15)；(w1, w2, w3)=(18,15,10)。(3)按pi /wi比值的次序把物品放到包里。選效益值和容量之比為量度標(biāo)準(zhǔn)ü 每一次裝入的物品使它占用的每一p容量獲得當(dāng)前最大的效益ü 結(jié)果是一個(gè)最優(yōu)解，因?yàn)槊恳蝗萘康脑黾訉@得最大的效益值。16(p2/w2, p3/w3, p1/w1)=(24/15, 15/10, 25/18)算法5.2 背包問題的貪心算法先將物品按p

10、i /wi比值的次序排序(降序)procedure GREEDY-KNAPSACK(P,W,M,X,n)float P(1:n), W(1:n), X(1:n), M, cu;inti, n;將解向量X初始化為0，cu為背包的剩余重量X¬ 0;cu ¬ M;若物品i的重量大于背包的剩余重量，則循環(huán)若物品i的重量小于等于背包的剩余容量，則物品i可放入背包內(nèi)if (i£n) then endifX(i) ¬ cu/W(i);放入物品i 的一部分end GREEDY-KNAPSACK17for i ¬ 1 to n doif (W(i)>cu)

11、 then exit; endif； X(i) ¬ 1;cu ¬ cu-W(i); repeat運(yùn)行過程如下p 如果物品事先按照效益值的次序或物品重量的非降次序。那么利用算法5.2即可分別得到量度標(biāo)準(zhǔn)為最優(yōu)（使每次效益增量最大或容量消耗最慢）的解。18輸入?yún)?shù)P= (24,15,25)；W=(15, 10,18)；M=20；n=3。初始：X=(0, 0, 0)；cu=20。for 循環(huán)部分：(1) 15<cu，then x(1)=1，cu=cu-w(1)=5；(2) 10>cu，then 跳出循環(huán)； 結(jié)尾：x(2)=cu/w(2)=0.5。輸入?yún)?shù)X=(1, 0

12、.5, 0)。(p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10)(p2/w2 , p3/w3 , p1/w1 )=(24/15, 15/10, 25/18)最優(yōu)解證明的基本思想把這個(gè)貪心解X與任一最優(yōu)解Y相比較，如果這兩個(gè)解不同，就去找開始不同的第一個(gè)xi，然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)yi ，并證明最優(yōu)解在分量代換前后的總效益值無(wú)任何變化。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心是最優(yōu)解。19定理5.1p 如果p1/w1 ³ p2/w2 / ¼ ³ pn/wn，則算法GREEDY-K

13、NAPSACK對(duì)于給定的背包問題實(shí)例生成一個(gè)最優(yōu)解。證明: 設(shè)X=(x1, ¼, xn )是算法所生成的解。1. 如果所有的xi 等于1，顯然這個(gè)是最優(yōu)解。2. 否則，設(shè)j是使xj ¹ 1的最小下標(biāo)，由算法可知： 對(duì)于 1£i<j，xi=1；對(duì)于 j<i£n，xi=0； 對(duì)于 i=j，0 £ xj<1。203.若X不是最優(yōu)解，則必存在一個(gè)最優(yōu)解Y= (y1, ¼, yn)，使得å piyi >åpixi 。假定åwiyi=M，設(shè)k是使得 yk ¹ xk的最小下標(biāo)，則可以推

14、出yk<xk成立。三種可能發(fā)生的情況：(1)k<j；(2)k=j；(3)k>j4. 現(xiàn)在，假定把yk 增加到 xk ，那么必須從(yk+1,¼,yn)中減去同樣多的量，使得所用的總?cè)萘咳詾镸。這導(dǎo)致一個(gè)新的解Z=(z1,¼, zn)，其中 zi = xi，1£i£k，并且åwi ( yi - zi )=wk ( zk-yk)k<i£n215.å1£i£n因此，對(duì)于Z有pizi= å piyi +(zk-yk)pk -å(yi - zi)pi1£i

15、63;nk+1£i£n= å piyi +(zk - yk)wk pk /wk - å(yi - zi)wipi/wi1£i£nk+1£i£n³ å piyi +(zk - yk)wk - å(yi - zi)wipk/wk1£i£n=å piyi1£i£nk+1£i£n元素按p /w 非ii所以åpizi ³åpiyi 成立增次序排列。6. 若åpizi>piyi，則Y

16、不可能是最優(yōu)解。所以å pi zi = å piyi ，如果Z=X，則X就是最優(yōu)解；否則Z¹X，則重復(fù)上面的討論，每次Y中少一個(gè)和X不同的值，最終把Y轉(zhuǎn)換成X，從而證明了X也是最優(yōu)解， 證畢。22定理5.1證明總結(jié)p 分析貪心解的形式p 假設(shè)最優(yōu)解p 比較貪心解和最優(yōu)解p 重新構(gòu)造最優(yōu)解p 證明重新構(gòu)造的最優(yōu)解與貪心解相同235.3 帶有限期的作業(yè)排序n 問題描述n 帶限期的作業(yè)排序算法n 定理5.2n 定理5.3n 算法5.4n 算法5.524問題描述上處理n個(gè)作業(yè)， 每個(gè)作p 假定只能在一臺(tái)時(shí)間內(nèi)完成；又假定每個(gè)作業(yè)i都業(yè)均可在有一個(gè)截止期限di>0(d

17、i是整數(shù))，當(dāng)且僅當(dāng)作業(yè)i 在它的期限截止之前被完成時(shí)獲得pi>0的效益。p 該問題的一個(gè)可行解是這n個(gè)作業(yè)的一個(gè)子集合完成，可行解的效益值是J中這些作業(yè)的效益之大效益值的可行是最優(yōu)解限制條件25目標(biāo)函數(shù)和åpj 。具有最J，J中的每個(gè)作業(yè)都能在各自的截止期限之前形式化描述目標(biāo)函數(shù)： å pjjÎJ約束條件：作業(yè)j 的處理時(shí)間 tj£dj，dj >0，pj>0，1£j£n26例5.2有4個(gè)作業(yè)n=4；(p , p , p , p )=1234(100, 10, 15, 20)；(d1, d2, d3, d4)=(2,

18、 1, 2, 1)；27可行解J處理順序效益值 åpj（1）1100（2）210（3）315（4）420（1，3）1, 3 或 3, 1115（1，2）2，1110（1，4）4，1120（2，3）2，325（3，4）4，335帶限期的作業(yè)排序算法的實(shí)現(xiàn)思想p 為得到最優(yōu)解，貪心策略應(yīng)制定一個(gè)量度標(biāo)準(zhǔn)，使得所選擇的下一個(gè)作業(yè)在這種量度下達(dá)到最優(yōu)。p 選擇目標(biāo)函數(shù)å pj作為量度標(biāo)準(zhǔn)，使下一個(gè)要計(jì)入的作業(yè)是滿足J是一個(gè)可行解的限制條件下使åpj得到最大增加的作業(yè)，只需將各作業(yè)J中的每個(gè)作業(yè)按效益pi降序排列即可，即：p都能在各自的截止期限之前完成。28算法5.3 帶限

19、期的作業(yè)排序算法描述procedure GREEDY_JOB(D, J, n)/ 作業(yè)按p1³ p2³ ¼ ³ pn的次序輸入；它們的期限值D(i)³1，1£i£n，n³1。J是在它們的截止期限前完成的作業(yè)的集合。/J¬1for i ¬ 2tondoif (JÈi的業(yè)都能在它們的截止期限前完成)J ¬ J Èithen endifrepeat算法中最關(guān)鍵的一步end GREEDY_JOB29兩個(gè)問題p 算法5.3所描述的貪心方法是否能提供一個(gè)最優(yōu)解？p 對(duì)于給定的作

20、業(yè)集合J，如何確定它是否是可行解？30定理5.2p 對(duì)于作業(yè)排序問題用算法5.3所描述的貪心方法總是得到一個(gè)最優(yōu)解。p 證明思路：ü J是貪心方法求出的作業(yè)集合，I是一個(gè)最優(yōu)解的作業(yè)集合?？梢宰C明J和I具有相同的效益值，從而J也是最優(yōu)解。ü 假定I¹J，則IËJ且JË I 。aJIba是使得aÎJ且aÏI的一個(gè)最高效益值的作業(yè)31由貪心方法可知，對(duì)于在I中又不在J中的業(yè)b， pa³pb。這是因?yàn)?，若pb >pa， 則貪心方先于a考慮b，并把b計(jì)入到J中去。ü 設(shè)SJ和SI分別是J和I的可行調(diào)度表。令

21、調(diào)度表中相同作業(yè)在相同的時(shí)間片執(zhí)行。具體方法如下：t < t SJ: .i.k.SI: i.t < tt < tSJ:i.SI: .i.k.t < tn 用J中作業(yè)a替換掉I中同時(shí)間片調(diào)用的作業(yè)b，得到作業(yè)集合I=I-bÈa的一個(gè)可行調(diào)度表。顯然，I的效益值不小于I的效益值，并且I比I少一個(gè)與J不同的作業(yè)。n 重復(fù)應(yīng)用上述轉(zhuǎn)換，使I在不減效益值的情況下轉(zhuǎn)換成J，因此J也必定是最優(yōu)解，證畢。32SJ: .i.SI: .k.i.SJ: .ki.SI: i.確定作業(yè)集合J是否是可行解p 假定J中有k個(gè)作業(yè)，檢驗(yàn)J的所有可能的排列ü s=i1, i2, &#

22、188;, ik是J中作業(yè)的一種排列;ü 完成作業(yè)ij的最早時(shí)間是j，1£j£n；ü 若排列中每個(gè)作業(yè)的dij ³j，則s是一個(gè)的調(diào)度序列，J是一個(gè)可行解；否則，檢驗(yàn)其他排列形式。檢驗(yàn)一種特殊的排列：按期限的非降次序。33一個(gè)例子(p1, p2 , p3, p4)= (100, 10, 15, 20)，(d1, d2, d3, d4)=(2, 1, 2, 1)s：d2 £ d4 £ d1 £ d3J=1, 4J=2, 3J=2, 4處理次序：4, 1，J是一個(gè)可行解處理次序：2, 3，J是一個(gè)可行解處理次序： 2,

23、 4，但是作業(yè)4它的期限，所以J不是一個(gè)可行解34定理5.3p 設(shè)J是k個(gè)作業(yè)的集合，s=i1,i2,¼,ik是J中作業(yè)的一種排列，它使得di1£di2£¼£dik。J是一個(gè)可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照s的次序而又不來(lái)處理。任何一個(gè)期限的情況35證明思想：p 如果J中的作業(yè)可以按照s的次序而又不任何一個(gè)期限，則J是一個(gè)可行解。p 若J是可行解，則必存在s=r1,r2,¼,rk，使得drj³j， 1£j£k。ü 假設(shè)s¹s，令a是使得ra¹ia的最小下標(biāo)。ü 設(shè)

24、rb=ia，顯然b>a。ü 在s s”。換ra與rb的位置，產(chǎn)生新的可行排列成ra延后執(zhí)行違p 連續(xù)使用這種方法，就 drb=dia£dra是否可行？.反任何一個(gè)期限。s : ra.r.b.s” : rb.r.a.s : ias : ia.36根據(jù)定理5.3，帶有限期的作業(yè)排序問題可如下處理：p 首先將作業(yè)按p1³p2 ³ ¼ ³ pn排序，將作業(yè)1存入數(shù)組J中，然后處理作業(yè)2到作業(yè)n。p 假設(shè)已處理了i-1個(gè)作業(yè)，其中有k個(gè)作業(yè)已存入J(1), J(2),J(k)中，且DJ(1)£DJ(2) £¼

25、£ DJ(k)pp現(xiàn)在處理作業(yè)i，JÈi是否可行，即，是否能找到一個(gè)適當(dāng)?shù)奈恢胷，滿足如下條件：ü Di<DJ(l) AND DJ(l)>l, r+1£l£k類似于直接ü DJ(r)£Di;法對(duì)期限值進(jìn)行非降次序排列。ü Di>r;若找到，則進(jìn)行如下處理：ü 位置r+1¼k共k-r個(gè)作業(yè)依次后移一個(gè)位置，即延遲一個(gè)37時(shí)間再處理；實(shí)例：n=5，(p1, p2, p3, p4, p5)=(10, 1, 15, 20, 5)(d1, d2, d3, d4, d5)=( 1, 4,

26、3, 2, 4)Di<DJ(l) AND DJ(l)>l, r+1£l£kDJ(r)£Di;Di>r;38J0J1J2J3J4J503124J0J1J2J3J4J50 3 1 2J0J1J2J3J4J5012012345p20151051d023144算法5.4 帶有限期的作業(yè)排序的貪心算法procedure JS(D, J, n, k)從D(J(k)到 D(J(1)依次與D(i)比較來(lái)尋找位置r的過程integerD(0:n), J(0:n), i, k, n, r;D(0) ¬J(0) ¬0; k¬1; J(1)

27、 ¬ 1;for i¬2 to n dor ¬ k;滿足條件表示找到位置r作業(yè)r+1到k依次往后一個(gè)位置repeatend JS到r+1位置將作業(yè)i39if ( D(J(r)£D(i) and D(i)>r ) then實(shí)現(xiàn)J(r+1)¬ i ;k¬k+1；作業(yè)endif移動(dòng)for l¬k to r+1 by -1 doJ(l+1)¬J(l);repeatwhile ( D(J(r)>D(i) and D(J(r) ¹r ) dor¬r-1 repeat實(shí)例：n=5,(p1, p2,

28、 p3, p4, p5)=(10, 1, 15, 20, 5)(d1, d2, d3, d4, d5)=( 1, 4, 3, 2, 4)D(0)=J(0)=0; k=1; J(1)=1;for循環(huán)(i =2時(shí))r=k=1;while (D(J(r)D(i)andD(J(r) ¹r) 條件不滿足，不執(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)J(2)=i=2 ;k=k+1=2;40J(0)J(1)J(2)J(3)J(4)J(5)012012345p20151051d023144算

29、法5.4的時(shí)間復(fù)雜度p 算法JS有兩個(gè)賴以測(cè)量其時(shí)間復(fù)雜度的參數(shù)： 作業(yè)數(shù) n 和包含在解J中的作業(yè)數(shù) sp 內(nèi)層的while循環(huán)至多循環(huán)k次， 執(zhí)行時(shí)間為O(k-r)p 外層for循環(huán)共執(zhí)行(n-1)次作業(yè) i 要p 如果s是k的終值，即s是最后所得解的作業(yè)數(shù)， 則JS算法所需要的總時(shí)間為O (sn)p 由于s £n，所以JS算法的時(shí)間復(fù)雜度為O(n2)43一種更快的作業(yè)排序算法p 算法思想ü 對(duì)作業(yè)i分配時(shí)間時(shí)，分給它一個(gè)時(shí)間片，在這個(gè)時(shí)間片里作業(yè)i能完成。時(shí)間片是一個(gè)時(shí)間范圍，在考慮已 經(jīng)分配的時(shí)間片的基礎(chǔ)上，時(shí)間上界應(yīng)盡可能的取大（可能的話盡量將作業(yè)向后排）可以把J

30、S的計(jì)算時(shí)間由O(n2)降低到數(shù)量級(jí)接近于O(n)。p 算法的非形式化描述ü 如果J是作業(yè)的可行子集，可使用下述規(guī)則來(lái)確定J中每個(gè)作業(yè)的處理時(shí)間：若還沒給作業(yè)i分配處理時(shí)間， 則分給它時(shí)間片a-1, a，其中a 應(yīng)盡量取大，且該時(shí)間片是空的。若正在被考慮的作業(yè)i不存在這樣的a，44則這個(gè)作業(yè)就不能計(jì)入中快速作業(yè)排序?qū)嵗?5如何得到a？可行解J已分配的時(shí)間片考慮的作業(yè)分配動(dòng)作Æ無(wú)1分配1, 211, 22分配0, 11, 20, 1 1, 23舍棄1, 20, 1 1, 24分配2, 31, 2, 40, 1 1, 2 2, 35舍棄i12345pi20151051di221

31、332.4.3集合的樹表示和不相交集合的合并表表示，每個(gè)結(jié)點(diǎn)只需設(shè)置PARENT信l息段。l PARENT(i) ：存放著元素i在其父結(jié)點(diǎn)的指針l 根結(jié)點(diǎn)的PARENT信息段的內(nèi)容為零。l 并操作的實(shí)現(xiàn)將兩棵樹合并27109462.4.3集合的樹表示和不相交集合的合并將以i和j為根的兩棵樹合并為一棵樹Procedure U(i, j) integer i, j PARENT(i)¬jendU合并后樹根為j1Procedure F(i) integer i, jj¬i2589710return(j) end F47while PARENT(j)>0 doj¬P

32、ARENT(j)repeat2.4.3集合的樹表示和不相交集合的合并規(guī)則：如果樹i的結(jié)點(diǎn)數(shù)少于樹j的結(jié)點(diǎn)數(shù)，則j為i的父親，反之，i為j的父親。p 樹根i：PARENT(i)不再為0，而是樹i中結(jié)點(diǎn)個(gè)數(shù)的負(fù)數(shù)形式。p482.4.3集合的樹表示和不相交集合的合并Procedure UNION(i, j) integer i, j, x x¬PARENT(i)+PARENT(j) if PARENT(i)>PARENT(j)then PARENT(i) ¬jPARENT(j) ¬xelsePARENT(j) ¬iPARENT(i)¬xendi

33、fend UNION合并后集合中元素個(gè)數(shù)若樹j的結(jié)點(diǎn)個(gè)數(shù)多，以j為根若樹i的結(jié)點(diǎn)個(gè)數(shù)多或兩棵樹結(jié)點(diǎn)個(gè)數(shù)相同，以i為根492.4.3集合的樹表示和不相交集合的合并p 引理2.3設(shè)T是一棵由算法UNION所產(chǎn)生的有n個(gè)結(jié)點(diǎn)的樹。在T中沒有結(jié)點(diǎn)的級(jí)數(shù)會(huì)大于ëlognû+1.p 執(zhí)行一次查找需要的時(shí)間至多是O(logn)p 在查找時(shí)使用壓縮規(guī)則：如果j是由i到其根的路徑上的一個(gè)結(jié)點(diǎn)，則置PARENT(j)¬root(i)502.4.3集合的樹表示和不相交集合的合并procedure FIND(i) integer i, j, k找到結(jié)點(diǎn)i所在樹的樹根jj¬i從結(jié)

34、點(diǎn)i到樹根j的路徑上所有結(jié)點(diǎn)k的return(j) end FINDPARENT(k)為j51while k¹j dot¬PARENT(k) PARENT(k) ¬jk¬trepeatwhile PARENT(j)>0 doj ¬PARENT(j)repeatk¬ik：由i到j(luò)的路徑上經(jīng)過的結(jié)點(diǎn)j：樹根結(jié)點(diǎn)兩個(gè)重要的集合操作UNION(i, j)：將以i和j為根的兩棵樹合并為一棵規(guī)則，如果樹i的結(jié)點(diǎn)數(shù)少于樹j的樹，根據(jù)結(jié)點(diǎn)數(shù)，則j為i的父親，反之，i為j的父親。FIND(i)：找到結(jié)點(diǎn)i所在樹的樹根j，并且將從結(jié)點(diǎn)i到樹根j的路

35、徑上所有結(jié)點(diǎn)k的PARENT(k)都變?yōu)閖，并返回根節(jié)點(diǎn)j .52算法5.5設(shè)計(jì)思想思想：將期限值表示成集合，使得確定a的時(shí)間減小1.存在n個(gè)作業(yè)，每個(gè)作業(yè)花費(fèi)一個(gè)時(shí)間，因此只需考慮時(shí)間片i-1, i，1£i£b，b=minn, maxdi.對(duì)于任一期限i，設(shè)ni是滿足 £i且2.1為空的最大整數(shù)若期限值i¹j，但ni=nj，設(shè)i<j表明時(shí)間i+1,用F(i)表示當(dāng)前最接近的空時(shí)j是滿的，所以期限值為i+1, i+2, ¼, j的作間片都為空，F(xiàn)(i) = i.業(yè)可能分到ni-1, ni時(shí)間片引進(jìn)一個(gè)虛構(gòu)的期限值0和時(shí)間片-1,0，期限值

36、按可以分配到的時(shí)間片被分成不同集合，初始有b+1個(gè)集合.3.4.把每個(gè)集合表示成一棵樹，P(i)把期限值i 開始時(shí)P(i) = -1，0£i£b.作業(yè)i的可用空時(shí)間片，即找minn,di的根j，若F(j)¹0， 說(shuō)明有時(shí)間片可以分配，則F(j)是最接近的時(shí)間片。標(biāo)識(shí)F(j)被占用：以j為根的集合樹與包含期限F(j)-1的集合到它的集合樹。6.7.53樹合并，F(xiàn)(j)更新?？焖僮鳂I(yè)排序?qū)嵗篿：截止期限P(i)：父結(jié)點(diǎn)指針，初值為-1F(i) ：當(dāng)前最大可用時(shí)間片，初值為i例：設(shè)n=7，(p1, ,p7) = (35, 30, 25, 20, 15, 10, 5)(

37、d1,d7) = ( 4,2,4,3,4,8, 3)樹（截至期限的樹）考慮作業(yè)無(wú)JÆ0-11-12-13-14-156-17F(0)(1) (2) (3) (4) (5) (6) (7)-1-1012345675-16-17-10-11-12-13-21101233567435-16-17-10-11-23-21,2201133567143255例：設(shè)n=7，(p1, ,p7)=(35, 30, 25, 20, 15, 10, 5)(d1,d7)=( 4,2,F(0)(1) (2) (3) (4) (5) (6) (7)4,樹3,4,8, 3)考慮作業(yè)J5-16-17-10-11-4

38、3011135671,2,3213141-535-16-17-11,2,3,44001135670121314356例：設(shè)n=7，(p1, ,p7)=(35, 30, 25, 20, 15, 10, 5)(d1,d7)=( 4,2,4,3,4,樹8,3)JF(0)(1) (2) (3) (4) (5) (6) (7)考慮作業(yè)5-16-11-5-5(舍棄)5671,2,3,401125-16-21-56001135661,2,3,4,601113237647(舍棄)1,2,3,4,600113566同上最優(yōu)解J=1,2,3,4,6，處理次序4,2,3,1,6，效益值12057算法5.5設(shè)計(jì)思想p

39、 F(i)：期限i能分配到的時(shí)間片，初始化為ip P(i)： 期限i的父結(jié)點(diǎn)，初始化為-1p 對(duì)于當(dāng)前考慮的作業(yè)w作業(yè)w的期限D(zhuǎn)(w)所在的集合FIND(D(w)®jj是否已被分配F(j)是否為0若F(j)不為0，則給作業(yè)w分配時(shí)間片F(xiàn)(j)并做標(biāo)58記集合的變化：j所在的集合和前面的集合l合并線性表的變化： 對(duì)F(j)重新賦值為F(l)的值算法5.5設(shè)計(jì)思想初始ü p1³ p2 ³ ¼ ³ pnü b=minn,maxdjü F(i) ¬ iü P(i) ¬ - 1依次檢驗(yàn)每個(gè)作業(yè)w

40、pj¬FIND(min(n, D(w)pk¬k+1;J(k)¬w;ü 尋找D(w)所在樹的根節(jié)點(diǎn)jü 如果F(j)¹0， F(j)時(shí)間片可以分配給作業(yè)w ，因此， 將w并入到解集合J中，ü 尋找F(j)-1所在樹的根節(jié)點(diǎn)l，將l和j所在的兩個(gè)樹合并到一起。ü F(j) ¬ F(l)l¬FIND(F(j)-1);call UNION(l,j);59算法5.5 作業(yè)排序的一個(gè)更快算法Procedure FJS(D,n,b,k.J)/作業(yè)已按p1³p2³³pn被排序，b

41、= minn,maxD(i)./找最優(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 DOF(i)¬i ; P(i) ¬ -1 ; repeatk¬0for w¬1 TO n DOj¬FIND(min(n, D(w) ;作業(yè)i的期限值所在集合的根可以給作業(yè)i分配時(shí)間片if F(j)¹0 thenk¬k+1; J(k) ¬w ;l¬FIND(F(j)-1)endif repeat end FJS標(biāo)識(shí)F(j)被占用60U

42、NION(l, j);F(j)¬F(l)5.4最優(yōu)歸并模式將兩個(gè)分別包含n個(gè)和m個(gè)的已排序文件歸并成一個(gè)包含(n+m)個(gè)文件1：n=3的排序文件, 時(shí)間為O(n+m)文件2：m=5Ø 若待歸并的文件數(shù)大于2，如何處理呢？61456795.4最優(yōu)歸并模式例，將4個(gè)文件X1,X2,X3,X4進(jìn)行歸并，有不同的歸并方式：Y3Y3Y2Y2Y1Y1n個(gè)文件歸并，有多種歸并方式，需要的時(shí)間也不同。62X4X3X2X1X4X3X2X15.4最優(yōu)歸并模式歸并的計(jì)算時(shí)間，即比較和移動(dòng)的時(shí)間。問題：如何確定一個(gè)把n個(gè)已排序文件歸并在一起的最優(yōu)方法，即需要時(shí)間最少的方法。n=3，長(zhǎng)度分別為30,

43、20,1060Y3最優(yōu)60Y250Y130Y1302010302010移動(dòng)的總次數(shù)：30+60=90移動(dòng)的總次數(shù)：50+60=11063X3X2X1X3X2X15.4最優(yōu)歸并模式量度標(biāo)準(zhǔn)：每一步都?xì)w并比較小的兩個(gè)文件例：有五個(gè)文件長(zhǎng)度分別是(F1,F5)=(20, 30,10, 5, 30)Z4這種模式稱二路歸并模式，用二元?dú)w并樹來(lái)表示9535Z2內(nèi)部結(jié)點(diǎn)，每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)兒子，表示它是由兩個(gè)文件歸并而得到的Z360Z115葉結(jié)點(diǎn)稱外部結(jié)點(diǎn)表示已知的文件F4F3F1F2F5643030201055.4Ø 帶權(quán)外部路徑長(zhǎng)度最優(yōu)歸并模式如果di表示從根到代表文件Fi的外部結(jié)點(diǎn)的距離，q

44、i表示文件Fi的長(zhǎng)度(即數(shù))，則這棵二元?dú)w并樹移動(dòng)總量是：Sdiqi( i=1,2,¼,n)的計(jì)算實(shí)例中的移動(dòng)總量Z495Sdiqi=5´3+10´3+20´2+30´2+30´2=205Ø 一個(gè)最優(yōu)二路歸并模式與一棵具有最小外部路徑的二元樹相對(duì)應(yīng)Z235Z360Z115F4F3F1F2F53030201055.4最優(yōu)歸并模式Ø 生成二元?dú)w并樹算法§算法把n個(gè)樹的表L作為輸入，的每一個(gè)結(jié)點(diǎn)有三個(gè)信息段( LCHILD,RCHILD,WEIGHT )起初L中的每一棵樹正好是一個(gè)結(jié)點(diǎn)，即外部結(jié)點(diǎn)，§結(jié)點(diǎn)的LCHILD和RCHILD信息0，而WEIGHT信息段的值就是已知文件的長(zhǎng)度。算法運(yùn)行時(shí)，對(duì)于L中的任何一棵具有根結(jié)點(diǎn)T的樹，WEIGHT(T)表示要?dú)w并的文件的長(zhǎng)度。WEIGHT(T)=樹T中外部結(jié)點(diǎn)的長(zhǎng)度和。§665.4最優(yōu)歸并模式構(gòu)造一個(gè)新結(jié)點(diǎn)作procedure TREE(L, n)for i ¬1 to n-1 do為當(dāng)前樹的根結(jié)點(diǎn)找出L中一棵WEIGHT 最小的樹，把它作為新結(jié)點(diǎn)的左子樹，然后在L中將這棵樹刪除callGETNODE(T);LCHILD(T)¬LEA