一、學(xué)習(xí)要點(diǎn)

??理解貪心算法的概念。
??掌握貪心算法的基本要素
??（1）最優(yōu)子結(jié)構(gòu)性質(zhì)
??（2）貪心選擇性質(zhì)
??理解貪心算法與動態(tài)規(guī)劃算法的差異
??理解貪心算法的一般理論
??通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。
??（1）活動安排問題；
??（2）最優(yōu)裝載問題；
??（3）哈夫曼編碼；
??（4）單源最短路徑；
??（5）最小生成樹；
??（6）多機(jī)調(diào)度問題。

二、找硬幣問題

??有四種硬幣，二角五分、一角、五分和一分，求找六角三分錢時，使用硬幣最少的方法。
??自然會想到2個二角五分，1個一角和3個一分，總是在當(dāng)前條件下使用硬幣最少的那個選擇，結(jié)果一般就是最優(yōu)方法。
??有三種硬幣，一角一分、五分和一分，求找一角五分時，使用硬幣最少的方法。

2.1 概述

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

三、活動安排問題

??活動安排問題就是要 在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

??設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而 在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si <fi 。如果選擇了活動i，則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)sj≥fi時，活動i與活動j相容。

??例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：

3.1 策略選擇

??策略一：開始時間早的優(yōu)先；證明這種方法不可行
??策略二：占用時間少的優(yōu)先；舉出反例，推翻此策略
??策略三：結(jié)束時間早的優(yōu)先；使用貪心算法，可以得到最優(yōu)解！

??由于 輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。
??算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。

??算法greedySelector 的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。

3.2 活動安排問題程序代碼

template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
       A[1]=true;
       int j=1;
       for (int i=2;i<=n;i++) {
          if (s[i]>=f[j]) { A[i]=true; j=i; }
          else A[i]=false;
          }
}

??各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列。

??若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。
??貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法卻總能求得整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。
??貪心算法是否正確，能否得到最優(yōu)解，必須進(jìn)行證明！

3.3 一般使用數(shù)學(xué)歸納法進(jìn)行證明

??例：證明對于任何自然數(shù)n，
??1+2+…+n=n(n+1)/2
??證：n=1時，左=1，右=1(1+1)/2=1
??假設(shè)對任何自然數(shù)n等式成立，則
??1+2+…+n+(n+1)=n(n+1)/2+(n+1)
??=(n+1)(n/2+1)
??=(n+1)2(n/2+1)/2
??=(n+1)(n+2)/2

3.4 活動選擇算法的命題

??算法執(zhí)行到第k步，選擇k項(xiàng)活動，i1=1,i2,…ik；則存在最優(yōu)解A包含活動i1=1,i2,…ik
??根據(jù)上述命題，對于任何k，算法前k步的組合都將導(dǎo)致最優(yōu)解，最多到第n步，將得到問題實(shí)例的最優(yōu)解。

3.4.1 先看k=1時是否正確

??證明存在最優(yōu)解包含活動1
??任取最優(yōu)解A，A中活動按截止時間遞增排序，如果A中第一個活動為j≠1，用1替換A中的活動j得到A’，即A’=(A-{j})∪{1}，
??由于f1<=fj， A’也是最優(yōu)解，且含有1。

3.4.2 歸納步驟，k->k+1

??算法執(zhí)行到第k步，選擇了活動i1=1,i2,…ik
??根據(jù)歸納假設(shè)存在最優(yōu)解A包含i1=1,i2,…ik
??A中剩下的活動選自集合S’
??S’={i|i∈Si>=fk}
??A={i1,i2,…ik}∪B

3.4.3 歸納步驟（續(xù)）

??B是S’的最優(yōu)解（若不然，S’的最優(yōu)解為B*， B的活動比B多，那么B∪{1,i2,…ik}是S的最優(yōu)解，且比A的活動多，與A的最優(yōu)性相矛盾）
??將S’看成子問題，根據(jù)歸納基礎(chǔ)，存在S’中的最優(yōu)解B’，有S’中的第一個活動ik+1，且| B’ |=| B|，于是{i1,i2,…ik}∪B’={i1,i2,…ik,ik+1}∪(B’-{ik+1})也是原問題的最優(yōu)解

四、貪心算法的基本要素

??本節(jié)著重討論 可以用貪心算法求解的問題的一般特征。
??對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。
??但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

4.1 貪心選擇性質(zhì)

??所謂貪心選擇性質(zhì)是指 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。
??動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。
??對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明 每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。

4.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)鍵特征。

4.3 貪心算法與動態(tài)規(guī)劃算法的差異

??貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個共同點(diǎn)。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究兩個經(jīng)典的組合優(yōu)化問題，并以此說明 貪心算法與動態(tài)規(guī)劃算法的主要差別。

4.4 0-1背包問題（動態(tài)規(guī)劃）

??給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
??在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。

4.5 背包問題（貪心選擇）

??與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。
??這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

4.6 用貪心算法解背包問題的基本步驟

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

void Knapsack(int n,float M,float v[],float w[],float x[])
{
       Sort(n,v,w);
       int i;
       for (i=1;i<=n;i++) x[i]=0;
       float c=M;
       for (i=1;i<=n;i++) {
          if (w[i]>c) break;
          x[i]=1;
          c-=w[i];
          }
       if (i<=n) x[i]=c/w[i];
}

??算法knapsack的 主要計(jì)算時間 在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計(jì)算時間上界為
O（nlogn）。
??為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。

??對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)?在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實(shí)上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多 互相重疊的子問題 。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。
??實(shí)際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。

五、最優(yōu)裝載問題

??有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

5.1 算法描述

??最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。
??數(shù)學(xué)建模（略）。

template<class Type>
void Loading(int x[],  Type w[], Type c, int n)
{
        int *t = new int [n+1];
        Sort(w, t, n);
        for (int i = 1; i <= n; i++) x[i] = 0;
        for (int i = 1; i <= n && w[t[i]] <= c; i++) {
	x[t[i]] = 1; 
	c -= w[t[i]];
	}
}

??該問題是 0-1背包問題的子問題，集裝箱相當(dāng)于物品，物品重量是wi，價值vi都等于1，輪船載重量限制C相當(dāng)于背包裝量限制b
??0-1背包問題目前沒有多項(xiàng)式時間的算法，但這個特殊的子問題可以！

5.2 貪心選擇性質(zhì)

??可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。

5.3 最優(yōu)子結(jié)構(gòu)性質(zhì)

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

5.4 最優(yōu)裝載問題正確性證明思路

??命題：對裝載問題任何規(guī)模為n的輸入實(shí)例，算法得到最優(yōu)解。設(shè)集裝箱從輕到重記為1,2,…n
??歸納基礎(chǔ)：證明對任何只含一個箱子的輸入實(shí)例，貪心法得到最優(yōu)解（顯然）。
??歸納步驟：假設(shè)對任何n個箱子的輸入實(shí)例，貪心法得到最優(yōu)解，那么n+1個箱子的輸入實(shí)例，貪心法也得到最優(yōu)解！

5.5 正確性證明

??假設(shè)對n個集裝箱的輸入，貪心法都可以得到最優(yōu)解。N={1,2,…n,n+1}其中w1<=w2<=…<=wn<=wn+1，由歸納假設(shè)，對于N’={2,3,…n,n+1}，C’=C-w1，貪心法得到最優(yōu)解I’，令I(lǐng)=I’∪{1}，要證明I是原問題N={1,2,…n,n+1}的最優(yōu)解。
??若不然，存在包含1的關(guān)于N的最優(yōu)解I*（如果I* 中沒有1，用1替換I* 中的第一個元素得到的解也是最優(yōu)解），且|I*|>|I|，那么I*-{1}是N’和C’的解且|I* -{1} |>|I -{1} |=|I’|,與I’是關(guān)于N’和C’的最優(yōu)解相矛盾，所以I*不是N的最優(yōu)解， N的最優(yōu)解只能是那個I。

六、哈夫曼編碼

??哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。
??給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。

6.1 前綴碼

??對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。
??非前綴碼的例子 a:001,b:00,c:010,d:01。
??解碼1:01,00,001 d,b,a。
??解碼2：010，00,01 c,b,d。

??前綴碼的二叉樹表示：
??前綴碼：{00000,00001,0001,001,01,100,101,11}
??頻率：{5%,5%,10%,15%,25%,10%,10%,20%}
??構(gòu)造樹：
??0-左子樹
??1-右子樹
??碼對應(yīng)一片樹葉
??最大位數(shù)為樹深

??編碼的前綴性質(zhì)可以使譯碼方法非常簡單。
??表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個兒子結(jié)點(diǎn)。
??平均碼長 定義為：

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

6.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。

??實(shí)例：
??輸入：a:45,b:13,c:12,d:16,e:9,f:5
??由此構(gòu)造哈夫曼樹，并求每個字符的編碼
??a:1
??b:011
??c:010
??d:001
??e:0001
??f:0000

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

6.3 哈夫曼算法的正確性

??要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。
??(1)貪心選擇性質(zhì)
??(2)最優(yōu)子結(jié)構(gòu)性質(zhì)

6.4 最優(yōu)前綴碼性質(zhì)（引理1）

??引理1：C是字符集，∨c∈C,f?為頻率，x,y ∈C,f(x),f(y)頻率最小，那么存在最優(yōu)前綴碼使得x,y碼字等長且僅在最后一位不同

6.5 最優(yōu)前綴碼性質(zhì)（引理2）

??引理2：設(shè)T是前綴碼的二叉樹，∨x,y ∈T，x,y是樹葉兄弟，z是x,y的父親，令T’=T-{x,y}且令z的頻率f(z)=f(x)+f(y)，T是對應(yīng)前綴碼C’=(C-{x,y})∪{z}的二叉樹，那么B（T）=B（T’）+f(x)+f(y)

6.6 算法正確性證明思路

??定理：哈夫曼算法對任意規(guī)模為n（>=2）的字符集C都得到關(guān)于C的最優(yōu)前綴碼的二叉樹。
??歸納基礎(chǔ) 證明：對于n=2的字符集，哈夫曼算法得到最優(yōu)前綴碼。
??歸納步驟 證明：假設(shè)哈夫曼算法對于規(guī)模為k的字符集都得到最優(yōu)前綴碼，那么對于規(guī)模為k+1的字符集也得到最優(yōu)前綴碼。

6.7 歸納基礎(chǔ)

??n=2，字符集C={x1,x2}，
??對任何代碼的字符至少都需要1位二進(jìn)制數(shù)字。哈夫曼算法得到的代碼是1和0，是最優(yōu)前綴碼。
??假設(shè)哈夫曼算法對于規(guī)模為k的字符集都得到最優(yōu)前綴碼，考慮規(guī)模為k+1的字符集C={x1,x2,…xk+1}，其中x1,x2 ∈ C是頻率最小的兩個字符。令C’=(C-{x,y})∪{z}，f(z)=f(x)+f(y)。
??根據(jù)歸納假設(shè)，算法得到一顆關(guān)于字符集C’,頻率f(z)和f(xi)(i=3,4,…,k+1)的最優(yōu)前綴碼的二叉樹T’。
??把x1,x2作為z的兒子附到T’上，得到樹T，那么T是關(guān)于C=（C’-{z}）∪{x1,x2}的最優(yōu)前綴碼的二叉樹。
??如若不然，存在更優(yōu)樹T*，B（T*）<B（T），且由引理1，其樹葉兄弟是x1,x2。
??去掉T* 中x1,x2，得到T*’，根據(jù)引理2 ，B（T*’）= B（T*）-（f(x1)+f(x2)）<B（T）-（f(x1)+f(x2)）=B（T’）。
??與T’是一顆關(guān)于C’的最優(yōu)前綴碼二叉樹矛盾。

6.8 應(yīng)用：文件歸并

??問題：給定一組不同長度的排好序文件構(gòu)成的集合S={f1,f2,…fn}，其中fi表示第i個文件含有的項(xiàng)數(shù)。使用二分歸并將這些文件歸并成一個有序文件。
??歸并過程對應(yīng)于二叉樹：文件為樹葉。fi與fj歸并的文件是它們的父節(jié)點(diǎn)。

6.9 兩兩順序歸并

??實(shí)例：S={21,10,32,41,18,70}
??歸并代價：最壞情況下的工作量
??（1）全部計(jì)算=483。
??（2）（21+10+32+41）*3+(18+70)*2-5=483。
??（3）哈夫曼歸并=456。文章來源地址http://www.zghlxwxcb.cn/news/detail-718117.html

到了這里，關(guān)于【算法分析與設(shè)計(jì)】貪心算法（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！