算法設(shè)計與分析 第7章 貪心法

1、第七章第七章 貪心法貪心法1234概述概述圖問題中的貪心法圖問題中的貪心法組合問題中的貪心法組合問題中的貪心法小結(jié)小結(jié)假設(shè)有面值為假設(shè)有面值為3元、元、1元、元、8角、角、5角、角、1角的角的貨幣若干枚，需要找給顧客貨幣若干枚，需要找給顧客4元元6角現(xiàn)金，角現(xiàn)金，為使付出的貨幣的數(shù)量最少，需要為使付出的貨幣的數(shù)量最少，需要3張貨幣：張貨幣：1個個3元和元和2個個8角。角。 而按貪心法找給顧客的而按貪心法找給顧客的是是1個個3元、元、1個個1元、元、1個個5角和角和1個個1角共角共4張張貨幣。貨幣。找零錢問題找零錢問題采用怎樣的裝包方法采用怎樣的裝包方法才會使裝入背包物品才會使裝入背包物品的總收

2、益最大？的總收益最大？背包問題背包問題貪心法是一種簡單有效的方法。貪心法是一種簡單有效的方法。它在解決問題的策略上只根據(jù)當(dāng)它在解決問題的策略上只根據(jù)當(dāng)前已有的信息就做出選擇，而且前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。么結(jié)果，這個選擇都不會改變。貪心法的設(shè)計思想貪心法的設(shè)計思想貪心法并不是從整體最優(yōu)考慮，它所做出貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解最優(yōu)解，但通常能獲得但通常能獲得近似最優(yōu)

3、解近似最優(yōu)解。如果一個問題。如果一個問題的最優(yōu)解只能用蠻力法窮舉得到，則貪心的最優(yōu)解只能用蠻力法窮舉得到，則貪心法不失為尋找問題近似最優(yōu)解的一個較好法不失為尋找問題近似最優(yōu)解的一個較好辦法。辦法。貪心法的設(shè)計思想貪心法的設(shè)計思想一個簡單的例子一個簡單的例子埃及分數(shù)埃及分數(shù)問題描述：古埃及人只用分子為問題描述：古埃及人只用分子為1的分數(shù)，在表的分數(shù)，在表示一個真分數(shù)時，將其分解為若干個埃及分數(shù)示一個真分數(shù)時，將其分解為若干個埃及分數(shù)之和，例如：之和，例如：7/8表示為表示為1/2 + 1/3 + 1/24。埃及。埃及分數(shù)問題要求把一個真分數(shù)表示為最少的埃及分數(shù)問題要求把一個真分數(shù)表示為最少的埃及

4、分數(shù)之和的形式。分數(shù)之和的形式。設(shè)真分數(shù)為設(shè)真分數(shù)為A/B，B除以除以A的整數(shù)部分為的整數(shù)部分為C，余數(shù)為，余數(shù)為D，則，則有下式成立：有下式成立： B = A C + D即：即： B/A = C + D/A 1/(C + 1)即即1/(C + 1) 即為真分數(shù)即為真分數(shù)A/B包含的最大埃及分數(shù)。包含的最大埃及分數(shù)。設(shè)設(shè)E = C + 1，由于，由于 A/B 1/E = (AE) B)/(BE)則真分數(shù)減去最大埃及分數(shù)后，得到真分數(shù)則真分數(shù)減去最大埃及分數(shù)后，得到真分數(shù) (AE) B)/BE該真分數(shù)可能存在公因子，需要化簡。該真分數(shù)可能存在公因子，需要化簡。 埃及分數(shù)埃及分數(shù)想法想法問題描述：

5、問題描述：TSPTSP問題是指旅行家要問題是指旅行家要旅行旅行n個城市，要求各個城市經(jīng)歷個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。并要求所走的路程最短。圖問題中的貪心法圖問題中的貪心法 TSP問題問題 從任意城市出發(fā)，每次在沒有到過的城市中選擇最從任意城市出發(fā)，每次在沒有到過的城市中選擇最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。城市。想法想法1：最近鄰點策略：最近鄰點策略C= 3 3 2 6 3 7 3 2 3 7 2 5 2 3 2 3 6 2 5 3 求解過程？求解過程？每

6、次在整個圖的范圍內(nèi)選擇最短邊加入到解集合每次在整個圖的范圍內(nèi)選擇最短邊加入到解集合中，但是，要保證加入解集合中的邊最終形成一中，但是，要保證加入解集合中的邊最終形成一個哈密頓回路。因此，當(dāng)從剩余邊集個哈密頓回路。因此，當(dāng)從剩余邊集E中選擇一中選擇一條邊條邊(u, v)加入解集合加入解集合S中，應(yīng)滿足以下條件：中，應(yīng)滿足以下條件： 邊邊(u, v)是邊集是邊集E中代價最小的邊；中代價最小的邊； 邊邊(u, v)加入解集合加入解集合S后，后，S中不產(chǎn)生回路；中不產(chǎn)生回路； 邊邊(u, v) 加入解集合加入解集合S后，后，S中不產(chǎn)生分枝。中不產(chǎn)生分枝。想法想法2：最短鏈接策略：最短鏈接策略C= 3

7、3 2 6 3 7 3 2 3 7 2 5 2 3 2 3 6 2 5 3 求解過程？求解過程？問題描述：給定無向連通圖問題描述：給定無向連通圖G=(V, E)，求圖，求圖G的最小色數(shù)的最小色數(shù)k，使得用，使得用k種顏色對種顏色對G中的頂點著中的頂點著色，可使任意兩個相鄰頂點著色不同。色，可使任意兩個相鄰頂點著色不同。圖問題中的貪心法圖問題中的貪心法 圖著色問題圖著色問題 3451212345考慮頂點順序為考慮頂點順序為1,5,2,3,4得到近似解得到近似解考慮頂點順序為考慮頂點順序為1,2,3,4,5得到最優(yōu)解得到最優(yōu)解圖問題中的貪心法圖問題中的貪心法 圖著色問題圖著色問題 1所有頂點置未著

8、狀態(tài)；所有頂點置未著狀態(tài)； 2顏色顏色k初始化為初始化為0； 3循環(huán)直到所有頂點均著色循環(huán)直到所有頂點均著色 3.1 取下一種顏色取下一種顏色k+; 3.2 依次考察所有頂點依次考察所有頂點 3.2.1 若頂點若頂點i已著色，則轉(zhuǎn)步驟已著色，則轉(zhuǎn)步驟3.2; 3.2.2 若頂點若頂點i著顏色著顏色k不沖突，則不沖突，則colori=k; 4輸出各頂點的著色輸出各頂點的著色;說明：說明： colorn表示頂點表示頂點n的著色情況。的著色情況。圖問題中的貪心法圖問題中的貪心法 圖著色問題圖著色問題 組合問題中的貪心法組合問題中的貪心法背包問題背包問題 問題描述：給定問題描述：給定n種物品和一個容量

9、為種物品和一個容量為C的背包，的背包，物品物品i的重量是的重量是wi，其價值為，其價值為vi，背包問題是如何，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的選擇裝入背包的物品，使得裝入背包中物品的總價值最大總價值最大? 背包問題與背包問題與0/1背包問題區(qū)別？背包問題區(qū)別？貪心策略的選擇：貪心策略的選擇：（1）選擇價值最大的物品；）選擇價值最大的物品；（2）選擇重量最輕的物品；）選擇重量最輕的物品；（3）選擇單位重量價值最大的物品。）選擇單位重量價值最大的物品。想想 法：法：哪一個更合理些？怎么處理？哪一個更合理些？怎么處理？20kg$6030kg$12010kg$5050kg策略策略

10、1：選擇價值最大的物品；：選擇價值最大的物品；策略策略2：選擇重量最輕的物品；：選擇重量最輕的物品；策略策略3 3：選擇單位重量價值最大的物品。：選擇單位重量價值最大的物品。1. 改變數(shù)組改變數(shù)組w和和v的排列順序，使其按單位重量的排列順序，使其按單位重量價值價值vi/wi降序排列；降序排列；2. 將數(shù)組將數(shù)組xn初始化為初始化為0； 3. i=1; 4. 循環(huán)直到循環(huán)直到(wiC) 4.1 將第將第i個物品放入背包：個物品放入背包：xi=1; 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;背包問題算法背包問題算法 設(shè)背包容量為設(shè)背包容量為C，共有，共有n個物品，物品重量存放在個

11、物品，物品重量存放在數(shù)組數(shù)組wn中，價值存放在數(shù)組中，價值存放在數(shù)組vn中，問題的解中，問題的解存放數(shù)組存放數(shù)組xn。 組合問題中的貪心法組合問題中的貪心法活動安排問題活動安排問題問題描述：設(shè)有問題描述：設(shè)有n個活動的集合個活動的集合E=1, 2, , n，其，其中每個活動都要求使用同一資源，而在同一時間中每個活動都要求使用同一資源，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動內(nèi)只有一個活動能使用這一資源。每個活動i都有都有一個要求使用該資源的起始時間一個要求使用該資源的起始時間si和一個結(jié)束時間和一個結(jié)束時間fi，且，且si =fj) 則則 4.1.1 B=B+j; 4.1.2 j=i

12、; 4.2 i+;活動安排問題活動安排問題算法算法問題描述：設(shè)有問題描述：設(shè)有n個獨立的作業(yè)個獨立的作業(yè)1, 2, , n，由，由m臺相同的機器臺相同的機器M1, M2, , Mm進行加工處理，進行加工處理，作業(yè)作業(yè)i所需的處理時間為所需的處理時間為ti（1in），每個作業(yè)），每個作業(yè)均可在任何一臺機器上加工處理，但不可間斷、均可在任何一臺機器上加工處理，但不可間斷、拆分。多機調(diào)度問題要求給出一種作業(yè)調(diào)度方拆分。多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。臺機器加工處理完成。組合問題中的貪心法組合問題中的

13、貪心法多機調(diào)度問題多機調(diào)度問題多機調(diào)度問題多機調(diào)度問題想法想法貪心法求解多機調(diào)度問題的貪心策略是最長處貪心法求解多機調(diào)度問題的貪心策略是最長處理時間作業(yè)優(yōu)先，即把處理時間最長的作業(yè)分理時間作業(yè)優(yōu)先，即把處理時間最長的作業(yè)分配給最先空閑的機器，這樣可以保證處理時間配給最先空閑的機器，這樣可以保證處理時間長的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能長的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理時間。短的處理時間。按照最長處理時間作業(yè)優(yōu)先的貪心策略，當(dāng)按照最長處理時間作業(yè)優(yōu)先的貪心策略，當(dāng)mn時，只要將機器時，只要將機器i的的0, ti)時間區(qū)間分配給作時間區(qū)間分配給作業(yè)業(yè)i即可；當(dāng)即可；當(dāng)mn時，首先將時，首先將n個作業(yè)依其所需個作業(yè)依其所需的處理時間從大到小排序，然后依此順序?qū)⒆鞯奶幚頃r間從大到小排序，然后依此順序