算法設(shè)計-第4章

第4章貪心算法1學(xué)習(xí)要點理解貪心算法的概念。掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動態(tài)規(guī)劃算法的差異理解貪心算法的一般理論通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計策略。（1）活動安排問題；（2）最優(yōu)裝載問題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；（6）多機調(diào)度問題。2 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。3基本思想通過作出在當(dāng)前看來最優(yōu)的選擇（貪心選擇），將原問題規(guī)?？s小，如此反復(fù)，直至得到最終解。貪心算法并非對所有問題都能得到整體最優(yōu)解。4例4.1設(shè)有4種硬幣，它們的面值分別為1角，5分，2分和1分。現(xiàn)在要找給某顧客3角7分錢。此時我們會不假思索地拿出3個1角，1個5分和1個2分的硬幣交給顧客，這種找法與其他找法相比，拿出的硬幣的個數(shù)時最少的。

找硬幣算法：首先選出一個面值不超過3角7分的最大硬幣（1角）然后從3角7分中減去1角，剩余2角7分再選出一個不超過2角7分的最大硬幣（另一個1角），…，直到找足3角7分。第4章貪心算法5voidzhao(int*p,intn){

inti=1;

while(n!=0){

if(n>=p[i]){

printf("%d",p[i]);n=n-p[i];}elsei++;}}6這個找硬幣的算法就是貪心算法：總是作出在當(dāng)前看來是最好的選擇，即貪心算法并不是從總體最優(yōu)上加以考慮，它所作的選擇只是在某種意義上的局部最優(yōu)選擇。找硬幣問題本身最優(yōu)原理成立，可以用動態(tài)規(guī)劃方法求解，但用貪心算法更簡單，直接且解題效率更高。這利用了問題本身的特性。7動態(tài)規(guī)劃算法： 使用dp，關(guān)鍵是找出遞歸方程，而該問題可以提煉出遞歸方程如下（令C(t)表示要找t元用的最少硬幣數(shù)，di表示幣種）： 當(dāng)求解總面值為t的找零最少硬幣數(shù)c[t]時，將其分解成求解c[t

–di]和一個面值為

di

元的硬幣，由于t

–di<t，其解c[t

–di]已經(jīng)存在，如果面值為di

的硬幣滿足題意，那么最終解c[t]則等于c[t

–di]再加上1（即面值為di）的這一個硬幣。

C(t)=min{1+C(t-di),c(di)}

據(jù)此，C++程序為：

//data[0]~data[n-1]存幣種，已排序（升序），要找total元

8int

dpCoin(int*data,int

n,inttotal){

if(total<data[0])returnINT_MAX;

int*tmp=newint[total+1];

//存下所有C(t)

intt=0;

for(inti=data[0];i<=total;++i){

if(t<n&&i==data[t]){

tmp[i]=1;

++t;

}

else{

//C(t)=min{1+C(t-di),di<=t,1<=i<=n}

tmp[i]=INT_MAX;

for(intk=0;k=data[0]&&tmp[i-data[k]]!=INT_MAX;++k){

intj=1+tmp[i-data[k]];

if(j<tmp[i])tmp[i]=j;

}

}

}

intresult=tmp[total];

delete[]tmp;

returnresult;

//返回INT_MAX表示不能找

}9例4.2刪數(shù)字問題對給定的n位高精度正整數(shù),去掉其中k(k<n)個數(shù)字后，按原左右次序?qū)⒔M成一個新的正整數(shù)，使得剩下的數(shù)字組成的新數(shù)最大。操作對象是一個可以超過有效數(shù)字位數(shù)的n位高精度數(shù),存儲在數(shù)組a中。每次刪除一個數(shù)字,選擇一個使剩下的數(shù)最大的數(shù)字作為刪除對象。之所以選擇這樣“貪心”的操作,是因為刪k個數(shù)字的全局最優(yōu)解包含了刪一個數(shù)字的子問題的最優(yōu)解。當(dāng)k=1時,在n位整數(shù)中刪除哪一個數(shù)字能達(dá)到最大的目的?從左到右每相鄰的兩個數(shù)字比較:若出現(xiàn)增,即左邊小于右邊,則刪除左邊的小數(shù)字。若所有數(shù)字全部降序,則刪除最右邊的數(shù)字。10當(dāng)k>1(當(dāng)然小于n),按上述操作一個一個刪除。刪除一個達(dá)到最大后,再從頭即從串首開始,刪除第2個,依此分解為k次完成。若刪除不到k個后已無左邊小于右邊的增序,則停止刪除操作,打印剩下串的左邊n-k個數(shù)字即可（相當(dāng)于刪除了若干個最右邊的數(shù)字）11貪心法也是一個多步?jīng)Q策法。每一步選擇都使得能構(gòu)成問題的一個可行解，同時使目標(biāo)函數(shù)的值增加最快（求max）或增加最?。ㄈ缜髆in），這種選擇過程是以某些最優(yōu)量度為根據(jù)，而最優(yōu)化量度有時可以是目標(biāo)函數(shù)本身，也可以是別的量度。最優(yōu)化度量的選擇是貪心算法的關(guān)鍵。124.1活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。134.1活動安排問題

設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si

<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容。14貪心算法GreedySelector（活動安排）中，各活動的開始時間和結(jié)束時間分別存儲于數(shù)組S和f中且按結(jié)束時間的非減序：排列（量度標(biāo)準(zhǔn)）。如果所給出的活動未按此序排列，可用O(nlogn)的時間重排?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。15活動安排問題貪心解法：將所有活動按結(jié)束時間的非減序排序，得到活動集合E={e1,e2…en}；先將e1選入結(jié)果集合A中，即A={e1}；依次掃描每一個活動ei：如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei；16活動安排問題解法證明：若E={e1,e2…en}是按結(jié)束時間排序的活動集合，則e1具有最早的結(jié)束時間，設(shè)存在一個最優(yōu)安排A不包含e1，并以ei開始，則易見：

A-{ei}∪{e1}也是最優(yōu)的活動安排；

依此類推。174.1活動安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;

intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面給出解活動安排問題的貪心算法GreedySelector:各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列

說明：用集合A存儲所選擇的活動?；顒觟在集合A中，當(dāng)且僅當(dāng)A[i]＝true。變量j用以記錄最近一次加入到A中所有活動。由于輸入的活動是按其結(jié)束時間的非減序排列，fj總是當(dāng)前集合A中所有活動的最大結(jié)束時間，即184.1活動安排問題 由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。194.1活動安排問題

例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314204.1活動安排問題

算法greedySelector

的計算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。214.1活動安排問題

說明：

若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。22貪心算法主要用于處理優(yōu)化問題。每個優(yōu)化問題都是由目標(biāo)函數(shù)和約束條件組成。滿足約束條件的解稱為可行解，而那些使得目標(biāo)函數(shù)取極值的可行解稱為最優(yōu)解。在貪婪算法（greedymethod）中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedycriterion）。4.2貪心算法的基本要素234.2貪心算法的基本要素

本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

241、貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。

動態(tài)規(guī)劃是由子問題的解得到當(dāng)前問題的解，所以動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題；而貪心算法則是由當(dāng)前問題的局部最優(yōu)解導(dǎo)出子問題，所以貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

該性質(zhì)是貪心法使用成功的保障，否則得到的是近優(yōu)解；

25 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。也就是說需要證明問題的一個整體最優(yōu)解是從貪心選擇開始的；證明方法：首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解。注：其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。264.2貪心算法的基本要素

當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、最優(yōu)子結(jié)構(gòu)性質(zhì)通過局部最優(yōu)選擇，原問題將被化簡為類似的子問題；亦即是說，整體最優(yōu)解中包含了子問題的最優(yōu)解；27除非滿足貪心性質(zhì)，否則貪心算法存在：不能保證求得的最后解是最佳的；只能求滿足某些約束條件的可行解的范圍。注：貪婪算法雖不能保證得到最優(yōu)結(jié)果，但對于一些除了“窮舉”方法外沒有有效算法的問題，用貪婪算法往往能很快地得出較好的結(jié)果，如果此較好結(jié)果與最優(yōu)結(jié)果相差不是很多的話，此方法還是很實用的。也就是說,在一些情況下，即使貪婪算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。284.2貪心算法的基本要素

貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。

0-1背包問題背包問題3、貪心算法與動態(tài)規(guī)劃算法的差異294.2貪心算法的基本要素0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。304.2貪心算法的基本要素背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

31其中（4.2.1）是目標(biāo)函數(shù)，（4.2.2）及（4.2.3）是約束條件。滿足約束條件的任一集合(x1,…,xn)一個可行解，使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。(4.2.1)(4.2.2)(4.2.3)對于背包問題，形式化描述為：32

例

考慮下列情況下的背包問題:n＝3,c＝20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的四個可行解是

①（1,2/15,0）2028.2②（0,2/3,1）2031③（0,1,1/2）2031.5先檢驗這四個為可行解*,即滿足約束條件(4.2.2),(4.2.3).再比較目標(biāo)函數(shù)值,∑vixi.知④組解效益值最大.該組解是背包問題的最優(yōu)解。33（1）取目標(biāo)函數(shù)作為量度標(biāo)準(zhǔn)，即每次選擇利潤最大的物品裝包，使背包獲得最大可能的效益值增量。在此量度標(biāo)準(zhǔn)下貪心方法就是按效益值的非增次序，將物品一一裝包，直到某一i物品放不下時，取一種能獲得最大增量的物品，將它（或其一部分）放入背包，而使最后一次裝包也符合量度標(biāo)準(zhǔn)的要求。例n＝3,c＝20,此解是一個次優(yōu)解。顯然，按物品效益值的非增次序裝包不能得最優(yōu)解。原因：背包可用容量消耗過快。34

（2）以容量作為量度。即按物品重量的非降次序?qū)⑽锲费b包。如例中的解②（讓背包盡可能慢被消耗）排序:(w3,w2,w1)=(10,15,18)V3=15,x3=1,w3=10,背包剩余C－10＝10;物品2有次大重量(w2＝15),但包裝不下。使用x2＝2/3，剛好裝滿背包且物品2裝入2/3與物品1裝入5/9的容量均為10個單位。但前者的效益值24×2/3=16>后者效益值＝25×5/9≈14，但②

∑vixi=31,

解（0，2/3，1)仍是一個次優(yōu)解

。原因：容量慢慢消耗，但效益值未能迅速增大。35

（3）效益值的增長速率和容量的消耗速率間取平衡的量度標(biāo)準(zhǔn)。即以單位效益為量度，使物品裝入次序按比值的非增次序排列，應(yīng)用于例中的數(shù)據(jù)，得解③:（0,1,1/2）,∑vixi=31.5,∑wixi=20.為例背包問題的最優(yōu)解.

選取最優(yōu)的量度標(biāo)準(zhǔn)實為用貪心方法求解問題的核心.364.2貪心算法的基本要素

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：374.2貪心算法的基本要素voidKnapsack(int

n,float

M,float

v[],float

w[],floatx[]){

Sort(n,v,w);

inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;

x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。38102030501.￥602.￥1003.￥1204.背包=￥220

=￥160

=￥180

=￥240100201203060101002060

10120306010100208020120

——×2030

0-1背包問題的例子39對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。說明40貪心算法與動態(tài)規(guī)劃的比較

利用動態(tài)規(guī)劃求解最優(yōu)問題的步驟：

（1）證明該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

（2）根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，寫出最優(yōu)值的遞歸表達(dá)式；

（3）根據(jù)遞歸式，采用自底向上的方式計算，最優(yōu)值；

（5）求得最優(yōu)解。利用貪心算法求解最優(yōu)問題的步驟：

（1）選定合適的貪心選擇的標(biāo)準(zhǔn)；

（2）證明在此標(biāo)準(zhǔn)下該問題具有貪心選擇性質(zhì)；

（3）證明該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

（4）根據(jù)貪心選擇的標(biāo)準(zhǔn)，寫出貪心選擇的算法，求得最優(yōu)解。

41動態(tài)規(guī)劃算法和貪心算法都屬于遞推算法，并且這兩個算法適用的問題都具有最優(yōu)子結(jié)構(gòu)，都利用局部最優(yōu)解來推導(dǎo)全局最優(yōu)解。42兩者的不同點：

1貪心算法作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優(yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。

2動態(tài)規(guī)劃算法的全局最優(yōu)解中一定包含某個局部最優(yōu)解，但不一定包含前一個局部最優(yōu)解，因此需要記錄之前的所有局部最優(yōu)解；43動態(tài)規(guī)劃算法和貪心算法有一個顯著區(qū)別：

1）在動態(tài)規(guī)劃算法中，以自底向上的方式來利用最優(yōu)子結(jié)構(gòu)，也就是說，首先找到子問題的最優(yōu)解，解決子問題，然后找到問題的一個最優(yōu)解。

2）在貪心算法中，以自頂向下的方式使用最優(yōu)子結(jié)構(gòu)，也就是說，貪心算法會先做出選擇，在當(dāng)時看起來是最優(yōu)的選擇，然后再求解一個結(jié)果子問題，而不是先求解子問題的最優(yōu)解，然后再做出選擇。

44性能分析45貪心算法存在問題：

（1）不能保證求得的最后解是最佳的；

（2）不能用來求最大最小解的問題；比如錢幣分為1元3元4元，要拿6元錢，貪心的話，先拿4，再拿兩個1，一共3張錢；實際最優(yōu)卻是兩張3元就夠了。464.3最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。該問題可形式化描述為其中變量xi=0表示不裝入集裝箱i，xi=1表示裝入集裝箱i。471、算法描述

最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。484.3最優(yōu)裝載template<classType>voidLoading(intx[],Typew[],Typec,intn){

int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}492、貪心選擇性質(zhì)

設(shè)集裝箱已依其重量從小到大排列，（x1,x2,…，xn）是最優(yōu)裝載問題的一個最優(yōu)解。又設(shè)

易知，如果給定的最優(yōu)裝載問題有解，則1≤K≤n。 （1）當(dāng)k=1時，（x1,x2,…,xn)是一個滿足貪心選擇性質(zhì)的最優(yōu)解。 （2）當(dāng)k>1時，取y1=1；yk=0;yi=xi,1<i≤n,i≠k,則

因此，（y1,y2,…,yn)是所給最優(yōu)裝載問題的可行解。

另一方面，由知，（y1,y2,…,yn)

是滿足貪心選擇性質(zhì)的最優(yōu)解。所以，裝載問題具有貪心選擇性質(zhì)。

ywniii?=1xwniii?=1xwniii?=1=w1-wk+≤≤c4.3最優(yōu)裝載ynii?=1=xnii?=1k=min{i|xi=1},1≤i≤n503、最優(yōu)子結(jié)構(gòu)性質(zhì)

設(shè)（x1,x2,…,xn）是最優(yōu)裝載問題的滿足貪心選擇性質(zhì)的最優(yōu)解，則易知，x1=1，(x2,x3,…,xn)是輪船載重量為c-w1，待裝船集裝箱為{2，3，…,n)時相應(yīng)最優(yōu)裝載問題的最優(yōu)解。也就是說，最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。4、算法復(fù)雜性

算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。

514.4哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。例如一個包含100,000個字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長變碼需要300,000位，而按表中變長編碼方案，文件的總碼長為：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。比用定長碼方案總碼長較少約45%。521、前綴碼 對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼01011001111101110053 譯碼過程需要方便地取出編碼的前綴，因此需要表示前綴碼的合適的數(shù)據(jù)結(jié)構(gòu)。為此，可以用二叉樹作為前綴編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹中，樹葉代表給定的字符，并將每一個字符的前綴碼看作是從樹根到代表該字符的樹葉的一條道路。

表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點都有2個兒子結(jié)點。

在一般情況下，若C是編碼字符集，表示其最優(yōu)前綴碼的二叉樹中有|C|個葉子，每個葉子對應(yīng)于字符集中的一個字符，該二叉樹恰有|C|-1個內(nèi)部結(jié)點。54給定編碼字符集C及其頻率分布f，即C中任一字符c以頻率f(c)在數(shù)據(jù)文件中出現(xiàn)。C的一個前綴碼編碼方案對應(yīng)于一棵二叉樹T。字符c在樹T中的深度即為dT(c)。dT(c)也是字符c的前綴碼長。該編碼方案的平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。

554.4哈夫曼編碼2、構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結(jié)點開始，執(zhí)行|C|－1次的“合并”運算后產(chǎn)生最終所要求的樹T。

56Template<classType>ClassHuffman{friendBinaryTree<int>HuffmanTree(Type[],int);public:operatorType()const{returnweight;}private:

BinaryTree<int>tree;Typeweight;};57Template<classType>BinaryTree<int>HuffmanTree(Typef[],intn){//生成單結(jié)點樹Huffman<Type>*w=newHuffman<Type>[n+1];

BinaryTree<int>z,zero;For(inti=1;i<=n;i++){

z.MakeTree(I,zero,zero);

w[i].weight=f[i];

w[i].tree=z;}//建優(yōu)先隊列

MinHeap<Huffmna<Type>>Q(1);

Q.Initialize(w,n,n);58//反復(fù)合并最小頻率樹

Huffman<Type>x,y;for(inti=1;i<n;i++){

Q.DeleteMin(x);

Q.DeleteMin(y);z.MakeTree(0,x.tree,y.tree);

x.weight+=y.weight;

x.tree=z;

Q.Insert(x);}

Q.DeleteMin(x);

Q.DeleteMin(y);delete[]w;returnx.tree;}594.4哈夫曼編碼在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。 算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。604.4哈夫曼編碼3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

(1)貪心選擇性質(zhì)

(2)最優(yōu)子結(jié)構(gòu)性質(zhì)61哈夫曼算法的證明貪心選擇性質(zhì)的證明設(shè)C是編碼字符集，C中字符c的頻率為f(c)。又設(shè)x和y是C中具有最小頻率的兩個字符，則存在C的最優(yōu)前綴碼使x和y具有相同碼長且僅最后一位編碼不同。證明：設(shè)二叉樹T表示C的任意一個最優(yōu)前綴碼。則可以證明對T做適當(dāng)調(diào)整得到一棵新的二叉樹T’’，使得在新樹中，x和y是最深葉子節(jié)點且為兄弟，同時新樹T’’的前綴碼也是C的最優(yōu)前綴碼。從而證明x和y在T’’表示的最優(yōu)前綴碼中具有相同的碼長且僅最后一位編碼不同。62哈夫曼算法的證明最優(yōu)子結(jié)構(gòu)性質(zhì)的證明設(shè)T是表示字符集C的一個最優(yōu)前綴碼的完全二叉樹。C中字符c的出現(xiàn)頻率為f(c)。設(shè)x和y是樹T中的兩個葉子結(jié)點且為兄弟，z是他們的父親。若將z看做是具有頻率f(z)=f(x)+f(y)的字符，則樹T’=T-{x,y}表示字符集C’=C-{x,y}U{z}的一個最優(yōu)前綴碼。即：取x,y的父結(jié)點代替x,y結(jié)點，取x,y的權(quán)值和作為其父結(jié)點的權(quán)值，得到的仍是一棵最優(yōu)二叉樹；

證明：設(shè)原二叉樹的權(quán)值為W=W’+x*d+y*d，d為x,y的深度，則用x,y的父結(jié)點取代x,y后的二叉樹的權(quán)值為W’+(x+y)*(d-1)，易見，若存在一個更優(yōu)的二叉樹，將x,y再替換回來也應(yīng)是一棵更優(yōu)的二叉樹；63XY證明：取x,y的父結(jié)點代替x,y結(jié)點，取x,y的權(quán)值和作為其父結(jié)點的權(quán)值，得到的仍是一棵最優(yōu)二叉樹。W=W’+x*d+y*dW’+(x+y)*(d-1)644.5單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源。現(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。

651、算法基本思想

Dijkstra于1959年提出了解決此問題的一般算法，此算法可按邊的權(quán)值由小到大的次序，通過貪婪選擇，逐步得到由給定源點到圖的其余各點間的最短路徑。 采用逐條構(gòu)造最短路徑的辦法，用迄今已生成的所有路徑長度之和為最小作為貪心準(zhǔn)則，為此，每一條單獨的路徑都必須具有最小長度。

66一般情況下，

Dist[k]=<源點到頂點k的弧上的權(quán)值>

或者=<源點到其它頂點的路徑長度>+<其它頂點到頂點k的弧上的權(quán)值>。674.5單源最短路徑 其基本思想是，設(shè)置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源點到該頂點的最短路徑長度已知。 初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。

Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。681）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點的Dist[k]值。假設(shè)求得最短路徑的頂點為u，若Dist[u]+G.arcs[u][k]<Dist[k]則將Dist[k]改為Dist[u]+G.arcs[u][k]。V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長度。69迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度（2）每個頂點對應(yīng)一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和（反證法可證）70求最短路徑步驟初使時令S={V},T={其余頂點}，T中頂點對應(yīng)的距離值若存在<V,Vi>，為<V,Vi>弧上的權(quán)值若不存在<V,Vi>，為

從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進(jìn)行修改：若加進(jìn)W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點，即S=V為止71516432085623013717329終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6VjS13<V0,V1>8<V0,V2>

30<V0,V4>

32<V0,V6>V2:8<V0,V2>{V0,V2}13<V0,V1>-------13<V0,V2,V3>30<V0,V4>

32<V0,V6>V1:13<V0,V1>{V0,V2,V1}--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>{V0,V2,V1,V3}---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>72Template<classType>VoidDijkstra(int

n,int

v,Type

dist[],int

prev[],type**c){//單源最短路徑問題的Dijkstra算法，c[i][j]表示邊（i,j)的權(quán)，dist[i]表示當(dāng)前//從源到頂點i的最短特殊路徑。

bool

s[maxint];for(inti=1;i<=n;i++){

dist[i]=c[v][i];

s[i]=false;if(dist[i]==maxint)prev[i]=0;//設(shè)空路徑elseprev[i]=v;}

dist[v]=0;s[v]=true;//初始化，v頂點屬于S集合//開始主循環(huán)，每次求得v到某個頂點的最短路徑，并加該頂點到S集73For(inti=1;i<n;i++){//其余n-1個頂點

inttemp=maxint;//當(dāng)前所指離v頂點的最近距離

Intu=v;for(intj=1;j<=n;j++)if((!s[j])&&(dist[j]<temp))//w頂點在V-S中，且w頂點離v更近{u=j;temp=dist[j];}

s[u]=true;//離v頂點最近的v加入S集合for(intj=1;j<=n;j++)//更新當(dāng)前最短路徑即距離if((!s[j]&&(c[u][j]<maxint)){typenewdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//修改D[w]和P[w]}}}744.5單源最短路徑

例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。754.5單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過程：

764.5單源最短路徑2、算法的正確性和計算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計算復(fù)雜性 對于具有n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時間。算法的其余部分所需要時間不超過。774.6最小生成樹

設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。 網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。78144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS794.6最小生成樹1、最小生成樹性質(zhì) 用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)

E，且u

U，v

V-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。

802、Prim算法

Prim在1957年提出一種算法，這種算法特別適用于邊數(shù)相對較多，即比較接近于完全圖的圖。此算法是按逐個將頂點連通的步驟進(jìn)行的，它只需采用一個頂點集合。這個集合開始時是空集，以后將已連通的頂點陸續(xù)加入到集合中去，到全部頂點都加入到集合中了，就得到所需的生成樹。

814.6最小生成樹2、Prim算法

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件i

S，j

V-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進(jìn)行到S=V時為止。 在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。82構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹V3V1V4V6V5V23652165546如何求連通圖的最小生成樹?？

求解:

連通6個城市且代價最小的交通線路?

834.6最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時，T中的所有邊構(gòu)成G的一棵最小生成樹。

例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。84V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}854.6最小生成樹86Prim最小生成樹算法描述VoidPrim(int

n,type**c){T=?；

S={1}；

while(S!=v){

（i,j)=i∈S

且j∈V-S的最小權(quán)邊；

T=T∪{(i,j)};S=S∪{j};}}874.6最小生成樹 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件i

S,j

V-S，且權(quán)c[i][j]最小的邊(i,j)。實現(xiàn)這個目的的較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修改。 用這個辦法實現(xiàn)的Prim算法所需的計算時間為88

有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)

無向連通網(wǎng)絡(luò):

G

為選擇權(quán)值最小的邊:

置一個一維數(shù)組：closedge[]，以記錄從U到

V-U具有最小代價的邊。對每一頂點vi

V-U,在輔助數(shù)組中相應(yīng)分量closedge[i-1],包括兩域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存儲該邊上的權(quán)Closedge[i-1].adjvex域：存儲該邊依附的在U中的頂點。

普魯姆算法涉及的數(shù)據(jù)和操作：

數(shù)據(jù)：無向連通網(wǎng)絡(luò)

操作:選擇權(quán)值最小的邊，不妨設(shè)為（u,v)

(u,v)加入TE，u加入UUV-U

viV2V0V3V5V4V-U

vivj89V3V1V4V6V5V23652165546例

111111

06

1

5maxmax

viadjvexlowcost

123456

vi

adjvexlowcost

123456

131133

05056

4U={v1}U={v1,v3}V3V1V4V6V5V23652165546UU對每一頂點vi

V-U,在輔助數(shù)組中相應(yīng)分量closedge[i-1],包括兩域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存儲該邊上的權(quán)Closedge[i-1].adjvex域：存儲該邊依附的在U中的頂點。V-U={v2,V3,V4,V5,V6}V-U={v2,V4,V5,V6}90

0v1v1v100

06

1

5maxmax

lowcost{v1}

0v30v1v3v3

05056

4

adjvexlowcost{v1,v3}

0v30v6v30

050

2

60

adjvexlowcost{v1,v3,v6}

0v300v30

0

5

0060

adjvexlowcost{v1,v3,v6,v4}

0000v20

0000

3

0

adjvexlowcost{v1,v3,v6,v4,v2}

000000

000000

adjvexlowcost{v1,v3,v6,v4,v2,v5}iadjvex

012345UV3V1V4V6V5V23652165546closedge

v1v2v3v4v5v691

設(shè)置一個輔助數(shù)組，對當(dāng)前V－U集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊：typedef

struct{

VertexType

adjvex;//U集中的頂點序號

VRType

lowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];92voidMiniSpanTree_P(MGraphG,VertexTypeu){

//用普里姆算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};//{adjvex,lowcost}

closedge[k].lowcost=0;//初始，U＝{u}for(i=0;i<G.vexnum;++i){繼續(xù)向生成樹上添加頂點;

}93

k=minimum(closedge);

//求出加入生成樹的下一個頂點(k)

printf(closedge[k].adjvex,G.vexs[k]);

//輸出生成樹上一條邊

closedge[k].lowcost=0;//第k頂點并入U集

for(j=0;j<G.vexnum;++j)

//修改其它頂點的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}}94abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c5516953、Kruskal算法

Kruskal

在1956年提出了1個最小生成樹算法，它的思路很容易理解。設(shè)G=(V,E)是一個連通帶權(quán)圖，V={1,2,…,n}。將圖中的邊按其權(quán)值由小到大排序，然后作如下的貪婪選擇，由小到大順序選取各條邊，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮。如此依次進(jìn)行，到選夠（n-1）條邊即得到最小生成樹。96具體做法:

先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。97算法思路：假設(shè)N=(V,{E})是連通圖，將N中的邊按權(quán)值從小到大的順序排列；（1）將n個頂點看成n個集合；（2）按權(quán)值由小到大的順序選擇邊，所選邊應(yīng)滿足兩個頂點不在同一個頂點集合內(nèi)，將該邊放到生成樹邊的集合中，同時將該邊的兩個頂點所在的頂點集合合并；（3）重復(fù)（2），直到所有的頂點都在同一個頂點集合內(nèi)。9899

例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。各邊按權(quán)值排序為：d13=1d46=2d25=3d36c4d14=

5d34=5d23=5d12=6d35=6d56=6100//在一個具有n個頂點的網(wǎng)絡(luò)中找棵最小生成樹令E為網(wǎng)絡(luò)中邊的集合令T為所選邊的集合,初始化T為空集

while(E不是空集&&T中元素個數(shù)不等于n-1){

令(u,v)為E中最小代價的邊;E=E-(u,v);//從中刪除該邊;if((u,v)加入T中不會產(chǎn)生環(huán))

將(u,v)加入T;}算法復(fù)雜度為O(n+eloge)Kruskal最小生成樹算法1014.6最小生成樹說明： 關(guān)于集合的一些基本運算可用于實現(xiàn)Kruskal算法。 按權(quán)的遞增順序查看等價于對優(yōu)先隊列執(zhí)行removeMin

運算?？梢杂枚褜崿F(xiàn)這個優(yōu)先隊列。

算法復(fù)雜性：

當(dāng)圖的邊數(shù)為e時，Kruskal算法所需的計算時間是。當(dāng)時，Kruskal算法比Prim算法差，但當(dāng)時，Kruskal算法卻比Prim算法好得多。102普里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法103問題描述：設(shè)有n個獨立的作業(yè){1,2,…,n}，由m臺相同的機器進(jìn)行加工處理。作業(yè)i所需的處理時間為ti?，F(xiàn)約定，任何作業(yè)可以在任何一臺機器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。4.7多機調(diào)度問題1044.7多機調(diào)度問題

多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。1054.7多機調(diào)度問題 采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。 按此策略，當(dāng)時，只要將機器i的[0,ti]時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。 當(dāng)時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。1064.7多機調(diào)度問題

例如，設(shè)7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。

各作業(yè)按時間由大到小排序為{4，2，5，6，3，7，1}1074.8貪心算法的理論基礎(chǔ)

借助于擬陣工具，可建立關(guān)于貪心算法的較一般的理論。這個理論對確定何時使用貪心算法可以得到問題的整體最優(yōu)解十分有用。1、擬陣 擬陣M定義為滿足下面3個條件的有序?qū)?S,I)： (1)S是非空有限集。 (2)I是S的一類具有遺傳性質(zhì)的獨立子集族，即若B

I，則B是S的獨立子集，且B的任意子集也都是S的獨立子集。空集

必為I的成員。 (3)I滿足交換性質(zhì)，即若A

I,B

I且|A|<|B|，則存在某一元素x

B-A，使得A∪{x}

I。1084.8貪心算法的理論基礎(chǔ)

例如，設(shè)S是一給定矩陣中行向量的集合，I是S的線性獨立子集族，則由線性空間理論容易證明(S,I)是一擬陣。擬陣的另一個例子是無向圖G=(V,E)的圖擬陣。 給定擬陣M=(S,I)，對于I中的獨立子集A

I，若S有一元素x

A，使得將x加入A后仍保持獨立性，即A∪{x}

I,則稱x為A的可擴展元素。 當(dāng)擬陣M中的獨立子集A沒有可擴展元素時，稱A為極大獨立子集。1094.8貪心算法的理論基礎(chǔ) 下面的關(guān)于極大獨立子集的性質(zhì)是很有用的。 定理4.1：擬陣M中所有極大獨立子集大小相同。

這個定理可以用反證法證明。 若對擬陣M=(S,I)