第八章-貪心算法

第8章貪心算法8.1簡(jiǎn)介例子例子：有4種硬幣，面值分別為2角5分、一角、五分和一分?，F(xiàn)在要求以最少的硬幣個(gè)數(shù)找給顧客6角三分。通常是：先拿兩個(gè)2角5分的＋1個(gè)一角＋3個(gè)一分這種找法所拿出的硬幣個(gè)數(shù)最少。這種算法其實(shí)就是貪心算法。顧名思義：該算法總是作出在當(dāng)前看來(lái)最好的選擇，并且不從整體上考慮最優(yōu)問(wèn)題，所作出的選擇只是在某種意義上的局部最優(yōu)解。上面的解法得到的恰好也是最優(yōu)解。因此，貪心方法的效率往往是很高的。假如，面值有一角一分、五分和一分，要找給顧客一角五分。如果還是使用上述貪心算法，得到的解是：一個(gè)一角一分＋4個(gè)一分。而最優(yōu)解是3個(gè)5分。又例如：154135437121154135437121424261615353求節(jié)點(diǎn)1到節(jié)點(diǎn)6的最短路徑。用貪心法得19，而實(shí)際為17。顯然貪心算法不能對(duì)所有問(wèn)題都能得到最優(yōu)解，但是對(duì)很多問(wèn)題（包括很多著名的問(wèn)題）都能產(chǎn)生整體最優(yōu)解。例如，我們今天要講的圖的單元最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題。在有些情況下，算法不能得到整體最優(yōu)解，但是結(jié)果確是最優(yōu)解的很好近似。貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇來(lái)達(dá)到，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素．也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別：動(dòng)態(tài)規(guī)劃算法：每步所做出的選樣往往依賴(lài)于相關(guān)子問(wèn)題的解，因而只有在解出相關(guān)子問(wèn)題后．才能做出選擇。貪心算法：僅在當(dāng)前狀態(tài)下做出最好選樣，即局部最優(yōu)選則。然后再去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。貪心算法所做出的貪心選則可以依賴(lài)于以往做過(guò)的選則，但決不依賴(lài)于將來(lái)所做的選樣，也不依賴(lài)于子問(wèn)題的解。動(dòng)態(tài)規(guī)劃：是自底向上的方法解各子問(wèn)題；貪心算法：是自頂向下的方法。每做出一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題.使用貪心法的難點(diǎn)在于：證明所設(shè)計(jì)的算法確實(shí)能夠正確解決所求解的問(wèn)題。即對(duì)于一個(gè)具體的問(wèn)題，必須證明每一步所做出的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。首先，考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開(kāi)始。做出貪心選擇后．原問(wèn)題簡(jiǎn)化為規(guī)模更小的類(lèi)似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明、通過(guò)每一步做貪心選擇．最終可得到問(wèn)題的整體最優(yōu)解。其中，證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模最小的類(lèi)似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類(lèi)算法的一個(gè)共同點(diǎn)。但是都具有最優(yōu)子結(jié)構(gòu)的問(wèn)題該選則貪心法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃法的也能用貪心算法解？背包問(wèn)題：給定n種物品和一個(gè)背包，物品i的體積為，價(jià)值為。已經(jīng)知道背包的承重量為C。假設(shè)是物體i被裝入背包的部分，；要求裝滿背包且背包內(nèi)物體價(jià)值最大。max選擇方法：目標(biāo)函數(shù)的值增加最快，而包載容量的消耗較慢的物體裝入包中。故優(yōu)先選擇價(jià)值體積比最大的物體裝入背包。背包與0-1背包的區(qū)別：結(jié)論0-1背包問(wèn)題能用動(dòng)態(tài)規(guī)劃法解，但不能用貪心法解。8.3單源最短路徑問(wèn)題(狄斯奎諾Dijkstra’s算法)一、問(wèn)題描述是一個(gè)有向圖，每條邊上有一個(gè)非負(fù)整數(shù)表示長(zhǎng)度值，其中有一個(gè)頂點(diǎn)稱(chēng)為源節(jié)點(diǎn)。所謂的單源最短路徑問(wèn)題就是：求解該源節(jié)點(diǎn)到所有其它節(jié)點(diǎn)的最短路徑值。不失去一般性，我們假設(shè)并且＝1。那么該問(wèn)題可以使用Dijkstra’s算法來(lái)求解，該算法是一種貪心算法，并且能求得最優(yōu)解。二、算法思想開(kāi)始時(shí)，我們將所有的頂點(diǎn)劃分為兩個(gè)集合。所有已經(jīng)計(jì)算好的頂點(diǎn)存放在中，中表示還沒(méi)有計(jì)算好的。中的每個(gè)頂點(diǎn)有一個(gè)對(duì)應(yīng)的量，該值是從源頂點(diǎn)到（并且只經(jīng)由中的頂點(diǎn)）的最短路徑值。下面就是選擇一個(gè)最小頂點(diǎn)，并將其移動(dòng)到中。一旦被從移動(dòng)到中，中每個(gè)和相鄰的頂點(diǎn)的都要更新：表示經(jīng)由到的一條更短的路徑被發(fā)現(xiàn)了。對(duì)于任意一個(gè)頂點(diǎn)，假如我們使用表示源頂點(diǎn)到頂點(diǎn)的最短路徑，最后，我們可以證明上述的貪心法結(jié)束后有。三、算法DIJKSTRA輸入：含權(quán)有向圖G=(V,E),V={1,2,…n}輸出：G中頂點(diǎn)1到其他頂點(diǎn)的距離1.;；2.Fory←2tonIfy相鄰于1thenElse；Endif6.endfor7.forj←1ton-18.令，找到最小9.X←X∪{y}/*將從移動(dòng)到中10Y←Y-{y}For每條邊{y,w}Ifw∈Yand+length[y,w]<then/*更新中和相鄰頂點(diǎn)的值endfor15.endfor四、舉例說(shuō)明：（手工解該題目）算法的詳細(xì)實(shí)現(xiàn)：有向圖用鄰接表來(lái)表示如圖假設(shè)每條邊是非負(fù)的X和Y集合用兩個(gè)向量來(lái)表示X[1..n],Y[1..n]。初始時(shí)X[1]=1,Y[1]=0.并且對(duì)于2<=i<=n,X[i]=0,Y[i]=1.因此，執(zhí)行的操作，就是X[y]=1,的操作就是，Y[y]=0。五、證明下面來(lái)證明，使用該DIJKSTRA方法得到的是最優(yōu)解，也就是。其中，表示源頂點(diǎn)到頂點(diǎn)的最短路徑；是從源頂點(diǎn)到（并且只經(jīng)由中的頂點(diǎn)）的最短路徑值。證明:歸納法顯然假設(shè)，當(dāng)前將移動(dòng)到中，并且在之前移動(dòng)到中的任何一個(gè)頂點(diǎn)，都有。由于是有限的，也就是說(shuō)必定存在一條從1到路徑，長(zhǎng)度為（我們需要來(lái)證明）。那么這條路徑總可以寫(xiě)作：：1→[]→[]→。。。→[]→[]→[]→y在上述序列中，我們總是可以找到一個(gè)頂點(diǎn)，不妨稱(chēng)之為（），使得之后的頂點(diǎn)均屬于，并且x是在y前最遲離開(kāi)Y的頂點(diǎn)。所以有以下兩種情形：1→[]→[]→。。?！鶾]→[x]→y(A)或是1→[]→[]→。。?！鶾x]→[]…→y(B)√對(duì)于情形(A)，算法要求歸納假設(shè)(A)是最短路徑√對(duì)于情形(B)，我們將之后的頂點(diǎn)不妨稱(chēng)之為，即：1→[]→[]→。。?！鶾x]→[w]…→y(B)于是有：由于在之前離開(kāi)算法要求歸納假設(shè)因?yàn)槭亲疃搪窂揭驗(yàn)槭亲疃搪窂轿覀円呀?jīng)說(shuō)了，是最短路徑了，因此。六、算法分析O(n2)或O(mn)稠圖的線性時(shí)間算法把算法的復(fù)雜度從O(n2)降到O(mlogn).基本思想是用最小堆數(shù)據(jù)結(jié)構(gòu)來(lái)保持集合Y中的頂點(diǎn)，使Y組中離V-Y最近的頂點(diǎn)y可以在O(logn)時(shí)間內(nèi)被選出.算法8.2SHORTESTPATH輸入：含權(quán)有向圖G=(V,E),V={1,2,…n}輸出：G中頂點(diǎn)1到其他頂點(diǎn)的距離.假設(shè)已有一個(gè)空堆H1.；;2.Fory←2tonIfy相鄰于1thenINSERT(H,y)Else；Endif6.endfor7.forj←1ton-18.Y←DELETEMIN(H)10Y←Y-{y}For對(duì)每個(gè)鄰接于y的頂點(diǎn)w∈YIf+length[y,w]<then/*更新中和相鄰頂點(diǎn)的值endifIfthenINSERT(H,w)ELSESIFTUP(H,H-1(w))endifendfor15.endfor其中，H-1(w)返回w再H中的位置，可以用一個(gè)數(shù)組實(shí)現(xiàn)。8.3最小生成樹(shù)設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，(V,T)是是G的一個(gè)子圖，并且T是一顆樹(shù)，那么稱(chēng)(V,T)是G的生成樹(shù)。如果T的權(quán)之和是所有生成樹(shù)中最小的，那么則稱(chēng)之為最小生成樹(shù)。我們假定G是連通的，如果G是非連通的，那么，可以對(duì)G的每個(gè)子圖應(yīng)用求解最小生成樹(shù)的算法。網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。最小生成樹(shù)性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹(shù)性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱(chēng)為MST性質(zhì)。8.33Kruskal算法（克魯斯卡爾）一、基本思想Kruskal算法構(gòu)造G的最小生成樹(shù)的基本思想是，首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹(shù)上的邊如下圖所示。二、KRUSKAL算法輸入：具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖輸出：的最小生成樹(shù)以非降序的方式對(duì)中各條邊的權(quán)進(jìn)行排序foreachMAKESET();endforwhilelet為中的下一條邊ifthentoendifendwhile關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。按權(quán)的遞增順序查看等價(jià)于對(duì)優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算?？梢杂枚褜?shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類(lèi)型并查集UnionFind所支持的基本運(yùn)算。三、Kruskal算法的正確性證明：我們只要證明，使用Kruskal算法過(guò)程中，每次循環(huán)所得到的(從空集增至最小生成樹(shù))總是圖G的最小生成樹(shù)的子集即可。使用歸納法＋反證法。G總是具有一個(gè)最小生成樹(shù)，不妨記為。當(dāng)前要加入的邊為。包含的那顆子樹(shù)的所有頂點(diǎn)用表示。假設(shè)在加入之前得到的均滿足，其中。令，下面我們要證明也是圖G的最小生成樹(shù)的子集。依據(jù)歸納假設(shè)，有。如果：顯然有如果：那么必將構(gòu)成一個(gè)環(huán)，也就是不再是樹(shù)。我們知道中必定包含這樣一條邊，且，且cost()cost()。否則，將被選擇加入。下面我們來(lái)證明就是。定義，那么也是圖的一個(gè)生成樹(shù)，并且cost()<cost()。也就是說(shuō)，是最小生成樹(shù)，那么不是最小生成樹(shù)。矛盾。所以必定是屬于的。也就必定有。證明完畢。四、時(shí)間復(fù)雜度：當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。8.4Prim算法（普里姆）一、基本思想設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n},。構(gòu)造G的最小生成樹(shù).Prim算法的基本思想：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹(shù)中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示二、算法算法8.4PRIM輸入：含權(quán)有向圖G=(V,E),V={1,2,…n}輸出：由G生成的最小耗費(fèi)生成樹(shù)T組成的邊的集合1.T←{};X←{1}；Y←V-{1}2.Fory←2tonIfy相鄰于1thenN[y]←1C[y]←c[1,y]Else；Endif8.endfor9.forj←1ton-1{尋找n-1條邊}10.令，找到最小11.T←T∪{(y,N[y]}{將邊y，N[y]加入T}12.X←X∪{y}/*將從移動(dòng)到中13Y←Y∪{y}For每個(gè)相鄰于y的頂點(diǎn)w∈YIfc[y,w]<C[w]thenN[w]←yC[w]←c[y,w]endif19.endfor20.endfor在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。三、算法分析用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。當(dāng)時(shí)，Kruskal算法比Prim算法差，但當(dāng)時(shí)，Kruskal算法卻比Prim算法好得多。8.6哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。哈夫曼編碼思想：給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。前綴碼對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱(chēng)為前綴碼。例：a:10,b:101存在二義性編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。平均碼長(zhǎng)定義為：使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱(chēng)為給定編碼字符集C的最優(yōu)前綴碼。構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱(chēng)為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二