1、目錄 算法設計技術 貪心法專題 1 一、貪心法的設計思想 1 例 1 埃及分數 1 例 2 TSP 問題 2 例 3 圖著色問題 3 例 4 最小生成樹問題 prim 算法 4 例 5 最小生成樹問題 Kruskal 算法 5 例 6 背包問題 6 例 7 活動安排問題 7 例 8 多機調度問題 9 算法設計技術貪心法專題 一、貪心法的設計思想 正如其名字一樣， 貪心法(greedy method)在解決問題的策略上目光短淺，只根據當前已有的 信息做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。 考慮用貪心法求解 付款問題 (payment problem ) 。假設有面

2、值為 5元、 2元、1元、5角、2角、 1 角的貨幣，需要找給顧客 4 元 6 角現金，為使付出的貨幣的數量最少，首先選出1 張面值不超過 4 元 6 角的最大面值的貨幣，即 2 元，再選出 1 張面值不超過 2 元 6 角的最大面值的貨幣，即 2 元， 再選出 1 張面值不超過 6角的最大面值的貨幣，即 5角，再選出 1張面值不超過 1 角的最大面值的 貨幣，即 1角，總共付出 4 張貨幣。在付款問題每一步的貪心選擇中，在不超過應付款金額的條件 下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定： 一旦選出了一張貨幣，就永遠選定。付款問題的貪心選擇策略是盡可

3、能使付出的貨幣最快地滿足支 付要求，其目的是使付出的貨幣張數最慢地增加，這正體現了貪心法的設計思想。 上述付款問題應用貪心法得到的是整體最優解，但是如果把面值改為3 元、1元、 8角、5角、 1 角，需要找給顧客 4 元 6 角現金，則找給顧客的是 1 個 3 元、 1 個 1 元、 1 個 5 角和 1 個 1 角共 4 張貨幣，但最優解卻是 3 張貨幣： 1 個 3 元和 2個 8 角。由于貪心法并不是從整體最優考慮，它所 做出的選擇只是在某種意義上的局部最優，這種局部最優選擇并不總能獲得整體最優解 ( optimal solution )，但通常能獲得 近似最優解(near-optima

4、l solution )。如果一個問題的最優解只能用蠻力法 窮舉得到，則貪心法不失為尋找問題近似最優解的一個較好辦法。 例1 埃及分數 【問題】 埃及同中國一樣，也是世界文明古國之一。古埃及人只用分子為1 的分數，在表示一 個真分數時，將其分解為若干個埃及分數之和，例如：7/8表示為1/2 + 1/3 + 1/24。埃及分數問題(Egypt fraction )要求把一個真分數表示為最少的埃及分數之和的形式。 【想法】一個真分數的埃及分數表示不是唯一的， 例如： 7/8又可以表示為 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 。顯然，把一個真分數表示為最少的

5、埃及分數之和的形式，其貪心策略是選擇真分數 包含的最大埃及分數， 以7/8為例，7/8 1/2，則1/2是第一次貪心選擇的結果； 7/8 -1/2 = 3/8 1/3 , 則1/3是第二次貪心選擇的結果；7/8 -1/2 -1/3 = 1/24，則1/24是第三次貪心選擇的結果， 即7/8 = 1/2 + 1/3 + 1/24 。 接下來的問題是：如何找到真分數包含的最大埃及分數？設真分數為A/B , B除以A的整數部 分為C,余數為D，則有下式成立： B = A X C + D 即： B/A = C + D/A 1/(C + 1) 即1/(C + 1)即為真分數A/B包含的最大埃及分數。設E

6、 = C + 1，由于 A/B T/E = (A X E) -B)/(B X E) 則真分數減去最大埃及分數后，得到真分數(A X E) -B)/B X E,該真分數可能存在公因子，需要化 簡，可以將分子和分母同時除以最大公約數。 【算法】設函數EgyptFraction實現埃及分數問題，算法用偽代碼描述如下： ；算法 7.1 :埃及分數 EgyptFraction: :輸入：真分數的分子 A和分母B； : -輸出：最少的埃及分數之和： i :1. E = B/A + 1; :2.輸出 1/E;: ! ：3. A = A * E -B; B = B * E; j! :4.求A和B的最大公約數

7、R，如果R不為1,則將A和B同時除以R; :5.如果A等于1,則輸出1/B，算法結束；否則轉步驟1重復執行；： 例2 TSP問題 【問題】TSP問題是指旅行家要旅行 n個城市，要求各個城市經歷且僅經歷一次然后回到出發 城市，并要求所走的路程最短。 【想法1】TSP問題的貪心策略可以采用最近鄰點策略：從任意城市出發，每次在沒有到過的 城市中選擇最近的一個，直到經過了所有的城市，最后回到出發城市。 如圖7.1(a)所示是一個無向圖的代價矩陣，從頂點1出發，按照最近鄰點的貪心策略，得到的路 徑是13t1,總代價是14,求解過程如圖 7.1(b)(f)所示。 f OO 3 3 2 6 3 CO 7 3

8、 2 廠 / C= 3 7 CO 2 5 / / 2 3 2 CO 3 / / 6 1 2 5 3 CO J O- (a) 一個無向圖的代價矩陣 (b)頂點1t頂點4 (c)頂點 4t頂點3 1 2 (d)頂點3 t頂點5 (e)頂點5t頂點2 (f)頂點2 t頂點1 1 3 2 圖7.1最近鄰點貪心策略求解 TSP問題的過程 需要說明的是，用最近鄰點貪心策略求解TSP問題所得的結果不一定是最優解，例如，圖7.1(a) 中從頂點1出發的最優解是1 t2t5t4t3t 1,總代價只有13。當圖中頂點個數較多并且各邊的代 價分布比較均勻時，最近鄰點策略可以給出較好的近似解，不過，這個近似解以何種程

9、度近似于最 優解，卻難以保證。例如，在圖7.1中，如果增大邊(2, 1)的代價，則總代價只好隨之增加，沒有選 擇的余地。 【算法1】設圖G中n個頂點的編號為1,2,n, q表示頂點i到頂點j的代價(1 i, j n), 集合V存儲圖的頂點，集合P存儲經過的邊，從頂點w出發采用最近鄰點策略求解 TSP問題的算法 如下： 算法7.2:最近鄰點策略求解 TSP問題 :輸入：無向帶權圖 G=(V, E) .輸出：回路長度TSPLe ngth 1. 初始化：P= ; TSPLength = 0; 2. u=w; V=V-w; :3.循環直到集合P中包含n-1條邊: |3.1查找與頂點u鄰接的最小代價邊(

10、u, v)并且v屬于集合V;! 3.2 P=P+(u, v); V=V-v; TSPLe ngth = TSPLe ngth + Cuv； |3.3輸出經過的路徑 u v，u=v，轉步驟3繼續求解；| 4.輸出 TSPLength + Cuw； 例3圖著色問題 【問題】給定無向連通圖 G=(V, E)，圖著色問題(graph coloring problem)求圖G的最小色數k, 使得用k種顏色對G中的頂點著色，可使任意兩個相鄰頂點著不同顏色。例如，圖7.3所示的無向 圖可以只用兩種顏色著色，將頂點 1、3和4著一種顏色，將頂點 2和頂點5著另外一種顏色。 【想法】假定k個顏色的集合為1,2,

11、k。一種顯然的貪心策略是選擇一種顏色，用該顏色 為盡可能多的頂點著色，具體地，選取顏色 1,依次考察圖中的未被著色的每個頂點，如果某頂點 可以用顏色1著色，換言之，該頂點的鄰接點都還未被著色，則用顏色1為該頂點著色；再選擇顏 色2,依次考察圖中的未被著色的每個頂點，如果某頂點著顏色2與其相鄰頂點的著色不發生沖突， 則用顏色2為該頂點著色；如果還有未著色的頂點，則選取顏色3并為盡可能多的頂點著色，依此 類推。 需要說明的是，貪心法求解圖著色問題得到的不一定是最優解。考慮一個具有2n個頂點的無向 圖，頂點的編號從1到2n，當i是奇數時，頂點i與除了頂點i+1之外的其他所有編號為偶數的頂點 鄰接，當

12、i是偶數時，頂點i與除了頂點i-1之外的其他所有編號為奇數的頂點鄰接，這樣的圖稱為 二部圖(bipartite graph)。在二部圖中，頂點可以分成兩個集合V1 (編號為奇數的頂點集合)和V2 (編號為偶數的頂點集合)，并且每一條邊都連接 V1中的一個頂點和 V2中的一個頂點。圖 7.4 所示 就是一個具有8個頂點的二部圖。 圖7.4具有8個頂點的二部圖 顯然，二部圖只用兩種顏色就可以完成著色，例如，可以將奇數頂點全部著成顏色1將偶數 頂點全部著成顏色 2。如果貪心法以1,3,2n-1,2, 4,2n的順序為二部圖著色，則算法可以得 到這個最優解，但是如果貪心法以1,2,n的自然順序為二部圖

13、著色，則算法找到的是一個需要n 種顏色的解。 【算法】設數組colorn表示頂點的著色情況，貪心法求解圖著色問題的算法如下： |算法7.4：貪心法求解圖著色問題； :輸入：無向連通圖 G=(V, E); -輸出：最小色數 k- :1.所有頂點置未著色狀態：1 :2.顏色k初始化為0;- :! :3.循環直到所有頂點均著色: |3.1 取下一種顏色k+;| |3.2依次考察所有頂點：I ! !3.2.1若頂點i已著色，則轉步驟 3.2，考察下一個頂點；| |3.2.2 若頂點i著顏色k不沖突，則colori=k;| | 4.輸出各頂點的著色； 例4最小生成樹問題prim算法 【問題】 設G=(V

14、, E)是一個無向連通網，求 G的最小生成樹。 最小生成樹(minimal spanning tree)是各邊的權值之和最小的生成樹。 【想法】 最小生成樹問題的貪心策略可以采用最近頂點策略：任選一個頂點，并以此建立生成 樹的根結點，每一步的貪心選擇是把不在生成樹中的最近頂點添加到生成樹中。Prim算法就應用了 這個貪心策略，它使生成樹以一種自然的方式生長，即從任意頂點開始，每一步為這棵樹添加一個 分枝，直到生成樹中包含全部頂點。 設最小生成樹 T=(U, TE)，初始時U=u。 ( U0為任意頂點)，TE= 。顯然，Prim算法的關鍵是 如何找到連接U和V-U的最短邊來擴充生成樹 T。對于每

15、一個不在當前生成樹中的頂點v V-U ,必 須知道它連接生成樹的最短邊信息。所以，對不在當前生成樹中的頂點v V-U，需要保存兩個信息： lowcostv表示頂點v到生成樹中所有頂點的最短邊；adjvexv表示該最短邊在生成樹中的頂點。例 如，對于圖7.5(a)所示連通網，圖7.5(b)(g)給出了從頂點A出發，用Prim算法構造最小生成樹的過 程。 v0 (a)連通網 (b)初始化 (c)加入最近頂點V5(d)加入最近頂點V2 (e)加入最近頂點V3 圖7.5 Prim算法構造最小生成樹的過程 【算法】設置數組shortEdgen表示候選最短邊集，數組元素包括 adjvex和lowcost兩

16、個域，分 別表示候選最短邊的鄰接點和權值，例如，式7-1表明候選最短邊(Vj, vQ的權值為w，其中Vj V-U , Vk U。 -shortEdgei.adjvex = k 彳(式7-1) -shortEdgei.lowcost = w 假設從頂點w出發構造最小生成樹，則初始時，U = w，且shortEdgew.lowcost = 0 ,表示頂 點 w 已加入集合 U 中，數組元素 shortEdgei.adjvex = 0, shortEdgei.lowcost = (w, i)的權值(1 i w n-1)。然后在數組 shortEdgen中不斷選取最小權值shortEdge k.low

17、cost，將 shortEdgek.lowcost 置為0,表示頂點k已加入集合U中。由于頂點k從集合V-U進入集合U后，候選最短邊集發生了 變化，依據式7-2更新數組shortEdge的內容： (式 7-2) shortEdgej.lowcost = min shortEdgej.lowcost , cost( j, k) shortEdgej.adjvex = k (如果 cost(j, k)C) |4.1將第i個物品放入背包：xi=1; 4.2 C=C-wi; 4.3 i+; :5.xi=C/wi; 例7活動安排問題 【問題】設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資

18、源(如演講會場)， 而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間色 和一個結束時間fi,且Si fj或sjfi時，活動i與活動 j相容。活動安排問題 (activity arrangement problem )要求在所給的活動集合中選出最大的相容活動 子集。 【想法】貪心法求解活動安排問題的關鍵是如何選擇貪心策略，使得按照一定的順序選擇相容 活動，并能夠安排盡量多的活動。至少有兩種看似合理的貪心策略： (1) 最早開始時間：這樣可以增大資源的利用率。 (2) 最早結束時間：這樣可以使下一個活動盡早開始。 由于活動占用資源的時間沒有限制，因此，后一種貪心

19、選擇更為合理。直觀上，按這種策略選 擇相容活動可以為未安排的活動留下盡可能多的時間，也就是說，這種貪心選擇的目的是使剩余時 間段極大化，以便安排盡可能多的相容活動。 為了在每一次貪心選擇時快速查找具有最早結束時間的相容活動，可以將n個活動按結束時間 非減序排列。這樣，貪心選擇時取當前活動集合中結束時間最早的活動就歸結為取當前活動集合中 排在最前面的活動。 例如，設有11個活動等待安排，這些活動按結束時間的非減序排列如表7.1所示。 表7.111個活動的開始時間和結束時間 i 1 2 3 4 5 6 7 8 9 10 11 s 1 3 0 5 3 5 6 8 8 2 12 1 :i 4 5 6

20、7 8 9 10 11 12 13 14 貪心法求解活動安排問題的過程如圖7.9所示，其中陰影長條表示該活動已加入解集合中，空 白長條表示該活動是當前正在檢查相容性的活動。首先選擇活動1加入解集合，因為活動1具有最 早結束時間；活動 2和活動3與活動1不相容，所以舍棄他們；活動 4與活動1相容，因此將活動 4加入解集合；然后在剩下的活動中找與活動4相容并具有最早結束時間的活動，依此類推。最終 被選定的活動集合為1,4, 8, 11。 【算法】設有n個活動等待安排，色表示活動i的起始時間，fi表示活動i的結束時間(K i = fj)貝U 4.1.1 B=B+j；| 4.1.2 j=i; 4.2i

21、+; | 例8多機調度問題 【問題】設有n個獨立的作業1,2,n，由m臺相同的機器M M2,Mm進行加工處理， 作業i所需的處理時間為ti ( K i w n),每個作業均可在任何一臺機器上加工處理，但不可間斷、拆 分。多機調度問題 (multi-machine scheduling problem )要求給出一種作業調度方案，使所給的n個 作業在盡可能短的時間內由m臺機器加工處理完成。 【想法】貪心法求解多機調度問題的貪心策略是最長處理時間作業優先，即把處理時間最長的 作業分配給最先空閑的機器，這樣可以保證處理時間長的作業優先處理，從而在整體上獲得盡可能 短的處理時間。按照最長處理時間作業優

22、先的貪心策略，當mn時，只要將機器i的0, ti)時間區間 分配給作業i即可；當mvn時，首先將n個作業按其所需的處理時間從大到小排序，然后依此順序 將作業分配給最先空閑的處理機。 例如，設7個獨立作業1,2, 3, 4, 5, 6, 7由3臺機器M1, M2, M3加工處理，各作業所需的處理 時間分別為2, 14, 4, 16, 6, 5, 3,首先將這7個作業按處理時間從大到小排序，則作業4, 2, 5, 6, 3, 7, 1的處理時間為16, 14, 6, 5, 4, 3, 2,貪心法產生的作業調度如圖7.10所示，具體過程如下： (1) 按照最長處理時間作業優先的貪心策略，將作業4分配

23、給機器 M1,則機器M1將在時間 16后空閑；將作業2分配給機器M2,則機器M2將在時間14后空閑；將作業5分配給機器M3,則 機器M3將在時間6后空閑，至此，三臺機器均已分配作業； (2) 在三臺機器中空閑最早的是機器M3,將作業6分配給機器 M3,并且機器 M3將在時間6 + 5 = 11后空閑； 將作業3分配給機器 M3，并且機器 M3將在時間11 圖7.10三臺機器的調度冋題示例 tn中，m臺機器的空閑時間存儲在數組dm中, (3) 在三臺機器中空閑最早的是機器M3, + 4=15后空閑； (4) 在三臺機器中空閑最早的是機器 M2, 將作業7分配給機器M2,并且機器M2將在時間 14+ 3=17后空閑； (5) 在三臺機器中空閑最早的是機器M3, 將作業1分配給機器M3,并且機器M3將在時間 15+ 2=17后空閑。最后得到所需加工的最短時 間為17。 【算法】設n個作業的處理時間存儲在數組 集合數組Sm存儲每臺機器所處理的作業，其中集合Si表示機器i所處理的作業，貪心法