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

1、2022-4-4計算機算法設(shè)計與分析1第三章貪心算法2022-4-4計算機算法設(shè)計與分析2貪心算法的特點n貪心算法總是作出在當(dāng)前來看是最好的選擇。n就是說，貪心算法并不從整體最優(yōu)上來考慮，所作出的選擇只是某種意義上的局部最優(yōu)選擇。n當(dāng)然希望貪心算法得到的最終結(jié)果是最優(yōu)的。n可是貪心算法并不能保證最終結(jié)果是最優(yōu)的。n不過，在許多的情況下，應(yīng)用貪心算法能夠得到整體最優(yōu)解；并且在一些情況下，即使得到的不是最優(yōu)解，也是一個很好的近似解。2022-4-4計算機算法設(shè)計與分析3貪心算法的一般框架nGreedyAlgorithm(parameters)n初始化；n重復(fù)執(zhí)行以下的操作： n 選擇當(dāng)前可以選擇的

2、(相容)最優(yōu)解；n 將所選擇的當(dāng)前解加入到問題的解中；n直至滿足問題求解的結(jié)束條件。n2022-4-4計算機算法設(shè)計與分析4最小生成樹n設(shè)G = (V, E)是一個無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E的每條邊(v, w)的權(quán)為cvw。n如果G的一個子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。n生成樹的各邊的權(quán)的總和稱為該生成樹的耗費。n在G的所有生成樹中，耗費最小的生成樹稱為G的最小(優(yōu))生成樹。 2022-4-4計算機算法設(shè)計與分析5樹的基本性質(zhì)n連通無回路的圖G稱為樹。n樹是點比邊多一的連通圖，G連通且q=p1 。n樹是點比邊多一的無回路圖：G無回路且q=p1n樹若添條邊就有回路：G無

3、回路，但對任意的u, vV(G)，若uvE(G)，則G+uv中恰有一條回路n樹若減條邊就不連通：G連通，但對eE(G), Ge不連通。nn個頂點的連通圖的生成樹含有n 1條邊。2022-4-4計算機算法設(shè)計與分析6最小生成樹的貪心選擇性質(zhì)n令G中權(quán)最小的邊為e1。首先必定有圖G的一棵最小生成樹包含了e1。若G的任何最小生成樹都不包含e1。設(shè)T為G的最小生成樹，e1T。于是T+e1是一個有回路的圖且該回路中包含e1。該回路中必有條不是e的邊ei。令T=T+e1ei。T也是G的生成樹。又c(T) = c(T) + c(e1) c(e1)，c(e1) c(ei)，從而 c(T)c(T)，T是G的最小

4、生成樹且含有邊e1。矛盾。故必定有圖G的最小生成樹包含了e1。n選定第一條邊e1以后，該如何選擇第二條邊呢？n依據(jù)各條邊的權(quán)重，依次選出權(quán)重較輕的n 1條邊。這n 1條邊必定包括了G的n個頂點。這樣就得到了G的一棵最小生成樹。這樣做是否可以呢？n不行！因為不能保證這n 1條邊構(gòu)成樹？n要保證這n 1條邊構(gòu)成樹，必須使這n 1條邊是連通的或者是無回路的。nPrim算法的做法：在保證連通的前提下依次選出權(quán)重較小的n 1條邊（在實現(xiàn)中體現(xiàn)為n個頂點的選擇）。nKruskal算法的做法：在保證無回路的前提下依次選擇權(quán)重較小的n 1條邊。2022-4-4計算機算法設(shè)計與分析7Prim算法n基本思想：在保

5、證連通的前提下依次選出權(quán)重較小的n 1條邊。nG=(V, E)為無向連通帶權(quán)圖，令V=1, 2, , n。n設(shè)置一個集合S ，初始化S = 1，T = 。n貪心策略：如果VS中的頂點j與S中的某個點i連接且(i, j)是E中的權(quán)重最小的邊，于是就選擇j(將j加入S)，并將(i, j) 加入T中 。n重復(fù)執(zhí)行貪心策略，直至VS為空。 2022-4-4計算機算法設(shè)計與分析8Prim算法中的數(shù)據(jù)結(jié)構(gòu)n圖用連接矩陣Cij給出，即Cij為結(jié)點i到結(jié)點j的權(quán)重。n為了有效地找出VS中滿足與S中的某個點i連接且(i, j) 權(quán)重最小的頂點j，對其中的每個頂點j設(shè)立兩個數(shù)組closestj和lowcostj：

6、nclosestj是s中與j最近的頂點，(closestj, j)即為選中的邊，而lowcostj是相應(yīng)邊的權(quán)重。2022-4-4計算機算法設(shè)計與分析9Prim算法的實現(xiàn)nPrim(int n, Type *c) 初始化：結(jié)點1放入S；并初始化lowcost和 closest； 執(zhí)行以下操作n1次： 依據(jù)lowcost找出與S最近的點j并放入S； 調(diào)整lowcost和closest；int j = 1; sj = true; for (int i = 2; i = n; i+) closesti = 1; lowcosti=c1i; si=false;for (int i = 1; i n;

7、i+) min= inf; for (int k = 2; k = n; k+) if (lowcostkmin&!sk) min = lowcostk; j = k sj = true; s中僅加入了一個新成員j，因此只需要依據(jù)結(jié)點j調(diào)整lowcost和closest； for (int k = 2; k = n; k+) if (cjk lowcostk&!sk) lowcostk = cjk; closestk = j 2022-4-4計算機算法設(shè)計與分析10Prim算法的示例n給定一個連通帶權(quán)圖如下：1234561655536624n初始時S=1，T= ；1n第一次選擇

8、： (1, 3)權(quán)最小 S=1, 3 T= (1, 3) ；3n第二次選擇： (3, 6)權(quán)最小 S=1, 3, 6， T= (1, 3), (3, 6) ；6n第三次選擇： (6, 4)權(quán)最小 S=1, 3, 6, 4， T= (1, 3), (3, 6), (6, 4) ；4n第四次選擇： (2, 3)權(quán)最小 S=1, 3, 6, 4, 2， T= (1, 3), (3, 6), (6, 4), (2, 3) ；2n第五次選擇： (5, 2)權(quán)最小 S=1, 3, 6, 4, 2, 5， T= (1, 3), (3, 6), (6, 4), (3, 2) (2, 5) ；52022-4-4

9、計算機算法設(shè)計與分析11Kruskal算法n基本思想：在保證無回路的前提下依次選出權(quán)重較小的n 1條邊。n貪心策略：如果(i, j)是E中尚未被選中的邊中權(quán)重最小的，并且(i, j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇 (i, j)。問題：如何知道(i, j)不會造成回路？n若邊(i, j) 的兩個端點i和j屬于同一個連通分支，則選擇(i, j) 會造成回路，反之則不會造成回路。n因此初始時將圖的n個頂點看成n個孤立分支。2022-4-4計算機算法設(shè)計與分析12Kruskal算法的數(shù)據(jù)結(jié)構(gòu)n數(shù)組e表示圖的邊，eiu、eiv和ekw分別表示邊i的兩個端點及其權(quán)重。n函數(shù)Sort(e, w)將數(shù)

10、組e按權(quán)重w從小到大排序。n一個連通分支中的頂點表示為一個集合。n函數(shù)Initialize(n)將每個頂點初始化為一個集合n函數(shù)Find(u)給出頂點u所在的集合。n函數(shù)Union(a, b)給出集合a和集合b的并集。n重載算符!=判斷集合的不相等。2022-4-4計算機算法設(shè)計與分析13Kruskal算法的實現(xiàn)Kruskal(int n, *e) Sort(e, w); /將邊按權(quán)重從小到大排序 initialize(n); /初始時每個頂點為一個集合 k = 1; /k累計已選邊的數(shù)目， j = 1; /j為所選的邊在e中的序號 while (k n) /選擇n 1條邊 a = Find(

11、eju); b = Find(ejv); /找出第j條邊兩個端點所在的集合 if (a != b) tk+ = j; Union(a, b) /若不同，第j條邊放入樹中并合并這兩個集合 j+ /繼續(xù)考察下一條邊2022-4-4計算機算法設(shè)計與分析14Kruskal算法的例子1234561655536624131462253364145235345126356566初始時為6個孤立點123456選擇了邊1，于是1、3點合并為同一個集合。選擇了邊2，于是4、6點合并為同一個集合。選擇了邊3，于是2、5點合并為同一個集合。選擇了邊4，于是1、3、4、6點合并為同一個集合考察邊5，因為1、4點屬于同一

12、個集合，被放棄。選擇邊6，于是1、3、4、6、2、5點屬于同一個集合。已經(jīng)選擇邊了n1條邊，算法結(jié)束。結(jié)果如圖所示。uvw2022-4-4計算機算法設(shè)計與分析15Prim與Kruskal兩算法的復(fù)雜性nPrim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，因此其復(fù)雜性為O(n2)。nKruskal算法中，設(shè)邊數(shù)為e，則邊排序的時間為O(e)，確定邊的時間為O(loge)，所以整個時間復(fù)雜性為O(eloge)。n當(dāng)e = (n2)時，Kruskal算法要比Prim算法差；n當(dāng)e = (n2)時，Kruskal算法比Prim算法好得多。2022-4-4計算機算法設(shè)計與分析16貪心算法也能獲得

13、最優(yōu)解n用Kruskal算法得到的生成樹T*必是最優(yōu)樹。n證明：設(shè)T*不是最優(yōu)，令T是與T*有k條共同邊的最優(yōu)樹且k是最優(yōu)樹與T*共有邊數(shù)的最大值n TT* ek+1: ek+1 E(T)且ek+1E(T*)。n則T+ek+1含唯一回路C，C必有條邊ekE(T*)。n令T= (T+ek) ek, w(T)=w(T)+w(ek+1) w(ek)。 n由算法知，w(ek+1) w(ek)， T是最優(yōu)樹。n但T與T*有k+1條共同邊，矛盾。故T*是最優(yōu)2022-4-4計算機算法設(shè)計與分析17貪心算法的基本要素n貪心算法的基本要素是：貪心選擇性質(zhì)。n所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系

14、列局部最優(yōu)解的選擇，即貪心選擇來達到。n貪心選擇每次選取當(dāng)前最優(yōu)解，因此它依賴以往的選擇，而不依賴于將來的選擇。n貪心算法通常以自頂向下的方式進行，每次貪心選擇就將原問題轉(zhuǎn)化為規(guī)模更小的子問題。2022-4-4計算機算法設(shè)計與分析18如何確定貪心選擇性質(zhì)n證明貪心選擇將導(dǎo)致整體的最優(yōu)解：n首先證明存在問題的一個整體最優(yōu)解必定包含了第一個貪心選擇。n然后證明在做了貪心選擇后，原問題簡化為規(guī)模較小的類似子問題，即可繼續(xù)使用貪心選擇。n于是用數(shù)學(xué)歸納法可證明，經(jīng)過一系列貪心選擇可以得到整體最優(yōu)解。2022-4-4計算機算法設(shè)計與分析19旅行商問題n推銷員從某城市出發(fā)，遍歷n個城市最后返回出發(fā)城市。設(shè)

15、從城市i到城市j的費用為cij，如何選擇旅行路線使得該推銷員此趟旅行的總費用最小? n圖論語言表述：給定n個節(jié)點簡單無向完全圖G=，c(i,j)是節(jié)點i到j(luò)的代價(邊權(quán))。在G中求遍歷所有節(jié)點簡單回路C，使C上所有邊權(quán)的和最小。 2022-4-4計算機算法設(shè)計與分析20旅行商問題分析12345112752443312435 對于n個節(jié)點的旅行商問題，n個節(jié)點的任意一個圓排列都是問題的一個可能解。n個節(jié)點的圓排列有(n-1)!個，因此問題歸結(jié)為在(n-1)!個回路中選取最小回路。 是否能夠不用O(n-1)!)時間來求解旅行商問題？ 2022-4-4計算機算法設(shè)計與分析21旅行商問題的貪心算法n基

16、本思想：首先設(shè)置一個集合Path和當(dāng)前節(jié)點v，然后不斷地用貪心選擇來擴充這個集合，直至Path包含所有V中頂點。n貪心選擇：如果VPath中的頂點j是與當(dāng)前節(jié)點v相鄰接的頂點中邊權(quán)最小的，于是就選擇j(將j加入Path)，并將j作為新的當(dāng)前節(jié)點 。n初始化：Path中僅含有源v。2022-4-4計算機算法設(shè)計與分析22最臨近算法中的數(shù)據(jù)結(jié)構(gòu)n圖用連接矩陣Wij給出，即Wij為結(jié)點i到結(jié)點j的權(quán)重。nPath記錄依次連接的城市，p記錄當(dāng)前到達的最后一個頂點，cost為當(dāng)前路徑長度。n如果節(jié)點k已經(jīng)到達，則arrivedk=true。2022-4-4計算機算法設(shè)計與分析23旅行商問題的最臨近算法C

17、ostType Tray_Greedy(int n,CostType *w,int *path)for(i=1;i=n;i+) arrivedi=false; cost=0; /初始化 path1=1; p=1;arrived1=true; /從節(jié)點1出發(fā) for(i=2;i=n;i+) min=inf; for(j=1;j=n;j+) if (!arrivedj & wpjmin) k=j; min=wpj /搜索最臨近p且尚未到達過的節(jié)點k cost=cost+wpk; pathi=k; arrivedk=true; p=k; /將節(jié)點k加入到路徑中 cost=cost+wp1;

18、return cost; /加上回路最后一條邊的權(quán) 2022-4-4計算機算法設(shè)計與分析24旅行商算法舉例從節(jié)點1出發(fā)：Path= ;cost=14; 因此最臨近法不保證求得旅行商問題的精確解，只能得到問題地近似解。一般地，貪心選擇只依賴于前面選擇步驟地最優(yōu)性，因此是局部最優(yōu)的，所以貪心法不能夠確保求出問題的最優(yōu)解。 不難看出，從節(jié)點2出發(fā)：Path= ;cost=10;且此為最優(yōu)解！2022-4-4計算機算法設(shè)計與分析25改進的旅行商算法n如果分別從節(jié)點i出發(fā)（i=1,2,.n）執(zhí)行算法Tray_Greedy，通過結(jié)果比較，取最小代價回路，可以求得更接近于最佳解的近似解。 n詳見書上P40算

19、法Tray_Greedy12022-4-4計算機算法設(shè)計與分析26Tray_Greedy算法的計算復(fù)雜性nTray_Greedy算法有兩層循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)也是n次，因此Tray_Greedy算法的時間復(fù)雜度為 O(n2)nTray_Greedy1 算法分別從n個節(jié)點出發(fā)計算最小代價回路，其時間復(fù)雜度為O(n3)2022-4-4計算機算法設(shè)計與分析27活動安排問題n設(shè)有n個活動的集合E = 1, 2, , n，其中每個活動都要求使用同一資源，且在同一時間里只能有一個活動可以使用該資源?，F(xiàn)要求給出一個活動安排，使得利用該資源活動為最多。 n每個活動i都有使用該資源的一個啟始時間si和

20、一個結(jié)束時間fi，sifi，其占用資源的時間為半開區(qū)間si , fi)。若區(qū)間si , fi)與區(qū)間sj , fj)不相交，則稱活動i與活動j是相容的?；顒影才艈栴}就是求活動安排問題就是求E的最大相容活動子集。的最大相容活動子集。 2022-4-4計算機算法設(shè)計與分析28活動安排問題的貪心算法n基本思想：某項活動結(jié)束時間愈早，安排其它活動的剩余區(qū)間愈大。所以貪心策略為盡量選擇結(jié)束時間早的活動來安排。為此，將活動按結(jié)束時間的非減順序排序，即f1f2fn。顯然排序需要的時間為O(nlogn)。n貪心選擇：當(dāng)安排下第i個活動后，可能有：fisi+1，所以第i+1個活動無法安排，這就必須舍棄第i+1個

21、活動，檢測第i+2個活動直到第i+k個活動的si+kfi，就把此活動安排進來。2022-4-4計算機算法設(shè)計與分析29活動安排的例子首先選定活動1，其結(jié)束時間f1=4。然后因s4 = 54，選定活動4，這時f4 = 7。又因s8 = 87，選定活動8，這時f8 = 11。最后因s11 = 1211，選定活動11。最終的活動安排為：最終的活動安排為：1、4、8和和11。i12345678910 11si130535688212fi45678910 11 12 13 142022-4-4計算機算法設(shè)計與分析30活動安排貪心算法的實現(xiàn)typedef struct int number; /活動的編號

22、 float start; /活動開始的時間 float end; /活動結(jié)束的時間 Bool selected; /標(biāo)記活動是否被選擇Active; int greedySelector(Active activity, int n) QuitckSort(activity,n); /將活動按結(jié)束時間排序 activity1.selected=true; j=1;count=1; for(i=2;i=activityj.end) activityi.selected=true; j=i; count+; else activityi.selected=false; return count;

23、 2022-4-4計算機算法設(shè)計與分析31貪心算法能夠得到活動安排問題的最優(yōu)解 n設(shè)活動集合E=1, 2, , n以按結(jié)束時間的非減順序排列，活動1具有最早結(jié)束時間。n首先必定有最優(yōu)解包含活動1。否則設(shè)A是E的最優(yōu)解，且A中最早結(jié)束的活動是k。若k1，則活動1必與A中除k以外的活動相容。令B=Ak1，則B也是最優(yōu)解。 進一步，假設(shè)A是原問題的包含活動1的最優(yōu)解，則A=A1是活動集合E=iE且sif1的一個最優(yōu)解。反之，如果能夠找到E的一個解B，它包含了比A更多的活動，則將活動1加入到B中將產(chǎn)生E的一個解B，它包含比A更多的活動。這與假設(shè)矛盾n因此，所做的每一步貪心選擇都將產(chǎn)生一個比原問題規(guī)模更小的具有相同特征的子問題。由數(shù)學(xué)歸納法可知，貪心法得到的是最優(yōu)解。2022-4-4計算機算法設(shè)計與分析32算法復(fù)雜性分析n算法由兩部分組成：n第一部分是排序，時間復(fù)雜度為O(nlogn)；n第二部分是選擇合適的活動，是一個定長循環(huán)，時間復(fù)雜度為O(n)；n故總的時間復(fù)雜度為O(nlogn)。 2022-4-4計算機算法設(shè)計與分析33最優(yōu)裝載問題n有一批集裝箱要裝上一艘載重為C的輪船。其中集裝箱i的重量為Wi。假定裝載體積不受限制，要將盡可能多(這個多，是指的貨物數(shù)目)的集裝箱裝上輪船。n 該問題的形式化描述為： 有約束條件 , ni1 , 1 , 0