ACM程序設計基礎之貪心法.ppt

貪心算法,貪心法的設計思想,貪心法的求解過程,貪心法的基本要素,貪心法的應用舉例,貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），但通常能獲得近似最優(yōu)解（Near-Optimal Solution）。,1 貪心法的設計思想,引例 找零錢,一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。 假設提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。 售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應使零錢總數(shù)超過最終所需的數(shù)目。,算法思想,為使找回的零錢的硬幣數(shù)最小，不考慮找零錢的所有各種方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，只當不足大面值幣種的金額才會去考慮下一種較小面值的幣種。這就是在采用貪婪法。 這種方法在這里之所以總是最優(yōu)，是因為銀行對其發(fā)行的硬幣種類和硬幣面值的巧妙安排。 如果只有面值分別為1，5和11單位的硬幣，而希望找回總額為15單位的硬幣，按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優(yōu)的解答應是3個5單位面值的硬幣。,貪心法求解的問題的特征： （1）最優(yōu)子結(jié)構(gòu)性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)性原理。 （2）貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。,動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。,2 貪心法的求解過程,用貪心法求解問題應該考慮如下幾個方面： （1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構(gòu)成候選集合。 （2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構(gòu)成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構(gòu)成解集合。,（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應付款。 （4）選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目標函數(shù)有關(guān)。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。 （5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應付款。,貪心法的一般過程 Greedy(C) /C是問題的輸入集合即候選集合 S= ; /初始解集合為空集 while (not solution(S) /集合S沒有構(gòu)成問題的一個解 x=select(C); /在候選集合C中做貪心選擇 if feasible(S, x) /判斷集合S中加入x后的解是否可行 S=S+x; C=C-x; return S; ,例1、 活動安排問題,活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。,例1、活動安排問題,設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間begini和一個結(jié)束時間endi,且begini endi 。如果選擇了活動i，則它在半開時間區(qū)間begini, endi)內(nèi)占用資源。若區(qū)間begini, endi)與區(qū)間beginj, endj)不相交，則稱活動i與活動j是相容的。也就是說，當beginiendj或beginjendi時，活動i與活動j相容。,a 和 b 事件的開始時刻小于結(jié)束時刻 Begina= Enda 記為 b a 這時 b 事件與 a 事件不重疊.,例1、活動安排問題,例：設待安排的12個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：,找出 時間上不重疊的事件： 2#,9# 2#,8#,10# 2#,8#,11# 0#,3#,8#,10# 0#,3#,8#,11# 0#,1#,5#,8#,10# 0#,1#,5#,8#,11# 0#,1#,6#,10# 0#,1#,6#,11#,每個都選擇最早結(jié)束的序列-貪心策略 0#-1#-5#-8#-10# 這是最長序列,#include const int N=12; void OtputResult(int SelectN); cout“ 0”; for( int i=1; iN; i+ ) if ( Select i =1) cout“,” i ; cout “ “ endl; ,void main( ) int BeginN=1,3,0,3,2,5,6,4,10,8,15,15; int EndN=3,4,7,8,9,10,12,14,15,18,19,20; int SelectN=0,0,0,0,0,0,0,0,0,0,0,0; int i=0;/當前最早結(jié)束的事件 /當前可選事件的最早開始時間 int TimeStart=0;,while( i =TimeStart ) Select i =1; TimeStart=End i ; i +; OutputResult ( Select ) ; ,3、貪心算法的基本要素,對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。,3 貪心算法的基本要素,1.貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。,3 貪心算法的基本要素,2.最優(yōu)子結(jié)構(gòu)性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。,例2、 背包問題,給定n種物品和一個容量為C的背包，物品i的重量是wi，其價值為vi，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?,于是，背包問題歸結(jié)為尋找一個滿足約束條件式7.1，并使目標函數(shù)式7.2達到最大的解向量X=(x1, x2, , xn)。,設xi表示物品i裝入背包的情況，根據(jù)問題的要求，有如下約束條件和目標函數(shù)：,（式7.1）,（式7.2）,至少有三種看似合理的貪心策略： （1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。 （2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。 （3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。,應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,120 50 背包 180 190 200 (a) 三個物品及背包 (b) 貪心策略1 (c) 貪心策略2 (d) 貪心策略3,例如，有3個物品，其重量分別是20, 30, 10，價值分別為60, 120, 50，背包的容量為50，應用三種貪心策略裝入背包的物品和獲得的價值如圖所示。,設背包容量為C，共有n個物品，物品重量存放在數(shù)組wn中，價值存放在數(shù)組vn中，問題的解存放在數(shù)組xn中。,算法的時間主要消耗在將各種物品依其單位重量的價值從大到小排序。因此，其時間復雜性為O(nlog2n)。,Another one 最優(yōu)合并問題,給定k 個排好序的序列s1 , s2, sk , 用2 路合并算法將這k 個序列合并成一個 序列。假設所采用的2 路合并算法合并2 個長度分別為m和n的序列的m + n .試設 計一個算法確定合并這個序列的最優(yōu)合并 順序，使所得總值最少和最大。,解題思路,先確定貪心策略： 總的想法是希望總的合并長度最小。由 最優(yōu)子結(jié)構(gòu)性質(zhì)可知，子問題的長度也是 最短的，也就是最后的合并的兩個數(shù)是最 小的，亦即每次合并的都是最小的兩個 數(shù)，這樣就得出來玩解決問題的辦法。,最后實現(xiàn),思路很清晰了：每次都取加入了新數(shù)之后的集合中的最小值和次小值合并成一個新的數(shù)，并刪除這兩個數(shù)，把新數(shù)加入集合，循環(huán)到只有兩個數(shù)了位置。 取最小值：不斷循環(huán)，不斷