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

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

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

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

4、分?jǐn)?shù)之和的形式。分?jǐn)?shù)之和的形式。設(shè)真分?jǐn)?shù)為設(shè)真分?jǐn)?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) 即為真分?jǐn)?shù)即為真分?jǐn)?shù)A/B包含的最大埃及分?jǐn)?shù)。包含的最大埃及分?jǐn)?shù)。設(shè)設(shè)E = C + 1，由于，由于 A/B 1/E = (AE) B)/(BE)則真分?jǐn)?shù)減去最大埃及分?jǐn)?shù)后，得到真分?jǐn)?shù)則真分?jǐn)?shù)減去最大埃及分?jǐn)?shù)后，得到真分?jǐn)?shù) (AE) B)/BE該真分?jǐn)?shù)可能存在公因子，需要化簡(jiǎn)。該真分?jǐn)?shù)可能存在公因子，需要化簡(jiǎn)。 埃及分?jǐn)?shù)埃及分?jǐn)?shù)想法想法問(wèn)題描述：

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

6、次在整個(gè)圖的范圍內(nèi)選擇最短邊加入到解集合每次在整個(gè)圖的范圍內(nèi)選擇最短邊加入到解集合中，但是，要保證加入解集合中的邊最終形成一中，但是，要保證加入解集合中的邊最終形成一個(gè)哈密頓回路。因此，當(dāng)從剩余邊集個(gè)哈密頓回路。因此，當(dāng)從剩余邊集E中選擇一中選擇一條邊條邊(u, v)加入解集合加入解集合S中，應(yīng)滿(mǎn)足以下條件：中，應(yīng)滿(mǎn)足以下條件： 邊邊(u, v)是邊集是邊集E中代價(jià)最小的邊；中代價(jià)最小的邊； 邊邊(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 求解過(guò)程？求解過(guò)程？問(wèn)題描述：給定無(wú)向連通圖問(wèn)題描述：給定無(wú)向連通圖G=(V, E)，求圖，求圖G的最小色數(shù)的最小色數(shù)k，使得用，使得用k種顏色對(duì)種顏色對(duì)G中的頂點(diǎn)著中的頂點(diǎn)著色，可使任意兩個(gè)相鄰頂點(diǎn)著色不同。色，可使任意兩個(gè)相鄰頂點(diǎn)著色不同。圖問(wèn)題中的貪心法圖問(wèn)題中的貪心法 圖著色問(wèn)題圖著色問(wèn)題 3451212345考慮頂點(diǎn)順序?yàn)榭紤]頂點(diǎn)順序?yàn)?,5,2,3,4得到近似解得到近似解考慮頂點(diǎn)順序?yàn)榭紤]頂點(diǎn)順序?yàn)?,2,3,4,5得到最優(yōu)解得到最優(yōu)解圖問(wèn)題中的貪心法圖問(wèn)題中的貪心法 圖著色問(wèn)題圖著色問(wèn)題 1所有頂點(diǎn)置未著

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

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

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

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

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

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