第7章 貪心法

1、算法設計與分析算法設計與分析第第7章章 貪心法貪心法 貪婪，我找不到一個更好的詞來描述它，它就是好！它就是對！它就是有效！美國演員道格拉思，在影片華爾街中的臺詞2Coin ChangingGreed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit. - Gordon Gecko (Michael Douglas)算法設計與分析算法設計與分析思考思考 你的朋友要開一家安全公司，這需要得到n個不同的密碼軟件

2、的許可證根據(jù)規(guī)章，他們只能以每個月至多一個的速度得到這些許可證。每個許可證目前的售價是100美元，但他們?nèi)及粗笖?shù)增長曲線變得更貴，設許可證j的費用每個月按照rj1的因子增加，且假設所有價格增長率是不同的，應該按照什么次序買這些許可證使花的總錢數(shù)最少？ 貪婪法又叫登山法貪婪法又叫登山法, , 它的根本思想是逐步它的根本思想是逐步到達山頂?shù)竭_山頂, ,即逐步獲得最優(yōu)解。貪婪算法即逐步獲得最優(yōu)解。貪婪算法沒有沒有固定的算法框架固定的算法框架，算法設計的關鍵是貪婪策略，算法設計的關鍵是貪婪策略的選擇。的選擇。選擇的貪婪策略要具有選擇的貪婪策略要具有無后向性無后向性。某狀態(tài)。某狀態(tài)以后的過程不會影響以

3、前的狀態(tài)以后的過程不會影響以前的狀態(tài), ,只與當前狀只與當前狀態(tài)或以前的狀態(tài)有關態(tài)或以前的狀態(tài)有關, ,稱這種特性為稱這種特性為無后效性無后效性。算法設計與分析算法設計與分析7.1 概概 述述 7.2 圖問題中的貪心法圖問題中的貪心法7.3 組合問題中的貪心法組合問題中的貪心法算法設計與分析算法設計與分析7.1 概概 述述 7.1.1 貪心法的設計思想貪心法的設計思想 7.1.2 貪心法的求解過程貪心法的求解過程算法設計與分析算法設計與分析 貪心法在解決問題的策略上目光短淺，只根據(jù)當貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，前已有的信息就做出選擇，而

4、且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。換言不管將來有什么結果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。擇只是在某種意義上的局部最優(yōu)。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），但通常能獲得近似最優(yōu)解），但通常能獲得近似最優(yōu)解（Near-Optimal Solution）。）。7.1.1 貪心法的設計思想貪心法的設計思想 Coin ChangingnGoal. Given currency denomin

5、ations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins.nEx: 34.nCashiers algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid.nEx: $2.89.算法設計與分析算法設計與分析例：用貪心法求解付款問題。例：用貪心法求解付款問題。假設有面值為假設有面值為5元、元、2元、元、1元

6、、元、5角、角、2角、角、1角的貨幣，需角的貨幣，需要找給顧客要找給顧客4元元6角現(xiàn)金，為使付出角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首的貨幣的數(shù)量最少，首先選出先選出1張面值不超過張面值不超過4元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過張面值不超過2元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過張面值不超過6角的最大面值的貨幣，即角的最大面值的貨幣，即5角，再選角，再選出出1張面值不超過張面值不超過1角的最大面值的貨幣，即角的最大面值的貨幣，即1角，總共付出角，總共付出4張貨幣。張貨幣。算法設計與分析算法設計與分

7、析 在付款問題每一步的貪心選擇中，在不超過應付款在付款問題每一步的貪心選擇中，在不超過應付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定：后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠選定。付款問題的貪心選一旦選出了一張貨幣，就永遠選定。付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設計思想。法的設計思想。

8、算法設計與分析算法設計與分析貪心法求解的問題的特征：貪心法求解的問題的特征：（1）最優(yōu)子結構性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質(zhì)，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。v 動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。算法設計與分析算法設計與分析7.1.2 貪心法的求解過程貪心法的求解過程 用貪心法求解問題應該考慮如下幾個方面：（1）候選集合C：為了構造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終

9、解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構成解集合。算法設計與分析算法設計與分析 （3）解決函數(shù)solution：檢查解集合S是否構成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應付款。 （4）選擇函數(shù)select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數(shù)通常和目標函數(shù)有關。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。 （5）可行函數(shù)feasible：檢查解集合中加入一

10、個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應付款。 算法設計與分析算法設計與分析貪心法的一般過程Greedy(C) /C是問題的輸入集合即候選集合 S= ; /初始解集合為空集 while (not solution(S) /集合S沒有構成問題的一個解 x=select(C); /在候選集合C中做貪心選擇 if feasible(S, x) /判斷集合S中加入x后的解是否可行 S=S+x; C=C-x; return S;算法設計與分析算法設計與分析7.2 圖問題中的貪心法圖問題中的貪心法 7.2.1 TSP問題問

11、題 7.2.2 圖著色問題圖著色問題7.2.3 最小生成樹問題最小生成樹問題算法設計與分析算法設計與分析7.2.1 TSP問題問題 求解求解TSP問題至少有兩種貪心策略是合理的：問題至少有兩種貪心策略是合理的：（1）最近鄰點最近鄰點策略：從任意城市出發(fā)，每次策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇最近的一個，直到在沒有到過的城市中選擇最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。經(jīng)過了所有的城市，最后回到出發(fā)城市。 算法設計與分析算法設計與分析(d) 城市城市3城市城市5 (e) 城市城市5城市城市2 (f) 城市城市2城市城市1 最近鄰點貪心策略求解最近鄰點貪心策略求解TSP問

12、題的過程問題的過程25221543225221543232522154327363215432233215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 (a) 5城市的代價矩陣城市的代價矩陣 (b) 城市城市1城市城市4 (c) 城市城市4城市城市3算法設計與分析算法設計與分析算法算法7.1最近鄰點策略求解最近鄰點策略求解TSP問題問題 1 P= ; 2 V=V- -u0; u=u0; /從頂點從頂點u0出發(fā)出發(fā) 3 循環(huán)直到集合循環(huán)直到集合P中包含中包含n- -1條邊條邊 3.1 查找與頂點查找與頂點u鄰接的最小代價邊鄰接的最小代價邊(u, v)并且并且

13、v屬于集合屬于集合V； 3.2 P=P+(u, v); 3.3 V=V- -v; 3.4 u=v; /從頂點從頂點v出發(fā)繼續(xù)求解出發(fā)繼續(xù)求解 設圖設圖G有有n個頂點，邊上的代價存儲在二維數(shù)組個頂點，邊上的代價存儲在二維數(shù)組wnn中，集合中，集合V存儲圖的頂點，集合存儲圖的頂點，集合P存儲經(jīng)過的邊，最近鄰點存儲經(jīng)過的邊，最近鄰點策略求解策略求解TSP問題的算法如下：問題的算法如下： 算法設計與分析算法設計與分析 算法7.1的時間性能為O(n2)，因為共進行n-1次貪心選擇，每一次選擇都需要查找滿足貪心條件的最短邊。 用最近鄰點貪心策略求解TSP問題所得的結果不一定是最優(yōu)解，圖7.1(a)中從城市

14、1出發(fā)的最優(yōu)解是125431，總代價只有13。當圖中頂點個數(shù)較多并且各邊的代價值分布比較均勻時，最近鄰點策略可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。例如，在圖7.1中，如果增大邊(2, 1)的代價，則總代價只好隨之增加，沒有選擇的余地。 算法設計與分析算法設計與分析（2）最短鏈接最短鏈接策略：每次在整個圖的范圍內(nèi)選擇策略：每次在整個圖的范圍內(nèi)選擇最短邊加入到解集合中，但是，要保證加入解集合最短邊加入到解集合中，但是，要保證加入解集合中的邊最終形成一個哈密頓回路。因此，當從剩余中的邊最終形成一個哈密頓回路。因此，當從剩余邊集邊集E中選擇一條邊中選擇一條邊(u,

15、v)加入解集合加入解集合S中，應滿足中，應滿足以下條件：以下條件： 邊邊(u, v)是邊集是邊集E中中代價最小的邊代價最小的邊； 邊邊(u, v)加入解集合加入解集合S后，后，S中中不產(chǎn)生回路不產(chǎn)生回路； 邊邊(u, v) 加入解集合加入解集合S后，后，S中中不產(chǎn)生分枝不產(chǎn)生分枝；算法設計與分析算法設計與分析215432215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 (a) 5城市的代價矩陣城市的代價矩陣 (b) 城市城市1城市城市4 (c) 城市城市5城市城市22(d) 城市城市4城市城市3 (e) 城市城市3城市城市5 (f) 城市城市2回到出發(fā)城

16、市回到出發(fā)城市1最短鏈接貪心策略求解最短鏈接貪心策略求解TSP問題的過程問題的過程222154322221543222215432535算法設計與分析算法設計與分析算法7.2最短鏈接策略求解TSP問題 1P= ; 2E=E; /候選集合，初始時為圖中所有邊 3循環(huán)直到集合P中包含n-1條邊 3.1 在E中選取最短邊(u, v); 3.2 E=E-(u, v); 3.3 如果 (頂點u和v在P中不連通 and 不產(chǎn)生分枝) 則P=P+(u, v); 設圖設圖G有有n個頂點，邊上的代價存儲在二維數(shù)組個頂點，邊上的代價存儲在二維數(shù)組wnn中，中，集合集合E是候選集合即存儲所有未選取的邊，集合是候選集

17、合即存儲所有未選取的邊，集合P存儲經(jīng)過的存儲經(jīng)過的邊，最短鏈接策略求解邊，最短鏈接策略求解TSP問題的算法如下：問題的算法如下： 算法設計與分析算法設計與分析 在算法在算法7.2中，如果操作中，如果操作“在在E中選取最短邊中選取最短邊(u, v)”用順序查找，則算法用順序查找，則算法7.2的時間性能是的時間性能是O(n2)，如果采用堆排序的方法將集合，如果采用堆排序的方法將集合E中的邊中的邊建立堆，則選取最短邊的操作可以是建立堆，則選取最短邊的操作可以是O(log2n)，對于兩個頂點是否連通以及是否會產(chǎn)生分枝，可對于兩個頂點是否連通以及是否會產(chǎn)生分枝，可以用并查集的操作將其時間性能提高到以用并

18、查集的操作將其時間性能提高到O(n)，此，此時算法時算法7.2的時間性能為的時間性能為O(nlog2n)。 算法設計與分析算法設計與分析7.2.2 圖著色問題圖著色問題 給定無向連通圖給定無向連通圖G=(V, E)，求圖，求圖G的最小色數(shù)的最小色數(shù)k，使得用使得用k種顏色對種顏色對G中的頂點著色，可使任意兩個相中的頂點著色，可使任意兩個相鄰頂點著色不同。鄰頂點著色不同。算法設計與分析算法設計與分析12345例如，圖例如，圖7.3(a)所示的圖可以只用兩種顏色著色，將所示的圖可以只用兩種顏色著色，將頂點頂點1、3和和4著成一種顏色，將頂點著成一種顏色，將頂點2和頂點和頂點5著成另著成另外一種顏色

19、。為簡單起見，下面假定外一種顏色。為簡單起見，下面假定k個顏色的集合個顏色的集合為為顏色顏色1, 顏色顏色2, , 顏色顏色k。算法設計與分析算法設計與分析貪心策略：選擇一種顏色，以任意頂點作為開始頂點，依次貪心策略：選擇一種顏色，以任意頂點作為開始頂點，依次考察圖中的未被著色的每個頂點，如果一個頂點可以用顏色考察圖中的未被著色的每個頂點，如果一個頂點可以用顏色1著色，換言之，該頂點的鄰接點都還未被著色，則用顏色著色，換言之，該頂點的鄰接點都還未被著色，則用顏色1為為該頂點著色，當沒有頂點能以這種顏色著色時，選擇顏色該頂點著色，當沒有頂點能以這種顏色著色時，選擇顏色2和和一個未被著色的頂點作為

20、開始頂點，用第二種顏色為盡可能一個未被著色的頂點作為開始頂點，用第二種顏色為盡可能多的頂點著色，如果還有未著色的頂點，則選取顏色多的頂點著色，如果還有未著色的頂點，則選取顏色3并為盡并為盡可能多的頂點著色，依此類推?？赡芏嗟捻旤c著色，依此類推。 3451212345算法設計與分析算法設計與分析算法算法7.3圖著色問題圖著色問題 1color1=1; /頂點頂點1著顏色著顏色1 2for (i=2; i=n; i+) /其他所有頂點置未著色狀態(tài)其他所有頂點置未著色狀態(tài) colori=0; 3k=0; 4循環(huán)直到所有頂點均著色循環(huán)直到所有頂點均著色 4.1 k+; /取下一個顏色取下一個顏色 4.

21、2 for (i=2; iC) 4.1 xi=1; /將第將第i個物品放入背包個物品放入背包 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;算法算法7.6的時間主要消耗在將各種物品依其單位重量的價值的時間主要消耗在將各種物品依其單位重量的價值從大到小排序。因此，其時間復雜性為從大到小排序。因此，其時間復雜性為O(nlog2n)。算法設計與分析算法設計與分析7.3.2 活動安排問題活動安排問題 設有設有n個活動的集合個活動的集合E=1, 2, , n，其中每個活，其中每個活動都要求使用同一資源（如演講會場），而在同一時動都要求使用同一資源（如演講會場），而在同一時間內(nèi)只有一個活動能

22、使用這一資源。每個活動間內(nèi)只有一個活動能使用這一資源。每個活動i都有都有一個要求使用該資源的起始時間一個要求使用該資源的起始時間si和一個結束時間和一個結束時間fi，且且si =fj) 則則 4.1.1 B=B+j; 4.1.2 j=i; 4.2 i+; 算法算法7.7的時間主要消耗在將各個活動按結束時間從的時間主要消耗在將各個活動按結束時間從小到大排序。因此，算法的時間復雜性為小到大排序。因此，算法的時間復雜性為O(nlog2n)。算法設計與分析算法設計與分析算法算法7.8活動安排問題活動安排問題 int ActiveManage(int s , int f , bool a , int n

23、) /各活動的起始時間和結束時間存儲于數(shù)組各活動的起始時間和結束時間存儲于數(shù)組s和和f中且中且 /按結束時間的非減序排列按結束時間的非減序排列 a1=1; j=1; count=1; for (i=2; i=fj) ai=1; j=i; count+; else ai=0; return count; 算法設計與分析算法設計與分析7.3.3 多機調(diào)度問題多機調(diào)度問題 設有設有n個獨立的作業(yè)個獨立的作業(yè)1, 2, , n，由，由m臺相臺相同的機器同的機器M1, M2, , Mm進行加工處理，作業(yè)進行加工處理，作業(yè)i所需的處理時間為所需的處理時間為ti（1in），每個作業(yè)均可在），每個作業(yè)均可在任

24、何一臺機器上加工處理，但不可間斷、拆分。任何一臺機器上加工處理，但不可間斷、拆分。多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的給的n個作業(yè)在盡可能短的時間內(nèi)由個作業(yè)在盡可能短的時間內(nèi)由m臺機器加臺機器加工處理完成。工處理完成。算法設計與分析算法設計與分析貪心法求解多機調(diào)度問題的貪心策略是貪心法求解多機調(diào)度問題的貪心策略是最長處理最長處理時間時間作業(yè)優(yōu)先，即把處理時間最長的作業(yè)分配給作業(yè)優(yōu)先，即把處理時間最長的作業(yè)分配給最先空閑的機器，這樣可以保證處理時間長的作最先空閑的機器，這樣可以保證處理時間長的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理時間。按照最長處理時間作業(yè)優(yōu)先的貪心策略，時間。按照最長處理時間作業(yè)優(yōu)先的貪心策略，當當mn時，只要將機器時，只要將機器i的的0, ti)時間區(qū)間分配給作時間區(qū)間分配給作