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

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

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

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

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

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

6、nclosestj是s中與j最近的頂點(diǎn)，(closestj, j)即為選中的邊，而lowcostj是相應(yīng)邊的權(quán)重。2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析9Prim算法的實(shí)現(xiàn)nPrim(int n, Type *c) 初始化：結(jié)點(diǎn)1放入S；并初始化lowcost和 closest； 執(zhí)行以下操作n1次： 依據(jù)lowcost找出與S最近的點(diǎn)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中僅加入了一個(gè)新成員j，因此只需要依據(jù)結(jié)點(diǎn)j調(diào)整lowcost和closest； for (int k = 2; k = n; k+) if (cjk lowcostk&!sk) lowcostk = cjk; closestk = j 2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析10Prim算法的示例n給定一個(gè)連通帶權(quán)圖如下：1234561655536624n初始時(shí)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、計(jì)算機(jī)算法設(shè)計(jì)與分析11Kruskal算法n基本思想：在保證無(wú)回路的前提下依次選出權(quán)重較小的n 1條邊。n貪心策略：如果(i, j)是E中尚未被選中的邊中權(quán)重最小的，并且(i, j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇 (i, j)。問(wèn)題：如何知道(i, j)不會(huì)造成回路？n若邊(i, j) 的兩個(gè)端點(diǎn)i和j屬于同一個(gè)連通分支，則選擇(i, j) 會(huì)造成回路，反之則不會(huì)造成回路。n因此初始時(shí)將圖的n個(gè)頂點(diǎn)看成n個(gè)孤立分支。2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析12Kruskal算法的數(shù)據(jù)結(jié)構(gòu)n數(shù)組e表示圖的邊，eiu、eiv和ekw分別表示邊i的兩個(gè)端點(diǎn)及其權(quán)重。n函數(shù)Sort(e, w)將數(shù)

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

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

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

13、最優(yōu)解n用Kruskal算法得到的生成樹(shù)T*必是最優(yōu)樹(shù)。n證明：設(shè)T*不是最優(yōu)，令T是與T*有k條共同邊的最優(yōu)樹(shù)且k是最優(yōu)樹(shù)與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)樹(shù)。n但T與T*有k+1條共同邊，矛盾。故T*是最優(yōu)2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析17貪心算法的基本要素n貪心算法的基本要素是：貪心選擇性質(zhì)。n所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系

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

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

16、本思想：首先設(shè)置一個(gè)集合Path和當(dāng)前節(jié)點(diǎn)v，然后不斷地用貪心選擇來(lái)擴(kuò)充這個(gè)集合，直至Path包含所有V中頂點(diǎn)。n貪心選擇：如果VPath中的頂點(diǎn)j是與當(dāng)前節(jié)點(diǎn)v相鄰接的頂點(diǎn)中邊權(quán)最小的，于是就選擇j(將j加入Path)，并將j作為新的當(dāng)前節(jié)點(diǎn) 。n初始化：Path中僅含有源v。2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析22最臨近算法中的數(shù)據(jù)結(jié)構(gòu)n圖用連接矩陣Wij給出，即Wij為結(jié)點(diǎn)i到結(jié)點(diǎn)j的權(quán)重。nPath記錄依次連接的城市，p記錄當(dāng)前到達(dá)的最后一個(gè)頂點(diǎn)，cost為當(dāng)前路徑長(zhǎng)度。n如果節(jié)點(diǎn)k已經(jīng)到達(dá)，則arrivedk=true。2022-4-4計(jì)算機(jī)算法設(shè)計(jì)與分析23旅行商問(wèn)題的最臨近算法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é)點(diǎn)1出發(fā) for(i=2;i=n;i+) min=inf; for(j=1;j=n;j+) if (!arrivedj & wpjmin) k=j; min=wpj /搜索最臨近p且尚未到達(dá)過(guò)的節(jié)點(diǎn)k cost=cost+wpk; pathi=k; arrivedk=true; p=k; /將節(jié)點(diǎn)k加入到路徑中 cost=cost+wp1;

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

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

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

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

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