第四講貪心方法

1、第四講 貪心方法1. 一般方法在現(xiàn)實世界中，有這樣一類問題：它有n個輸入，而它的解就由這n個輸入的某個子集組成，不過這個子集必須滿足某些事先給定的條件。把那些必須滿足的條件稱為約束條件；而把滿足約束條件的子集稱為該問題的可行解。顯然，滿足約束條件的子集可能不止一個，因此，一般來說可行解不是唯一的。為了衡量可行解的優(yōu)劣，事先也給出了一定的標準，這些標準一般以函數(shù)形式給出，這些函數(shù)稱為目標函數(shù)。那些使目標函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。這一類需求取最優(yōu)解的問題，又可根據(jù)描述約束條件和目標函數(shù)的數(shù)學模型的特性或求解問題方法的不同，進一步劃分為線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等問

2、題。盡管各類規(guī)劃問題都有一些相應的求解方法，但其中的某些問題，還可用一種更直接的方法來求解，這種方法就是貪心方法（貪婪法）。貪心方法是一種改進了的分級處理方法。它首先根據(jù)題意，選取一種量度標準。然后按這種量度標準對這n個輸入排序，并按次序每次輸入一個輸入量。如果該輸入和當前已構成在這種量度意義下的部分最優(yōu)解組合在一起不能產生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法稱為貪心方法。要注意的是，對于一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的。但實際上，在貪心處理中，利用量度標準中的大多標準所得到的該量度意義下的最優(yōu)解

3、往往不是問題的最優(yōu)解，而是次優(yōu)解。尤其值得指出的是，把目標函數(shù)作為量度標準所得到的解也不一定是問題的最優(yōu)解。因此，選擇能產生問題最優(yōu)解的最優(yōu)量度標準是使用貪心法設計求解的核心問題。在一般情況下，要選出最優(yōu)量度標準并不是一件容易的事，不過，一旦能選擇出某個問題的最優(yōu)量度標準，那么用貪心方法求解這個問題則特別有效。貪心方法可以用下面的抽象化控制來描述。算法1.1 貪心方法的抽象化控制void Greedy(a，n) /A(1：n)包含n個輸入solution = /將解向量solution初始化為空for(j=1；j=n；+j) x = Select(a)；if Feasible(solution

4、，x) solution=union(solution，x)；/forreturn solution；/ Greedy函數(shù)Select的功能是按某種最優(yōu)量度標準從A(1：n)中選擇一個輸入，把它的值賦給x并從A中消去它。Feasible是一個布爾函數(shù)，它判定x是否可以包含在解向量中。union將x與解向量結合并修改目標函數(shù)。過程Greedy描述了用貪心策略設計算法的主要工作和基本控制路線。一旦給出一個特定的問題，就可將Select，F(xiàn)easible和Union具體化并付諸實現(xiàn)。2. 背包問題本節(jié)介紹使用貪心設計策略來解決更復雜的問題背包問題。背包問題的描述如下：已知有n種物品和一個可容納m重量

5、的背包，每種物品i的重量為wi。假定將物品i的一部分xi放人背包就會得到pixi的效益，0xi1，pi0。采用怎樣的裝包方法才會使裝入背包物品的總效益最大呢？顯然，由于背包容量是m，因此，要求所有選中要裝入背包的物品總重量不超過m。如果這n件物品的總重量不超過m，則把所有物品裝入背包自然獲得最大效益。如果這些物品重量的和大于m，則在這種情況下該如何裝包呢？這是本節(jié)所要解決的問題。根據(jù)以上討論，可將問題形式描述如下：極大化 pixi (4.1)1in約束條件 wixi m (4.2)1in0xi1，pi0，wi0，1in (4.3)其中，(4.1)式是目標函數(shù)，(4.2)和(4.3)是約束條件。

6、滿足約束條件的任一集合(x1，xn)是一個可行解(即能裝下)，使目標函數(shù)取最大值的可行解是最優(yōu)解。例2.1 考慮下面的背包問題。n=3，m=20，(pl，p2，p3)=(25,24,15)，(w1，w2，w3)=(18,15,10)。表2.1 例2.1問題的四個可行解序號(x1，x2，x3)wixi1inpixi1in(1/2，1/3，1/4)16.524.25(1，2/15，0)2028.2(0，2/3，1)2031(0，1，1/2)2031.5在這四個可行解中，第個解的效益值最大。下面將看到，該解是背包問題在這一情況下的最優(yōu)解。為了獲取背包問題的最優(yōu)解，必須要把物品放滿背包。由于可以取物品

7、i的一部分放到背包中去，因此這一要求是可以達到的。如果用貪心策略來求解背包問題，則正如第l節(jié)中所說的一樣，首先要選出最優(yōu)的量度標準。不妨先取目標函數(shù)作為量度標準，即每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標準下的貪心方法就是按效益值的非增次序（由大到小）將物品一件件放到背包中去。如果正在考慮中的物品放不進去，則可只取其一部分來裝滿背包。但這最后一次的放法可能不符合使背包每次獲得最大效益增量的量度標準，此時，可以換成一種能獲得最大增量的物品，將它(或它的一部分)放人背包，從而使最后一次裝包也符合量度標準的要求。例如，假定還剩有兩個單位的空間，而在背包外還有兩種物品，這兩種物品有

8、(pi=4，wi=4)和(pj=3，wj=2)，則使用j就比用i要好些。下面對例2.l的數(shù)據(jù)使用這種選擇策略。物品1有最大的效益值(p1=25)，因此首先將物品1放人背包，這時x1= 1，且獲得25的效益。背包容量中只剩下兩個單位空著。物品2有次大的效益值(P2=24)，但w2=15，在背包中裝不下物品2，使用x2=2/15就正好裝滿背包。不難看出，物品2的2/15效益值=3.2比物品3的2/10效益值=3.0高。所以此種選擇策略得到的解，總效益值是28.2。它是一個次優(yōu)解。由此例可知，按物品效益值的非增次序裝包不能得到最優(yōu)解。為什么上述貪心策略不能獲得最優(yōu)解呢？原因在于背包可用容量消耗過快。

9、由此，很自然地啟發(fā)我們用容量作為量度，讓背包容量盡可能慢地被消耗。這就要求按物品重量的非遞減次序（由小到大）把物品放入背包。例2.1的解就是使用這種貪心策略得到的，它仍是一個次優(yōu)解。這種策略也只能得到次優(yōu)解，其原因在于容量雖然慢慢地被消耗，但效益值沒能迅速地增加。這又啟發(fā)我們應采用在效益值的增長速率和容量的消耗速率之間取得平衡的量度標準。即每一次裝入的物品應使它占用的每一單位容量獲得當前最大的單位效益。這就需使物品的裝入次序按pi/wi比值的非增次序來考慮。在這種策略下的量度標準是：已裝入物品的累計效益值與所用容量之比，且每次裝入的結果要使得累計效益值與所用容量的比值，有最多的增加或最少的減小

10、(第二次和以后的裝入可能使該比值減小)。將此貪心策略應用于例2.l的數(shù)據(jù)，得到解。如果將物體事先按pi/wi的非增次序分好類，則過程Greedy_Knapsack可得到在這一策略下背包問題的解。如果將物品分類的時間不算在內，則此算法所用時間為(n)。算法2.1 背包問題的貪心算法void Greedy_Knapsack(float p，float w，float m，float x，int n) /p(1：n)和w(1：n)分別含有按p(i)/w(i)p(i+1)/w(i+l)排序的 n件物品的/效益值和重量。m是背包的容量大小，而x(1：n)是解向量int i；float cu； /cu是背

11、包的剩余容量for(i=1；i=n；+i) xi = 0； /將解向量初始化為零cu = m； /將背包剩余容量cu設成mfor(i=1；i=n；+i) if(wicu) break；else xi = 1；cu = cu - wi；/forif(in) x(i) = cu/w(i)；return x；/ Greedy_Knapsack值得指出的是，如果把物品事先按效益值的非增次序或重量的非遞減序分好類，再使用算法2.1就可分別得到量度標準為最優(yōu)(使每次效益增量最大或使容量消耗最慢)的解。由背包問題量度選取的研究可知，選取最優(yōu)的量度標準，實質上為用貪心方法求解問題的核心。下面來證明使用第三種策

12、略的貪心算法所得到的解是一個最優(yōu)解。證明的基本思想是：把這貪心解與任一最優(yōu)解相比較，如果這兩個解不同，就去找開始不同的第一個xi，然后設法用貪心解的這個xi去代換最優(yōu)解的那個xi，并證明最優(yōu)解在分量代換前后的總效益無任何變化。反復進行這種代換，直到新產生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解是最優(yōu)解。這種證明最優(yōu)解的方法今后將經常使用，因此請注意掌握它。定理2.1 如果p1/w1p2/w2pn/wn，則算法Greedy_Knapsack對于給定的背包問題實例可生成一個最優(yōu)解。證明：設x=(x1，xn)是Greedy_Knapsack所生成的解。如果所有的xi等于1，顯然這個解就是最優(yōu)解(效

13、益值為pi)。于是，設j是使 xj1的最小下標。由算法可知，對于lij，xi=1；對于jin，xi=0；對于j，0xj1。如果x不是一個最優(yōu)解，則必定存在一個可行解y=(y1，yn)，使得piyipixi。不失一般性，可以假定wiyi=m。設k是使得ykxk的最小下標。顯然，這樣的k必定存在。由上面的假設，可以推得ykxk。這可從三種可能發(fā)生的情況，即kj，k=j或kj分別得證明。 若kj，則xk=1。因ykxk，從而ykxk。 若k=j，由于wixi=m，且對于lij，有xi=yi=1，而對于jin，有 xi=0。若ykxk，顯然有wiyim，與y是可行解矛盾。若yk=xk，與假設ykxk矛

14、盾，故ykxk。 若kj，則wiyim，這是不可能的?，F(xiàn)在，假定把yk增加到xk，那么，必須從(yk+1，yn)中減去同樣多的量，使得所用的總容量仍是m。這導致一個新的解z=(z1，zn)其中，zi=xi，1ik，并且wi(yi-zi)=wk(zk-yk)。kin因此，對于z有pizi = piyi + (zk-yk)wkpk/wk -(yi-zi)wiPi/wi1in 1in kin piyi + (zk-yk)wk - (yi-zi)wi pi/wk1in kin= piyi1in 若pizipiyi，則y不可能是最優(yōu)解；若相等，且z=x，則x就是最優(yōu)解；若zx，則需重復上述討論，或者證明

15、y不是最優(yōu)解，或者把y轉換成x，從而證明了x也是最優(yōu)解。證畢。3. 帶有限期的作業(yè)排序在這一節(jié)將應用貪心設計策略來解決操作系統(tǒng)中單機、無資源約束且每個作業(yè)可在等量的時間內完成的作業(yè)調度問題。即，假定只能在一臺機器上處理n個作業(yè)，每個作業(yè)均可在單位時間內完成；又假定每個作業(yè)i都有一個截止期限di0(它是整數(shù))，當且僅當作業(yè)i在它的期限截止以前被完成時，則獲得pj0的效益。這個問題的一個可行解是:這n個作業(yè)的一個子集合J，J中的每個作業(yè)都能在各自的截止期限之前完成。可行解的效益值是J中作業(yè)的效益之和，即pi(iJ)。具有最大效益值的可行解就是最優(yōu)解。例3.1 n=4，(p1，p2，p3，p4) =

16、 (100，10，15，20)和(d1，d2，d3，d4) = (2，l，2，1)。這個問題的可行解和它們的效益值如表3.1。其中，解是最優(yōu)的，所允許的處理次序是：先處理作業(yè)4，再處理作業(yè)l。于是，在時間0開始處理作業(yè)4，而在時間2完成對作業(yè)1的處理。表3.1 例3.1的可行解與效益值序號可行解處理順序效益值(1)1100(2)210(3)315(4)420(1，2)2，1110(1，3)1，3或3，1115(1，4)4，1120(2，3)2，325(3，4)4，3353.l 帶有限期的作業(yè)排序算法為了擬制出一個最優(yōu)解的算法，應制定如何選擇下一個作業(yè)的量度標準，利用貪心策略，使得所選擇的下一個

17、作業(yè)在這種量度下達到最優(yōu)。不妨首先就把目標函數(shù)pi(iJ)作為量度。使用這一量度，下一個要計入的作業(yè)將是使得，在滿足所產生的J是一個可行解的限制條件下，讓pi(iJ)達到最大增加的作業(yè)。這就要求按Pi的非增次序來考慮這些作業(yè)。利用上例中的數(shù)據(jù)來應用這一準則。開始時，J=，pi = 0，由于作業(yè)1有最大效益且J=1是一個可行解，于是把作業(yè)1計入J。iJ下一步考慮作業(yè)4，J=1，4也是可行解。然后考慮作業(yè)3，因為1，3，4不是可行解，故作業(yè) 3被舍棄。最后考慮作業(yè)2，由于1，2，4也不可行，作業(yè)2被舍棄。最終所留下的是效益值為120的解J=1，4。它是這個問題的最優(yōu)解?，F(xiàn)在，對上面所敘述的貪心方法

18、，以算法3.1的形式給出其粗略的描述。算法3.1 作業(yè)排序算法的概略描述void GreedyJob(int d，int j，int n) /作業(yè)按p1，pn的次序輸入，它們的期限值di1，1in，n1。/J是在它們的截止期限前完成的作業(yè)的集合1 J = 1；2 for(i=2；i=n；+i) 3 if(J i的所有作業(yè)都能在它們的截止期限前完成) J = J i；4 if5 6 / GreedyJob定理3.1 算法3.1所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。證明：設(pi，di)，1in，是作業(yè)排序問題的任一實例，J是由貪心方法所選擇的作業(yè)的集合，I是一個最優(yōu)解的作業(yè)集合。可

19、證明J和 I具有相同的效益值，從而J也是最優(yōu)的。假定IJ，因為若I=J，則J即為最優(yōu)解。容易看出，如果I是J子集，則I就不可能是最優(yōu)的。由貪心法的工作方式也排斥了J是I的子集的可能。因此，至少存在著這樣的兩個作業(yè)a和b，使得aJ且a I，bI且b J。設a是使得aJ且a I的一個具有最高效益值的作業(yè)。由貪心方法可以得出，對于在I中又不在J中的所有作業(yè)b，都有papb。這是因為若pbpa，則貪心方法會先于作業(yè)a考慮作業(yè)b并且把b計入到J中去?，F(xiàn)在，設SJ和SI分別是J和I的可行調度表。設i是既屬于J又屬于I的一個作業(yè)；又設I在 SJ中的t到t+1時刻被調度，而在SI中則在t到t+1時刻被調度。如

20、果tt，則可以將SI中t，t+1時刻所調度的那個作業(yè)(如果有的話)與i相交換。如果J中在t，t+1時刻沒有作業(yè)被調度，則i移到t，t+l時刻調度。所形成的這個調度表也是可行的。如果tt，則可在SI中作類似的調換。用這種方法，就能得到調度表SJ和SI，使J和I中共有的所有作業(yè)在相同的時間被調度?？紤]SJ中ta，ta+1時刻，在這時刻內(上面所定義的)作業(yè)a被調度。設作業(yè)b在SI中的這一時刻被調度。根據(jù)對a的選擇，papb。在SI的ta，ta+1時刻去掉作業(yè)b而調度作業(yè)a，這就給出了一張關于作業(yè)集合I = I -ba可行的調度表。顯然I的效益值不小于I的效益值，并且 I比I少了一個與J不同的作業(yè)。

21、重復使用上述轉換，將使I能在不減效益值的情況下轉換成J，因此J也必定是最優(yōu)解。證畢。為了便于具體實現(xiàn)算法3.2，考慮對于一個給定的J，如何確定它是否為可行解的問題，一個明顯的方法是檢驗J中作業(yè)的所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能在其限期前完成。假定J中有k個作業(yè)，這就需要檢查k！個排列。對于所給出的一個排列=I1I2Ik，由于完成作業(yè)ij(1jk)的最早時間是j，因此，只要判斷出排列中的每個作業(yè)的dijj，就可得知是一個允許的調度序列，從而J就是一個可行解。反之，如果排列中有一個dijJ，則是一個行不通的調度序列，因為至少作業(yè)ij不會在它的限期前完成，故必須去檢查

22、J的另外形式的排列。事實上，對于J的可行性可以通過只檢驗J中作業(yè)的一種特殊的排列來確定，這個排列是按期限的非遞減次序來完成的。定理3.2 設J是k個作業(yè)的集合，=I1I2Ik是J中作業(yè)的一種排列，它使得dildi2dik。J是一個可行解，當且僅當J中的作業(yè)可以按照的次序而又不違反任何一個期限的情況來處理。證明:顯然，如果J中的作業(yè)可以按照的次序而又不違反任何一個期限的情況來處理，則J就是一個可行解?，F(xiàn)證，若J是可行解，則表示可以處理這些作業(yè)的一種允許的調度序列。由于J可行，則必存在=r1r2rk，使得dijj，1jk。假設，那么，令a是使得raia的最小下標。設rb=ia，顯然ba。在中將ra

23、與rb相交換，因為dradrb，故作業(yè)可依新產生的排列=s1s2sk的次序處理而不違反任何一個期限。連續(xù)使用該方法，就可將轉換成且不違反任何期限。證畢。即使這些作業(yè)有不同的處理時間ti0，上述定理亦真。其證明留作習題。根據(jù)定理3.2，可將帶限期的作業(yè)排序問題作如下處理：首先將作業(yè)1存入解數(shù)組J中，然后處理作業(yè)2到作業(yè)n。假設已處理了i-1個作業(yè)，其中有k個作業(yè)已計入J(1)，J(2)，J(k)之中，且有D(J(l)D(J(2)D(J(k)，現(xiàn)在處理作業(yè)i。為了判斷J i是否可行，只需看能否找出按期限的非遞減插入作業(yè) i的適當位置，使得作業(yè)i在此處插入后有D(J( r )r，lrk+1。找作業(yè)i

24、可能的插入位置按如下方式進行：將D(J(k)，D(J(k-l)，D(J(1)逐個與D(i)比較，直到找到位置q，它使得D(i) D(J(1)；q1k且D(J(q)D(i)。此時，若D(J(1)1，q1k，則說明這k-q個作業(yè)均可延遲一個單位時間處理，即可將這些作業(yè)在J中均后移一個位置而不違反各自的期限值。在以上條件成立時，只要D(i)q，就可將作業(yè)i在位置q+l處插入，從而得到一個按期限的非遞減序排列的含有k+1個作業(yè)的可行解。以上過程可反復進行到對第n個作業(yè)處理完畢，所得到的貪心解由定理3.1可知是一個最優(yōu)解。該處理過程可用算法3.2來描述。算法中引進了一個虛構的作業(yè)0，它被放在J(0)，且

25、D(J(0)=0。引入這一虛構作業(yè)是為了便于將作業(yè)插入位置1。算法3.2 帶有限期和效益的單位時間的作業(yè)排序貪心算法line void JS(int D，int J，int n，int k) /D(1)，D(n)是期限值，n1。作業(yè)已按plp2pn被排序。J(i)是最優(yōu)解中/的第i個作業(yè)，1ik。終止時，D(J(i)D(J(i+1)，1ik1 int i，r；2 d0 = j0 = 0 /初始化3 k = 1；j1 = 1； /計入作業(yè)14 for(i=2；i=n；+i) /按 p的非增次序考慮作業(yè)。找i的位置并檢查插入的可行性5 r = k；6 while(djr di) & (djr!=

26、r) 7 r = r - l；8 ；/ while9 if(djr r) /把 i插入J中10 for(i=k；i=r+l；-i) 11 ji+1 = j1)；12 ;/for13 jr+1 = i；k = k+1；14 if15 ；/for16 /JS對于JS，有兩個賴之以測量其復雜度的參數(shù)，即作業(yè)數(shù)n和包含在解中的作業(yè)數(shù)s。第68行的循環(huán)至多迭代k次，每次迭代的時間為O(l)。若第9行的條件為真，則執(zhí)行1013行語句。這些要求(k-r)時間去插入作業(yè)i。因此，對于415行的循環(huán)，其每次選代的總時間是(k)。該循環(huán)共選代n-1次。如果s是k的終值，即s是最后所得解的作業(yè)數(shù)，則算法JS所需要的

27、總時間是(sn)。由于sn，因此JS的最壞情況時間是(n2)。這種情況在p1=d1=n-i+1(1in)時就會出現(xiàn)。進而可以證明最壞情況計算時間為(n2)。在計算空間方面，除了D所需要的空間外，為了存放解J，還需要 (s)的空間量。要指出的是，JS并不需要具體的效益值，只要知道pipi+l(1in)即可。3.2 一種更快的作業(yè)排序算法通過使用不相交集合的Union與Find算法(使用壓縮規(guī)則的查找算法)以及使用一個不同的方法來確定部分解的可行性，可以把JS的計算時間由(n2)降低到數(shù)量級相當接近于(n)。如果J是作業(yè)的可行子集，那么可以使用下述規(guī)則來確定這些作業(yè)中的每一個作業(yè)的處理時間：若還沒

28、給作業(yè)i分配處理時間，則分配給它時間片-1，其中應盡量取大且時間片-1，是空的。此規(guī)則就是盡可能推遲對作業(yè)i的處理。于是，在將作業(yè)一個一個地裝配到J中時，就不必為接納新作業(yè)而去移動J中那些已分配了時間片的作業(yè)。如果正被考慮的新作業(yè)不存在在像上面那樣定義的，這個作業(yè)就不能計入J。這樣處理的正確性證明留作習題。例3.2 設n=5，(p1，p5)=(20，15，10，5，1)和(d1，d5)=(2，2，l，3，3)。使用上述可行性規(guī)則，可得結果如表3.2所示。表3.2 例3.2的執(zhí)行結果J已分配的時間片正被考慮的作業(yè)動作無1分配1，211，22分配0，11，20，1，1，23不合適，舍棄1，20，1

29、，1，24分配2，31，2，40，1，1，2，2，35舍棄最優(yōu)解是J=1，2，4。由于只有n個作業(yè)且每個作業(yè)花費一個單位時間，因此只需考慮這樣一些時間片i-1，i，1ib，其中 b=minn，maxdi。為簡便起見，以后用 i來表示時間片i-1，i。易于看出，這n個作業(yè)的期限值只能是l，2，b中的某些(或全部)元素。實現(xiàn)上述調度規(guī)則的一種方法是把這b個期限值分成一些集合。對于任一期限值i，設ni是使得nji的最大整數(shù)且是空的時間片。為避免極端情況，引進一個虛構的期限值0和時間片-1，0。當且僅當ni=nj時，期限值i和j在同一個集合中，即所要處理作業(yè)的期限值如果是 i或j，則當前可分配的最接近

30、的時間片是ni。顯然，若ij，則i，i+l，i+2，j都在同一個集合中。因此，上述方法就是作出一些以期限值為元素的集合，且使同一集合中的元素都有一個當前共同可用的最接近的空時間片。對于每個期限值i，0ib，當前最接近的空時間片可用線性表元素F(i)表示，即F(i)=ni。使用集合表示法，把每個集合表示成一棵樹。根結點就認為是這個集合。最初，這b+1個期限值最接近的空時間片是F(i)= i，0ib，并且有b+1個集合與b+1個期限值相對應。用P(i)把期限值i鏈接到它的集合樹上。開始時P(i)=-1，0ib 。如果要調度具有期限d的作業(yè)，那么就需要去尋找包含期限值minn,d的那個根。如果這個根

31、是j且只要F(j)0，則FQ是最接近的空時間片。在使用了這一時間片后，其根為j的集合應與包含期限值F(j)-1的集合合并。過程FJS描述了這個更快的算法。易于看出它的計算時間是(n(2n，n)(參看Ackermann函數(shù)的逆函數(shù))。它用于F和P的空間至多為2n個字節(jié)。算法3.3 作業(yè)排序的一個更快算法line void FJS(int d，int n，int b，int j，int k) /找最優(yōu)解J=J(1)，J(k).假定plp2pn，b=minn，max(D(i)l int fb，pb；2 for(i=0；i=n；+i) /將樹置初值3 fi=i；pi=-1；4 ；/5 k=0；/初始化

32、J6 for(i=0；i=n；+i) /使用貪心規(guī)則7 j=Find(min(n，di)；8 if(fj!=0) k=k+l；jk=i； /選擇作業(yè)i9 i = Find(fj-1)；Union(l，j)；10 fj=f1 ；11 ；/if12 ；/for13 /FJS例3.4 設n=7，(P1，P7)=(35,30,25,20,15,10,5)和(d1，d7)=(4,2,4,3,4,8,3)。利用算法FJS求解上述作業(yè)排序問題的最優(yōu)解。最優(yōu)解J=1，2，3，4，6。過程如表3.3所示。表3.3 例3.4的執(zhí)行過程考慮作業(yè)F(0) F(1) F(2) F(3) F(4) F(5) F(6) F

33、(7)-10 1 2 3 4 5 6 7-1-1-1-1-1-1-1樹J()無0 1 2 3 4 5 6 7110 1 2 3 4 5 6 7-10 1 3 5 6 7-1-2-1-1-13412-10 1 2 3 5 6 7-1-1-2-1-1-1341,220 1 1 3 3 5 6 71,2,330 1 1 1 3 5 6 7-10 1 5 6 7-41-1-1-1341231,2,3,440 0 1 1 3 5 6 71 1 5 6 7-51-1-1-13410321,2,3,45舍棄0 0 1 1 3 5 6 71 1 5 6 7-51-1-1-11410321,2,3,460 0

34、1 1 3 5 6 61 1 5 6 -51-1-2614103277舍棄結構不變4 最優(yōu)歸并模式在前面已學過兩個分別包含n個和m個記錄的已分類文件可以在(n+m)時間內歸并在一起而得到一個分類文件。當要把兩個以上的已分類文件歸并在一起時，可以通過成對地重復歸并已分類的文件來完成。例如，假定X1，X2，X3，X4是要歸并的文件，則可以首先把X1和X2歸并成文件Y1，然后將Y1和X3歸并成Y2，最后將Y2和X4歸并，從而得到想要的分類文件；也可以先把X1和X2歸并成Y1，然后把X3和X4歸并成Y2，最后歸并Y1和Y2而得到想要的分類文件。給出n個文件，則有許多種把這些文件成對地歸并成一個單一分類

35、文件的方法。不同的配對法要求不同的計算時間?，F(xiàn)在所要論及的問題是確定一個把n個已分類文件歸并在一起的最優(yōu)方法(即需要最少比較的方法)。例4.1 X1，X2和X3是各自有30個記錄、20個記錄和10個記錄的三個已分類文件，歸并X1和X2需要50次記錄移動，再與X3歸并則還要60次移動，其所需要的記錄移動總量是110。如果首先歸并X2和X3(需要30次移動)，然后歸并X1(需要60次移動)，則所要作的記錄移動總數(shù)僅為90。因此，第二個歸并模式比第一個要快些。試圖得到最優(yōu)歸并模式的貪心方法是容易表達的。由于歸并一個具有n個記錄的文件和一個具有m個記錄的文件可能需要n+m次記錄移動，因此對于量度標準的

36、一種明顯的選擇是：每一步都歸并記錄數(shù)最小的兩個文件。例如，有五個文件(Fl，F(xiàn)5)，它們的記錄數(shù)為(20，30，10，5，30)，由以上的貪心策略就會產生以下的歸并模式：F3和F4歸并成Z1(|Z1|=15)；歸并Z1和Fl得到Z2(|Z2|=35)；把F2和F5歸并成Z3(|Z3|=60)；歸并Z2和Z3而得到答案Z4。記錄移動總量是205?？梢宰C明這是給定問題實例的最優(yōu)歸并模式。像剛才所描述的歸并模式稱為二路歸并模式(每一個歸并步包含兩個文件的歸并)。二路歸并模式可以用二元歸并樹來表示。圖4.1顯示了一棵表示上面五個文件所得到的最優(yōu)歸并模式的二元歸并樹。葉結點被畫成方塊形，表示這五個已知的

37、文件。這些結點稱為外部結點。剩下的結點被畫成圓圈，稱為內部結點。每個內部結點恰好有兩個兒子，它表示把它的兩個兒子所表示的文件歸并而得到的文件。每個結點中的數(shù)字都是那個結點所表示的文件的長度(即記錄數(shù))。95Z4351560Z12030Z2Z3105F1F2F330F4F5圖4.1 例4.1的二元歸并樹第4級外部結點F4距離根結點Z4的路徑長度為3(一個i級結點距離根結點的路徑長度為i-1)，因此文件F4的記錄都要移動3次，一次得到Z1，一次得到Z2，最后移動一次就得到Z4。如果di是由根到代表文件Fi的外部結點的距離；qi是Fi的長度，則這棵二元歸并樹的記錄移動總量是:ndiqii=1這個和數(shù)

38、叫做這棵樹的帶權外部路徑長度。一個最優(yōu)二路歸并模式與一棵具有最小權外部路徑的二元樹相對應，算法4.1的函數(shù)Tree使用上面所敘述的規(guī)則去獲得n個文件的二元歸并樹。這算法把n個樹的表L作為輸入。樹中的每一個結點有三個信息段，LChild，RChild和Weight。起初，L中的每一棵樹正好有一個結點。這個結點是一個外部結點，而且其LChild和RChild信息段為0，而Weight是要歸并的n個文件之一的長度。在這個算法運行期間，對于L中的任何一棵具有根結點T的樹，Weight(T)(樹T中外部結點的長度的和)表示要歸并的文件的長度。過程Tree用了三個子算法，GetNode(T)，Least(

39、L)和Insert(L，T)。函數(shù)GetNode(T)為構造這棵樹提供一個新結點。Least(L)找出L中一棵其根具有最小的Weight值的樹，并把這棵樹從L中刪去。Insert(L，T)把根為T的樹插入到表L中。定理4.1將證明貪心過程Tree(算法4.1)將產生一棵最優(yōu)的二元歸并樹。算法4.1 生成二元歸并樹算法line void Tree(list L，int n) /L是如上所述的n個單結點二元樹的表l for(i=1；i=n-1；+i) 2 GetNode(T) ； /用于歸并兩棵樹3 LChild(T) = Least(L)； /最小的長度4 RChild(T) = Least(L

40、)；5 Weight(T) = Weight(LChild(T) + Weight(RChild(T)；6 Insert(L，T)7 ；/for8 return Least(L)； /留在L中的樹是歸并樹9 ；/Tree 圖4.2 例4.1表L中樹的構造過程迭代后開始L235577799913131313123452355102355102357916791613235102353979161323510235例4.2 當L最初表示其長度為2，3，5，7，9，13的六個文件時，算法Tree是如何工作的。圖4.2顯示出在for循環(huán)的每一次選代結束時的表L。在算法結束時所產生的二元歸并樹可以用來確

41、定歸并了哪些文件。歸并是在這棵樹中“最低”(有最大的深度)的那些文件上進行的。現(xiàn)在來分析算法4.1需要的計算時間。主循環(huán)執(zhí)行n-1次。如果保持L按照這些根中的Weight值的非遞減，則Least(L)只需要(1)時間，Insert(L，T)在(n)時間內被執(zhí)行。因此所花費的時間總量是(n2)。在L被表示成一個min-堆的情況下，其中根的值不超過它的孩子們的值(見堆的定義)，則Least(L)和Insert(L，T)可以在(logn)時間內完成。在這種情況下Tree的計算時間是(nlogn)。將第6行的Insert(L，T)和第 4行的Least(L)結合起來還可以加快一些速度。Least(L)

42、和Insert(L，T)的算法以及其計算時間的分析留作習題。定理 4.1 若L最初包含n1個單個結點的樹，這些樹有Weight值為(ql，q2，qn)，則算法Tree對于具有這些長度的n個文件生成一棵最優(yōu)的二元歸并樹。q1+q2q1q2T圖4.3 最簡單的二元歸并樹證明:通過施歸納法于n來證明。對于n=1，返回一棵沒有內部結點的樹且這棵樹顯然是最優(yōu)的。假定該算法對于所有的(ql，q2，qm)，lmn，都生成一棵最優(yōu)二元歸并樹，現(xiàn)在來證明對于所有的(q1，q2，qn)也生成最優(yōu)的樹。不失一般性，假定q1q2qn，且q1和q2是在for 循環(huán)的第一次迭代期間由第3行和第4行中的算法Least所找到

43、的兩棵樹的Weight信息段的值。于是就生成了圖4.3的子樹T。設T是一棵對于(q1，q2，qn)的最優(yōu)二元歸并樹。設p是距離根最遠的一個內部結點。如果P的兒子不是q1和q2，則可以用q1和q2來代換p現(xiàn)在的孩子而不增加T的帶權外部路徑長度。因此T也是一棵最優(yōu)歸并樹中的子樹。于是在T中如果用其權為q1+q2的一個外部結點來代換T，則所產生的樹T是關于中(q1+q2，q3，qn)的一棵最優(yōu)歸并樹。由歸納假設，在用其權為q1+q2的那個外部結點代換了T以后，過程Tree轉化成去求取一棵關于(q1+q2，q3，qn)的最優(yōu)歸并樹。因此Tree生成一棵關于(q1，q2，qn)的最優(yōu)歸并樹。證畢。生成歸

44、并樹的貪心方法也適用于k路歸并的情況。在這種情況下，相應的歸并樹是一棵k元樹。由于所有的內部結點的度數(shù)必須為k，因此對于n的某些值，就不與k元歸并樹相對應。例如，當k=3時，就不存在具有n=2個外部結點的k元歸并樹。所以有必要引進一定量的“虛”外部結點。每一個虛結點被賦以0值的qi。這個虛值不會影響所產生的k元村的帶權外部路徑長度。本章習題11表明其所有內部結點都具有度數(shù)為k的k元樹的存在性，只有當外部結點數(shù)n滿足等式n mod(k-l)=1時才成立。因此至多應增加k-2個虛結點。生成最優(yōu)歸并樹的貪心規(guī)則是：在每一步，選取k棵具有最小長度的子樹用于歸并。關于它的最優(yōu)性證明，則留作習題。5 最小

45、生成樹定義:設G=(V，E)是一個無向連通圖。如果G的生成子圖T=(V，E)是一棵樹，則稱T是G的一棵生成樹(Spanning Tree)。例5.1 圖5.1顯示了4個結點的完全圖以及它的三棵生成樹。圖5.1 一個無向圖和它的三棵生成樹應用生成樹可以得到關于一個電網(wǎng)的一組獨立的回路方程。第一步是要得到這個電網(wǎng)的一棵生成樹。設B是那些不在生成樹中的電網(wǎng)的邊的集合，從B中取出一條邊添加到這生成樹上就生成一個環(huán)。從B中取出不同的邊就生成不同的環(huán)。把克?；舴?Kirchoff)第二定律用到每一個環(huán)上，就得到一個回路方程。用這種方法所得到的環(huán)是獨立的(即這些環(huán)中沒有一個可以用那些剩下的環(huán)的線性組合來得到

46、)，這是因為每一個環(huán)包含一條從B中取來的邊(生成樹固定的情況下)，而這條邊不包含在任何其它的環(huán)中。因此，這樣所得的這組回路方程也是獨立的?？梢宰C明，通過一次取B中的一條邊放進所產生的生成樹中而得到的這些環(huán)組成一個環(huán)基，從而這圖中所有其它的環(huán)都能夠用這個基中的這些環(huán)的線性組合構造出來。生成樹在其它方面也有廣泛的應用。一種重要的應用是由生成樹的性質所產生的，這一性質是，生成樹是G的這樣一個最小子圖T，它使得V(T)=V(G)且T連通并具有最少的邊數(shù)。任何一個具有n個結點的連通圖都必須至少有n-1條邊，而所有具有n-1條邊的n結點連通圖都是樹。如果G的結點代表城市，邊代表連接兩個城市的可能的交通線，

47、則連接這n個城市所需要的最少交通線是n-l條。G的那些生成樹代表所有可行的選擇。然而，在實際情況下，這些邊都有分配給它們的權。這些權可以代表建造的成本、交通線的長度以及其它。假定給出一個帶權圖(假定所有的權都是正數(shù))，則人們就會希望在結構上選擇一組交通線，它們連接所有的城市并且有最小的總成本或者有最小的總長度。顯然，在這兩種情況下所選擇的連線都必須構成一棵樹。感興趣的是找出G中具有最小成本的生成樹。圖5.2顯示了一個圖和它的最小成本生成樹中的一棵生成樹。圖5.2 一個帶權無向圖和它的一棵最小生成樹11923456162111331418610512345616111865獲得最小成本生成樹的貪

48、心方法應該是一條邊一條邊地構造這棵樹。根據(jù)某種量度標準來選擇將要計入的下一條邊。最簡單的量度標準是選擇使得迄今為止所計入的那些邊的成本的和有最小增量的那條邊。有兩種可能的方法來解釋這一量度標準。第一種方法使得迄今所選擇的邊的集合A構成一棵樹，即將要計入到A中的下一條邊(u，v)是一條不在A中且使得A (u，v)也是一棵樹的最小成本的邊。這種選擇準則產生一棵最小成本生成樹的證明留作習題。其相應的算法稱為Prim算法。圖5.3 Prim方法構造最小生成樹的例子130234561045402055251535501234561020251535例5.2 圖5.3是一個連通帶權無向圖，試按照prim思

49、想構造最小生成樹。所得到的最小生成樹的代價為105。由上述可知，Prim方法是如何運行的以及使用這一方法來獲得求取最小生成樹的類C語言算法。該算法是在只計入了G中一條最小成本邊的一棵樹的情況下開始的，然后一條邊一條邊地加進這棵樹中。所要加的下一條邊(i，j)是這樣的一條邊，其i是已計入到這棵樹中的一個結點，j是還沒有計入的一個結點，且(i，j)的成本COST(i，j)是所有的滿足上述要求的一些邊中成本最小的邊。為了有效地求出這條邊(i，j)，把還沒計入這樹中的每一個結點j和值near(j)聯(lián)系起來。near(j)是樹中的這樣一個結點，它使得COST(j，near(j)是對near(j)所有選擇

50、中的最小值。而對于已經在樹中的所有結點j，定義near(j)=0。用使near(j)0（j不在樹中）且COST(j，near(j)為最小值的結點來確定要計入的下一條邊。在函數(shù)Prim(算法5.1)中，第3行選取一條最小成本邊。第410行給變量置初值以便表示僅包含一條邊(k，l)的樹。在1121行中，逐條邊地構造生成樹的剩余部分。第12行選取(j，near(j)作為要計入的下一條邊。第 1620行修改 near()。算法5.1 Prim最小生成樹算法line void Prim(edge，COST，int n，&T，int minCOST) / edge()是G的邊集。COST(n，n)是n結點圖G的成本鄰接矩陣，矩陣元素COST(i，j)/是一個正實數(shù)，如果不存在邊(i，j)，則為+。計算一棵最小生成樹并把它作為一個/集合存放到數(shù)組T(1：n-1，2)中。(T(i，1)，T(i，2)是最小成本生成樹的一條邊。/最小成本生成樹的總成本最后賦給minCOST。1 float COSTn，n