第5章貪心算法

1、125.1 貪心算法概述貪心算法概述5.2 貪心算法的理論基礎(chǔ)貪心算法的理論基礎(chǔ) 5.3 刪數(shù)字問(wèn)題刪數(shù)字問(wèn)題5.4 背包問(wèn)題背包問(wèn)題 5.5 覆蓋問(wèn)題覆蓋問(wèn)題5.6 圖的著色問(wèn)題圖的著色問(wèn)題5.7 遍歷問(wèn)題遍歷問(wèn)題5.8 最小生成樹(shù)最小生成樹(shù) 5.9 哈夫曼編碼哈夫曼編碼35.1 貪心算法概述貪心算法概述5.1.1 貪心算法貪心算法有一艘大船準(zhǔn)備用來(lái)裝載貨物。所有待裝貨物都裝在有一艘大船準(zhǔn)備用來(lái)裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第同。設(shè)第i個(gè)貨箱的重量為個(gè)貨箱的重量為wi（1in），而貨船的最

2、大載），而貨船的最大載重量為重量為c，我們的目的是在貨船上裝入最多箱的貨物。，我們的目的是在貨船上裝入最多箱的貨物。 這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：設(shè)存在一組這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：設(shè)存在一組變量變量xi ，其可能取值為，其可能取值為0或或1。如。如xi為為0，則貨箱，則貨箱i 將不被裝將不被裝上船；如上船；如xi為為1，則貨箱，則貨箱i 將被裝上船。我們的目的是找到將被裝上船。我們的目的是找到一組一組xi ，使它滿足限制條件，使它滿足限制條件ni =wixi c 且且xi0, 1, 1 in。相應(yīng)的優(yōu)化函數(shù)是。相應(yīng)的優(yōu)化函數(shù)是ni=wixi取極值取極值 。滿足限制條件。滿足

3、限制條件的每一組的每一組xi都是一個(gè)可行解，能使都是一個(gè)可行解，能使ni=wixi取得極大值的取得極大值的方案是最優(yōu)解。方案是最優(yōu)解。4找硬幣問(wèn)題找硬幣問(wèn)題假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某個(gè)顧客六角三分錢。這時(shí)，我們會(huì)不假思索地拿出2個(gè)二角五分的硬幣，1個(gè)一角的硬幣和3個(gè)一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，拿出的硬幣個(gè)數(shù)是最少的。這里，使用了這樣的找硬幣方法：首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出不超過(guò)三角八分的最大硬幣，即又一個(gè)二角五分，如此一直做下去。這個(gè)找硬幣的方法實(shí)

4、際上就是貪心算法貪心算法。5 貪心算法（也稱貪心策略）總是作出在當(dāng)前看來(lái)是最好貪心算法（也稱貪心策略）總是作出在當(dāng)前看來(lái)是最好的選擇。如上面的找硬幣問(wèn)題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，的選擇。如上面的找硬幣問(wèn)題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動(dòng)態(tài)規(guī)劃算法來(lái)解。但我們看到，用貪心算法更它可以用動(dòng)態(tài)規(guī)劃算法來(lái)解。但我們看到，用貪心算法更簡(jiǎn)單，更直接且解題效率更高。這利用了問(wèn)題本身的一些簡(jiǎn)單，更直接且解題效率更高。這利用了問(wèn)題本身的一些特性。特性。 貪心算法在求解最優(yōu)化問(wèn)題時(shí)，從初始階段開(kāi)始，每一貪心算法在求解最優(yōu)化問(wèn)題時(shí)，從初始階段開(kāi)始，每一個(gè)階段總是作一個(gè)使局部最優(yōu)的貪心選擇，不斷把將問(wèn)題個(gè)階段總是作一

5、個(gè)使局部最優(yōu)的貪心選擇，不斷把將問(wèn)題轉(zhuǎn)化為規(guī)模更小的子問(wèn)題。也就是說(shuō)貪心算法并不從整體轉(zhuǎn)化為規(guī)模更小的子問(wèn)題。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。這樣處理，對(duì)大多數(shù)優(yōu)化問(wèn)題來(lái)說(shuō)能得到最優(yōu)解，選擇。這樣處理，對(duì)大多數(shù)優(yōu)化問(wèn)題來(lái)說(shuō)能得到最優(yōu)解，但也并不總是這樣。從求解效率來(lái)說(shuō)，貪心算法比動(dòng)態(tài)規(guī)但也并不總是這樣。從求解效率來(lái)說(shuō)，貪心算法比動(dòng)態(tài)規(guī)劃更高，且不存在空間限制的影響。另外，對(duì)一些劃更高，且不存在空間限制的影響。另外，對(duì)一些NP完全完全問(wèn)題或規(guī)模很大的優(yōu)化問(wèn)題，可通過(guò)仿貪心算法能得到很問(wèn)題或規(guī)模很大

6、的優(yōu)化問(wèn)題，可通過(guò)仿貪心算法能得到很好的近世解，而用動(dòng)態(tài)規(guī)劃根本無(wú)法解。好的近世解，而用動(dòng)態(tài)規(guī)劃根本無(wú)法解。65.1.2. 貪心算法的基本思想貪心算法的基本思想 貪心算法的基本思想是通過(guò)一系列選擇步驟來(lái)構(gòu)造問(wèn)題貪心算法的基本思想是通過(guò)一系列選擇步驟來(lái)構(gòu)造問(wèn)題的解，每一步都是對(duì)當(dāng)前部分解的一個(gè)擴(kuò)展，直至獲得問(wèn)題的解，每一步都是對(duì)當(dāng)前部分解的一個(gè)擴(kuò)展，直至獲得問(wèn)題的完整解。所做的每一步選擇都必須滿足：的完整解。所做的每一步選擇都必須滿足： (1) 可行的：必須滿足問(wèn)題的約束?？尚械模罕仨殱M足問(wèn)題的約束。 (2) 局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部選擇。局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部

7、選擇。 (3) 不可取消不可取消: 選擇一旦做出，在后面的步驟中就無(wú)法改選擇一旦做出，在后面的步驟中就無(wú)法改變了。變了。 貪心算法是通過(guò)做一系列的選擇來(lái)給出某一問(wèn)題的最優(yōu)貪心算法是通過(guò)做一系列的選擇來(lái)給出某一問(wèn)題的最優(yōu)解，對(duì)算法的每一個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來(lái)）是最佳解，對(duì)算法的每一個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來(lái)）是最佳的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。 75.2 貪心算法的理論基礎(chǔ)貪心算法的理論基礎(chǔ) 1.“矩陣胚矩陣胚”理論理論 “矩陣胚矩陣胚”理論是一種能夠確定貪心算法何理論是一種能夠確定貪心算法何時(shí)能夠產(chǎn)生最優(yōu)解的理論，雖然這套理

8、論還很時(shí)能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問(wèn)題時(shí)發(fā)揮著越來(lái)越不完善，但在求解最優(yōu)化問(wèn)題時(shí)發(fā)揮著越來(lái)越重要的作用。重要的作用。定義定義 矩陣胚是一個(gè)序?qū)仃嚺呤且粋€(gè)序?qū)=S，I ，其中，其中S是是一個(gè)有序非空集合，一個(gè)有序非空集合，I是是S的一個(gè)非空子集，成的一個(gè)非空子集，成為為S的一個(gè)獨(dú)立子集。的一個(gè)獨(dú)立子集。8如果如果M是一個(gè)是一個(gè)NM的矩陣的話，即的矩陣的話，即: 若若M是無(wú)向圖是無(wú)向圖G的矩陣胚的話，則的矩陣胚的話，則S為圖的邊為圖的邊集，集，I是所有構(gòu)成森林的一組邊的子集。是所有構(gòu)成森林的一組邊的子集。如果對(duì)如果對(duì)S的每一個(gè)元素的每一個(gè)元素X（XS）賦予一個(gè)

9、正）賦予一個(gè)正的權(quán)值的權(quán)值W（X），則稱矩陣胚），則稱矩陣胚M(jìn)=（S，I）為一）為一個(gè)加權(quán)矩陣胚。個(gè)加權(quán)矩陣胚。9適宜于用貪心算法來(lái)求解的許多問(wèn)題都可以歸結(jié)為適宜于用貪心算法來(lái)求解的許多問(wèn)題都可以歸結(jié)為在加權(quán)矩陣胚中找一個(gè)具有最大權(quán)值的獨(dú)立子集的在加權(quán)矩陣胚中找一個(gè)具有最大權(quán)值的獨(dú)立子集的問(wèn)題，即給定一個(gè)加權(quán)矩陣胚，問(wèn)題，即給定一個(gè)加權(quán)矩陣胚，M=（S，I），若能），若能找出一個(gè)獨(dú)立且具有最大可能權(quán)值的子集找出一個(gè)獨(dú)立且具有最大可能權(quán)值的子集A，且，且A不被不被M中比它更大的獨(dú)立子集所包含，那么中比它更大的獨(dú)立子集所包含，那么A為最為最優(yōu)子集，也是一個(gè)最大的獨(dú)立子集。優(yōu)子集，也是一個(gè)最大的獨(dú)立

10、子集。 矩陣胚理論對(duì)于我們判斷貪心算法是否適用于某一矩陣胚理論對(duì)于我們判斷貪心算法是否適用于某一復(fù)雜問(wèn)題是十分有效的。復(fù)雜問(wèn)題是十分有效的。 10對(duì)給定的對(duì)給定的n位高精度正整數(shù)位高精度正整數(shù),去掉其中去掉其中k(k1(當(dāng)然小于當(dāng)然小于n),按上述操作一個(gè)一個(gè)刪除。按上述操作一個(gè)一個(gè)刪除。刪除一個(gè)達(dá)到最大后刪除一個(gè)達(dá)到最大后, 再?gòu)念^即從串首開(kāi)始再?gòu)念^即從串首開(kāi)始,刪除第刪除第2個(gè)個(gè),依此分解為依此分解為k次完成。次完成。若刪除不到若刪除不到k個(gè)后已無(wú)左邊小于右邊的增序個(gè)后已無(wú)左邊小于右邊的增序,則停止刪除操作則停止刪除操作, 打印剩下串的左邊打印剩下串的左邊n-k個(gè)個(gè)數(shù)字即可數(shù)字即可(相當(dāng)于

11、刪除了若干個(gè)最右邊的數(shù)相當(dāng)于刪除了若干個(gè)最右邊的數(shù)字字)。下面我們給出采用貪心算法的刪數(shù)字問(wèn)題下面我們給出采用貪心算法的刪數(shù)字問(wèn)題 的的部分部分c語(yǔ)言代碼：語(yǔ)言代碼：12 while(kx & m=0) i=i+1; if(ai-1ai) /* 出現(xiàn)遞增,刪除遞增的首數(shù)字 */ printf(%d ,ai-1); for(j=i-1;j=n-x-2;j+) aj=aj+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

12、(i=1;i=n-k;i+) /* 打印剩下的左邊n-k個(gè)數(shù)字 */ printf(%d,ai-1); 13 5.4 背包問(wèn)題背包問(wèn)題 已知已知n種物品和一個(gè)可容納種物品和一個(gè)可容納c重量的背包，物品重量的背包，物品i的重的重量為量為wi，產(chǎn)生的效益為，產(chǎn)生的效益為pi。裝包時(shí)物品可拆，即可只裝。裝包時(shí)物品可拆，即可只裝每種物品的一部分。顯然物品每種物品的一部分。顯然物品i的一部分放入背包可產(chǎn)的一部分放入背包可產(chǎn)生的效益為，這里。問(wèn)如何裝包，使所得整體效益最大。生的效益為，這里。問(wèn)如何裝包，使所得整體效益最大。 (1) 算法設(shè)計(jì)算法設(shè)計(jì) 應(yīng)用貪心算法求解。每一種物品裝包，由可以整個(gè)裝入，應(yīng)用貪

13、心算法求解。每一種物品裝包，由可以整個(gè)裝入，也可以只裝一部分，也可以不裝。也可以只裝一部分，也可以不裝。約束條件：目標(biāo)函數(shù)：要使整體效益即目標(biāo)函數(shù)最大，約束條件：目標(biāo)函數(shù)：要使整體效益即目標(biāo)函數(shù)最大，按單位重量的效益非增次序一件件物品裝包，直至某一按單位重量的效益非增次序一件件物品裝包，直至某一件物品裝不下時(shí)，裝這種物品的一部分把包裝滿。件物品裝不下時(shí)，裝這種物品的一部分把包裝滿。解背包問(wèn)題貪心算法的時(shí)間復(fù)雜度為解背包問(wèn)題貪心算法的時(shí)間復(fù)雜度為O(n)。 14幾個(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,1

14、5,15，p=40,25,25 ，c=304.w=2,4,6,7，p=6,10,12,13,c=11;15物品可拆背包問(wèn)題物品可拆背包問(wèn)題C程序設(shè)計(jì)代碼如下：程序設(shè)計(jì)代碼如下：for(i=1;i=n-1;i+) /* 對(duì)對(duì)n件物品按單位重量的效益從件物品按單位重量的效益從大到小排序大到小排序 */for(j=i+1;j=n;j+) if(pi/wipj/wj) h=pi;pi=pj; pj=h; h=wi;wi=wj; wj=h; cw=c;s=0; /* cw為背包還可裝的重量為背包還可裝的重量 */for(i=1;icw) break; xi=1.0; /* 若若w(i)cw,裝入一部分裝

15、入一部分x(i) */s=s+pi*xi;16printf(裝包：裝包：); /* 輸出裝包結(jié)果輸出裝包結(jié)果 */for(i=1;i=n;i+) if(xi0 & xi0) 設(shè)設(shè)v是具有最大的是具有最大的N e w i 的頂點(diǎn)；的頂點(diǎn)； C m + + = v ; for( 所有鄰接于所有鄰接于v的頂點(diǎn)的頂點(diǎn)j) if (!Covj) Covj= true; 對(duì)于所有鄰接于對(duì)于所有鄰接于j的頂點(diǎn)，使其的頂點(diǎn)，使其N e w k 減減1 21if (有些頂點(diǎn)未被覆蓋有些頂點(diǎn)未被覆蓋) 失敗失敗 else 找到一個(gè)覆蓋找到一個(gè)覆蓋該算法的時(shí)間復(fù)雜度取決于數(shù)據(jù)的存儲(chǔ)方式，該算法的時(shí)間復(fù)雜度取

16、決于數(shù)據(jù)的存儲(chǔ)方式，若使用鄰接矩陣，則需花若使用鄰接矩陣，則需花(n2 ) 的時(shí)間來(lái)尋找的時(shí)間來(lái)尋找圖中的邊，若用鄰接鏈表，則需圖中的邊，若用鄰接鏈表，則需(n+e) 的時(shí)的時(shí)間。故覆蓋算法總的復(fù)雜性為間。故覆蓋算法總的復(fù)雜性為O( n2)或或O (n +e)22 圖著色問(wèn)題是其實(shí)對(duì)應(yīng)很多應(yīng)用的例子，假設(shè)要在圖著色問(wèn)題是其實(shí)對(duì)應(yīng)很多應(yīng)用的例子，假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。(這個(gè)問(wèn)這個(gè)問(wèn)題實(shí)際上是著名的圖著色問(wèn)題。若將每一個(gè)活動(dòng)作為題實(shí)際上是著名

17、的圖著色問(wèn)題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場(chǎng)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場(chǎng)數(shù)。數(shù)。) 活動(dòng)安排問(wèn)題：設(shè)有活動(dòng)安排問(wèn)題：設(shè)有n個(gè)活動(dòng)個(gè)活動(dòng)a1, a2, , an , 每個(gè)每個(gè)活動(dòng)都要求使用同一資源，而同一時(shí)間內(nèi)只允許一個(gè)活動(dòng)都要求使用同一資源，而同一時(shí)間內(nèi)只允許一個(gè)活動(dòng)使用這一資源。已知活動(dòng)活動(dòng)使用這一資源。已知活動(dòng)ai要求使用該資源的起要求使用該資源的起始時(shí)間為始時(shí)間為si，結(jié)束時(shí)間為，結(jié)束時(shí)間為fi，且，且si= fi 。要求在。要求在a1, a2,

18、 , an中選出最大的相容活動(dòng)子集。中選出最大的相容活動(dòng)子集。 兩活動(dòng)兩活動(dòng)ai , aj (ij)相容是指：相容是指：5.6 圖的著色問(wèn)題圖的著色問(wèn)題jjiifsfs,23例：例：n=4 , 活動(dòng)：活動(dòng)： a1 a2 a3 a4 si： 4 2 1 8 fi： 7 4 5 10貪心選擇策略：貪心選擇策略：按結(jié)束時(shí)間從早到晚安排活動(dòng)，每按結(jié)束時(shí)間從早到晚安排活動(dòng)，每次選擇與已選出的活動(dòng)相容的結(jié)束時(shí)間盡可能早的次選擇與已選出的活動(dòng)相容的結(jié)束時(shí)間盡可能早的活動(dòng)?；顒?dòng)。局部最優(yōu)性：局部最優(yōu)性：每次為資源留下盡可能多的時(shí)間以容每次為資源留下盡可能多的時(shí)間以容納其它活動(dòng)。納其它活動(dòng)。該算法的時(shí)間復(fù)雜性：

19、該算法的時(shí)間復(fù)雜性：(nlogn)。使用貪心算法求解圖的著色問(wèn)題并不總能得到最優(yōu)使用貪心算法求解圖的著色問(wèn)題并不總能得到最優(yōu)解解,只保證得到近似最優(yōu)解。其實(shí)，頂點(diǎn)的編號(hào)方法只保證得到近似最優(yōu)解。其實(shí)，頂點(diǎn)的編號(hào)方法決定了這種算法的結(jié)果。至少存在一種編號(hào)方法使決定了這種算法的結(jié)果。至少存在一種編號(hào)方法使這個(gè)貪心算法能得到最優(yōu)解。這個(gè)貪心算法能得到最優(yōu)解。 24void color_up(int nodes) /著色函數(shù)著色函數(shù) int i, j, k = 1; int *color; color = (int*)malloc(sizeof(int)*(nodes+1);/初始初始化顏色數(shù)化顏色數(shù)

20、 for(i=1; i= nodes; i+) colori = 0; color1=1; do for(i=2; i 0) continue; 下面給出圖的著色問(wèn)題的下面給出圖的著色問(wèn)題的c語(yǔ)言程序語(yǔ)言程序 :25 for(j = 1; j 0) & (j = nodes) j+; k+; while(j = nodes); for(i = 1; i 64輸出一個(gè)解，返回上一步驟輸出一個(gè)解，返回上一步驟c-(x,y) c計(jì)算計(jì)算(x,y)的八個(gè)方位的子結(jié)點(diǎn)，選出那此可行的子的八個(gè)方位的子結(jié)點(diǎn)，選出那此可行的子結(jié)點(diǎn)結(jié)點(diǎn)循環(huán)遍歷所有可行子結(jié)點(diǎn)，循環(huán)遍歷所有可行子結(jié)點(diǎn)，c+重復(fù)重復(fù)25.7

21、 遍歷問(wèn)題遍歷問(wèn)題27顯然（）是一個(gè)遞歸調(diào)用的過(guò)程，大致如下：顯然（）是一個(gè)遞歸調(diào)用的過(guò)程，大致如下：void dfs(int x,int y,int count) int i,tx,ty;if(countN*N) output_solution();/輸出一個(gè)解輸出一個(gè)解 return; for(I=0;i8;+i) tx=hni.x;/hn保存八個(gè)方位子結(jié)點(diǎn)保存八個(gè)方位子結(jié)點(diǎn) ty=hni.y; stxty=count; dfs(tx,ty,count+1);/遞歸調(diào)用遞歸調(diào)用 stxty=0; 28這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當(dāng)這樣做是完全可行的，它輸入的是全部解，但

22、是馬遍歷當(dāng)時(shí)解是非常之多的，用天文數(shù)字形容也不為過(guò)，這時(shí)解是非常之多的，用天文數(shù)字形容也不為過(guò)，這樣一來(lái)求解的過(guò)程就非常慢，并且出一個(gè)解也非常慢。樣一來(lái)求解的過(guò)程就非常慢，并且出一個(gè)解也非常慢。怎么才能快速地得到部分解呢？怎么才能快速地得到部分解呢？其實(shí)馬踏棋盤的問(wèn)題很早就有人提出，且早在其實(shí)馬踏棋盤的問(wèn)題很早就有人提出，且早在1823年，年，J.C.Warnsdorff就提出了一個(gè)有名的算就提出了一個(gè)有名的算法。在每個(gè)結(jié)點(diǎn)對(duì)其子結(jié)點(diǎn)進(jìn)行選取時(shí)，優(yōu)先選法。在每個(gè)結(jié)點(diǎn)對(duì)其子結(jié)點(diǎn)進(jìn)行選取時(shí)，優(yōu)先選擇擇出口出口最小的進(jìn)行搜索，最小的進(jìn)行搜索，出口出口的意思是的意思是在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個(gè)

23、數(shù)，也就在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個(gè)數(shù)，也就是是孫子孫子結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法選取，這是一種局部調(diào)整最優(yōu)的做法 .29 其實(shí)這種求解就是利用了貪心算法，它對(duì)整個(gè)求其實(shí)這種求解就是利用了貪心算法，它對(duì)整個(gè)求解過(guò)程的局部做最優(yōu)調(diào)整，它只適用于求較優(yōu)解或解過(guò)程的局部做最優(yōu)調(diào)整，它只適用于求較優(yōu)解或者部分解，而不能求最優(yōu)解。這樣的調(diào)整方法叫貪者部分解，而不能求最優(yōu)解。這樣的調(diào)整方法叫貪心策略，至于什么問(wèn)題需要什么樣的貪心策略是不心策略，至于什么問(wèn)題需要什么樣的貪心策略是不確定的，具體問(wèn)題具體分析。實(shí)驗(yàn)可以證明馬遍歷確定的，

24、具體問(wèn)題具體分析。實(shí)驗(yàn)可以證明馬遍歷問(wèn)題在運(yùn)用到了上面的貪心策略之后求解速率有非問(wèn)題在運(yùn)用到了上面的貪心策略之后求解速率有非常明顯的提高，如果只要求出一個(gè)解甚至不用回溯常明顯的提高，如果只要求出一個(gè)解甚至不用回溯就可以完成，因?yàn)樵谶@個(gè)算法提出的時(shí)候世界上還就可以完成，因?yàn)樵谶@個(gè)算法提出的時(shí)候世界上還沒(méi)有計(jì)算機(jī)，這種方法完全可以用手工求出解來(lái)，沒(méi)有計(jì)算機(jī)，這種方法完全可以用手工求出解來(lái)，其效率可想而知。其效率可想而知。 30下面我們給出馬踏棋盤問(wèn)題的下面我們給出馬踏棋盤問(wèn)題的c代碼（代碼（）：int ways_out(int x,int y) /計(jì)算結(jié)點(diǎn)出口多少計(jì)算結(jié)點(diǎn)出口多少 int i,co

25、unt=0,tx,ty; if(x0|y=N|y=N|sxy0) return -1;/-1表示該結(jié)點(diǎn)非法或者已經(jīng)跳過(guò)了表示該結(jié)點(diǎn)非法或者已經(jīng)跳過(guò)了 for(i=0;i8;+i) tx=x+dxi; ty=y+dyi; if(tx0|ty=N|ty=N) continue; if(stxty=0) +count; return count;31void sortnode(h_node *hn,int n)/采用簡(jiǎn)單排序法，采用簡(jiǎn)單排序法，因?yàn)樽咏Y(jié)點(diǎn)數(shù)最多只有因?yàn)樽咏Y(jié)點(diǎn)數(shù)最多只有8 /按結(jié)點(diǎn)出口進(jìn)行排序按結(jié)點(diǎn)出口進(jìn)行排序 int i,j,t; h_node temp; for(i=0;in;+i

26、) for(t=i,j=i+1;jn;+j) if(hnj.waysouti) temp=hni; hni=hnt; hnt=temp; 32void dfs(int x,int y,int count) /修改后的搜索函數(shù) int i,tx,ty; h_node hn8; if(countN*N) output_solution(); return; for(i=0;i8;+i)/求子結(jié)點(diǎn)和出口 hni.x=tx=x+dxi; hni.y=ty=y+dyi; hni.waysout=ways_out(tx,ty); sortnode(hn,8); 33for(i=0;hni.waysout0

27、;+i);/不考慮無(wú)用結(jié)點(diǎn) for(;i8;+i) tx=hni.x; ty=hni.y; stxty=count; dfs(tx,ty,count+1); stxty=0; 345.8 最小生成樹(shù)最小生成樹(shù) 假設(shè)已知一無(wú)向連通圖假設(shè)已知一無(wú)向連通圖G=(V,E)，其加權(quán)函數(shù)為，其加權(quán)函數(shù)為w:ER，我們希望找到圖我們希望找到圖G的最小生成樹(shù)。后文所討論的兩種算法都的最小生成樹(shù)。后文所討論的兩種算法都運(yùn)用了貪心方法，但在如何運(yùn)用貪心法上卻有所不同。運(yùn)用了貪心方法，但在如何運(yùn)用貪心法上卻有所不同。 下列的算法下列的算法GENERNIC-MIT正是采用了貪心算法，每步形正是采用了貪心算法，每步形成

28、最小生成樹(shù)的一條邊。算法設(shè)置了集合成最小生成樹(shù)的一條邊。算法設(shè)置了集合A，該集合一直是，該集合一直是某最小生成樹(shù)的子集。在每步?jīng)Q定是否把邊某最小生成樹(shù)的子集。在每步?jīng)Q定是否把邊(u,v)添加到集添加到集合合A中，其添加條件是中，其添加條件是A(u,v)仍然是最小生成樹(shù)的子集。仍然是最小生成樹(shù)的子集。我們稱這樣的邊為我們稱這樣的邊為A的安全邊，因?yàn)榭梢园踩匕阉砑拥降陌踩?，因?yàn)榭梢园踩匕阉砑拥紸中而不會(huì)破壞上述條件。中而不會(huì)破壞上述條件。 GENERNIC-MIT(G,W)1. A2. while A沒(méi)有形成一棵生成樹(shù)沒(méi)有形成一棵生成樹(shù)3 do 找出找出A的一條安全邊的一條安全邊(u,v

29、);4. AA(u,v);5. return A35定理定理5.1 設(shè)圖設(shè)圖G(V,E)是一無(wú)向連通圖，且在是一無(wú)向連通圖，且在E上定義了上定義了相應(yīng)的實(shí)數(shù)值加權(quán)函數(shù)相應(yīng)的實(shí)數(shù)值加權(quán)函數(shù)w，設(shè)，設(shè)A是是E的一個(gè)子集且包含的一個(gè)子集且包含于于G的某個(gè)最小生成樹(shù)中，割的某個(gè)最小生成樹(shù)中，割(S,V-S)是是G的不妨害的不妨害A的的任意割且邊任意割且邊(u,v)是穿過(guò)割是穿過(guò)割(S,V-S)的一條輕邊，則邊的一條輕邊，則邊(u,v)對(duì)集合對(duì)集合A是安全的。是安全的。下面介紹兩個(gè)算法：下面介紹兩個(gè)算法：Kruskal算法和算法和Prim算法算法(1) Kruskal算法算法 Kruskal算法是直接基

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

31、一種貪心算法，因?yàn)樗惴恳徊教砑拥缴种械倪叺臋?quán)值都盡可能小林中的邊的權(quán)值都盡可能小 36Kruskal算法的實(shí)現(xiàn)類似于計(jì)算連通支的算法。它使用了分算法的實(shí)現(xiàn)類似于計(jì)算連通支的算法。它使用了分離集合數(shù)據(jù)結(jié)構(gòu)以保持?jǐn)?shù)個(gè)互相分離的元素集合。通過(guò)離集合數(shù)據(jù)結(jié)構(gòu)以保持?jǐn)?shù)個(gè)互相分離的元素集合。通過(guò)FIND-SET(v)來(lái)確定兩結(jié)點(diǎn)來(lái)確定兩結(jié)點(diǎn)u和和v是否屬于同一棵樹(shù)，通過(guò)是否屬于同一棵樹(shù)，通過(guò)操作操作UNION來(lái)完成樹(shù)與樹(shù)的聯(lián)結(jié)。來(lái)完成樹(shù)與樹(shù)的聯(lián)結(jié)。 MST-KRUSKAL(G,w)1. A2. for 每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)v VG 3. do MAKE-SET(v)4. 根據(jù)權(quán)根據(jù)權(quán)w的非遞減順序?qū)Φ姆沁f

32、減順序?qū)的邊進(jìn)行排序的邊進(jìn)行排序5. for 每條邊每條邊(u,v)E，按權(quán)的非遞減次序，按權(quán)的非遞減次序6. do if FIND-SET(u) FIND-SET(v)7. then AA(u,v)8. UNION(u,v)9 return A37Kruskal算法在圖算法在圖G=(V,E)上的運(yùn)行時(shí)間取決于分離集合這一數(shù)上的運(yùn)行時(shí)間取決于分離集合這一數(shù)據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)。我們采用在分離集合中描述的按行結(jié)合和通路據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)。我們采用在分離集合中描述的按行結(jié)合和通路壓縮的啟發(fā)式方法來(lái)實(shí)現(xiàn)分離集合森林的結(jié)構(gòu)，這是由于從漸近壓縮的啟發(fā)式方法來(lái)實(shí)現(xiàn)分離集合森林的結(jié)構(gòu)，這是由于從漸近意義上來(lái)說(shuō)，這是

33、目前所知的最快的實(shí)現(xiàn)方法。意義上來(lái)說(shuō)，這是目前所知的最快的實(shí)現(xiàn)方法。(2) Prim算法算法Prim算法的特點(diǎn)是集合算法的特點(diǎn)是集合A中的邊總是只形成單棵樹(shù)。因中的邊總是只形成單棵樹(shù)。因?yàn)槊看翁砑拥綐?shù)中的邊都是使樹(shù)的權(quán)盡可能小的邊，因?yàn)槊看翁砑拥綐?shù)中的邊都是使樹(shù)的權(quán)盡可能小的邊，因此上述策略也是貪心的。有效實(shí)現(xiàn)此上述策略也是貪心的。有效實(shí)現(xiàn)Prim算法的關(guān)鍵是算法的關(guān)鍵是設(shè)法較容易地選擇一條新的邊添加到由設(shè)法較容易地選擇一條新的邊添加到由A的邊所形成的的邊所形成的樹(shù)中，在下面的偽代碼中，算法的輸入是連通圖樹(shù)中，在下面的偽代碼中，算法的輸入是連通圖G和將和將生成的最小生成樹(shù)的根生成的最小生成樹(shù)的

34、根r。在算法執(zhí)行過(guò)程中，不在樹(shù)。在算法執(zhí)行過(guò)程中，不在樹(shù)中的所有結(jié)點(diǎn)都駐留于優(yōu)先級(jí)基于中的所有結(jié)點(diǎn)都駐留于優(yōu)先級(jí)基于key域的隊(duì)列域的隊(duì)列Q中。中。對(duì)每個(gè)結(jié)點(diǎn)對(duì)每個(gè)結(jié)點(diǎn)v，keyv是連接是連接v到樹(shù)中結(jié)點(diǎn)的邊所具有的到樹(shù)中結(jié)點(diǎn)的邊所具有的最小權(quán)值；按常規(guī)，若不存在這樣的邊則最小權(quán)值；按常規(guī)，若不存在這樣的邊則keyv=。域域pv說(shuō)明樹(shù)中說(shuō)明樹(shù)中v的的“父母父母”。 38在算法執(zhí)行中，GENERIC-MST的集合A隱含地滿足： A=(v,pv)|vV-r-Q當(dāng)算法終止時(shí)，優(yōu)先隊(duì)列Q為空，因此G的最小生成樹(shù)A滿足: A=(v,pv)|v V-r MST-PRIM(G,w,r)1. QVG2. fo

35、r 每個(gè)uQ3. do keyu4. keyr05. prNIL6. while Q7. do uEXTRACT-MIN(Q)8. for 每個(gè)vAdju9. do if vQ and w(u,v)keyv10. then pvu11. keyvw(u,v)39Prim算法的性能分析算法的性能分析Prim算法的性能取決于我們?nèi)绾螌?shí)現(xiàn)優(yōu)先隊(duì)列算法的性能取決于我們?nèi)绾螌?shí)現(xiàn)優(yōu)先隊(duì)列Q。若用二。若用二叉堆來(lái)實(shí)現(xiàn)叉堆來(lái)實(shí)現(xiàn)Q,我們可以使用過(guò)程我們可以使用過(guò)程BUILD-HEAP來(lái)實(shí)現(xiàn)第來(lái)實(shí)現(xiàn)第1-4行的初始化部分，其運(yùn)行時(shí)間為行的初始化部分，其運(yùn)行時(shí)間為O(V)。循環(huán)需執(zhí)行。循環(huán)需執(zhí)行|V|次，次，且由

36、于每次且由于每次EXTRACT-MIN操作需要操作需要O(V)的時(shí)間，所以的時(shí)間，所以對(duì)對(duì)EXTRACT-MIN的全部調(diào)用所占用的時(shí)間為的全部調(diào)用所占用的時(shí)間為O(VV)。第第8-11行的行的for循環(huán)總共要執(zhí)行循環(huán)總共要執(zhí)行O(E)次，這是因?yàn)樗朽彺?，這是因?yàn)樗朽徑颖淼拈L(zhǎng)度和為接表的長(zhǎng)度和為2|E|。在。在for循環(huán)內(nèi)部，第循環(huán)內(nèi)部，第9行對(duì)隊(duì)列行對(duì)隊(duì)列Q的的成員條件進(jìn)行測(cè)試可以在常數(shù)時(shí)間內(nèi)完成，這是由于我們成員條件進(jìn)行測(cè)試可以在常數(shù)時(shí)間內(nèi)完成，這是由于我們可以為每個(gè)結(jié)點(diǎn)空出可以為每個(gè)結(jié)點(diǎn)空出1位位(bit)的空間來(lái)記錄該結(jié)點(diǎn)是否在的空間來(lái)記錄該結(jié)點(diǎn)是否在隊(duì)列隊(duì)列Q中，并在該結(jié)點(diǎn)被移出隊(duì)

37、列時(shí)隨時(shí)對(duì)該位進(jìn)行更新。中，并在該結(jié)點(diǎn)被移出隊(duì)列時(shí)隨時(shí)對(duì)該位進(jìn)行更新。第第11行的賦值語(yǔ)句隱含一個(gè)對(duì)堆進(jìn)行的行的賦值語(yǔ)句隱含一個(gè)對(duì)堆進(jìn)行的DECREASE-KEY操作，該操作在堆上可用操作，該操作在堆上可用0(V)的時(shí)間完成。因此，的時(shí)間完成。因此，Prim算法的整個(gè)運(yùn)行時(shí)間為算法的整個(gè)運(yùn)行時(shí)間為O(VV+EV)=O(EV)，從漸近，從漸近意義上來(lái)說(shuō)，它和實(shí)現(xiàn)意義上來(lái)說(shuō)，它和實(shí)現(xiàn)Kruskal算法的運(yùn)行時(shí)間相同。算法的運(yùn)行時(shí)間相同。 40通過(guò)使用通過(guò)使用Fibonacci堆，堆，Prim算法的漸近意義算法的漸近意義上的運(yùn)行時(shí)間可得到改進(jìn)。在上的運(yùn)行時(shí)間可得到改進(jìn)。在Fibonacci堆中堆中我

38、們己經(jīng)說(shuō)明，如果我們己經(jīng)說(shuō)明，如果|V|個(gè)元素被組織成個(gè)元素被組織成Fibonacci堆，可以在堆，可以在O(V)的平攤時(shí)間內(nèi)完的平攤時(shí)間內(nèi)完成成EXTRACT-MIN操作，在操作，在O(1)的平攤時(shí)間里的平攤時(shí)間里完成完成DECREASE-KEY操作（為實(shí)現(xiàn)第操作（為實(shí)現(xiàn)第11行的行的代碼），因此，若我們用代碼），因此，若我們用Fibonacci堆來(lái)實(shí)現(xiàn)堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列優(yōu)先隊(duì)列Q，Prim算法的運(yùn)行時(shí)間可以改進(jìn)為算法的運(yùn)行時(shí)間可以改進(jìn)為O(E+VV)。415.9 哈夫曼編碼哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常

39、在效的編碼方法。其壓縮率通常在20%90%之間。之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。 例如一個(gè)包含例如一個(gè)包含100,000個(gè)字符的文件，各字符出個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長(zhǎng)變碼需要現(xiàn)頻率不同，如下表所示。定長(zhǎng)變碼需要300,000位，而按表中變長(zhǎng)編碼方案，文件的總位，而按表中變長(zhǎng)編碼方案，文件的總碼長(zhǎng)為：碼長(zhǎng)為： （451+133+123+163+94+54）1000=224,000。比用定長(zhǎng)碼方案總碼長(zhǎng)較少約比用定長(zhǎng)碼方案總碼長(zhǎng)較少約45%。 42對(duì)每一個(gè)字符規(guī)定一個(gè)對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。綴碼。 編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。 表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)