第八講 貪心算法 一種求解最優(yōu)化問(wèn)題的有效算法

1、Algorithms Design Techniques and Analysis第八章貪心算法 一種求解最優(yōu)化問(wèn)題的有效算法Algorithms Design Techniques and Analysis本章內(nèi)容本章內(nèi)容引言最短路徑問(wèn)題最小耗費(fèi)生成樹(shù)Kruskal算法Prim算法文件壓縮Algorithms Design Techniques and Analysis8.1 引言 顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。 雖然貪心算法不能對(duì)所有問(wèn)題都得到

2、整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路徑問(wèn)題，最小生成樹(shù)問(wèn)題等。 在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。Algorithms Design Techniques and Analysis8.1 引言 與動(dòng)態(tài)規(guī)劃算法比較: 貪心算法通常用來(lái)于求解最優(yōu)化問(wèn)題，即量的最大化或最小化。 然而，貪心算法不像動(dòng)態(tài)規(guī)劃算法，它通常包含一個(gè)用以尋找局部最優(yōu)解的迭代過(guò)程。在某些實(shí)例中，這些局部最優(yōu)解轉(zhuǎn)變成了全局最優(yōu)解，而在另外一些情況下，則無(wú)法找到最優(yōu)解。Algorithms Design Techniques and Analysis基本思想 貪心算法

3、在少量計(jì)算的基礎(chǔ)上做出正確猜想而不急于考慮以后的情況。 它一步步地來(lái)構(gòu)筑解。 每一步均是建立在局部最優(yōu)解的基礎(chǔ)之上，而每一步又都擴(kuò)大了部分解的規(guī)模。 做出的選擇產(chǎn)生最大的直接收益而又保持可行性。 因?yàn)槊恳徊降墓ぷ骱苌偾一谏倭啃畔?，所得算法特別有效。Algorithms Design Techniques and Analysis例子: 分?jǐn)?shù)背包問(wèn)題 問(wèn)題描述: 給出n個(gè)大小為s1, s2,. , sn,值為v1 ,v2,.,vn的項(xiàng)目，并設(shè)背包容量為C,要找到非負(fù)實(shí)數(shù)x1,x2,xn使和 在約束 下最大 niiivx1niiiCsx1Algorithms Design Techniques

4、and Analysis例子 n=3, C=20, (v1,v2,v3)=(25,24,15),(s1,s2,s3)=(18,15,10) 可行方案: (x1,x2,x3)sixi vixi(1)(1/2,1/3,1/4)16.524.5 (2)(1,2/15,0)2028.2(3)(0,2/3,1)2031(4)(0,1,1/2)2031.5Algorithms Design Techniques and Analysis選擇策略-1 從剩下的物品中選擇最大價(jià)值的物品裝入背包，得到： 方案(2)(1,2/15,0) 2028.2 (非最優(yōu)) 原因：雖然價(jià)值很大，但是容量的消耗太快Algori

5、thms Design Techniques and Analysis選擇策略-2 從剩下的物品中選擇最小尺寸的物品裝入背包。 方案(3) (0,2/3,1) 2031 (非最優(yōu)) 原因：雖然容量損耗較少，但是價(jià)值增長(zhǎng)速度太慢Algorithms Design Techniques and Analysis選擇策略-3 從剩下的物品中選擇最大vi/si比率的物品裝入背包。 Solution (4) (0,1,1/2)2031.5 (最優(yōu))Algorithms Design Techniques and AnalysisGreedy algorithm to solve Knapsack Ste

6、p 1: 每項(xiàng)計(jì)算yi=vi/si，即該項(xiàng)值和大小的比 Step 2: 再按比值的降序來(lái)排序，從第一項(xiàng)開(kāi)始裝背包，然后是第二項(xiàng)，依次類(lèi)推，盡可能地多放，直至裝滿背包。Algorithms Design Techniques and Analysis算法Greedy-KNAPSACK輸入輸入: 按照v(i)/s(i)比率降序排列的 n個(gè)物品的容量數(shù)組s1.n和物品價(jià)值數(shù)組v1.n; 背包的總?cè)萘緾, 物品的數(shù)量n輸出輸出: 最優(yōu)貪心算法結(jié)果x1.n for i 0 to n 初始化xi xi 0end forcu Cfor i 0 to n 物品按次序裝入背包 if si cu then exi

7、t end if x(i) 1 cu cu-s(i) 剩余背包容量end forif i n then x(i) cu/s(i) end if 最后剩余背包容量中裝入物品i的比率return xAlgorithms Design Techniques and Analysis貪心算法架構(gòu)Algorithm GREEDY(A,n)solutionfor i1 to n doxSELECT(A)if FEASIBLE(solution,x)then solutionUNION(solution,x)end ifend forreturn (solution)Algorithms Design Te

8、chniques and Analysis貪心算法特點(diǎn) 算法由一個(gè)簡(jiǎn)單的迭代過(guò)程構(gòu)成，在維持可行性的前提下它選擇能產(chǎn)生最大直接利益的項(xiàng)。 貪心算法產(chǎn)生全局最優(yōu)解的最重要因素是選擇策略。Algorithms Design Techniques and Analysis貪心算法基本要素 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。 但是，從許多可用貪心算法求解的問(wèn)題中我們看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 Algorithms Design Techniques and Analysis貪心選擇性質(zhì)

9、所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。Algorithms Design Techniques and Analysis最優(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ì)。問(wèn)

10、題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類(lèi)算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解? 是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?Algorithms Design Techniques and Analysis8.2 最短路徑問(wèn)題 問(wèn)題描述: 設(shè)G = (V, E)是一個(gè)每條邊有非負(fù)長(zhǎng)度的有向圖，有一個(gè)特異頂點(diǎn)s稱(chēng)為源。 單源最短路徑問(wèn)題，或者簡(jiǎn)稱(chēng)為最短路徑問(wèn)題，是要確定從s到V中每一個(gè)其他頂點(diǎn)的距離，這里從頂點(diǎn)s到頂點(diǎn)x的距離定義為從s到x的最短路徑的長(zhǎng)

11、度。Algorithms Design Techniques and AnalysisDijkstra算法基本思想貪心技術(shù): Select the path in nonincreasing order. 為簡(jiǎn)便起見(jiàn)，我們假設(shè)V=1,2,n, s=1. 初始時(shí)，將頂點(diǎn)分為兩個(gè)集合X = 1 和 Y = 2,3,.,n。這樣做的目的是讓X包含這樣的頂點(diǎn)集合:從源點(diǎn)到這些頂點(diǎn)的距離已經(jīng)確定。 在每一步中，我們選定源點(diǎn)到它的距離己經(jīng)獲得的一個(gè)頂點(diǎn)y Y ，并將這個(gè)頂點(diǎn)移到X中。 與Y中的每個(gè)頂點(diǎn)y聯(lián)系的是標(biāo)記y，它是只經(jīng)過(guò)X中頂點(diǎn)的最短路徑的長(zhǎng)度，一旦頂點(diǎn)y Y移到X中，與y相鄰的每個(gè)頂點(diǎn) w Y的

12、標(biāo)記就被更新，這表示找到了經(jīng)過(guò)y到w的更短路徑。 Algorithms Design Techniques and Analysis算法算法8.1 DIJKSTRA 輸入:含權(quán)有向圖G=(V,E), where V=1,2,n.輸出: G中頂點(diǎn)1到其他頂點(diǎn)的距離。1. X=1; YV-1; 102. for y2 to n3. if y 相鄰于 1 then ylength1,y4.else y 5.end if6.end for7.for j1 to n-18. 令y Y 使得y 最小9.XX y 將頂點(diǎn)y 加入X10.YY-y 將頂點(diǎn)y 從 Y中刪除11.for 每條邊(y,w)12.if

13、 w Y and y+lengthy,w w then13. w y+lengthy,w14.end for15. end forAlgorithms Design Techniques and Analysis例子261534112531549413X11,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6Y34561221356104456171938619513617Success!Algorithms Design Techniques and Analysis數(shù)據(jù)結(jié)構(gòu)123456T FFFFF123456F TTTTT123456213 123943553451361

14、564X:Y:Algorithms Design Techniques and Analysis正確性引理8.1: 在算法DIJKSTRA中，當(dāng)頂點(diǎn)y在第8步中被選中，如果標(biāo)記y 是有限的，那么、 y = y。(y 表示從源點(diǎn)x到y(tǒng)的距離）證明： 對(duì)頂點(diǎn)離開(kāi)集合Y并進(jìn)入X的次序做歸納。 第1個(gè)離開(kāi)的頂點(diǎn)是1，我們有1=1=0。假設(shè)引理中的結(jié)論對(duì)于所有在y前離開(kāi)Y的頂點(diǎn)都成立。 因?yàn)閥是有限的，則必存在從1到y(tǒng)的路徑，它的長(zhǎng)是y。設(shè)=1,x,w,y是從1到y(tǒng)的最短路徑，其中x是在y前最遲離開(kāi)Y的頂點(diǎn)。我們有y w x+length(x,w)=x+length(x,w)= w y. 上述的證明基于

15、這樣一個(gè)假設(shè)，即所有的邊長(zhǎng)都是非負(fù)的。 p149Algorithms Design Techniques and Analysis算法分析 第1步: (n) 時(shí)間. 第3步 和第4步: 分別為(n) 和O(n) 第8步: (n2). 第9步和第 10步:每次迭代花費(fèi)時(shí)間(1) ，公用了(n) 時(shí)間. 第11步和第12步共需要時(shí)間(m). 這里m=|E|. 根據(jù)以上得出算法的時(shí)間復(fù)雜性是(m+n2) = (n2). p149 定理 8.1 給出一個(gè)邊具有非負(fù)權(quán)的有向圖G和源頂點(diǎn)s ，算法DIJKSTRA在時(shí)間 (n2)內(nèi)找出從s到其他每一頂點(diǎn)距離的長(zhǎng)度Algorithms Design Tech

16、niques and Analysis8.2.1 稠圖的線性時(shí)間算法 基本思想: 用最小堆數(shù)據(jù)結(jié)構(gòu)來(lái)保持集合Y中的頂點(diǎn)，使Y組中離V-Y最近的頂點(diǎn)y可以在O(log n)時(shí)間內(nèi)被選出 與每個(gè)頂點(diǎn)v相關(guān)的鍵就是它的標(biāo)記v. 最后的算法如算法SHORTESTPATH所示Algorithms Design Techniques and Analysis算法算法8.2 SHORTESTPATH輸入:含權(quán)有向圖G=(V,E), where V=1,2,.,n.輸出: G中頂點(diǎn)1到其他頂點(diǎn)的距離。假設(shè)已有一個(gè)空堆H。1.YV-1; 10; key(1) 12.for y2 to n3.if y 鄰接于1

17、then4. y=length1,y5. key(y) y6. INSERT(H,y)7.else8. y 9. keyy y10.end if 11. end for NEXT PAGEAlgorithms Design Techniques and Analysis算法算法8.2 SHORTESTPATH 12. for j1 to n-113.yDELETEMIN(H)14.YY-y 將頂點(diǎn)y從Y刪除15. for每個(gè)鄰接于y的頂點(diǎn)w Y16. if y+lengthy,w0 ，m n1+，那么它可以被改善為在時(shí)間time O(m/)內(nèi)運(yùn)行。 P151Algorithms Design

18、Techniques and Analysis8.3 最小耗費(fèi)生成樹(shù) (Kruskal算法) 定義8.1: 設(shè)G = (V, E)是一個(gè)具有含權(quán)邊的連通無(wú)向圖。G的一裸生成樹(shù)(V, T)是G的作為樹(shù)的子圖。如給G加權(quán)并且T的各邊的權(quán)的和為最小值，那么(V,T)就稱(chēng)為最小耗費(fèi)生成樹(shù)或簡(jiǎn)稱(chēng)為最小生成樹(shù) 問(wèn)題描述 假設(shè)G為連通的，怎么找到最小生成樹(shù) (MST)?Algorithms Design Techniques and AnalysisKruskal算法基本思想工作原理：維護(hù)由許多生成樹(shù)組成的一個(gè)森林，這些生成樹(shù)逐步合并直到最終森林只由一棵樹(shù)組成，這棵樹(shù)就是最小耗費(fèi)生成樹(shù)。Step 1:此算法

19、先從對(duì)權(quán)以非降序排列著手。Step 2:接著從由圖的頂點(diǎn)組成而不包含邊的森林(V, T)開(kāi)始，重復(fù)下面的這一步，直到(V, T)被變換成一棵樹(shù)： 設(shè)(V,T)是到現(xiàn)在為止構(gòu)建的森林， eE-T為當(dāng)前考慮的邊，如果把e加到T中不生成一個(gè)回路，那么將e加入進(jìn)T，否則丟棄。 這個(gè)處理在恰好加完n-1條邊后結(jié)束。Algorithms Design Techniques and Analysis例子61235412131139746(1,2)(1,3)(4,6)(5,6)(2,3)(4,5)(3,4)(2,4)(3,5)12346791113612354!構(gòu)成回路, 這條邊被丟棄.Success!Alg

20、orithms Design Techniques and AnalysisKruskal算法的執(zhí)行 數(shù)據(jù)結(jié)構(gòu)來(lái)表示森林: 為有效地實(shí)現(xiàn)此算法，我們需要某種機(jī)制來(lái)檢測(cè)加入邊后是否構(gòu)成回路。讓它在算法的每個(gè)時(shí)刻來(lái)表示森林，并且在向T中添加邊時(shí)動(dòng)態(tài)檢測(cè)是否有回路生成。 這種數(shù)據(jù)結(jié)構(gòu)的一個(gè)合適選擇是4.3節(jié)討論過(guò)的不相交集表示法 開(kāi)始時(shí)，圖的每個(gè)頂點(diǎn)由一棵包含一個(gè)頂點(diǎn)的樹(shù)表示 在算法的執(zhí)行過(guò)程中，森林中的每個(gè)連通分量由一棵樹(shù)來(lái)表示。Algorithms Design Techniques and Analysis算法算法8.3 KRUSKAL輸入:包含n個(gè)頂點(diǎn)的含權(quán)連通無(wú)向圖G=(V,E)。輸出:由

21、G生成的最小耗費(fèi)生成樹(shù)T組成的邊的集合。1. 按非降序權(quán)重將E中的邊排序2.for 每條邊vV3.MAKESETv4.end for5.T=6.while |T|n-17.令 (x,y)為E中的下一條邊.8.if FIND(x) FIND(y) then 檢查x，y是否在同一顆樹(shù)中9. 將(x,y) 加入 T10 UNION(x,y)11end if12. end whileAlgorithms Design Techniques and Analysis正確性 引理8.2: 在含權(quán)無(wú)向圖中，算法KRUSKAL正確地找出最小生成樹(shù)。 反證法：假設(shè)KRUSKAL生成的不是最小生成樹(shù)1).設(shè)KRU

22、SKAL生成的樹(shù)為G02).假設(shè)存在Gmin使得cost(Gmin)cost(G0) 則在Gmin中存在不屬于G03).將加入G0中可得一個(gè)環(huán)，且不是該環(huán)的最長(zhǎng)邊(這是因?yàn)镚min)4).這與KRUSKAL每次生成最短邊矛盾5).故假設(shè)不成立，命題得證.Proof P241(or P153)Algorithms Design Techniques and Analysis算法分析 第1步和第2步分別花費(fèi)O(mlogm) 和(n), 這里 m = |E|. 第7步好執(zhí)行n-1次總共要(n)時(shí)間。合并運(yùn)算執(zhí)行n-1次，查找運(yùn)算最多2m次. 第5步花費(fèi)(1)，再加上第9步最多執(zhí)行m次，它的總花費(fèi)是O

23、(m). 由定理4.3，這兩個(gè)運(yùn)算的總花費(fèi)是O(mlog*n). 。這樣算法總的運(yùn)行時(shí)間取決于排序步，也就是O(mlogm) p153Algorithms Design Techniques and Analysis8.4 最小耗費(fèi)生成樹(shù) (Prim算法) 基本思想 設(shè)G=(V,E)，為了簡(jiǎn)便起見(jiàn)，V取整數(shù)集合 1,2,n. 算法從建立兩個(gè)頂點(diǎn)集合開(kāi)始: X=1和Y=2,n 。接著生長(zhǎng)一棵生成樹(shù)，每次一條邊。 在每一步，它找出一條權(quán)重最小的邊(x,y) ，這里xX，y Y并且把y從Y移到X。重復(fù)這一步直到Y(jié)為空。Algorithms Design Techniques and Analysis

24、Prim算法此算法概況如下：T; X1; YV-1while Y 設(shè)(x,y)是最小權(quán)重的邊，其中xX and yY XXy YY-y TT(x,y)end while Algorithms Design Techniques and Analysis例子61235412131139746Success!Algorithms Design Techniques and Analysis算法算法 8.4 PRIM p154輸入:含權(quán)連通無(wú)向圖G=(V,E), 其中 V=1,2,.,n.輸出:由G生成的最小耗費(fèi)生成樹(shù)T組成的邊的集合。1.T; X1; YV-12.for y2 to n3.if y

25、 鄰接于1 then4.Ny15.Cyc1,y6.else Cy7.end if 8.end for NEXT PAGEAlgorithms Design Techniques and Analysis算法算法 8.4 PRIM9. for j1 to n-1 尋找n-1 條邊10. 令yY 使得 Cy 最小11.TTy,Ny 將邊(y,Ny) 加入 T12.XXy 將頂點(diǎn)y 加入 X13. YY-y 從Y刪除頂點(diǎn)14. for 每個(gè)鄰接于y的頂點(diǎn) w Y15. if cy,wCw then16. Nwy17. Cwcy,w18. end if19. end for20. end for Al

26、gorithms Design Techniques and Analysis算法分析 第1步耗費(fèi) (n)時(shí)間. 第2步的for循環(huán)需要時(shí)間(n) .第3步到第6步需要時(shí)間O(n). 第10步搜索離X最近的頂點(diǎn)y，每迭代一次需要花費(fèi)時(shí)間(n) ，而這一步執(zhí)行了n-1次，所以第10步一共花費(fèi)時(shí)間(n2) 第11步、第12步和第13步，每迭代一次花費(fèi)時(shí)間(1) 總共花費(fèi)時(shí)間(n) 。 第14步的for循環(huán)執(zhí)行了2m次，第14步一共需要的時(shí)間是(m)P156 這就得到了算法的時(shí)間復(fù)雜性是(m+n2) Algorithms Design Techniques and Analysis8.4.1 稠圖的

27、線性時(shí)間算法基本思想 現(xiàn)在要改進(jìn)算法PRIM，就像曾經(jīng)對(duì)算法DIJKSTRA所做的那樣，目標(biāo)是把m= o(n2)的那類(lèi)圖的時(shí)間復(fù)雜性從(n2)減少到O(mlogn) 。以后還要進(jìn)一步改進(jìn)它，使在稠圖情況下，可以在對(duì)邊數(shù)的線性時(shí)間內(nèi)運(yùn)行。 就像在算法SHORTESTPATH中那樣，基本思想是用最小堆數(shù)據(jù)結(jié)構(gòu)(見(jiàn)4.2節(jié))來(lái)保持邊界頂點(diǎn)集，使得可以在O(logn)時(shí)間內(nèi)取得Y集中的頂點(diǎn)y，這個(gè)y和V-Y集中一個(gè)頂點(diǎn)連接的邊的耗費(fèi)是最小的。修改后的算法在算法MST中給出。Algorithms Design Techniques and Analysis算法算法 8.5 MST輸入:含權(quán)連通無(wú)向圖G=

28、(V,E), where V=1,2,.,n.輸出:由G生成的最小耗費(fèi)生成樹(shù)T組成的邊的集合。假設(shè)我們已有一個(gè)空堆H.1.T; YV-12.for y2 to n3. if y 鄰接于1 then4.Ny15.key(y)c1,y6.INSERT(H,y)7. else key(y)8. end if9. end for NEXT PAGEAlgorithms Design Techniques and Analysis 算法8.5 MST 10. for j1 to n-1 查找n-1 條邊11. yDELETEMIN(H)12. TT(y,N|y|) 添加邊(y,N|y|)到T13. YY

29、-y 從Y刪除頂點(diǎn)y14. for 每個(gè)鄰接于y的頂點(diǎn)w Y15. if cy,w0, m n1+，那么它可以被進(jìn)一步改進(jìn)為在O(m/) 時(shí)間內(nèi)運(yùn)行。Algorithms Design Techniques and Analysis8.5 文件壓縮 問(wèn)題描述: 假設(shè)有一個(gè)字符串文件，我們希望用這樣一種方法盡可能多地壓縮文件，但源文件能夠很容易地被重建。 設(shè)文件中的字符集是C = c1,c2,.,cn，又設(shè)f(ci),1 i n，是文件中字符ci的頻度，即文件中ci出現(xiàn)的次數(shù)。用定長(zhǎng)比特?cái)?shù)表示每個(gè)字符，稱(chēng)為字符的編碼，文件的大小取決于文件中的字符數(shù)。Algorithms Design Techniques and Analysis變長(zhǎng)編碼 然而由于有些字符的頻度可能遠(yuǎn)大于另外一些字符的頻度，所以用變長(zhǎng)的編碼是有道理的。從直觀上說(shuō)，那些頻度大的字符將被賦予短的編碼，而長(zhǎng)的編碼可以賦給那些頻度小的字符。當(dāng)編碼在長(zhǎng)度上變化時(shí)，我們規(guī)定一個(gè)字符的編碼