第5章貪心算法1VisualFoxPro主要內(nèi)容5.1貪心算法概述5.2貪心算法的理論基礎(chǔ)5.3刪數(shù)字問(wèn)題5.4背包問(wèn)題5.5覆蓋問(wèn)題5.6圖的著色問(wèn)題5.7遍歷問(wèn)題5.8最小生成樹(shù)5.9哈夫曼編碼2VisualFoxPro5.1貪心算法概述5.1.1貪心算法

有一艘大船準(zhǔn)備用來(lái)裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i個(gè)貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多箱的貨物。

這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：設(shè)存在一組變量xi，其可能取值為0或1。如xi為0，則貨箱i將不被裝上船；如xi為1，則貨箱i將被裝上船。我們的目的是找到一組xi，使它滿(mǎn)足限制條件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。相應(yīng)的優(yōu)化函數(shù)是ni=∑wixi取極值。滿(mǎn)足限制條件的每一組xi都是一個(gè)可行解，能使ni=∑wixi取得極大值的方案是最優(yōu)解。3VisualFoxPro找硬幣問(wèn)題假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某個(gè)顧客六角三分錢(qián)。這時(shí)，我們會(huì)不假思索地拿出2個(gè)二角五分的硬幣，1個(gè)一角的硬幣和3個(gè)一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，拿出的硬幣個(gè)數(shù)是最少的。這里，使用了這樣的找硬幣方法：首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出不超過(guò)三角八分的最大硬幣，即又一個(gè)二角五分，如此一直做下去。這個(gè)找硬幣的方法實(shí)際上就是貪心算法。4VisualFoxPro

貪心算法（也稱(chēng)貪心策略）總是作出在當(dāng)前看來(lái)是最好的選擇。如上面的找硬幣問(wèn)題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動(dòng)態(tài)規(guī)劃算法來(lái)解。但我們看到，用貪心算法更簡(jiǎn)單，更直接且解題效率更高。這利用了問(wèn)題本身的一些特性。貪心算法在求解最優(yōu)化問(wèn)題時(shí)，從初始階段開(kāi)始，每一個(gè)階段總是作一個(gè)使局部最優(yōu)的貪心選擇，不斷把將問(wèn)題轉(zhuǎn)化為規(guī)模更小的子問(wèn)題。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。這樣處理，對(duì)大多數(shù)優(yōu)化問(wèn)題來(lái)說(shuō)能得到最優(yōu)解，但也并不總是這樣。從求解效率來(lái)說(shuō)，貪心算法比動(dòng)態(tài)規(guī)劃更高，且不存在空間限制的影響。另外，對(duì)一些NP完全問(wèn)題或規(guī)模很大的優(yōu)化問(wèn)題，可通過(guò)仿貪心算法能得到很好的近世解，而用動(dòng)態(tài)規(guī)劃根本無(wú)法解。5VisualFoxPro5.1.2.貪心算法的基本思想

貪心算法的基本思想是通過(guò)一系列選擇步驟來(lái)構(gòu)造問(wèn)題的解，每一步都是對(duì)當(dāng)前部分解的一個(gè)擴(kuò)展，直至獲得問(wèn)題的完整解。所做的每一步選擇都必須滿(mǎn)足：(1)可行的：必須滿(mǎn)足問(wèn)題的約束。(2)局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部選擇。(3)不可取消:選擇一旦做出，在后面的步驟中就無(wú)法改變了。貪心算法是通過(guò)做一系列的選擇來(lái)給出某一問(wèn)題的最優(yōu)解，對(duì)算法的每一個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來(lái)）是最佳的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。6VisualFoxPro5.2貪心算法的理論基礎(chǔ)

“矩陣胚”理論

“矩陣胚”理論是一種能夠確定貪心算法何時(shí)能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問(wèn)題時(shí)發(fā)揮著越來(lái)越重要的作用。定義

矩陣胚是一個(gè)序?qū)=[S，I]

，其中S是一個(gè)有序非空集合，I是S的一個(gè)非空子集，成為S的一個(gè)獨(dú)立子集。7VisualFoxPro如果M是一個(gè)N×M的矩陣的話，即:

若M是無(wú)向圖G的矩陣胚的話，則S為圖的邊集，I是所有構(gòu)成森林的一組邊的子集。如果對(duì)S的每一個(gè)元素X（X∈S）賦予一個(gè)正的權(quán)值W（X），則稱(chēng)矩陣胚M(jìn)=（S，I）為一個(gè)加權(quán)矩陣胚。8VisualFoxPro適宜于用貪心算法來(lái)求解的許多問(wèn)題都可以歸結(jié)為在加權(quán)矩陣胚中找一個(gè)具有最大權(quán)值的獨(dú)立子集的問(wèn)題，即給定一個(gè)加權(quán)矩陣胚，M=（S，I），若能找出一個(gè)獨(dú)立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨(dú)立子集所包含，那么A為最優(yōu)子集，也是一個(gè)最大的獨(dú)立子集。矩陣胚理論對(duì)于我們判斷貪心算法是否適用于某一復(fù)雜問(wèn)題是十分有效的。

9VisualFoxPro對(duì)給定的n位高精度正整數(shù),去掉其中k(k<n)個(gè)數(shù)字后，按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)，使得剩下的數(shù)字組成的新數(shù)最大。操作對(duì)象是一個(gè)可以超過(guò)有效數(shù)字位數(shù)的n位高精度數(shù),存儲(chǔ)在數(shù)組a中。每次刪除一個(gè)數(shù)字,選擇一個(gè)使剩下的數(shù)最大的數(shù)字作為刪除對(duì)象。之所以選擇這樣“貪心”的操作,是因?yàn)閯hk個(gè)數(shù)字的全局最優(yōu)解包含了刪一個(gè)數(shù)字的子問(wèn)題的最優(yōu)解。當(dāng)k=1時(shí),在n位整數(shù)中刪除哪一個(gè)數(shù)字能達(dá)到最大的目的?從左到右每相鄰的兩個(gè)數(shù)字比較:若出現(xiàn)增,即左邊小于右邊,則刪除左邊的小數(shù)字。若不出現(xiàn)減,即所有數(shù)字全部升序,則刪除最右邊的大數(shù)字。5.3刪數(shù)字問(wèn)題10VisualFoxPro當(dāng)k>1(當(dāng)然小于n),按上述操作一個(gè)一個(gè)刪除。刪除一個(gè)達(dá)到最大后,再?gòu)念^即從串首開(kāi)始,刪除第2個(gè),依此分解為k次完成。若刪除不到k個(gè)后已無(wú)左邊小于右邊的增序,則停止刪除操作,打印剩下串的左邊n-k個(gè)數(shù)字即可(相當(dāng)于刪除了若干個(gè)最右邊的數(shù)字)。下面我們給出采用貪心算法的刪數(shù)字問(wèn)題的部分c語(yǔ)言代碼：11VisualFoxPro

while(k>x&&m==0){i=i+1;if(a[i-1]<a[i])/*出現(xiàn)遞增,刪除遞增的首數(shù)字*/{printf("%d",a[i-1]);for(j=i-1;j<=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù)*/i=0;/*從頭開(kāi)始查遞增區(qū)間*/}if(i==n-x-1)/*已無(wú)遞增區(qū)間,m=1脫離循環(huán)*/m=1;}printf("\n刪除后所得最大數(shù):");for(i=1;i<=n-k;i++)/*打印剩下的左邊n-k個(gè)數(shù)字*/printf("%d",a[i-1]);

12VisualFoxPro

5.4背包問(wèn)題已知n種物品和一個(gè)可容納c重量的背包，物品i的重量為wi，產(chǎn)生的效益為pi。裝包時(shí)物品可拆，即可只裝每種物品的一部分。顯然物品i的一部分放入背包可產(chǎn)生的效益為，這里。問(wèn)如何裝包，使所得整體效益最大。(1)算法設(shè)計(jì)應(yīng)用貪心算法求解。每一種物品裝包，由可以整個(gè)裝入，也可以只裝一部分，也可以不裝。約束條件：目標(biāo)函數(shù)：要使整體效益即目標(biāo)函數(shù)最大，按單位重量的效益非增次序一件件物品裝包，直至某一件物品裝不下時(shí)，裝這種物品的一部分把包裝滿(mǎn)。解背包問(wèn)題貪心算法的時(shí)間復(fù)雜度為O(n)。

13VisualFoxPro幾個(gè)背包實(shí)例1.w=[100,10,10]，p=[20,15,15]，c=105;2.w=[10,20]，p=[5,100]，c=25;3.w=[20,15,15]，p=[40,25,25]，c=304.w=[2,4,6,7]，p=[6,10,12,13],c=11;14VisualFoxPro物品可拆背包問(wèn)題C程序設(shè)計(jì)代碼如下：for(i=1;i<=n-1;i++)/*對(duì)n件物品按單位重量的效益從大到小排序*/for(j=i+1;j<=n;j++)if(p[i]/w[i]<p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw為背包還可裝的重量*/for(i=1;i<=n;i++){if(w[i]>cw)break;x[i]=1.0;/*若w(i)<=cw,整體裝入*/cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)>cw,裝入一部分x(i)*/s=s+p[i]*x[i];15VisualFoxProprintf("裝包：");/*輸出裝包結(jié)果*/for(i=1;i<=n;i++)if(x[i]<1)break;elseprintf("\n裝入重量為%5.1f的物品.",w[i]);if(x[i]>0&&x[i]<1)printf("\n裝入重量為%5.1f的物品百分之%5.1f.",w[i],x[i]*100);printf("\n所得最大效益為：%7.1f",s);16VisualFoxPro作業(yè)：一個(gè)數(shù)列由n個(gè)正整數(shù)組成，對(duì)該數(shù)列進(jìn)行一次操作：去除其中兩項(xiàng)a、b，添加一項(xiàng)a*b+1。經(jīng)過(guò)n-1次操作后該數(shù)列剩一個(gè)數(shù)a，試求a的最大值。17VisualFoxPro二分圖是一個(gè)無(wú)向圖，它的n個(gè)頂點(diǎn)可二分為集合A和集合B，且同一集合中的任意兩個(gè)頂點(diǎn)在圖中無(wú)邊相連（即任何一條邊都是一個(gè)頂點(diǎn)在集合A中，另一個(gè)在集合B中）。當(dāng)且僅當(dāng)B中的每個(gè)頂點(diǎn)至少與A中一個(gè)頂點(diǎn)相連時(shí)，A的一個(gè)子集A‘覆蓋集合B（或簡(jiǎn)單地說(shuō)，A’是一個(gè)覆蓋）。覆蓋A‘的大小即為A’中的頂點(diǎn)數(shù)目。當(dāng)且僅當(dāng)A‘是覆蓋B的子集中最小的時(shí)，A’為最小覆蓋。二分覆蓋問(wèn)題類(lèi)似于集合覆蓋問(wèn)題?？梢詫⒓细采w問(wèn)題轉(zhuǎn)化為二分覆蓋問(wèn)題（反之亦然），即用A的頂點(diǎn)來(lái)表示S1,.,Sk，B中的頂點(diǎn)代表U中的元素。當(dāng)且僅當(dāng)S的相應(yīng)集合中包含U中的對(duì)應(yīng)元素時(shí)，在A與B的頂點(diǎn)之間存在一條邊。5.5覆蓋問(wèn)題18VisualFoxPro集合覆蓋問(wèn)題為NP-復(fù)雜問(wèn)題。由于集合覆蓋與二分覆蓋是同一類(lèi)問(wèn)題，二分覆蓋問(wèn)題也是NP-復(fù)雜問(wèn)題。因此可能無(wú)法找到一個(gè)快速的算法來(lái)解決它，但是可以利用貪心算法尋找一種快速啟發(fā)式方法。一種可能是分步建立覆蓋A‘，每一步選擇A中的一個(gè)頂點(diǎn)加入覆蓋。頂點(diǎn)的選擇利用貪心準(zhǔn)則：從A中選取能覆蓋B中還未被覆蓋的元素?cái)?shù)目最多的頂點(diǎn)。我們給出覆蓋問(wèn)題的貪心算法的偽代碼，可以證明：(1)當(dāng)且僅當(dāng)初始的二分圖沒(méi)有覆蓋時(shí)，算法找不到覆蓋；(2)啟發(fā)式方法可能找不到二分圖的最小覆蓋。19VisualFoxPro算法描述如下：

m=0;//當(dāng)前覆蓋的大小

對(duì)于A中的所有i，Malloc[i]=Degree[i]

對(duì)于B中的所有i，Cov[i]=false

while(對(duì)于A中的某些i,Malloc[i]>0){

設(shè)v是具有最大的New[i]的頂點(diǎn)；

C[m++]=v;

for(所有鄰接于v的頂點(diǎn)j){

if(!Cov[j]){

Cov[j]=true;

對(duì)于所有鄰接于j的頂點(diǎn)，使其N(xiāo)ew[k]減1

}}}20VisualFoxProif(有些頂點(diǎn)未被覆蓋)失敗

else找到一個(gè)覆蓋該算法的時(shí)間復(fù)雜度取決于數(shù)據(jù)的存儲(chǔ)方式，若使用鄰接矩陣，則需花(n2)的時(shí)間來(lái)尋找圖中的邊，若用鄰接鏈表，則需(n+e)的時(shí)間。故覆蓋算法總的復(fù)雜性為O(n2)或O(n+e)21VisualFoxPro

圖著色問(wèn)題是其實(shí)對(duì)應(yīng)很多應(yīng)用的例子，假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。(這個(gè)問(wèn)題實(shí)際上是著名的圖著色問(wèn)題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場(chǎng)數(shù)。)

活動(dòng)安排問(wèn)題：設(shè)有n個(gè)活動(dòng)a1,a2,…,an,每個(gè)活動(dòng)都要求使用同一資源，而同一時(shí)間內(nèi)只允許一個(gè)活動(dòng)使用這一資源。已知活動(dòng)ai要求使用該資源的起始時(shí)間為si，結(jié)束時(shí)間為fi，且si<=fi。要求在a1,a2,…,an中選出最大的相容活動(dòng)子集。兩活動(dòng)ai,aj(i≠j)相容是指：5.6圖的著色問(wèn)題22VisualFoxPro例：n=4,活動(dòng)：a1a2a3a4si：4218fi：74510貪心選擇策略：按結(jié)束時(shí)間從早到晚安排活動(dòng)，每次選擇與已選出的活動(dòng)相容的結(jié)束時(shí)間盡可能早的活動(dòng)。局部最優(yōu)性：每次為資源留下盡可能多的時(shí)間以容納其它活動(dòng)。該算法的時(shí)間復(fù)雜性：Θ(nlogn)。使用貪心算法求解圖的著色問(wèn)題并不總能得到最優(yōu)解,只保證得到近似最優(yōu)解。其實(shí)，頂點(diǎn)的編號(hào)方法決定了這種算法的結(jié)果。至少存在一種編號(hào)方法使這個(gè)貪心算法能得到最優(yōu)解。23VisualFoxProvoidcolor_up(intnodes)//著色函數(shù){

inti,j,k=1;

int*color;

color=(int*)malloc((sizeof(int))*(nodes+1));//初始化顏色數(shù)

for(i=1;i<=nodes;i++)

color[i]=0;

color[1]=1;

do

{

for(i=2;i<=nodes;i++)

{

if(color[i]>0)continue;

下面給出圖的著色問(wèn)題的c語(yǔ)言程序:24VisualFoxPro

for(j=1;j<i;j++)

if((color[j]==k)&&(graph[i-1][j-1]!=0))break;if(j==i)color[i]=k;

}

j=2;

while((color[j]>0)&&(j<=nodes))j++;

k++;

}while(j<=nodes);

for(i=1;i<=nodes;i++)

printf("node%dcolor:%d\n",i,color[i]);}25VisualFoxPro馬的遍歷問(wèn)題。在n×n方格的棋盤(pán)上，從任意指定方格出發(fā)，為馬尋找一條走遍棋盤(pán)每一格并且只經(jīng)過(guò)一次的一條路徑。在這里僅以8×8的棋盤(pán)為例。算法初步描述：首先這是一個(gè)搜索問(wèn)題，運(yùn)用深度優(yōu)先搜索進(jìn)行求解。算法如下：(1)輸入初始位置坐標(biāo)x,y；(2)初始化c:如果c>64輸出一個(gè)解，返回上一步驟c--(x,y)←c計(jì)算(x,y)的八個(gè)方位的子結(jié)點(diǎn)，選出那此可行的子結(jié)點(diǎn)循環(huán)遍歷所有可行子結(jié)點(diǎn)，c++重復(fù)25.7遍歷問(wèn)題26VisualFoxPro顯然（２）是一個(gè)遞歸調(diào)用的過(guò)程，大致如下：voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個(gè)解return;}for(I=0;i<8;++i){tx=hn[i].x;//hn[]保存八個(gè)方位子結(jié)點(diǎn)ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調(diào)用s[tx][ty]=0;}}27VisualFoxPro這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當(dāng)８×８時(shí)解是非常之多的，用天文數(shù)字形容也不為過(guò)，這樣一來(lái)求解的過(guò)程就非常慢，并且出一個(gè)解也非常慢。怎么才能快速地得到部分解呢？其實(shí)馬踏棋盤(pán)的問(wèn)題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個(gè)有名的算法。在每個(gè)結(jié)點(diǎn)對(duì)其子結(jié)點(diǎn)進(jìn)行選取時(shí)，優(yōu)先選擇‘出口’最小的進(jìn)行搜索，‘出口’的意思是在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個(gè)數(shù)，也就是‘孫子’結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法.28VisualFoxPro

其實(shí)這種求解就是利用了貪心算法，它對(duì)整個(gè)求解過(guò)程的局部做最優(yōu)調(diào)整，它只適用于求較優(yōu)解或者部分解，而不能求最優(yōu)解。這樣的調(diào)整方法叫貪心策略，至于什么問(wèn)題需要什么樣的貪心策略是不確定的，具體問(wèn)題具體分析。實(shí)驗(yàn)可以證明馬遍歷問(wèn)題在運(yùn)用到了上面的貪心策略之后求解速率有非常明顯的提高，如果只要求出一個(gè)解甚至不用回溯就可以完成，因?yàn)樵谶@個(gè)算法提出的時(shí)候世界上還沒(méi)有計(jì)算機(jī)，這種方法完全可以用手工求出解來(lái)，其效率可想而知。29VisualFoxPro下面我們給出馬踏棋盤(pán)問(wèn)題的c代碼（８×８）：intways_out(intx,inty)//計(jì)算結(jié)點(diǎn)出口多少{inti,count=0,tx,ty;if(x<0||y<0||x>=N||y>=N||s[x][y]>0)return-1;//-1表示該結(jié)點(diǎn)非法或者已經(jīng)跳過(guò)了for(i=0;i<8;++i){tx=x+dx[i];ty=y+dy[i];if(tx<0||ty<0||tx>=N||ty>=N)continue;if(s[tx][ty]==0)++count;}returncount;}30VisualFoxProvoidsortnode(h_node*hn,intn)//采用簡(jiǎn)單排序法，因?yàn)樽咏Y(jié)點(diǎn)數(shù)最多只有8{//按結(jié)點(diǎn)出口進(jìn)行排序inti,j,t;h_nodetemp;for(i=0;i<n;++i){for(t=i,j=i+1;j<n;++j)if(hn[j].waysout<hn[t].waysout)t=j;if(t>i){temp=hn[i];hn[i]=hn[t];hn[t]=temp;}}}31VisualFoxProvoiddfs(intx,inty,intcount)//修改后的搜索函數(shù){inti,tx,ty;h_nodehn[8];if(count>N*N){output_solution();return;}for(i=0;i<8;++i)//求子結(jié)點(diǎn)和出口{hn[i].x=tx=x+dx[i];hn[i].y=ty=y+dy[i];hn[i].waysout=ways_out(tx,ty);}sortnode(hn,8);

32VisualFoxProfor(i=0;hn[i].waysout<0;++i);//不考慮無(wú)用結(jié)點(diǎn)for(;i<8;++i){tx=hn[i].x;ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);s[tx][ty]=0;}}33VisualFoxPro5.8最小生成樹(shù)

假設(shè)已知一無(wú)向連通圖G=(V,E)，其加權(quán)函數(shù)為w:E→R，我們希望找到圖G的最小生成樹(shù)。后文所討論的兩種算法都運(yùn)用了貪心方法，但在如何運(yùn)用貪心法上卻有所不同。下列的算法GENERNIC-MIT正是采用了貪心算法，每步形成最小生成樹(shù)的一條邊。算法設(shè)置了集合A，該集合一直是某最小生成樹(shù)的子集。在每步?jīng)Q定是否把邊(u,v)添加到集合A中，其添加條件是A∪{(u,v)}仍然是最小生成樹(shù)的子集。我們稱(chēng)這樣的邊為A的安全邊，因?yàn)榭梢园踩匕阉砑拥紸中而不會(huì)破壞上述條件。GENERNIC-MIT(G,W)1.A←?2.whileA沒(méi)有形成一棵生成樹(shù)3do找出A的一條安全邊(u,v);4.A←A∪{(u,v)};5.returnA34VisualFoxPro定理5.1設(shè)圖G(V,E)是一無(wú)向連通圖，且在E上定義了相應(yīng)的實(shí)數(shù)值加權(quán)函數(shù)w，設(shè)A是E的一個(gè)子集且包含于G的某個(gè)最小生成樹(shù)中，割(S,V-S)是G的不妨害A的任意割且邊(u,v)是穿過(guò)割(S,V-S)的一條輕邊，則邊(u,v)對(duì)集合A是安全的。下面介紹兩個(gè)算法：Kruskal算法和Prim算法(1)Kruskal算法

Kruskal算法是直接基于上面中給出的一般最小生成樹(shù)算法的基礎(chǔ)之上的。該算法找出森林中連結(jié)任意兩棵樹(shù)的所有邊中具有最小權(quán)值的邊(u,v)作為安全邊，并把它添加到正在生長(zhǎng)的森林中。設(shè)C1和C2表示邊(u,v)連結(jié)的兩棵樹(shù)。因?yàn)?u,v)必是連C1和其他某棵樹(shù)的一條輕邊，所以由推論2可知(u,v)對(duì)C1是安全邊。Kruskal算法同時(shí)也是一種貪心算法，因?yàn)樗惴恳徊教砑拥缴种械倪叺臋?quán)值都盡可能小

35VisualFoxProKruskal算法的實(shí)現(xiàn)類(lèi)似于計(jì)算連通支的算法。它使用了分離集合數(shù)據(jù)結(jié)構(gòu)以保持?jǐn)?shù)個(gè)互相分離的元素集合。通過(guò)FIND-SET(v)來(lái)確定兩結(jié)點(diǎn)u和v是否屬于同一棵樹(shù)，通過(guò)操作UNION來(lái)完成樹(shù)與樹(shù)的聯(lián)結(jié)。MST-KRUSKAL(G,w)1.A←?2.for每個(gè)結(jié)點(diǎn)vV[G]3.doMAKE-SET(v)4.根據(jù)權(quán)w的非遞減順序?qū)的邊進(jìn)行排序5.for每條邊(u,v)?E，按權(quán)的非遞減次序6.doifFIND-SET(u)≠FIND-SET(v)7.thenA←A∪{(u,v)}8.UNION(u,v)9returnA36VisualFoxProKruskal算法在圖G=(V,E)上的運(yùn)行時(shí)間取決于分離集合這一數(shù)據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)。我們采用在分離集合中描述的按行結(jié)合和通路壓縮的啟發(fā)式方法來(lái)實(shí)現(xiàn)分離集合森林的結(jié)構(gòu)，這是由于從漸近意義上來(lái)說(shuō)，這是目前所知的最快的實(shí)現(xiàn)方法。(2)Prim算法Prim算法的特點(diǎn)是集合A中的邊總是只形成單棵樹(shù)。因?yàn)槊看翁砑拥綐?shù)中的邊都是使樹(shù)的權(quán)盡可能小的邊，因此上述策略也是貪心的。有效實(shí)現(xiàn)Prim算法的關(guān)鍵是設(shè)法較容易地選擇一條新的邊添加到由A的邊所形成的樹(shù)中，在下面的偽代碼中，算法的輸入是連通圖G和將生成的最小生成樹(shù)的根r。在算法執(zhí)行過(guò)程中，不在樹(shù)中的所有結(jié)點(diǎn)都駐留于優(yōu)先級(jí)基于key域的隊(duì)列Q中。對(duì)每個(gè)結(jié)點(diǎn)v，key[v]是連接v到樹(shù)中結(jié)點(diǎn)的邊所具有的最小權(quán)值；按常規(guī)，若不存在這樣的邊則key[v]=∞。域p[v]說(shuō)明樹(shù)中v的“父母”。

37VisualFoxPro在算法執(zhí)行中，GENERIC-MST的集合A隱含地滿(mǎn)足：A={(v,p[v])|v?V-{r}-Q}當(dāng)算法終止時(shí)，優(yōu)先隊(duì)列Q為空，因此G的最小生成樹(shù)A滿(mǎn)足:A={(v,p[v])|v?V-{r}}MST-PRIM(G,w,r)1.Q←V[G]2.for每個(gè)u?Q3.dokey[u]←∞4.key[r]←05.p[r]←NIL6.whileQ≠?7.dou←EXTRACT-MIN(Q)8.for每個(gè)v?Adj[u]9.doifv?Qandw(u,v)<key[v]10.thenp[v]←u11.key[v]←w(u,v)38VisualFoxProPrim算法的性能分析Prim算法的性能取決于我們?nèi)绾螌?shí)現(xiàn)優(yōu)先隊(duì)列Q。若用二叉堆來(lái)實(shí)現(xiàn)Q,我們可以使用過(guò)程BUILD-HEAP來(lái)實(shí)現(xiàn)第1-4行的初始化部分，其運(yùn)行時(shí)間為O(V)。循環(huán)需執(zhí)行|V|次，且由于每次EXTRACT-MIN操作需要O(㏒V)的時(shí)間，所以對(duì)EXTRACT-MIN的全部調(diào)用所占用的時(shí)間為O(V㏒V)。第8-11行的for循環(huán)總共要執(zhí)行O(E)次，這是因?yàn)樗朽徑颖淼拈L(zhǎng)度和為2|E|。在for循環(huán)內(nèi)部，第9行對(duì)隊(duì)列Q的成員條件進(jìn)行測(cè)試可以在常數(shù)時(shí)間內(nèi)完成，這是由于我們可以為每個(gè)結(jié)點(diǎn)空出1位(bit)的空間來(lái)記錄該結(jié)點(diǎn)是否在隊(duì)列Q中，并在該結(jié)點(diǎn)被移出隊(duì)列時(shí)隨時(shí)對(duì)該位進(jìn)行更新。第11行的賦值語(yǔ)句隱含一個(gè)對(duì)堆進(jìn)行的DECREASE-KEY操作，該操作在堆上可用0(㏒V)的時(shí)間完成。因此，Prim算法的整個(gè)運(yùn)行時(shí)間為O(V㏒V+E㏒V)=O(E㏒V)，從漸近意義上來(lái)說(shuō)，它和實(shí)現(xiàn)Kruskal算法的運(yùn)行時(shí)間相同。

39VisualFoxPro通過(guò)使用Fibonacci堆，Prim算法的漸近意義上的運(yùn)行時(shí)間可得到改進(jìn)。在Fibonacci堆中我們己經(jīng)說(shuō)明，如果|V|個(gè)元素被組織成Fibonacci堆，可以在O(㏒V)的平攤時(shí)間內(nèi)完成EXTRACT-MIN操作，在O(1)的平攤時(shí)間里完成DECREASE-KEY操作（為實(shí)現(xiàn)第11行的代碼），因此，若我們用Fibonacci堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列Q，Prim算法的運(yùn)行時(shí)間可以改進(jìn)為O(E+V㏒V)。40VisualFoxPro5.9哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的