第四章 貪心算法1

第四章貪心算法(GreedyAlgorithms)

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

本章提要：

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

最小生成樹

1一、Greedy算法的基本原理

（ElementsofGreedyAlgorithms)

Greedy算法的基本思想是求解最優(yōu)化問題的算法，包含一系列步驟每一步都在一組選擇中做當(dāng)前看最好的選擇希望通過做局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇Greedy算法不一定總產(chǎn)生優(yōu)化解Greedy算法是否產(chǎn)生優(yōu)化解，需要嚴(yán)格證明V0V12V13V21V11V23V22V34672414351212

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

背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用動態(tài)規(guī)劃算法來解。

但是，用貪心算法更簡單，解題效率更高。3

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

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

雖然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣的許多問題能產(chǎn)生整體最優(yōu)解。如：單源最短路經(jīng)問題,最小生成樹問題，哈夫曼編碼問題等。

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

V0V12V13V21V11V23V22V34672414351215

Greedy算法產(chǎn)生優(yōu)化解的條件

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

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

若一個優(yōu)化問題的全局優(yōu)化解可通過局部優(yōu)化選擇得到，則該問題稱為具有g(shù)reedy選擇性質(zhì)。6證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu)性質(zhì)證明算法所求解的問題具有Greedy選擇性說明算法確實(shí)按照Greedy選擇性進(jìn)行局部優(yōu)化選擇的。

Greedy算法正確性證明方法7

與動態(tài)規(guī)劃方法的比較

動態(tài)規(guī)劃：每一步作一個選擇—依賴于子問題的解。

貪心方法：每一步作一個選擇—不依賴于子問題的解。

可用動態(tài)規(guī)劃方法的條件：

最優(yōu)子結(jié)構(gòu)性質(zhì)；子問題的重疊性質(zhì)；子問題空間小。

可用貪心方法的條件：

最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。

動態(tài)規(guī)劃：自底向上求解；

貪心方法：自頂向下求解。可用貪心法時，動態(tài)規(guī)劃方法可能不適用；可用動態(tài)規(guī)劃方法時，貪心法可能不適用。8二、活動安排問題

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

活動安排問題是可以用貪心算法有效求解的一個很好的例子。

活動

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

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

活動安排問題是要在所給的活動集合中選出最大的相容活動子集合。sifisjfjtsjfifjsifjsi相容！相容！不相容！10<2>算法設(shè)計貪心思想：

為了選擇最多的相容活動，每次選

fi最小的活動，使剩余的可安排時間段極大化，以便接待盡可能多的相容活動。輸入：

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

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

按貪心算法計算最大相容活動子集A的過程如下:

A={1}

與活動1相容的剩余活動子集為：

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

與活動4相容的剩余活動子集為：

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

與活動8相容的剩余活動子集為：

{11}A={1,4,8,11}與活動11相容的剩余活動子集為：

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

int

j=1;

//

j用以記錄最近一次加入到A中的活動。

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

j=i;

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

設(shè)S={1,2,…,n}是n個活動集合，[sj，fj]是活動的起止時間，且f1≤f2≤…≤fn，則S的活動選擇問題的某個優(yōu)化解包括活動1。證：設(shè)A是一個優(yōu)化解，按結(jié)束時間排序A中活動，設(shè)其第一個活動為k，第二個活動為j。

如果k=1，引理成立。

如果k≠1，令B=A-{k}∪{1}，

由于A中的活動相容，f1≤fk≤sj，

B中的活動相容?！遼B|=|A|，∴B是一個優(yōu)化解，且包含活動1。i1234567891011s[i]130535688212f[i]456789101112131414定理1

設(shè)S={1,2,…,n}是n個活動集合，[sj，fj]是活動j

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

∴A2是S2的解。

我們僅需證明A2是最大的。若不然，

存在一個S2的活動選擇問題的優(yōu)化解B2，|B2|>|A2|

令B={1}∪B2，對于j∈S2，sj≥f1，B中活動相容。B是S的一個解。

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

∴|B|

>

|A|，與|A|最大矛盾。

定理1說明活動選擇問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。15

2.證明問題具有貪心選擇性定理2

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

={j∈S|sj≥fl

i-1}中具有最小結(jié)束時間fli的活動(設(shè)l0=0，f0=0)。設(shè)A是S的包含活動1的優(yōu)化解，則A=。證：對|A|作歸納法（即對貪心選擇的次數(shù)作歸納法）。

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

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

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

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

由歸納假設(shè)，A2=。于是，A=。

定理2說明活動選擇問題具有貪心選擇性。163.GREEDY_ACTIVITY-SELECTOR算法是按定理2的Greedy選擇性進(jìn)行局部優(yōu)化選擇的。

因此GREEDY_ACTIVITY_SELECTOR算法對于活動安排問題來說，總能求得整體最優(yōu)解(即相容活動集合A的規(guī)模最大)。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個集裝箱的重量，輪船的載重量c。輸出：

裝進(jìn)輪船的集裝箱編號(最多的集裝箱）。19算法：Template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);//數(shù)組元素t[i]存放重量第i輕的集裝箱號。

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ù)雜性：算法的主要計算量是將集裝箱依其重量從小到大排序，∴T(n)=O(nlogn)+O(n)=O(nlogn)20四、哈夫曼編碼(Huffmancodes)<1>問題定義二進(jìn)制字符編碼：

每個字符用一個二進(jìn)制0,1串來表示。固定長編碼：

每個字符都用等長的0,1串來表示?？勺冮L編碼：

經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的字符用長碼。前綴編碼：

無任何字符的編碼是另一個字符編碼的前綴。21前綴碼的哈夫曼樹表示每個字符的編碼:從根到對應(yīng)的葉路徑上的0,1串。100A:4555012530C:12B:13E:9D:1614F:511110000葉結(jié)點(diǎn)：用字符及其出現(xiàn)頻數(shù)標(biāo)記。邊標(biāo)記：一個結(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的一個前綴編碼方案對應(yīng)一棵二叉樹T。字符c在樹T中的深度記為dT(c)。dT(c)也是字符c的前綴碼長。該編碼方案的平均碼長定義為：。目標(biāo)：求出使平均碼長最小的前綴編碼方案――哈夫曼編碼。23

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

循環(huán)地選擇具有最低頻率的兩個根結(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)先隊列用堆來實(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)時間循環(huán)n-1次每個堆操作需O(logn)時間算法的時間復(fù)雜性：T(n)=O(n)+O(nlogn)=O(nlogn)

輸入：C={a,b,c,d}，f(C)={6,5,3,7}25算法復(fù)雜性分析：

設(shè)優(yōu)先隊列Q由一個堆實(shí)現(xiàn)。

第二步使用堆排序的初始建堆算法實(shí)現(xiàn)，需要的時間為O(n);

每個堆操作要求O(logn),循環(huán)n-1次，需要O(nlogn);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中任意兩個相鄰葉結(jié)點(diǎn)，z是它們的父結(jié)點(diǎn)，則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)bzT1cf(x)+f(y)f(b)f(c)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)z28往證：z作為概率為f(z)=f(x)+f(y)的字符，

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

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

x

f(y)

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

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

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

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

x

f(y)cbzT1cf(x)+f(y)f(b)f(c)292．證明具有貪心選擇性定理2（Greedy選擇性）:

設(shè)C是字母表，,

f(c)是c在文件中出現(xiàn)的頻率。設(shè)x,y是C中具有最小概率的兩個字符，則存在一個C的優(yōu)化前綴樹,在該優(yōu)化前綴樹中x,y具有最大深度，其編碼長度相同，僅在最末一位不同。證：設(shè)T是C的優(yōu)化前綴樹，且b,c是具有最大深度的兩個字符。不失一般性，設(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。byuT

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

x

f(y)cxyuT1f(b)f(x)f(c)

b

f(y)cxcuT2f(b)f(x)f(y)

bf(c)y30同理可證，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具有相同長度編碼，而且僅最后一位不同（且在該優(yōu)化前綴樹中具有最大深度）。3．哈夫曼算法是按定理2的Greedy選擇性進(jìn)行局部優(yōu)化選擇的。

因此哈夫曼算法是正確的，即HUFFMAN(C)產(chǎn)生C的一個最優(yōu)前綴碼。xyuT1f(b)f(x)f(c)

b

f(y)cxcuT2f(b)f(x)f(y)

bf(c)ybyuT

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

x

f(y)c31五、單源最短路徑問題

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

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

按路徑長度遞增的次序產(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)色。

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

Dijkstra算法的動態(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)是一個邊帶權(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的最小生成樹。六、最小生成樹(MinimumSpanningTree)

34

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

在構(gòu)造最小生成樹的過程中頂點(diǎn)集與邊集的變化情況：1.構(gòu)造最小生成樹的方法—Prim算法

對下圖所示的連通網(wǎng)絡(luò)G，用普里姆(Prim)算法求G的最小生成樹T

。在算法執(zhí)行過程中，依次加入T的邊集TE和頂點(diǎn)集TV？

5545735

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算法對下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T

。

在算法執(zhí)行過程中，依次加入T的邊集TE中的邊？36并查集（不相交集合

DisjointSets）并查集是一種抽象數(shù)據(jù)類型。并查集的數(shù)學(xué)模型是若干個不相交的動態(tài)集合的集合S={A，B，…}，支持以下的運(yùn)算：MakeSet(A,x):構(gòu)造一個取名為A的集合，

它只包含一個元素x;Union(A,B):

將集合A和B合并,

其結(jié)果取名為A或B;Find-Set(x):

找出元素x所在集合,

并返回該集合的名字。37并查集的一個應(yīng)用是確定集合上的等價關(guān)系。例：S={10,20,30,40,50,60,70}，要求作出S的等價劃分滿足給定的等價性條件：

10≡20，50≡60，30≡40，10≡40。

先將S的每一個元素看成一個等價類，然后順序地處理所列的條件。沒處理完一個條件，所得到的相應(yīng)的等價類列表如下：10≡20

｛10,20｝｛30｝,｛40｝,｛50｝,｛60｝,｛70｝50≡60

｛10,20｝,｛30｝,｛40｝,｛50,60｝,｛70｝30≡40

｛10,20｝,｛30,40｝,｛50,60｝,｛70｝10≡40

｛10,20,30,40｝,｛50,60｝,｛70｝38<2>Kruskal算法基本思想：首先將圖G的n個頂點(diǎn)看成n個孤立的連同分支。將所有的邊按權(quán)從小到大排序。按邊權(quán)遞