第4章貪心算法-1

第四章貪心算法

Greedymethod貪婪，我找不到一個更好的詞來描述它，它就是好！它就是對！它就是有效！——影片《華爾街》中的臺詞主要內(nèi)容貪心算法的基本概念與要素幾個實例：活動安排、最優(yōu)裝載、Huffman編碼、單源最短路徑、最小生成樹、多機調(diào)度問題、帶有完成期限的作業(yè)調(diào)度重點與難點：算法本身較簡單，很少用遞歸；關(guān)鍵是如何選擇貪心策略；如何證明你選擇的貪心策略能獲得最優(yōu)解。例貪心算法概述貪心算法也稱為優(yōu)先策略顧名思義是“擇優(yōu)錄取”，在某些方面的應用是非常成功的，也是我們設計算法時經(jīng)常使用的一種策略。國外叫做Greedymethod，意即見到好的就抓住不放。它并不一定對所有問題都成功，但是對某些問題特別簡單、有效。在貪婪算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準則(criterion)。貪心算法常常用于求解某些問題的最優(yōu)解。這類問題一般有n個輸入，而其解由這n個輸入的某個子集組成，要求該子集滿足預先給定的約束條件。這一子集稱為該問題的一個可行解。其中使目標函數(shù)取得極值的可行解稱為最優(yōu)解。N個輸入約束條件可行解準則最優(yōu)解貪心法的關(guān)鍵是找到一個衡量優(yōu)劣的標準，然后把n個輸入按這種標準排序并嘗試局部解。如果這個輸入和當前的部分解加起來不能產(chǎn)生一個可行解，則不把此輸入加入到部分解當中。一般地，選取最優(yōu)度量標準并非易事，因此貪心法得到的解往往不是最優(yōu)解，而是次優(yōu)解。而一旦找到最優(yōu)度量標準，則貪心法特別有效。貪心法逐步給出解的各部分，在每一步“貪婪地”選擇最好的部分解，而不顧及這樣選擇對整體的影響，因此未必得到最優(yōu)解。貪心法應用的成功示例有：單源最短路徑問題、最小生成樹問題以及作業(yè)調(diào)度等。即使得不到最優(yōu)解，往往能得到較好的近似解。例1[找零錢]：一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為25、10、5、1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪心準則如下：每一次選擇應使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應使零錢總數(shù)超過最終所需的數(shù)目。假設需要找給小孩67美分，首先入選的是兩枚25美分的硬幣，第三枚入選的不能是25美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過67美分），第三枚應選擇10美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時所用的硬幣數(shù)目的確最少。例2：找零錢問題與硬幣面值的設定有關(guān)。比如：要找給顧客3角7分錢，如果硬幣面值為1角、5分、2分、1分，那么按照貪心算法：

1角：3枚；5分：1枚；2分：1枚合計：5枚能得到最優(yōu)解。如果硬幣面值為11分、7分、5分、1分，那么按照貪心算法：

11分：3枚；1分：4枚合計：7枚但最優(yōu)解應該是5枚，貪心法不成功。背包問題假設：n=3,c=20,(w1,w2,w3)=(18,15,10)(v1,v2,v3)=(25,24,15)四個可行解：可行解重量價值（1/2，1/3，1/4）16.524.25

（1，2/15，0）2028.2

（0，2/3，1）2031

（0，1，1/2）2031.5選取度量標準是用貪心法求解問題的關(guān)鍵。任意選取策略價值優(yōu)先策略重量最小優(yōu)先策略單價高優(yōu)先策略用貪心算法求解背包問題的步驟：1）計算每種物品的單價vi/wi2）按物品的單價，從大到小排序3）單價高的物品優(yōu)先裝包，直至裝滿。（最后一種物品可能裝入一部分）時間復雜性排序：O(nlogn)其它：O(n)為什么采用貪心策略能得到最優(yōu)解？0/1背包問題的幾種貪婪策略：1）從剩余的物品中，選出可以裝入背包的價值最大的物品2）從剩下的物品中選擇可裝入背包的重量最小的物品3）從剩余物品中選擇可裝入包的pi/wi值最大的物品這三種策略都不能保證得到最優(yōu)解。我們不必因所考察的幾個貪婪算法都不能保證得到最優(yōu)解而沮喪，0/1背包問題是一個NP復雜問題。對于這類問題，也許根本就不可能找到具有多項式時間的算法。雖然按pi/wi非遞增的次序裝入物品不能保證得到最優(yōu)解，但它是一個直覺上近似的解。我們希望它是一個好的啟發(fā)式算法，且大多數(shù)時候能很好地接近最后算法。據(jù)統(tǒng)計，在600個隨機產(chǎn)生的背包問題中，用這種啟發(fā)式貪婪算法來解有239題為最優(yōu)解。有583個例子與最優(yōu)解相差10%，所有600個答案與最優(yōu)解之差全在25%以內(nèi)。該算法能在O(n

log

n)時間內(nèi)獲得如此好的性能。我們也許會問，是否存在一個x(x<100)，使得貪婪啟發(fā)法的結(jié)果與最優(yōu)值相差在x%以內(nèi)。答案是否定的。為什么貪心策略不適用于0/1背包問題？例：c=50,w=(10,20,30),V=(60,100,120)單價v/w=(6,5,4)

按貪心策略，應裝入前兩個物品，價值160；而最優(yōu)解應為裝入后兩種物品，價值220。原因：貪心法不能保證0/1背包裝滿，閑置部分使背包價值降低?？紤]0/1背包問題，應比較選擇wi與不選擇wi所導致的結(jié)果，然后作出選擇，由此導致相互重疊的子問題。所以可用動態(tài)規(guī)劃法。voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//按單位價值排序/inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;//c為背包剩余空間/for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]