計算理論與算法分析設(shè)計：04-greedy

貪心法（貪婪法）

貪心算法顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解：如單源最短路徑問題，最小生成樹問題等在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。2數(shù)錢

一出納員支付一定數(shù)量的現(xiàn)金。假設(shè)他手

中有各種面值的紙幣和硬幣，要求他用最

少的貨幣數(shù)支付規(guī)定的現(xiàn)金。

例如，現(xiàn)有4種硬幣：它們的面值分別為1

分、2分、5分和1角。要支付2角5分。首先支付2個1角硬幣，然后支付一個5分

硬幣，這就是貪心策略。3貪心法不一定能產(chǎn)生正確的答案。例如，若引進(jìn)一個“1角1分”的硬幣，設(shè)從如下集合{1,1,2,2,2,5,10,10,11,11}中數(shù)出25分，按貪心法，共4個硬幣。但最優(yōu)解僅為3個硬幣。這說明貪心法得到的解只是一個可行解。4貨郎擔(dān)（TSP）問題設(shè)售貨員要到五個城市去售貨，最后再回到出發(fā)的城市。已知從一個城市到其他城市的費(fèi)用，求總費(fèi)用最少的路線5權(quán)為13從不同結(jié)點(diǎn)出發(fā)：

依貪心算法

1）結(jié)點(diǎn)a為起點(diǎn)：

2）結(jié)點(diǎn)b為起點(diǎn)：

3）結(jié)點(diǎn)c為起點(diǎn)：

4）結(jié)點(diǎn)d為起點(diǎn)：權(quán)為13權(quán)為13權(quán)為13abcd213743或者156而實際上圖中最短哈密頓

回路的長度為12。即abcdaabcd2137437活動安排:問題描述有n個活動集E={1,2,…,n}使用同一資源，而同一時間內(nèi)同一資源只能由一個活動使用。每個活動的使用時間為[si,fi)i=1,…,n，si為開始時間，fi為結(jié)束時間，若[si,fi)與[sj,fj)不相交稱活動i和活動j是相容的，即當(dāng)si≥fj或sj≥fi時。問題：選出最大的相容活動子集合。8貪心策略將各活動按結(jié)束時間排序f1≤f2≤…≤fn，先選出活動1，然后按活動編好從小到大的次序依次選擇與當(dāng)前活動相容的活動。注：這種策略使剩余的可安排時間極大化，以便于安排盡可能多的相容活動。

9voidActivitySelection(intn,s[],f[],boola[]){//f[]已排序，a[]記錄選擇的活動，即a[i]=true表示活動i已選擇

a[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;}elsea[i]=false;}}T(n)=O(nlogn)10找出與之相容且結(jié)束時間最早的活動活動安排:計算示例11個活動已按結(jié)束時間排序，用貪心算法求解：

i1234567891011start_timei130535688212finish_timei456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活動：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a1111活動安排問題由于以活動完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。12活動安排問題貪心算法并不總能求得問題的整體最優(yōu)解對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大可以用數(shù)學(xué)歸納法證明13活動安排貪心算法最優(yōu)化證明首先，若活動安排E={1,2,…,n}問題有一個最優(yōu)解，其必包括活動1假設(shè)A是最優(yōu)解，且其第一個活動為kk=1：滿足k>1：設(shè)B=(A–{k})U{1}。由于f1<=fk，則若fk相容，則f1必相容，因為f1比fk先結(jié)束；故k應(yīng)設(shè)為1選擇活動1后，原問題就簡化為找出E中所有與活動1相容的活動A為E最優(yōu)解，則A’=A–{1}為E’={iE:si>=f1}的最優(yōu)解假設(shè)E’的最優(yōu)解為B’，則它應(yīng)含有比A’更多的活動因此B’+{1}大于A’+{1}，與A為最優(yōu)解矛盾144.2貪心算法的基本要素對于一個具體的問題是否可用貪心算法解此問題？能否得到問題的最優(yōu)解呢?從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)154.2貪心算法的基本要素貪心選擇性質(zhì)所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到貪心算法可行的第一個基本要素與動態(tài)規(guī)劃算法的主要區(qū)別動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題164.2貪心算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征174.2貪心算法的基本要素貪心算法與動態(tài)規(guī)劃算法的差異 共同點(diǎn)：都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)疑問：對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法？是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別0-1背包問題背包問題184.2貪心算法的基本要素0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。194.2貪心算法的基本要素背包問題：

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

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

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

已知一個容量大小為M重量的背包和n種物品，物品i的重量為wi,假定物品i的一部分xi放入背包會得到vixi這么大的收益，這里，0≤xi≤1，vi>0。采用怎樣的裝包方法才會使裝入背包的物品總效益最大？例：考慮以下情況下的背包問題

n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)22n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

1)按效益值非增次序?qū)⑽锲芬来畏湃氡嘲?/p>

(x1,x2,x3)ΣwixiΣvixi2)按物品重量的非降次序?qū)⑽锲芬来畏湃氡嘲?1,2/15,0)18+225+24*2/15=28.2(0,2/3,1)10+1015+24*2/3=3123n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

3)按vi/wi的非增次序?qū)⑽锲芬来畏湃氡嘲?/p>

(x1,x2,x3)ΣwixiΣvixi

(0,1,1/2)15+524+15/2=31.5算法：背包問題的貪心算法24voidGreedyKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//使v1/w1≥v2/w2≥…≥vn/wnfor(inti=1;i<=n;i++)x[i]=0;floatc=M;for(inti=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}25

算法的計算時間上界為O(nlogn)，主要用于排序操作。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。證明使用此貪心算法所得到的貪心解是一個最優(yōu)解。證明的基本思想是：把這個貪心解與任一個最優(yōu)解相比較，如果這兩個解不同，就去找開始不同的第一個xi，然后設(shè)法用貪心解的這個xi去代換最優(yōu)解的那個xi，并證明在分量作了代換之后其總效益與代換之前無任何損失。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解是最優(yōu)解。264.2貪心算法的基本要素對于0-1背包問題，貪心選擇不能得到最優(yōu)解它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的一個重要特征274.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。假設(shè)n=8,[w1,...,w8]=[100,200,50,90,150,50,20,80],c=400。28

4.3最優(yōu)裝載

從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。

29[w1,...,w8]=[100,200,50,90,150,50,20,80],c=400。

利用貪婪算法時，所考察貨箱的順序為7,3,6,8,4,1,5,2。貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載，剩下的裝載能力為10個單位，小于剩下的任何一個貨箱。在這種貪婪解決算法中得到[x1,...,x8]=[1,0,1,1,0,1,1,1]且∑xi=6。304.3最優(yōu)裝載voidContainerLoading(intx[],floatw[],floatc,intn){Sort(w,t,n);//此時,w[i]≤w[i+1]for(inti=1;i<=n;i++)//初始化xx[i]=0;for(i=1;i<=n&&w[i]<=c;i++){x[i]=1;c-=w[i];}//

剩余容量}T(n)=O(nlogn)314.3最優(yōu)裝載2.貪心選擇性質(zhì)最優(yōu)裝載問題具有貪心選擇性質(zhì)。3.最優(yōu)子結(jié)構(gòu)性質(zhì)

最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

32貪心算法性質(zhì)的通用證明方法通用證明步驟首先考察問題的一個整體最優(yōu)解，并嘗試通過貪心選擇來修改這個最優(yōu)解把這個貪心解與任一個最優(yōu)解相比較，如果這兩個解不同，就去找開始不同的第一個xi，然后設(shè)法用貪心解的這個xi去代換最優(yōu)解的那個xi，并證明在分量作了代換之后其總效益與代換之前無任何損失。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明貪心解是最優(yōu)解。334.3最優(yōu)裝載問題貪心性質(zhì)的證明

344.4哈夫曼編碼廣泛用于數(shù)據(jù)文件壓縮的編碼方法壓縮率通常在20%～90%之間用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長354.4哈夫曼編碼1、前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。消除解碼的歧義364.4哈夫曼編碼編碼的前綴性質(zhì)可以使譯碼方法非常簡單表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個兒子結(jié)點(diǎn)平均碼長定義為：使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。37

4.4哈夫曼編碼2、構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結(jié)點(diǎn)開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。384.4哈夫曼編碼編碼字符集中每一字符c的頻率是f(c)以f為鍵值的優(yōu)先隊列Q用在貪心選擇時確定當(dāng)前要合并的2棵具有最小頻率的樹2棵具有最小頻率的樹合并后產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。O(nlogn)39Huffman編碼某通訊系統(tǒng)只使用5種字符a、b、c、d、e，使用頻率分別為0.1,0.14,0.2,0.26,0.3,利用二叉樹設(shè)計不等長編碼：1）構(gòu)造以a、b、c、d、e為葉子的二叉樹；2）將該二叉樹所有左分枝標(biāo)記0，所有右

分枝標(biāo)記1；3）從根到葉子路徑上標(biāo)記作為葉子結(jié)點(diǎn)所

對應(yīng)字符的編碼；40

acbdea:000b:001c:01d:10e:115種字符a、b、c、d、e，使用頻率分別為0.1,0.14,0.2,0.26,0.3414.4哈夫曼編碼3、哈夫曼算法的正確性要證明哈夫曼算法的正確性，需證明(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)424.5單源最短路徑給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點(diǎn)，稱為源?，F(xiàn)在要計算從源到所有其它各頂點(diǎn)的最短路長度。這個問題通常稱為單源最短路徑問題。1、算法基本思想Dijkstra算法是單源最短路徑問題的貪心算法434.5單源最短路徑Dijkstra最短路：按路徑長度遞增的次序產(chǎn)生從源點(diǎn)v到其余各點(diǎn)的最短路徑。設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑(設(shè)其終點(diǎn)為x)，或者為有向邊(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)x的路徑。反證法：假設(shè)此路徑上有一個頂點(diǎn)y不在S中，則說明存在一條終點(diǎn)不在S而長度比此路徑短的路徑。但這是不可能的。因為我們是按路徑長度遞增的次序來產(chǎn)生各最短路徑的，故長度比此路徑短的所有路徑都已產(chǎn)生，它們的終點(diǎn)必在S中，即假設(shè)不成立。44最短路例10(v5)第1短V1V5V4V2V3V610101002050205030510v2v3v4v5v6step1503010010∞20(v4)第2短step2503020∞30(v3)第3短step34030∞35(v2)第4短step4355045(v6)第5短step545/V1/V5/V1/V3/V245例例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下頁的表中。Dijkstra算法的迭代過程：迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10/V1∞301001{1,2}26030/V11002{1,2,4}450/V4903{1,2,4,3}360/V34{1,2,4,3,5}51050306046算法的正確性和計算復(fù)雜性Dijkstra算法的正確性：(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)計算復(fù)雜性：對于具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要O(n)時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時間。算法的其余部分所需要時間不超過O(n2)。47小張被借調(diào)到一個新單位，圖中a點(diǎn)是小張

的住宅，z為新單位的位置，邊上的數(shù)字表

示距離，則小張到新單位的最短距離為__.a2z1292682795124311497361348最小生成樹最小生成樹的定義Kruskal算法Prim算法49網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。最小生成樹50最小生成樹

設(shè)G=(V,E)是一個無向連通帶權(quán)圖，如果G的一個子圖T’是一棵包含G的所有頂點(diǎn)的樹(G的生成樹)，生成樹T’上各邊權(quán)的總和(生成樹的耗費(fèi))最小，則T’稱為G的最小生成樹(MST：minimumspanningtree)144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS51Kruskal最小生成樹算法

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

5d34=5d23=5d12=6d35=6d56=653按Kruskal算法選取邊的過程如下圖所示。54Kruskal最小生成樹算法最小生成樹//在一個具有n個頂點(diǎ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)55Prim最小生成樹算法

Prim在1957