《算法設(shè)計(jì)與分析》- 第 4 章 貪心算法 - A

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析授課教師：劉偉授課教師：劉偉電電 話：話郵 件：件：bme_ QQ：1071271580辦辦 公公 室：長安校區(qū)室：長安校區(qū) 2 號(hào)實(shí)驗(yàn)樓號(hào)實(shí)驗(yàn)樓 303 室室 （軟件工程系辦公室）（軟件工程系辦公室）西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，可用當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，可用動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法求解。求解。但有時(shí)會(huì)有但有時(shí)會(huì)有更簡單有效更簡單有效的算法。的算法?！纠空矣矌艈栴}。要找給顧客六角三分錢，現(xiàn)有 4 種硬幣，面值分別為：二角五分、一角、五分、一分。要求找出的硬幣個(gè)數(shù)最少，采用何種方案？第第

2、4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法“找硬幣問題”本身具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，可以用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法算法來解。分析如下：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院【方法方法】先選出一個(gè)不超過六角三分的最大面值硬幣，即二角五分；減去二角五分得三角八分，再次選出一個(gè)不超過三角八分的最大面值硬幣，即二角五分；。如此一直做下去，可以得到一個(gè)解得到一個(gè)解：2 個(gè)二角五分、個(gè)二角五分、1 個(gè)一角、個(gè)一角、3 個(gè)個(gè) 1 分的硬幣交給顧客分的硬幣交給顧客。這個(gè)做法就是“貪心算法（貪心法，貪心算法（貪心法， Greedy algorithm

3、）”。第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法貪心算法總是作出在當(dāng)前看來最好的選擇貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種它所作出的選擇只是在某種意義上的局部最優(yōu)選擇意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最即使貪心算法不能得到整體最優(yōu)

4、解，其最終結(jié)果卻是最優(yōu)解的很好近似優(yōu)解的很好近似。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法【例】還是找硬幣問題。如果硬幣面值改為：一角一分、五分、一分。要找一角五分錢，要求找出的硬幣個(gè)數(shù)最少，采用何種方案？【方法方法】如果采用貪心法，得到的解是得到的解是：1 個(gè)一角一分、個(gè)一角一分、4 個(gè)個(gè)一分一分。顯然最優(yōu)解是 3 個(gè)五分個(gè)五分。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院找硬幣問題本身具有最優(yōu)子結(jié)構(gòu)性質(zhì)，可以采用動(dòng)態(tài)規(guī)劃法求解。但是用用“貪心法貪心法”更簡單，更直接更簡單，更直接且解題效率更高且解題效率更高。第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院

5、西安郵電大學(xué)計(jì)算機(jī)學(xué)院教學(xué)內(nèi)容和要求教學(xué)內(nèi)容和要求（講授（講授 6 學(xué)時(shí)，學(xué)時(shí)，2 學(xué)時(shí)上機(jī)實(shí)驗(yàn)，共學(xué)時(shí)上機(jī)實(shí)驗(yàn)，共 8 學(xué)時(shí)）學(xué)時(shí)）（1）活動(dòng)安排問題活動(dòng)安排問題（理解理解）（2）貪心算法的基本要求貪心算法的基本要求（掌握掌握）（3）最優(yōu)裝載（掌握）（4）多機(jī)調(diào)度問題（理解）第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院4.1 活動(dòng)安排問題活動(dòng)安排問題本節(jié)要求理解解決活動(dòng)安排問題的貪心算法設(shè)計(jì)活動(dòng)安排問題的貪心算法設(shè)計(jì)以及用數(shù)學(xué)歸納法證明此貪心數(shù)學(xué)歸納法證明此貪心算法的整體最優(yōu)性算法的整體最優(yōu)性。第第4章章 貪心算法貪心算法活動(dòng)安排問題活動(dòng)安排問題就是要在所給的活動(dòng)

6、集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共該問題要求高效地安排一系列爭用某一公共資源的活動(dòng)資源的活動(dòng)。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法問題的提出：問題的提出：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法ntemplate nvoid GreedySelector( int n, Type s, Type f, bool A )nn A 1 = true;n int j = 1;n for (

7、 int i = 2; i = f j ) A i = true; j = i; n else A i = false;n n各活動(dòng)的起始時(shí)間和結(jié)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組束時(shí)間存儲(chǔ)于數(shù)組 s 和和 f中且按結(jié)束時(shí)間的非減中且按結(jié)束時(shí)間的非減序排列序排列 西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法 GreedySelector 每次總是選擇具有最早完成時(shí)間的相容活動(dòng)（因?yàn)槭孪纫呀?jīng)排好序）具有最早完成時(shí)間的相容活動(dòng)（因?yàn)槭孪纫呀?jīng)排好序）加入集合 A 中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的

8、時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。算法 GreedySelector 的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需 O( n ) 的時(shí)間安排 n 個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用 O( nlogn ) 的時(shí)間重排。 西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法【例】設(shè)待安排的 11 個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法算法 GreedySelector 的

9、計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。若被檢查的活動(dòng) i 的開始時(shí)間開始時(shí)間 Si 小于最近選擇的活動(dòng) j 的結(jié)束時(shí)間結(jié)束時(shí)間 fj，則不選擇活動(dòng) i，否則選擇活動(dòng) i 加入集合 A 中。 西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法貪心算法并不總能求得問題的整體最優(yōu)解貪心算法并不總能求得問題的整體最優(yōu)解。但對(duì)于活動(dòng)安排活動(dòng)安排問題問題，貪心算法 GreedySelector 卻總能求得的整體最優(yōu)解總能求得的整體最優(yōu)解，即它最終所確定的相容

10、活動(dòng)集合 A 的規(guī)模最大。這個(gè)結(jié)論可這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明以用數(shù)學(xué)歸納法證明。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.2 貪心算法的基本要素貪心算法的基本要素本節(jié)要求掌握貪心算法的兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)以及貪心算法與動(dòng)態(tài)規(guī)劃算法的差異，是本課程的重點(diǎn)本課程的重點(diǎn)。對(duì)于一個(gè)具體的問題，怎么知道是否

11、可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2 個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.2.1 貪心選擇性質(zhì)貪心選擇性質(zhì)（1）貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別規(guī)劃算法的主要區(qū)別。（2）動(dòng)

12、態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂自頂向下向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。（3）對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.2.2 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)

13、構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法或貪心算法貪心算法求解的關(guān)鍵特征。“活動(dòng)安排問題活動(dòng)安排問題”的最優(yōu)子結(jié)構(gòu)性質(zhì)：的最優(yōu)子結(jié)構(gòu)性質(zhì)：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.2.3 貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)，這是 2 類算法的一個(gè)共同點(diǎn)。（1）對(duì)于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解 ?（2）是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解 ?西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法0-1 背

14、包問題背包問題給定 n 種物品和一個(gè)背包。物品 i 的重量是 wi ，其價(jià)值為 vi ，背包的容量為 c 。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大裝入背包中物品的總價(jià)值最大 ?在選擇裝入背包的物品時(shí)，在選擇裝入背包的物品時(shí)，對(duì)每種物品對(duì)每種物品 i 只有只有 2 種選擇，即裝入種選擇，即裝入背包或不裝入背包背包或不裝入背包。不能將物品。不能將物品 i 裝入背包多次，也不能只裝入裝入背包多次，也不能只裝入部分的物品部分的物品 i 。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法背包問題背包問題給定 n 種物品和一個(gè)背包。物品 i 的重量是 wi ，其價(jià)

15、值為 vi ，背包的容量為 c 。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大裝入背包中物品的總價(jià)值最大 ?與與 0-1 背包問題類似，背包問題類似，所不同的是在選擇物品所不同的是在選擇物品 i 裝入背包時(shí)，可裝入背包時(shí)，可以選擇物品以選擇物品 i 的一部分，而不一定要全部裝入背包的一部分，而不一定要全部裝入背包，1 i n。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法這 2 類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似。對(duì)于“0-1背包問題背包問題”，設(shè) A 是能夠裝入容量為 c 的背包的具有最大價(jià)值的物品集合，則 Aj = A - j 是 n

16、1 個(gè)物品 1，2，j-1，j+1，n 可裝入容量為 c wj 的背包的具有最大價(jià)值的物品集合。對(duì)于“背包問題背包問題”，類似地，若它的一個(gè)最優(yōu)解包含物品 j ，則從該最優(yōu)解中拿出所含的物品 j 的那部分重量 w（即只取物品的部分重量即只取物品的部分重量），剩余的將是 n 1 個(gè)原重物品 1，2，j-1，j+1，n（即物品的重量沒有改變即物品的重量沒有改變）及重為 wj w 的物品 j 中可裝入容量為 c w 的背包且具有最大價(jià)值的物品。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法背包問題可以用貪心算法求解背包問題可以用貪心算法求解，而 0-1 背包問背包問題卻不能

17、用貪心算法求解題卻不能用貪心算法求解。 西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法用貪心算法解背包問題的基本步驟用貪心算法解背包問題的基本步驟首先計(jì)算每種物品單位重量的價(jià)值每種物品單位重量的價(jià)值 vi / wi，然后依貪心選擇策略貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 c，則選擇單位重量價(jià)值次高的物品并盡可能選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心

18、算法貪心算法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 c ) break; x i = 1; c -= w i ; if ( i = n ) x i = c / w i ; 算法算法 Knapsack 的的主要計(jì)算時(shí)間在于主要計(jì)算時(shí)間在于將將各種物品依其單位重各種物品依其單位重量的價(jià)值從大到小排量的價(jià)值從大到小排序序。因此，算法的計(jì)。因此，算法的計(jì)算

19、時(shí)間上界為算時(shí)間上界為O（nlogn）。）。為了證明算法的正確為了證明算法的正確性，還必須證明背包性，還必須證明背包問題具有問題具有貪心選擇性貪心選擇性質(zhì)質(zhì)。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法這種貪心選擇策略對(duì) 0-1 背包問題背包問題不適用，如下例：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法對(duì)于 0-1 背包問題背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在

20、考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題背包問題。西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.3 最優(yōu)裝載最優(yōu)裝載本節(jié)要求掌握解決最優(yōu)裝載問題的貪心算法解決最優(yōu)裝載問題的貪心算法以及此算法的貪心選擇算法貪心選擇算法和最優(yōu)最優(yōu)子結(jié)構(gòu)性質(zhì)子結(jié)構(gòu)性質(zhì)的證明，是本課程的重點(diǎn)本課程的重點(diǎn)。問題的提出：問題的提出：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)學(xué)院第第4章章 貪心算法貪心算法4.3.1 算法描述算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下：西安郵電大學(xué)計(jì)算機(jī)學(xué)院西安郵電大學(xué)計(jì)算機(jī)