ACM程序設(shè)計(jì)基礎(chǔ)之貪心法.ppt

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