第5章 貪心算法

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

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

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

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

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

“矩陣胚”理論

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

矩陣胚是一個序對M=[S，I]

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

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

9VisualFoxPro對給定的n位高精度正整數(shù),去掉其中k(k<n)個數(shù)字后，按原左右次序將組成一個新的正整數(shù)，使得剩下的數(shù)字組成的新數(shù)最大。操作對象是一個可以超過有效數(shù)字位數(shù)的n位高精度數(shù),存儲在數(shù)組a中。每次刪除一個數(shù)字,選擇一個使剩下的數(shù)最大的數(shù)字作為刪除對象。之所以選擇這樣“貪心”的操作,是因為刪k個數(shù)字的全局最優(yōu)解包含了刪一個數(shù)字的子問題的最優(yōu)解。當k=1時,在n位整數(shù)中刪除哪一個數(shù)字能達到最大的目的?從左到右每相鄰的兩個數(shù)字比較:若出現(xiàn)增,即左邊小于右邊,則刪除左邊的小數(shù)字。若不出現(xiàn)減,即所有數(shù)字全部升序,則刪除最右邊的大數(shù)字。5.3刪數(shù)字問題10VisualFoxPro當k>1(當然小于n),按上述操作一個一個刪除。刪除一個達到最大后,再從頭即從串首開始,刪除第2個,依此分解為k次完成。若刪除不到k個后已無左邊小于右邊的增序,則停止刪除操作,打印剩下串的左邊n-k個數(shù)字即可(相當于刪除了若干個最右邊的數(shù)字)。下面我們給出采用貪心算法的刪數(shù)字問題的部分c語言代碼：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)計刪除數(shù)字的個數(shù)*/i=0;/*從頭開始查遞增區(qū)間*/}if(i==n-x-1)/*已無遞增區(qū)間,m=1脫離循環(huán)*/m=1;}printf("\n刪除后所得最大數(shù):");for(i=1;i<=n-k;i++)/*打印剩下的左邊n-k個數(shù)字*/printf("%d",a[i-1]);

12VisualFoxPro

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

13VisualFoxPro幾個背包實例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物品可拆背包問題C程序設計代碼如下：for(i=1;i<=n-1;i++)/*對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("裝包：");/*輸出裝包結果*/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è)：一個數(shù)列由n個正整數(shù)組成，對該數(shù)列進行一次操作：去除其中兩項a、b，添加一項a*b+1。經過n-1次操作后該數(shù)列剩一個數(shù)a，試求a的最大值。17VisualFoxPro二分圖是一個無向圖，它的n個頂點可二分為集合A和集合B，且同一集合中的任意兩個頂點在圖中無邊相連（即任何一條邊都是一個頂點在集合A中，另一個在集合B中）。當且僅當B中的每個頂點至少與A中一個頂點相連時，A的一個子集A‘覆蓋集合B（或簡單地說，A’是一個覆蓋）。覆蓋A‘的大小即為A’中的頂點數(shù)目。當且僅當A‘是覆蓋B的子集中最小的時，A’為最小覆蓋。二分覆蓋問題類似于集合覆蓋問題?？梢詫⒓细采w問題轉化為二分覆蓋問題（反之亦然），即用A的頂點來表示S1,.,Sk，B中的頂點代表U中的元素。當且僅當S的相應集合中包含U中的對應元素時，在A與B的頂點之間存在一條邊。5.5覆蓋問題18VisualFoxPro集合覆蓋問題為NP-復雜問題。由于集合覆蓋與二分覆蓋是同一類問題，二分覆蓋問題也是NP-復雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪心算法尋找一種快速啟發(fā)式方法。一種可能是分步建立覆蓋A‘，每一步選擇A中的一個頂點加入覆蓋。頂點的選擇利用貪心準則：從A中選取能覆蓋B中還未被覆蓋的元素數(shù)目最多的頂點。我們給出覆蓋問題的貪心算法的偽代碼，可以證明：(1)當且僅當初始的二分圖沒有覆蓋時，算法找不到覆蓋；(2)啟發(fā)式方法可能找不到二分圖的最小覆蓋。19VisualFoxPro算法描述如下：

m=0;//當前覆蓋的大小

對于A中的所有i，Malloc[i]=Degree[i]

對于B中的所有i，Cov[i]=false

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

設v是具有最大的New[i]的頂點；

C[m++]=v;

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

if(!Cov[j]){

Cov[j]=true;

對于所有鄰接于j的頂點，使其New[k]減1

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

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

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

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

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

其實這種求解就是利用了貪心算法，它對整個求解過程的局部做最優(yōu)調整，它只適用于求較優(yōu)解或者部分解，而不能求最優(yōu)解。這樣的調整方法叫貪心策略，至于什么問題需要什么樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之后求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。29VisualFoxPro下面我們給出馬踏棋盤問題的c代碼（８×８）：intways_out(intx,inty)//計算結點出口多少{inti,count=0,tx,ty;if(x<0||y<0||x>=N||y>=N||s[x][y]>0)return-1;//-1表示該結點非法或者已經跳過了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)//采用簡單排序法，因為子結點數(shù)最多只有8{//按結點出口進行排序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)//求子結點和出口{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);//不考慮無用結點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最小生成樹

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

Kruskal算法是直接基于上面中給出的一般最小生成樹算法的基礎之上的。該算法找出森林中連結任意兩棵樹的所有邊中具有最小權值的邊(u,v)作為安全邊，并把它添加到正在生長的森林中。設C1和C2表示邊(u,v)連結的兩棵樹。因為(u,v)必是連C1和其他某棵樹的一條輕邊，所以由推論2可知(u,v)對C1是安全邊。Kruskal算法同時也是一種貪心算法，因為算法每一步添加到森林中的邊的權值都盡可能小

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

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

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

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