《算法設(shè)計(jì)與分析教學(xué)資料》第4章

第4章貪心算法1編輯ppt理解貪心算法的概念掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異理解貪心算法的一般理論學(xué)習(xí)要點(diǎn)2編輯ppt通過(guò)應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略（1）活動(dòng)安排問(wèn)題；（2）最優(yōu)裝載問(wèn)題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；（6）多機(jī)調(diào)度問(wèn)題。學(xué)習(xí)要點(diǎn)3編輯ppt問(wèn)題描述：有位顧客買了兩斤蘋果，需付3元7角，實(shí)付10元，你需找零6元3角。假設(shè)你抽屜里有一些硬幣，面值分別為：2元5角、1元、5角和1角，現(xiàn)在問(wèn)題是：怎么找?guī)抛羁欤ㄈ∮矌糯螖?shù)最少）？貪心算法的引入--找?guī)艈?wèn)題4編輯ppt問(wèn)題抽象：M=6.3，n=4V={2.5,1.0,0.5,0.1}（分量用vi表示）X={x1,x2,x3,x4}（xi>=0,i=1~4）問(wèn)題即求:

約束條件：

貪心算法的引入--找?guī)艈?wèn)題5編輯ppt貪心算法的引入--0-1背包問(wèn)題0-1背包問(wèn)題的形式化描述：約束條件：

結(jié)論：找?guī)艈?wèn)題可以使用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)！

思考：找?guī)艈?wèn)題還可以使用其他方法求解嗎？6編輯ppt一種更簡(jiǎn)單可行的方法：先取2.52枚價(jià)值2.5+2.5=5.0余6.3-5=1.3再取1.01枚價(jià)值1.0余1.3-1=0.3不取0.50枚因?yàn)?.5>0.3再取0.13枚價(jià)值0.1×3=0.3余0.3-0.3=0找零完畢。得最優(yōu)解X={2,1,0,3}，共需最少的硬幣數(shù)6枚。方法總結(jié)：在不超余額的前提下，每次都找最大面值的硬幣。這種找?guī)诺姆椒ń凶鲐澬乃惴?。思考：有沒有可能不是最好的方法？貪心算法的引入--找?guī)艈?wèn)題7編輯ppt顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹問(wèn)題等。貪心算法—描述8編輯ppt在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。動(dòng)態(tài)規(guī)劃一定可以得到問(wèn)題最優(yōu)解，而貪心算法不一定，這也是貪心算法使用的困難之處，如何去證明它得到的是問(wèn)題需要的解。貪心算法—描述9編輯ppt貪心算法—描述10編輯ppt貪心算法—基本思想11編輯ppt貪心算法—基本思想12編輯ppt活動(dòng)安排問(wèn)題—引入新學(xué)期來(lái)臨，為迎接新生，各院系都要舉辦迎新晚會(huì)。時(shí)間將近，各院系在申請(qǐng)使用學(xué)院禮堂進(jìn)行彩排。為了提高禮堂使用率，決定白天不間斷的開放，各院系可以上報(bào)各自使用的時(shí)間區(qū)間（開始時(shí)間以及終止時(shí)間，時(shí)間長(zhǎng)短不限），由禮堂管理人員安排盡可能多的院系在同一天里彩排。請(qǐng)根據(jù)以下時(shí)間段盡可能多安排幾個(gè)院系：[8:00,10:30),[9:00,11:30),[7:00,11:00),[11:30-14:00),[12:00,13:30),[13:00,15:30),[15:00,16:00),[14:30,16:00),[16:00,18:00)13編輯ppt活動(dòng)安排問(wèn)題—描述活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的典型例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。14編輯ppt活動(dòng)安排問(wèn)題—描述設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源（爭(zhēng)用！）。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在時(shí)間的半開半閉區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。15編輯ppt活動(dòng)安排問(wèn)題—解決方案將各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中，且按結(jié)束時(shí)間的非減序排列：

f1<=f2<=f3......<=fn即需要先對(duì)各活動(dòng)按結(jié)束時(shí)間排序。如：[2,3),[1,4),[3,5),[1,2)按結(jié)束時(shí)間排序后：[1,2),[2,3),[1,4),[3,5)剩余時(shí)間越多，可安排的活動(dòng)就越多！16編輯ppt活動(dòng)安排問(wèn)題—算法實(shí)現(xiàn)publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;//加入最早結(jié)束的活動(dòng)intj=1;//剛加入集合的活動(dòng)號(hào)intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;//j用以記錄最近一次加入到集合A中的活動(dòng)count++;}elsea[i]=false;}returncount;}各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

17編輯ppt活動(dòng)安排問(wèn)題—算法分析由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法GreedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。18編輯ppt活動(dòng)安排問(wèn)題—算法分析算法GreedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列時(shí)，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。19編輯ppt

例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314活動(dòng)安排問(wèn)題—示例20編輯ppt活動(dòng)安排問(wèn)題—示例21編輯ppt計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)已選入集合，而空白長(zhǎng)條表示當(dāng)前正在檢查相容性的活動(dòng)。若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。22編輯ppt活動(dòng)安排問(wèn)題—結(jié)論考慮：完整的算法如何實(shí)現(xiàn)？23編輯ppt貪心算法的基本要素下面著重討論可以用貪心算法求解的問(wèn)題的一般特征。對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)24編輯ppt1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。貪心算法的基本要素—貪心選擇性質(zhì)25編輯ppt貪心算法的基本要素—貪心選擇性質(zhì)1.貪心選擇性質(zhì)動(dòng)態(tài)規(guī)劃算法中，每步所作的選擇往往依賴于相關(guān)子問(wèn)題的解。因此，動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。26編輯ppt2.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。

貪心算法的基本要素—最優(yōu)子結(jié)構(gòu)性質(zhì)27編輯ppt以下證明活動(dòng)安排問(wèn)題具備這兩個(gè)基本要素，即可由貪心算法求最優(yōu)解。貪心算法的基本要素—活動(dòng)安排問(wèn)題28編輯ppt設(shè)E＝{1,2,…,n}為所給的活動(dòng)集合。E中活動(dòng)按結(jié)束時(shí)間的非減序排列，故活動(dòng)1具有最早的完成時(shí)間。首先，需要證明活動(dòng)安排問(wèn)題有一個(gè)（僅有一個(gè)？）最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動(dòng)1。活動(dòng)安排問(wèn)題--貪心選擇性質(zhì)29編輯ppt設(shè)A是E的一個(gè)子集，且A是所給的活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解，且A中活動(dòng)也按結(jié)束時(shí)間非減序排列，A中第一個(gè)活動(dòng)是活動(dòng)k。若k=1，則A中第一個(gè)活動(dòng)是活動(dòng)1，活動(dòng)1是E中最早結(jié)束的，即A就是一個(gè)以貪心選擇開始的最優(yōu)解。若k>1，則我們可以設(shè)B=(A-{k})∪{1}.即用活動(dòng)1替換掉活動(dòng)k，由于f1≤fk，且A中活動(dòng)是互為相容的，故B中活動(dòng)也是互為相容的（說(shuō)明B是一個(gè)可行解）。又B中活動(dòng)個(gè)數(shù)與A中活動(dòng)個(gè)數(shù)相等，且A是最優(yōu)的，則B也是最優(yōu)的。活動(dòng)安排問(wèn)題--貪心選擇性質(zhì)30編輯ppt也就是說(shuō)，B是一個(gè)以貪心選擇活動(dòng)1開始的最優(yōu)活動(dòng)安排。因此，我們證明了總存在一個(gè)以貪心選擇開始的最優(yōu)活動(dòng)安排方案（a）。以下證明在貪心選擇了活動(dòng)1之后，原問(wèn)題簡(jiǎn)化為對(duì)E中所有與1相容的活動(dòng)進(jìn)行活動(dòng)安排的子問(wèn)題?；顒?dòng)安排問(wèn)題--貪心選擇性質(zhì)31編輯ppt若A是原問(wèn)題的一個(gè)以貪心選擇開始的最優(yōu)解，則A’=A-{1}是活動(dòng)安排問(wèn)題E’={i∈E:si≥f1}的一個(gè)最優(yōu)解。-－最優(yōu)子結(jié)構(gòu)性質(zhì)證明：如能找到E’的一個(gè)解B’，它包含比A’更多的活動(dòng)，則將活動(dòng)1加入B’中將產(chǎn)生E的一個(gè)解B，它包含比A更多的活動(dòng)。這與A的最優(yōu)性矛盾?；顒?dòng)安排問(wèn)題--最優(yōu)子結(jié)構(gòu)性質(zhì)32編輯ppt因此，每一步所作的貪心選擇都將問(wèn)題簡(jiǎn)化為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題（b）。綜合a和b，對(duì)貪心選擇的次數(shù)用數(shù)學(xué)歸納法即知，貪心算法GreedySelector最終產(chǎn)生原問(wèn)題的一個(gè)最優(yōu)解?；顒?dòng)安排問(wèn)題--最優(yōu)子結(jié)構(gòu)性質(zhì)33編輯ppt貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。34編輯ppt0-1背包和一般背包問(wèn)題35編輯ppt0-1背包和一般背包問(wèn)題0-1背包問(wèn)題：

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。36編輯ppt0-1背包和一般背包問(wèn)題一般背包問(wèn)題（簡(jiǎn)稱背包問(wèn)題）：

37編輯ppt0-1背包和一般背包問(wèn)題一般背包問(wèn)題（簡(jiǎn)稱背包問(wèn)題）：與0-1背包問(wèn)題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。38編輯ppt0-1背包和一般背包問(wèn)題一般背包問(wèn)題（簡(jiǎn)稱背包問(wèn)題）：

39編輯ppt0-1背包和一般背包問(wèn)題貪心選擇的策略有哪些呢？每次從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品。從剩下的物品中選擇可裝入背包的重量最小的物品。從剩余物品中選擇可裝入包的vi/wi

值（性價(jià)比—效益值）最大的物品。40編輯ppt0-1背包和一般背包問(wèn)題41編輯ppt0-1背包和一般背包問(wèn)題42編輯ppt0-1背包和一般背包問(wèn)題43編輯ppt0-1背包和一般背包問(wèn)題44編輯ppt0-1背包和一般背包問(wèn)題用貪心算法解背包問(wèn)題的基本步驟：首先，計(jì)算每種物品單位重量的價(jià)值Vi/Wi；然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。45編輯pptpublicstaticfloatknapsack(floatc,float[]w,float[]v,float[]x){intn=v.length;Element[]d=newElement[n];for(inti=0;i<n;i++)d[i]=newElement(w[i],v[i],i);MergeSort.mergeSort(d);inti;floatopt=0;for(i=0;i<n;i++)x[i]=0;for(i=0;i<n;i++){if(d[i].w>c)break;x[d[i].i]=1;opt+=d[i].v;c-=d[i].w;}if(i<n){x[d[i].i]=c/d[i].w;opt+=x[d[i].i]*d[i].v;}returnopt;}算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。當(dāng)然，為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)。46編輯ppt0-1背包和一般背包問(wèn)題實(shí)例：背包容量50千克；物品1重10千克，價(jià)值60元；物品2重20千克，價(jià)值100元；物品3重30千克，價(jià)值120元。若該實(shí)例為背包問(wèn)題，則可用貪心算法求得最優(yōu)解240；若該實(shí)例為0-1背包問(wèn)題，則用貪心算法求得解為160，而最優(yōu)解實(shí)為220(由動(dòng)態(tài)規(guī)劃法求得)。47編輯ppt0-1背包和一般背包問(wèn)題對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。48編輯ppt0-1背包和一般背包問(wèn)題雖然使用貪心選擇不能保證得到0-1背包的最優(yōu)解，但它是一個(gè)直覺上近似的解。在600個(gè)隨機(jī)產(chǎn)生的0-1背包問(wèn)題中，用這種啟發(fā)式貪婪算法來(lái)解有239題可得到最優(yōu)解，所有600個(gè)答案與最優(yōu)解之差全在25%以內(nèi)。49編輯ppt0-1背包和一般背包問(wèn)題事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。50編輯ppt貪心算法的局限性51編輯ppt貪心算法的特點(diǎn)52編輯ppt哈夫曼編碼—描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0,1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符以較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。53編輯ppt哈夫曼編碼—回憶54編輯ppt哈夫曼編碼—回憶55編輯ppt哈夫曼編碼—回憶解決的問(wèn)題:通訊過(guò)程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)制碼。由于英文字母使用頻率不同,若頻率高的字母對(duì)應(yīng)短的編碼,頻率低的字母對(duì)應(yīng)長(zhǎng)的編碼,傳輸?shù)臄?shù)據(jù)總量就會(huì)降低。要求找到一個(gè)編碼方案,使傳輸?shù)臄?shù)據(jù)量最少。

56編輯ppt哈夫曼編碼—前綴碼哈夫曼編碼是一種前綴碼。1、前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。57編輯ppt哈夫曼編碼—前綴碼非前綴碼 如：abcd01010111

試譯出：1010

結(jié)果會(huì)有兩種：bb或ca

原因在于：b的代碼是c的代碼的前綴。哈夫曼編碼是一種前綴碼，可以避免以上情況。58編輯ppt哈夫曼編碼—前綴碼

編碼的前綴性質(zhì)使譯碼方法非常簡(jiǎn)單。

001011101(P96表4.1) →001011101aabe59編輯ppt哈夫曼編碼—前綴碼用二叉樹作為前綴編碼的數(shù)據(jù)結(jié)構(gòu)（why?）表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹（定義有什么問(wèn)題？）樹中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。每個(gè)葉子對(duì)應(yīng)字符集中的一個(gè)字符。

60編輯ppt哈夫曼編碼—前綴碼定義：f(c)是字符集C中字符c的出現(xiàn)頻率，dT(c)是葉子結(jié)點(diǎn)c在樹中的深度（此時(shí)根的深度應(yīng)該是多少？）。 則：平均碼長(zhǎng)定義為：使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為字符集C的一個(gè)最優(yōu)前綴碼。61編輯ppt哈夫曼編碼—構(gòu)造2、構(gòu)造哈夫曼編碼德國(guó)數(shù)學(xué)家哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼算法。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。

62編輯ppt哈夫曼編碼—構(gòu)造貪心準(zhǔn)則：每次找出具有最小頻率的兩棵樹合并

63編輯ppt哈夫曼編碼—構(gòu)造算法思路：1)以n個(gè)字母為結(jié)點(diǎn)構(gòu)成n棵僅含一個(gè)點(diǎn)的二叉樹集合,字母的頻率即為結(jié)點(diǎn)的權(quán)2)每次從二叉樹集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹：增加一個(gè)根結(jié)點(diǎn)將這兩棵樹作為左右子樹，新樹的權(quán)為兩棵子樹的權(quán)之和3)反復(fù)進(jìn)行步驟2)直到只剩一棵樹為止

64編輯ppt設(shè)在1000個(gè)字母的文章中各字母出現(xiàn)的頻率為:

a:83,b:14,c:28,d:38,e:131,f:29,g:20,h:53......1420282938538313134282938538313134573853831315772538313172110831311101551311552413963961552411101315357728334382829142010101010101010最佳編碼:a:10;b:1111;c:0101;d:110;e:00;f:0100;g:1110;h:0111)將權(quán)從小到大排序2)每次選取最小權(quán)合并編輯ppt哈夫曼編碼—構(gòu)造哈夫曼算法構(gòu)造哈夫曼樹的具體過(guò)程：

一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹T。

66編輯ppttemplate<classT>BinaryTree<int>HuffmanTree(Tf[],intn){//根據(jù)權(quán)f[1:n]構(gòu)造哈夫曼樹

//創(chuàng)建一個(gè)單節(jié)點(diǎn)樹的數(shù)組

Huffman<T>*W=newHuffman<T>[n+1]；//構(gòu)造n個(gè)Huffman對(duì)象W

BinaryTree<int>z,zero；//初始化空樹

for(inti=1；i<=n；i++){z.MakeTree(i,zero,zero)；//構(gòu)造節(jié)點(diǎn)左、右孩子為空的樹

W[i].weight=f[i]；

W[i].tree=z:}//用字符集C中每一個(gè)字符c的頻率f(c)初始化節(jié)點(diǎn)

//數(shù)組變成—個(gè)最小堆,建立優(yōu)先隊(duì)列

MinHeap<Huffman<T>>Q(1)；

Q.Initialize(w,n,n)；

哈夫曼樹算法編輯ppt//將堆中的樹不斷合并Huffman<T>x,yfor(i=1;i<n;i++){//從Q中取出具有最小頻率的兩棵樹x和yQ.DeleteMin(x)；

Q.DeleteMin(y)；//將x和y合并為一棵新樹z

z.MakeTree(0,x.tree,y.tree)；//z的頻率是x和y的頻率之和

x.weight+=y.weight；x.tree=z；

Q.Insert(x)；}Q.DeleteMin(x)；//最后的樹

Q.Deactivate()；

delete[]w；

returnx.tree；哈夫曼樹算法編輯ppt哈夫曼編碼—構(gòu)造算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。

69編輯ppt哈夫曼樹算法算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間;最小堆的DeleteMin和Insert運(yùn)算均需O(logn)時(shí)間,n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。70編輯ppt哈夫曼編碼—正確性3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問(wèn)題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。71編輯ppt最優(yōu)子結(jié)構(gòu):

設(shè)T為帶權(quán)w1≤w2≤...≤wt的最優(yōu)樹,若將以帶權(quán)w1和w2的樹葉為兒子的分枝點(diǎn)改為帶權(quán)w1+w2的樹葉,得到一棵新樹T',則T'也是最優(yōu)樹。貪心選擇性

:設(shè)T為帶權(quán)w1≤w2≤...≤wt的最優(yōu)樹,a).帶權(quán)w1和w2的樹葉vw1和vw2是兄弟.b).以vw1和vw2為兒子的分枝點(diǎn),其通路長(zhǎng)度最長(zhǎng).算法分析HuffmanTree初始化優(yōu)先隊(duì)列Q需要O(n)DeleteMin和Insert需O(logn).n-1次的合并總共需要O(nlogn)所以n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)哈夫曼樹算法哈夫曼編碼—正確性編輯ppt單源最短路徑—描述單源最短路徑問(wèn)題:給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。給定V中的一個(gè)頂點(diǎn)，稱為源。計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路徑上各邊權(quán)之和。73編輯ppt單源最短路徑—基本思想Dijkstra(迪杰斯特拉

)算法是解單源最短路徑問(wèn)題的貪心算法?；舅枷?一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇（是什么？）來(lái)擴(kuò)充這個(gè)集合。74編輯ppt單源最短路徑—基本思想貪心策略：

每次都從V-S中找出具有最短特殊路長(zhǎng)的頂點(diǎn)u加入S。75編輯ppt單源最短路徑—基本思想算法思路：初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。76編輯ppt單源最短路徑—基本思想算法思路：Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了V中所有頂點(diǎn)，dist就記錄了從源到其它所有頂點(diǎn)之間的最短路徑長(zhǎng)度。77編輯ppt單源最短路徑—示例 例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其他頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。78編輯ppt單源最短路徑—示例Dijkstra算法的迭代過(guò)程：

迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}110maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}51050306079編輯ppt單源最短路徑—算法描述Template<classtype>VoidDijkstra(intn,intv,Typedist[],intprev[],Type**c){//單源最短路徑問(wèn)題的Dijkstra算法

//初始化bools[maxint];//頂點(diǎn)集合s，maxint是大整數(shù)

for(inti=1;i<=n;i++)//n個(gè)頂點(diǎn)

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

//c[v][i]表示邊(v,i)的權(quán)—鄰接矩陣

//dist[i]表示從源v到i的最短路長(zhǎng)

s[i]=false;

if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;//prev[i]表示從源到i的路徑上i之前的那個(gè)點(diǎn)

}80編輯ppt單源最短路徑—算法描述

//初始s中僅含源v

dist[v]=0;s[v]=true;

//迭代n-1次，把所有點(diǎn)加入s

for(inti=1;i<n;i++){//找到具有最短特殊路長(zhǎng)度的頂點(diǎn)uinttemp=maxint;intu=v;for(intj=1;j<=n;j++)if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}s[u]=true;81編輯ppt單源最短路徑—算法描述

//對(duì)數(shù)組dist作必要的修改for(intj=1;j<=n;j++)if((!s[j])&&(c[u][j]<maxint)){Typenewdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;

prev[j]=u;}}}}82編輯ppt單源最短路徑—分析算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)。83編輯ppt最小生成樹—描述設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。

84編輯ppt最小生成樹—描述網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。

85編輯ppt最小生成樹—描述用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)。86編輯ppt最小生成樹—性質(zhì)1、最小生成樹性質(zhì)設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(i,j)E，且iU，jV-U，且在所有這樣的邊