第4章貪心算法

1第4章貪心法

4.1一般法方法4.2背包問(wèn)題4.324.1一般方法

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

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

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

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

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

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

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

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

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

問(wèn)題的形式描述

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

約束條件：

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

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

最優(yōu)解：能夠使目標(biāo)函數(shù)取最大值的可行解是問(wèn)題的最優(yōu)解——最優(yōu)解也可能為多個(gè)。8例4.1背包問(wèn)題的實(shí)例設(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//沒(méi)有放滿背包//②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.59物品可拆背包問(wèn)題C程序設(shè)計(jì)代碼如下：程序5－2for(i=1;i<=n-1;i++)/*對(duì)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)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1、算法描述

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

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)裝載問(wèn)題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

154.4哈夫曼編碼

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

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

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

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

4.4.1哈夫曼樹

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

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

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

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

它們的帶權(quán)路徑長(zhǎng)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最小，即為對(duì)應(yīng)權(quán){5,4,7,2,8}的哈夫曼樹。21

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

考慮到每一次排序可能改變w數(shù)組元素順序，設(shè)置u數(shù)組，每次所得新結(jié)點(diǎn)，其數(shù)據(jù)傳送給u數(shù)組，最后輸出時(shí)不是按已改變次序的w數(shù)組，而是按u數(shù)組輸出。4）為具體畫出哈夫曼樹提供方便，輸出展示每一個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)的表。1.哈夫曼算法要點(diǎn)24for(k=1;k<=n-1;k++)//實(shí)施操作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項(xiàng)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)路徑長(zhǎng)為：%d",s);2.哈夫曼算法描述25264.7多機(jī)調(diào)度問(wèn)題

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

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

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

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

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

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

I，若S有一元素x

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

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

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

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

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

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

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

while(S!=){

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

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

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

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

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

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