第四章 貪心算法

第四章貪心算法(GreedyAlgorithms)

貪心算法基本原理用貪心法求解一些問題，如：哈夫曼編碼

本章提要：

最優(yōu)裝載問題活動(dòng)安排問題單源最短路徑問題

最小生成樹

1

我們可能會(huì)想到用動(dòng)態(tài)規(guī)劃法去求解最優(yōu)化問題。但有時(shí)用貪心算法會(huì)更簡(jiǎn)單、有效。例子：背包問題：給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為W。問應(yīng)如何選擇物品裝入背包，使得裝入背包中的物品的總價(jià)值最大？在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分,而不一定要全部裝入背包。貪心算法：每次選vi/wi最大的物品i放進(jìn)包中。

背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動(dòng)態(tài)規(guī)劃算法來解。但是，用貪心算法更簡(jiǎn)單，解題效率更高。2

貪心算法總是做出在當(dāng)前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，所以貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解。例子：0-1背包問題：給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇物品裝入背包，使得裝入背包中的物品的總價(jià)值最大？在選擇物品裝入背包時(shí)，對(duì)每種物品i只有兩種選擇，要么裝入，要么不裝入，不能將物品i裝入背包多次，也不能只裝入物品i的一部分。因此，該問題稱為0-1背包問題。

0-1背包問題也具有最優(yōu)子結(jié)構(gòu)性質(zhì)。但是0-1背包問題卻不能用貪心算法求解。

對(duì)于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樗鼰o法保證最終將背包裝滿，部分背包空間的閑置使每公斤背包空間所具有的價(jià)值降低了。(該問題不具有貪心選擇性)例：背包容量C=10，n=3，三個(gè)物品的重量W={3,5,7}，三個(gè)物品的價(jià)值V={9,10,12}。貪心法裝入背包的價(jià)值為19。但最優(yōu)值是21。3

雖然貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問題能產(chǎn)生整體最優(yōu)解。如：?jiǎn)卧醋疃搪方?jīng)問題，最小生成樹問題，哈夫曼編碼問題等。

在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但卻是最優(yōu)解的很好的近似解。如：在下圖中求從V0到V3的最短路徑問題。

V0V12V13V21V11V23V22V34672414351214一、活動(dòng)安排問題

（Anactivity-selectionproblem）<1>問題的定義

活動(dòng)安排問題是可以用貪心算法有效求解的一個(gè)很好的例子。活動(dòng)

設(shè)有n個(gè)活動(dòng)的集合E＝{１,２,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只允許一個(gè)活動(dòng)使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi，且si<fi。如果選擇了活動(dòng)i，則它在半開的時(shí)間區(qū)間(si，fi]內(nèi)占用資源。5相容活動(dòng)

若區(qū)間［si，fi］與區(qū)間［sj，fj］不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)sj≥fi或si

≥fj時(shí)，活動(dòng)i與活動(dòng)j是相容。問題定義

活動(dòng)安排問題是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合。sifisjfjtsjfifjsifjsi相容！相容！不相容！6<2>算法設(shè)計(jì)貪心思想：為了選擇最多的相容活動(dòng)，每次選fi

最小的活動(dòng)，使剩余的可安排時(shí)間段極大化，以便接待盡可能多的相容活動(dòng)。輸入：

各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s[n]和f[n]中，且按結(jié)束時(shí)間的非減序：f1≤f2≤…≤fn排列。輸出：

最大相容活動(dòng)子集A。7例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：

按貪心算法計(jì)算最大相容活動(dòng)子集A的過程如下:

A={1}

與活動(dòng)1相容的剩余活動(dòng)集為：

{4，6，7，8，9，11}A={1,4}

與活動(dòng)4相容的剩余活動(dòng)集為：

{8，9，11}A={1,4,8}

與活動(dòng)8相容的剩余活動(dòng)集為：

{11}A={1,4,8,11}與活動(dòng)11相容的剩余活動(dòng)集為：

{}i1234567891011s[i]130535688212f[i]45678910111213148算法：Template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;

int

j=1;

//

j用以記錄最近一次加入到A中的活動(dòng)。

for(inti=2;i<=n;i++){if（s[i]>=f[j]）

{A[i]=true;

j=i;

}elseA[i]=false;}}算法的時(shí)間復(fù)雜性：當(dāng)結(jié)束時(shí)間已排序，T(n)=θ(n)。當(dāng)結(jié)束時(shí)間未排序，T(n)=θ(n)+θ(nlogn)。9<3>算法正確性證明1.證明問題具有優(yōu)化子結(jié)構(gòu)引理1

設(shè)S={1,2,…,n}是n個(gè)活動(dòng)集合，[sj，fj]是活動(dòng)的起止時(shí)間，且f1≤f2≤…≤fn，則S的活動(dòng)選擇問題的某個(gè)優(yōu)化解包括活動(dòng)1。證：設(shè)A是一個(gè)優(yōu)化解，按結(jié)束時(shí)間排序A中活動(dòng)，設(shè)其第一個(gè)活動(dòng)為k，第二個(gè)活動(dòng)為j。如果k=1，引理成立。如果k≠1，令B=A-{k}∪{1}，由于A中的活動(dòng)相容，f1≤fk≤sj，B中的活動(dòng)相容。因?yàn)閨B|=|A|，所以B是一個(gè)優(yōu)化解，且包含活動(dòng)1。10定理1

設(shè)S={1,2,…,n}是n個(gè)活動(dòng)集合，[sj，fj]是活動(dòng)j(1≤j≤n)的起止時(shí)間，且f1≤f2≤…≤fn。設(shè)A是S的調(diào)度問題的一個(gè)優(yōu)化解，且包括活動(dòng)1，則A2=A-{1}是S2={j∈S|sj≥f1}的調(diào)度問題的優(yōu)化解。證：顯然，A2中的活動(dòng)是相容的。

我們僅需要證明A2是最大的。

若不然，存在一個(gè)S2的活動(dòng)選擇問題的優(yōu)化解B2，|B2|>|A2|。

令B={1}∪B2，對(duì)于j∈S2，sj≥f1，B中活動(dòng)相容。B是S的一個(gè)解。

由于|A|=|A2|+1，|B|=|B2|+1>

|A2|+1=|A|，

與|A|最大矛盾。定理1說明活動(dòng)選擇問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。112.證明問題具有貪心選擇性定理2

設(shè)S={1,2,…,n}是n個(gè)活動(dòng)集合，[sj，fj]是活動(dòng)j的起止時(shí)間，且f1≤f2≤…≤fn。li是Si

={j∈S|sj≥fl

i-1}中具有最小結(jié)束時(shí)間fli的活動(dòng)(設(shè)l0=0，f0=0)。設(shè)A是S的包含活動(dòng)1的優(yōu)化解，則A=

。證：對(duì)|A|作歸納法（即對(duì)貪心選擇的次數(shù)作歸納法）。

當(dāng)|A|=1時(shí)，由引理１，命題成立；

設(shè)|A|<k時(shí)，命題成立；

當(dāng)|A|=k時(shí)，A={1}∪A2,

由定理1，A2是S２={j∈S|sj≥f1}的優(yōu)化解。

由歸納假設(shè)，A2=

。于是，A=。定理2說明活動(dòng)選擇問題具有貪心選擇性。123.GREEDY_ACTIVITY-SELECTOR算法是按定理2的Greedy選擇性進(jìn)行局部?jī)?yōu)化選擇的。

因此，GREEDY_ACTIVITY_SELECTOR算法對(duì)于活動(dòng)安排問題來說，總能求得整體最優(yōu)解(即相容活動(dòng)集合A的規(guī)模最大)。13二、Greedy算法的基本原理

<1>Greedy算法的基本思想求解最優(yōu)化問題的算法包含一系列步驟。每一步都在一組選擇中做出在當(dāng)前看來最好的選擇。希望通過做出局部?jī)?yōu)化選擇達(dá)到全局優(yōu)化選擇。Greedy算法不一定總產(chǎn)生優(yōu)化解，所以一個(gè)Greedy算法是否產(chǎn)生優(yōu)化解，需要嚴(yán)格證明。14<2>可用Greedy方法的條件

①Optimalsubstructure（最優(yōu)子結(jié)構(gòu)性質(zhì)）②Greedy-choiceproperty（貪心選擇性質(zhì)）定義1（最優(yōu)子結(jié)構(gòu)性質(zhì)）

若一個(gè)問題的優(yōu)化解包括它的子問題的優(yōu)化解，則稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。定義2（greedy選擇性質(zhì)）

若一個(gè)優(yōu)化問題的全局優(yōu)化解可以通過局部?jī)?yōu)化選擇得到，則該問題稱為具有g(shù)reedy選擇性質(zhì)。15<3>Greedy算法正確性證明方法

①證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu)；②證明算法所求解的問題具有Greedy選擇性；③算法按②中的Greedy選擇性進(jìn)行局部?jī)?yōu)化選擇。16<4>與動(dòng)態(tài)規(guī)劃方法的比較

動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇—依賴于子問題的解。貪心方法：每一步作一個(gè)選擇—不依賴于子問題的解。

可用動(dòng)態(tài)規(guī)劃方法的條件：最優(yōu)子結(jié)構(gòu)性質(zhì)；子問題的重疊性質(zhì)；子問題空間小。

可用貪心方法的條件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動(dòng)態(tài)規(guī)劃：自底向上求解；貪心方法：自定頂向下求解。可用貪心法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用；可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心法可能不適用。17

其中，xi∈{0,1},1≤i≤n(n是集裝箱總數(shù))，

<1>問題定義有一批集裝箱要裝上一艘載重量為c的輪船。其中，集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定，在裝載體積不受限制的情況下，應(yīng)如何裝載才能將盡可能多的集裝箱裝上輪船。該問題可形式化地描述為:三、最優(yōu)裝載問題(LoadingProblem)

18<2>算法基本思想：

用重量最輕者先裝的貪心策略。由此可產(chǎn)生裝載問題的最優(yōu)解。輸入：

n個(gè)集裝箱的重量，輪船的載重量c。輸出：

裝進(jìn)輪船的集裝箱編號(hào)。19算法：Template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];

Sort(w,t,n);//數(shù)組元素t[i]存放重量第i輕的集裝箱號(hào)。

for(inti=1;i<=n;i++)

x[i]=0;//數(shù)組元素x[i]=0表示不裝入集裝箱i。

for(inti=1;i<=n&&w[t[i]]<=c;i++) {x[t[i]]=1;c-=w[t[i]];}}算法復(fù)雜性：算法的主要計(jì)算量是將集裝箱依其重量從小到大排序，∴T(n)=O(nlogn)+O(n)=O(nlogn)20四、哈夫曼編碼(Huffmancodes)<1>問題定義二進(jìn)制字符編碼：

每個(gè)字符用一個(gè)二進(jìn)制0,1串來表示。固定長(zhǎng)編碼：每個(gè)字符都用等長(zhǎng)的0,1串來表示?？勺冮L(zhǎng)編碼：經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的字符用長(zhǎng)碼。前綴編碼：無任何字符的編碼是另一個(gè)字符編碼的前綴。21前綴碼的哈夫曼樹表示每個(gè)字符的編碼:

從根到對(duì)應(yīng)的葉路徑上的0,1串。100A:4555012530C:12B:13E:9D:1614F:511110000葉結(jié)點(diǎn)：用字符及其出現(xiàn)頻數(shù)標(biāo)記。邊標(biāo)記：一個(gè)結(jié)點(diǎn)的左側(cè)邊標(biāo)記為0,右側(cè)邊標(biāo)記為1。內(nèi)結(jié)點(diǎn)：其子樹的葉子頻數(shù)和。22問題定義

給定編碼字符集C及其概率分布f，即C中任意字符c以概率f(c)在數(shù)據(jù)文件中出現(xiàn)。C的一個(gè)前綴編碼方案對(duì)應(yīng)一棵二叉樹T。字符c在樹T中的深度記為dT(c)。dT(c)也是字符c的前綴碼長(zhǎng)。該編碼方案的平均碼長(zhǎng)定義為：。目標(biāo)：求出使平均碼長(zhǎng)最小的前綴編碼方案――哈夫曼編碼。23

<２>構(gòu)造最優(yōu)前綴碼的哈夫曼算法基本思想：

循環(huán)地選擇具有最低頻率的兩個(gè)根結(jié)點(diǎn)，生成一棵子樹，直到形成樹。輸入：

字符表C={c1,c2,…,cn},

及其相應(yīng)的權(quán)。輸出：

Huffman樹。24算法：HUFFMAN(C)//使用堆操作實(shí)現(xiàn)

{n=|C|;Q=Initialize（C）;//初始建堆。優(yōu)先隊(duì)列用堆來實(shí)現(xiàn)。

for(i=1;i<n;i++){z=malloc(sizeof(node));x=DeleteMin(Q);//堆操作

y=DeleteMin(Q);//堆操作

z->lchild=x;z->rchild=y;z->f=x->f+y->f;

Insert(z,Q);//堆操作

}

return(DeleteMin(Q));}初始建堆需O(n)時(shí)間循環(huán)n-1次每個(gè)堆操作需O(logn)時(shí)間算法的時(shí)間復(fù)雜性：T(n)=O(n)+O(nlogn)=O(nlogn)25算法復(fù)雜性分析：

設(shè)優(yōu)先隊(duì)列Q由一個(gè)堆實(shí)現(xiàn)。第二步使用堆排序的初始建堆算法實(shí)現(xiàn)，需要的時(shí)間為O(n);

每個(gè)堆操作要求O(log

n),循環(huán)n-1次，需要O(nlog

n);T(n)=O(n)+O(nlogn)=O(nlogn).26<3>哈夫曼算法的正確性證明1．證明具有最優(yōu)子結(jié)構(gòu)性質(zhì)定理1（最優(yōu)子結(jié)構(gòu)）：

設(shè)T是字母表C的哈夫曼樹，，f(c)是c在文件中出現(xiàn)的概率。設(shè)x，y是T中任意兩個(gè)相鄰葉結(jié)點(diǎn)，z是它們的父結(jié)點(diǎn)，則z作為概率為f(z)=f(x)+f(y)的字符，T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼樹。27bzT1cf(x)+f(y)f(b)f(c)往證：z作為概率為f(z)=f(x)+f(y)的字符，

T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼樹。證:bycT

f(x)f(b)f(c)xf(y)28往證：z作為概率為f(z)=f(x)+f(y)的字符，

T1=T-{x,y}表示了字母表C1=C-{x,y}∪{z}的哈夫曼樹。bycT3

f(x)f(b)f(c)x

f(y)

因?yàn)閦在C1中是一個(gè)字符，它必是T2中的葉子。把結(jié)點(diǎn)x，y加入T2，作為z的子結(jié)點(diǎn)，則得到C的一個(gè)前綴樹T3。

T3的代價(jià)為：

若T1不是C1的優(yōu)化前綴編碼樹，則必存在T2，其葉子在C1中，使B(T2)<B(T1)。zbf(x)+f(y)cf(b)f(c)T2=B(T2)+f(x)+f(y)<B(T)

與T是優(yōu)化的(即HUFFMAN樹)矛盾，故T1是優(yōu)化的。

292．證明具有貪心選擇性定理2（Greedy選擇性）:

設(shè)C是字母表，,f(c)是c在文件中出現(xiàn)的頻率。設(shè)x,y是C中具有最小概率的兩個(gè)字符，則存在一個(gè)C的優(yōu)化前綴樹,在該優(yōu)化前綴樹中x,y具有最大深度，其編碼長(zhǎng)度相同，僅在最末一位不同。證：設(shè)T是C的優(yōu)化前綴樹，且b,c是具有最大深度的兩個(gè)字符。不失一般性，設(shè)f(b)<f(c)，f(x)<f(y).因x與y是具有最低概率的字符,所以f(b)≥f(x),f(c)≥f(y).從T構(gòu)造T1，交換T的b和x;從T1構(gòu)造T2,交換T1的c和y;往證，T2是最大前綴樹。B(T)-B(T1)==f(x)dT(x)+f(b)dT(b)-(f(x)dT1(x)+f(b)dT1(b))=f(x)dT(x)+f(b)dT(b)-f(x)dT(b)-f(b)dT

(x)=(f(b)-f(x))(dT(b)-dT(x))因?yàn)閒(b)≥f(x)，dT(b)≥dT(x)

（因?yàn)閎的深度最大）所以B(T)-B(T1)≥0，B(T)≥B(T1)。byuT

f(x)f(b)f(c)x

f(y)c30同理可證，B(T1)≥B(T2)。于是B(T)≥B(T2)。又由于T是優(yōu)化的，所以B(T)≤B(T2)。于是B(T)=B(T2).

所以T2是C的最優(yōu)前綴編碼樹。在T2中，x,y具有相同長(zhǎng)度編碼，而且僅最后一位不同（且在該優(yōu)化前綴樹中具有最大深度）。3．哈夫曼算法是按定理2的Greedy選擇性進(jìn)行局部?jī)?yōu)化選擇的.

因此哈夫曼算法是正確的，即HUFFMAN(C)產(chǎn)生C的一個(gè)最優(yōu)前綴碼。31五、單源最短路徑問題

(SingleSourceShortestPaths)1.單源最短路徑問題

對(duì)于給定的有向網(wǎng)絡(luò)G=（V,E）及單個(gè)源點(diǎn)v,求從v到G中其余各頂點(diǎn)的最短路徑。2.單源最短路徑問題的貪心策略？32Dijkstra算法（貪心法）基本思想：

按路徑長(zhǎng)度遞增的次序產(chǎn)生諸頂點(diǎn)的最短路徑。求解過程：

設(shè)集合S存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，逐步擴(kuò)充集合S，直到S=V。

約定S中頂點(diǎn)涂成紅色，V-S中頂點(diǎn)涂成藍(lán)色。算法初始時(shí)，紅點(diǎn)集中只有源點(diǎn)；以后的每一步都從當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短路徑最小的藍(lán)點(diǎn)來擴(kuò)充紅點(diǎn)集；算法直到圖中的所有頂點(diǎn)都涂成紅色時(shí)終止。

Dijkstra算法的動(dòng)態(tài)執(zhí)行情況12534101006020503010有向網(wǎng)絡(luò)G=(V,E)4循環(huán)初始化紅點(diǎn)集S{4}

D[1]

D[2]D[3]D[4]D[5]∞

∞20

0

601{4，3}

∞

∞

200

302{4，3，5}

∞

∞

20030

3{4，3，5，1}

∞

∞

200304{4，3，5，1，2}

∞

∞20030351233<1>問題定義生成樹：

設(shè)G=(V,E)是一個(gè)邊帶權(quán)的無向連通圖。G的生成樹是無向樹S=(V,T),

。以下用T表示S。如果W:E→{實(shí)數(shù)}是G的權(quán)函數(shù)，T的權(quán)值定為

。最小生成樹：

G的最小生成樹是W(T)最小的G的生成樹。問題定義：

給定邊帶權(quán)的無向連通圖G=(V,E)，求出G的最小生成樹。六、最小生成樹(MinimalSpanningTree)

34

1254634653126123456123TE={}TV={1}TE={(2,3)}TV={1,3}TE={(2,3),(3,4)}TV={1,3,6}TE={(2,3),(3,4),(4,6)}TV={1,3,6,4}TE={(2,3),(3,4),(4，6),(1,5)TV={1,3,6,4,2}TE={(2,3),(3,4),(4，6),(1,5),(1,2)}TV={1,3,6,4,2,5}

在構(gòu)造最小生成樹的過程中頂點(diǎn)集與邊集的變化情況：1.構(gòu)造最小生成樹的方法—Prim算法對(duì)下圖所示的連通網(wǎng)絡(luò)G，用普里姆(Prim)算法求G的最小生成樹T。在算法執(zhí)行過程中，依次加入T的邊集TE和頂點(diǎn)集TV？

554535

1254631416185691911262112345656111416TE={}TE={(2,3)}TE={(2,3),(3,4)}TE={(2,3),(3,4),(4,6)}TE={(2,3),(3,4),(4，6),(1,5)}TE={(2,3),(3,4),(4，6),(1,5),(1,2)}在構(gòu)造最小生成樹中的過程中邊集的變化情況：2.構(gòu)造最小生成樹的方法—Kruskal算法對(duì)下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T。

在算法執(zhí)行過程中，依次加入T的邊集TE中的邊？

36<2>Kruskal算法基本思想：

首先將圖G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連同分支，將所有的邊按權(quán)從小到大排序。然后從第一條開始，依邊權(quán)遞增的次序查看每一條邊，并按下述方法連接兩個(gè)不同的連通分支：當(dāng)查看到第k條邊（v,w）時(shí),

如果端點(diǎn)v和w分別是當(dāng)前兩個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊（v,w）將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊。這個(gè)過程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。此時(shí)，這個(gè)連通分支就是G的一棵最小生成樹。輸入：

邊帶權(quán)的無向連通圖G=(V,E)，設(shè)V={1,2,…,n}。輸出：

G的最小生成樹G1=(V,T)

。37算法：Kruskal(G){(1)T=Φ;(2)fordoMake-Set(v);//構(gòu)造集合

(3)按照權(quán)值的遞增順序排列E(G);(4)for(按權(quán)值遞增順序)doif(Find-Set(u)≠Find-Set(v))

//確定u,v是否屬同一集合

{T∪{(u,v)};

Union(u,v);//將u,v所屬的集合并成一個(gè)集合

}(8)returnT;//返回生成樹的邊集}38并查集（不相交集合

DisjointSets）并查集的定義

在一些應(yīng)用中,我們需要?jiǎng)澐謓個(gè)不同的元素成若干組,每一組的元素構(gòu)成一個(gè)集合。這種問題的一個(gè)解決辦法是,在開始時(shí),讓每一個(gè)元素自成一個(gè)單元素集合,然后按一定順序,將屬