第4章貪心算法

1第4章貪心法

4.1一般法方法4.2背包問題4.324.1一般方法

31.問題的一般特征最優(yōu)化問題是指這樣一類問題，問題給定某些約束條件,滿足這些約束條件的問題解稱為可行解。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數(shù)值函數(shù)，稱為目標(biāo)函數(shù),使目標(biāo)函數(shù)取最大（或最?。┲档目尚薪夥Q為最優(yōu)解。41.問題的一般特征問題有n個輸入，問題的解是由這n個輸入的某個子集組成，這個子集必須滿足某些事先給定的條件。

約束條件：子集必須滿足的條件；

可行解：滿足約束條件的子集；可行解可能不唯一；

目標(biāo)函數(shù)：用來衡量可行解優(yōu)劣的標(biāo)準(zhǔn)，一般以函數(shù)的形式給出；

最優(yōu)解：能夠使目標(biāo)函數(shù)取極值（極大或極小）的可行解。

貪心方法：一種改進(jìn)的分級的處理方法，可對滿足上述特征的某些問題方便地求解。54.2背包問題

64.2.2貪心法求解問題的描述已知可容納M重量的背包，

n種物品具有重量(w1,w2,…,wn)，效益值(p1,p2,…,pn)；設(shè)當(dāng)物品i全部或一部分xi放入背包將得到pixi的效益，這里，0≤xi≤1,pi>0。

問題：采用怎樣的裝包方法才能使裝入背包的物品的總效益最大？7

問題的形式描述

目標(biāo)函數(shù)：

約束條件：

可行解：滿足上述約束條件的任一集合(x1,x2,…,xn)都是問題的一個可行解——可行解可能為多個。

(x1,x2,…,xn)稱為問題的一個解向量

最優(yōu)解：能夠使目標(biāo)函數(shù)取最大值的可行解是問題的最優(yōu)解——最優(yōu)解也可能為多個。8例4.1背包問題的實例設(shè)，n=3，M=20，

(p1,p2,p3)=(25,24,15)，

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

列舉可能的可行解如下：

(x1,x2,x3)①(1/2,1/3,1/4)14.524.25//沒有放滿背包//②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.59物品可拆背包問題C程序設(shè)計代碼如下：程序5－2for(i=1;i<=n-1;i++)/*對n件物品按單位重量的效益從大到小排序*/for(j=i+1;j<=n;j++)

if(p[i]/w[i]<p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw為背包還可裝的重量*/for(i=1;i<=n;i++){if(w[i]>cw)break;

x[i]=1.0;/*若w(i)<=cw,整體裝入*/

cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)>cw,裝入一部分x(i)*/s=s+p[i]*x[i];10printf("裝包：");/*輸出裝包結(jié)果*/for(i=1;i<=n;i++)

if(x[i]<1)break;else

printf("\n

裝入重量為%4.1f的物品.",w[i]);if(x[i]>0&&x[i]<1)

printf("\n

裝入重量為%4.1f的物品百分之%4.1f.",w[i],x[i]*100);printf("\n

所得最大效益為：%4.1f",s);11124.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1、算法描述

最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。

134.3最優(yōu)裝載template<classType>voidLoading(intx[],Typew[],Typec,intn){

int*t=newint[n+1];

Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}144.3最優(yōu)裝載2、貪心選擇性質(zhì)可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。

154.4哈夫曼編碼

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

平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。

174.4哈夫曼編碼2、構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結(jié)點開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。

184.4哈夫曼編碼 在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。 算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。194.4哈夫曼編碼3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì)

4.4.1哈夫曼樹

設(shè)二叉樹共有n個端點，從二叉樹第k個端點到樹的根結(jié)點的路徑長度l(k)為該端結(jié)點（或葉子）的祖先數(shù)，即該葉子的層數(shù)減1。同時，每一個結(jié)點都帶一個權(quán)（實數(shù)），第k個端點所帶權(quán)為w(k)。定義各個端結(jié)點的路徑長l(k)與該點的權(quán)w(k)的乘積之和為該二叉樹的帶權(quán)路徑長，即

對n個權(quán)值w(1),w(2),…,w(n)，構(gòu)造出所有由n個分別帶這些權(quán)值的葉結(jié)點組成的二叉樹，其中帶權(quán)路徑長wpl最小的二叉樹稱為哈夫曼樹。4.4

哈夫曼樹及其應(yīng)用20

例如，給出5個權(quán)值{5,4,7,2,8},可生成多棵二叉樹，下圖所示為其中的3棵：

它們的帶權(quán)路徑長wpl分別為(a)wpl=7×3+2×3+4×2+5×2+8×2=61(b)wpl=5×3+2×3+8×2+4×2+7×2=59(c)wpl=2×3+4×3+5×2+7×2+8×2=58

比較所有的二叉樹，其中圖(c)的wpl最小，即為對應(yīng)權(quán){5,4,7,2,8}的哈夫曼樹。21

哈夫曼給出一個貪心策略的算法，稱為哈夫曼算法。1）根據(jù)給定的n個權(quán)值{w(1),w(2),…,w(n)}構(gòu)成n棵二叉樹的森林F=(T1,…,Tn)。其中每棵二叉樹中只有一個帶權(quán)為w(k)的根結(jié)點，其左右子樹為空。2）在F中選取兩棵結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上結(jié)點權(quán)值之和。3）在F中刪除這兩棵樹，并把新得的二叉樹加入F中。4）重復(fù)以上2），3），直到F只含一棵樹為止。這棵樹即為哈夫曼樹。1.哈夫曼算法22231）首先，對給定的n個權(quán)值作升序排列。2）設(shè)置n-1次操作的k（1——n-1）循環(huán)，在第k次操作中，由兩個最小權(quán)值葉結(jié)點生成一個新結(jié)點：x=w[2*k-1];y=w[2*k];w[n+k]=x+y;lc[n+k]=x;rc[n+k]=y;3）新結(jié)點參與排序，為下一次操作做準(zhǔn)備。

考慮到每一次排序可能改變w數(shù)組元素順序，設(shè)置u數(shù)組，每次所得新結(jié)點，其數(shù)據(jù)傳送給u數(shù)組，最后輸出時不是按已改變次序的w數(shù)組，而是按u數(shù)組輸出。4）為具體畫出哈夫曼樹提供方便，輸出展示每一個結(jié)點的左右子結(jié)點的表。1.哈夫曼算法要點24for(k=1;k<=n-1;k++)//實施操作n-1次{x=w[2*k-1];y=w[2*k];w[n+k]=x+y;s=s+w[n+k];z=w[n+k];u[n+k]=w[n+k];printf("\n第%d次操作后為:",k);for(i=2*k+1;i<=2*k+2;i++)//

操作后找出最小的2項for(j=i+1;j<=n+k;j++)if(w[i]>w[j]){h=w[i];w[i]=w[j];w[j]=h;}for(j=2*k+1;j<=n+k;j++)//

輸出第k次操作結(jié)果{printf("%d",w[j]);if(w[j]==z)printf("(%d+%d)",x,y);}}printf("\n最小帶權(quán)路徑長為：%d",s);2.哈夫曼算法描述25264.7多機(jī)調(diào)度問題

多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機(jī)器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。

約定，每個作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。274.7多機(jī)調(diào)度問題 采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機(jī)調(diào)度問題的較好的近似算法。 按此策略，當(dāng)時，只要將機(jī)器i的[0,ti]時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。 當(dāng)時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計算時間為O(nlogn)。284.7多機(jī)調(diào)度問題

例如，設(shè)7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。

294.8貪心算法的理論基礎(chǔ)

借助于擬陣工具，可建立關(guān)于貪心算法的較一般的理論。這個理論對確定何時使用貪心算法可以得到問題的整體最優(yōu)解十分有用。1、擬陣 擬陣M定義為滿足下面3個條件的有序?qū)?S,I)： (1)S是非空有限集。 (2)I是S的一類具有遺傳性質(zhì)的獨立子集族，即若BI，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占貫镮的成員。 (3)I滿足交換性質(zhì)，即若AI,BI且|A|<|B|，則存在某一元素xB-A，使得A∪{x}I。304.8貪心算法的理論基礎(chǔ)

例如，設(shè)S是一給定矩陣中行向量的集合，I是S的線性獨立子集族，則由線性空間理論容易證明(S,I)是一擬陣。擬陣的另一個例子是無向圖G=(V,E)的圖擬陣。 給定擬陣M=(S,I)，對于I中的獨立子集A

I，若S有一元素x

A，使得將x加入A后仍保持獨立性，即A∪{x}

I,則稱x為A的可擴(kuò)展元素。 當(dāng)擬陣M中的獨立子集A沒有可擴(kuò)展元素時，稱A為極大獨立子集。314.8貪心算法的理論基礎(chǔ) 下面的關(guān)于極大獨立子集的性質(zhì)是很有用的。 定理4.1：擬陣M中所有極大獨立子集大小相同。

這個定理可以用反證法證明。 若對擬陣M=(S,I)中的S指定權(quán)函數(shù)W，使得對于任意x

S，有W(x)>0，則稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為。2、關(guān)于帶權(quán)擬陣的貪心算法 許多可以用貪心算法求解的問題可以表示為求帶權(quán)擬陣的最大權(quán)獨立子集問題。

324.8貪心算法的理論基礎(chǔ) 給定帶權(quán)擬陣M=(S,I)，確定S的獨立子集AI使得W(A)達(dá)到最大。這種使W(A)最大的獨立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨立子集。

例如，在最小生成樹問題可以表示為確定帶權(quán)擬陣的最優(yōu)子集問題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹問題。 下面給出求帶權(quán)擬陣最優(yōu)子集的貪心算法。該算法以具有正權(quán)函數(shù)W的帶權(quán)擬陣M=(S,I)作為輸入，經(jīng)計算后輸出M的最優(yōu)子集A。334.8貪心算法的理論基礎(chǔ)Setgreedy(M,W){A=;

將S中元素依權(quán)值W（大者優(yōu)先）組成優(yōu)先隊列；

while(S!=){

S.removeMax(x);if(A∪{x}I)A=A∪{x};}returnA}344.8貪心算法的理論基礎(chǔ) 算法greedy的計算時間復(fù)雜性為。 引理4.2(擬陣的貪心選擇性質(zhì)) 設(shè)M=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列。又設(shè)x

S是S中第一個使得{x}是獨立子集的元素，則存在S的最優(yōu)子集A使得x

A。 算法greedy在以貪心選擇構(gòu)造最優(yōu)子集A時，首次選入集合A中的元素x是單元素獨立集中具有最大權(quán)的元素。此時可能已經(jīng)舍棄了S中部分元素。可以證明這些被舍棄的元素不可能用于構(gòu)造最優(yōu)子集。354.8貪心算法的理論基礎(chǔ) 引理4.3：設(shè)M=(S,I)是擬陣。若S中元素x不是空集的可擴(kuò)展元素，則x也不可能是S中任一獨立子集A的可擴(kuò)展元素。

引理4.4(擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)) 設(shè)x是求帶權(quán)擬陣M＝(S，I)的最優(yōu)子集的貪心算法greedy所選擇的S中的第一個元素。那么，原問題可簡化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問題，其中： S’={y|y

S且{x,y}

I} I’={B|B

S-{x}且B∪{x}

I} M’的權(quán)函數(shù)是M的權(quán)函數(shù)在S’上的限制(稱M’為M關(guān)于元素x的收縮)。364.8貪心算法的理論基礎(chǔ) 定理4.5(帶權(quán)擬陣貪心算法的正確性) 設(shè)M＝(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法greedy返回M的最優(yōu)子集。3、任務(wù)時間表問題

給定一個單位時間任務(wù)的有限集S。關(guān)于S的一個時間表用于描述S中單位時間任務(wù)的執(zhí)行次序。時間表中第1個任務(wù)從時間0開始執(zhí)行直至?xí)r間1結(jié)束，第2個任務(wù)從時間1開始執(zhí)行至?xí)r間2結(jié)束，…，第n個任務(wù)從時間n-1開始執(zhí)行直至?xí)r間n結(jié)束。374.8貪心算法的理論基礎(chǔ) 具有截止時間和誤時懲罰的單位時間任務(wù)時間表問題可描述如下。 (1)n個單位時間任務(wù)的集合S={1,2,…,n}； (2)任務(wù)i的截止時間,1≤i≤n,1≤≤n，即要求任務(wù)i在時間之前結(jié)束； (3)任務(wù)i的誤時懲罰,1≤i≤n,即任務(wù)i未在時間之前結(jié)束將招致的懲罰；若按時完成則無懲罰。

任務(wù)時間表問題要求確定S的一個時間表（最優(yōu)時間表）使得總誤時懲罰達(dá)到最小。384.8貪心算法的理論基礎(chǔ) 這個問題看上去很復(fù)雜，然而借助于擬陣，可以用帶權(quán)擬陣的貪心算法有效求解。 對于一個給定的S的時間表，在截止時間之前完成的任務(wù)稱為及時任務(wù)，在截止時間之后完成的任務(wù)稱為誤時任務(wù)。 S的任一時間表可以調(diào)整成及時優(yōu)先形式，即其中所有及時任務(wù)先于誤時任務(wù)，而不影響原時間表中各任務(wù)的及時或誤時性質(zhì)。 類似地，還可將S的任一時間表調(diào)整成為規(guī)范形式，其中及時任務(wù)先于誤時任務(wù)，且及時