第6講 貪心算法

1、 貪心算法找零錢問題找零錢問題l問題描述：用面額為d1d2dm的最少數(shù)量的硬幣找出金額為n的零錢。例：美國廣泛使用的硬幣面額為d1=25，d2=10，d3=5，d4=1。如何用這些面額給出48美分的找零？1個25美分，2個10美分，3個1美分基于“貪心”的想法可以將剩余的硬幣數(shù)量降為最低找零錢問題找零錢問題l例：假設(shè)有面值單位分別為1、4和6的硬幣。如果需要找出金額為8的零錢。若采用貪心算法，得到的解決方案如何？先選取面值最大的，然后再選小面值的采用1枚面值為6的硬幣，兩枚面值為2的硬幣更優(yōu)的解：2枚面值為4的硬幣l貪心算法并不能總是找出最優(yōu)解l采用動態(tài)規(guī)劃求最優(yōu)解貪心算法貪心算法l貪心法建議

2、通過一系列步驟來構(gòu)造問題的解，每一步對目前構(gòu)造的部分解做一個擴(kuò)展，直到獲得問題的完整解為止。l所做的每一步選擇都必須滿足以下條件：可行：即它必須滿足問題的約束局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇不可取消：選擇一旦做出，在算法的后面步驟中就無法改變了背包問題背包問題l問題描述給定n個體積分別為s1,s2,sn、價值分別為v1,v2,vn的物品和一個容量為C的背包，要找到非負(fù)實數(shù)x1,x2,xn, 使和 在約束 下最大。0/1背包問題：物品不可分一般背包問題：物品是可分割的在最優(yōu)解中，以某種合適的順序選擇每個物品，并盡可能將該物品裝入背包。niiivx1niiiCsx1Csxnii

3、i1背包問題背包問題l選擇函數(shù)：選擇剩余物品中價值最大的選擇剩余物品中體積最小的選擇單位體積上價值最高的l例：s1020304050v2030664060v/s2.01.52.21.01.2選擇xi值最大vi 0 0 1 0.5 1146最小si 1 1 1 1 0156最大vi/si 1 1 1 0 0.8164Algorithm Greedy-KNAPSACKlInput: size vector s1.n and value vector v1.n of n items that are both sorted as non-increasing order according to t

4、he ratio v(i)/s(i); the capacity C of the knapsack, the total number of items nlOutput: the greedy optimal solution x1.n lfor i 0 to nl xi 0lend forlcu Clfor i 0 to nl if si cu then lexit lend ifl x(i) 1l cu cu-s(i)lend forlif i n then x(i) cu/s(i) end iflreturn x活動安排問題活動安排問題活動安排問題就是要在所給的活動集合中選出最大的相

5、容活動子集合，是可以用貪心算法有效求解的很好例子活動安排問題活動安排問題l1 問題描述：設(shè)有設(shè)有n個活動的集合個活動的集合E=1,2,n，其中每個活動，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。內(nèi)只有一個活動能使用這一資源。每個活動每個活動i都有一個要求使用該資源的起始時間都有一個要求使用該資源的起始時間si和一個結(jié)束時間和一個結(jié)束時間fi,且且si fi 。如果選擇了活動。如果選擇了活動i，則它，則它在半開時間區(qū)間在半開時間區(qū)間si, fi)內(nèi)占用資源。內(nèi)占用資源。若區(qū)間若區(qū)間si, fi)與區(qū)間與區(qū)

6、間sj, fj)不相交，則稱活動不相交，則稱活動i與活與活動動j是相容的。也就是說，當(dāng)是相容的。也就是說，當(dāng)sifj或或sjfi時，活動時，活動i與活與活動動j相容。相容。 活動安排問題就是在所給的集合中選出最大的相活動安排問題就是在所給的集合中選出最大的相容活動子集合。容活動子集合。lint greedySelector(int s , int n, int f , bool a )l a1=true; j=1;l count=1;l for ( i=2;i=fj) l ai=true;l j=i;l count+;l l else ai=false;l l return count;l 各

7、活動的起始時間和結(jié)束時間各活動的起始時間和結(jié)束時間存儲于數(shù)組存儲于數(shù)組s s和和f f中且按結(jié)束時中且按結(jié)束時間的非減序排列間的非減序排列 活動安排問題活動安排問題活動安排問題活動安排問題由于輸入的活動以其完成時間的非減序非減序排列，所以算法greedySelectorgreedySelector每次總是選擇具具有最早完成時間有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。 活動安排問題活動安排問題例：例：設(shè)待安排的11個活動的

8、開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下： i1234567891011Si130535688212fi4567891011121314活動安排問題活動安排問題 算法算法greedySelector greedySelector 的計算過程的計算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。 活動安排問題活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)即證明活動安排問題總存在一個最優(yōu)解從貪心選擇開始。4.2 活動安排問題活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)設(shè)E=1,2

9、,n為所給的活動集合。由于E中的活動按結(jié)束時間的非遞減排序，故活動1具有最早完成時間。首先證明活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1.4.2 活動安排問題活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)設(shè)AE是所給活動安排問題的一個最優(yōu)解，且A中的活動也按結(jié)束時間非遞減排序，A中的第一個活動是k?；顒影才艈栴}活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)若k1,則A就是以貪心選擇開始的最優(yōu)解。若k1,設(shè)B=A-k1。因為f1=fk且A中的活動是相容的。古B中的活動也是相容的。又由于B中的活動個數(shù)與A中的活動個數(shù)相同，故A是最優(yōu)的，B也是最優(yōu)的。

10、即B是以選擇活動1開始的最優(yōu)活動安排。由此可見，總存在以貪心選擇開始的最優(yōu)活動安排方案?；顒影才艈栴}活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）2 最優(yōu)子結(jié)構(gòu)性質(zhì)在作出了貪心選擇，即選擇了活動1后，原問題簡化為對E中所有與活動1相容的活動進(jìn)行活動安排的子問題。即若A是原問題的最優(yōu)解，則A=A-1是活動安排問題的E=iE:Sif1的最優(yōu)解?；顒影才艈栴}活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）2 最優(yōu)子結(jié)構(gòu)性質(zhì)反證法：若E中存在另一個解B，比A有更多的活動，則將1加入B中產(chǎn)生另一個解B，比A有更多的活動。與A的最優(yōu)性矛盾。 活動安排問題活動安排問題l正確性證明（用數(shù)學(xué)歸納法證明）因此，每一步所

11、作出的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。對貪心選擇次數(shù)用歸納法可知，貪心算法greedySelector產(chǎn)生問題的最優(yōu)解。單源最短路徑問題（單源最短路徑問題（Dijkstra算法）算法）l問題描述已知有向圖 G = (V, E)，每條邊上的權(quán)值均為非負(fù)。其中一個結(jié)點s指定為源點，求從源點s到圖中所有其它結(jié)點x的距離，即s到x的最短路徑長度。lDijkstra算法 貪心策略按照最短路徑長度遞增的次序求得源點到達(dá)每一個頂點的最短路徑單源最短路徑問題單源最短路徑問題l最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)：最短路徑的子路徑是最短路徑子路徑是最短路徑對于一給定的帶權(quán)有向圖G=(V,E)，設(shè)p

12、=是從v1到vk的最短路徑。那么對于任意i,j，其中1 i j k，設(shè)pij=為p中從頂點vi到頂點vj的子路徑。那么，pij是從vi到vj的最短路徑。l證明：證明：如果將路徑p分解為 ，則有w(p)=w(p1i )+w(pij )+w(pjk )。假設(shè)存在一條從vi到vj的路徑pij，其權(quán)值w(pij)w(pij)。 那么， 是從v1到vk的一條路徑，它的權(quán)值w(p)=w(p1i )+w(pij)+w(pjk )小于w(p)，這與p是v1至vk的最短路徑相矛盾。kpjpipvvvvjkiji11kpjpipvvvvjkiji11Dijkstra算法思想算法思想l假設(shè)V=1,2,n, 源點s=

13、1。l初始頂點分為兩個集合X = 1 和Y = 2,3,.,n。X集中的頂點是已求得最短路徑的頂點；lY集中的每個頂點y都有一個標(biāo)記y, 它是目前從源點到頂點y，中間只經(jīng)過X集中的頂點的最短路徑的長度；l每次從Y集中選擇一個y值最小的頂點y加入X集；l一旦y加入X集，那么考察與y相鄰的每個頂點w的標(biāo)記，如果源點經(jīng)過y到達(dá)w的路徑更短，則更新該標(biāo)記；l若y表示從源點到v的距離，那么算法結(jié)束時，對每個頂點均有y= yAlgorithm 8.1 DIJKSTRA Input: A weighted directed graph G=(V,E), where V=1,2,n.Output: The d

14、istance from vertex 1 to every other vertex in G.1. X=1; YV-1; 102. for y2 to n3. if y is adjacent to 1 then ylength1,y4.else y 5.end if6.end for7.for j1 to n-18. Let y Y be such that y is minimum9.XX y add vertex y to X10.YY-y delete vertex y form Y11.for each edge (y,w)12.if w Y and y+lengthy,w w

15、then13. w y+lengthy,w14.end for15. end forDijkstra算法算法261534112531549413X11,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6Y34561221356104456171938619513617Dijkstra算法總是在Y集中選擇離源點最近的頂點加入集合X，故稱該算法使用了貪心策略。Dijkstra算法的貪心選擇性質(zhì)（正確性證明）算法的貪心選擇性質(zhì)（正確性證明）l貪心策略并非總是能獲得全局意義上的最理想結(jié)果，但Dijkstra算法確實得到了最短路徑。關(guān)鍵要證明，當(dāng)頂點y加入集合X時，有y= y1xwyX數(shù)

16、學(xué)歸納法證明數(shù)學(xué)歸納法證明Dijkstra算法算法l定理8.1：給出一個邊具有非負(fù)權(quán)值的有向圖G和源點s， Dijkstra算法在時間(n2) 內(nèi)找出從s到其他每一頂點距離的長度。l對Dijkstra算法的改進(jìn)針對稠密圖利用小頂堆數(shù)據(jù)結(jié)構(gòu)，在O(log)時間內(nèi)從Y集中選出頂點y采用鄰接表為圖的存儲結(jié)構(gòu)Algorithm 8.2 SHORTESTPATHInput: A weighted directed graph G=(V,E), where V=1,2,.,n.Output: The distance from vertex 1 to every other vertex in G. As

17、sume that we have an empty heap H at the beginning.1.YV-1; 10; key(1) 12.for y2 to n3.if y is adjacent to 1 then4. y=length1,y5. key(y) y6. INSERT(H,y)7.else8. y 9. keyy y10.end if 11. end for NEXT PAGEAlgorithm 8.2 SHORTESTPATH 12. for j1 to n-113.yDELETEMIN(H)14.YY-y15.for each vertex w Y that is

18、adjacent to y16. if y+lengthy,w w then17. w y+lengthy,w18.key(w) w19. end if20. if w H then INSERT(H,w)21. else SIFTUP(H,H-1(W)22. end if23.end for24. end forO(mlog n)最小生成樹問題（最小生成樹問題（Kruskal算法）算法）l定義8.1：設(shè)G = (V, E)是一個具有含權(quán)邊的連通無向圖。G的一棵生成樹(V,T)是G的作為樹的子圖。如給G加權(quán)并且T的各邊的權(quán)的和為最小值，那么(V,T)就稱為最小耗費生成樹，簡稱生成樹。l Kru

19、skal算法：對G的邊以非降序權(quán)重排列；對排好序的每條邊，如果將其加入T不會形成回路，則加入樹T中；否則將其丟棄。例：例： Kruskal算法算法61235412131139746(1,2)(1,3)(4,6)(5,6)(2,3)(4,5)(3,4)(2,4)(3,5)12346791113612354若構(gòu)成回路，則丟棄該邊若構(gòu)成回路，則丟棄該邊Kruskal算法的實現(xiàn)算法的實現(xiàn)l表示森林的數(shù)據(jù)結(jié)構(gòu)用不相交集數(shù)據(jù)結(jié)構(gòu)來表示森林初始時，圖的每個頂點由包含一個頂點的樹表示算法執(zhí)行時，森林中的每個連通分量由一棵樹來表示選擇權(quán)值最小的邊將兩個連通分量連接起來由Union操作實現(xiàn)Algorithm 8.

20、3 KRUSKAL Input: A weighted connected undirected graph G=(V,E) with n vertices. Output: The set of edges T of a minimum cost spanning tree for G.1.Sort the edges in E by nondecreasing weight2.for each vertex vV3.MAKESETv4.end for5.T=6.while |T|n-17.Let (x,y) be the next edge in E.8.if FIND(x) FIND(y

21、) then9. Add(x,y) to T10 UNION(x,y)11end if12. end whileKruskal算法正確性證明算法正確性證明l引理8.2：在含權(quán)無向圖中，Kruskal算法能正確地找出最小生成樹l證明：對T的大小實施歸納法，證明T是最小生成樹邊集的子集初始時，T=，命題成立；設(shè)加入邊e = (x,y)之前命題成立，即有TT*，其中T*是最小生成樹邊的集合；設(shè)X是包含x的子樹的頂點集，T=Te，需證明T也是最小生成樹邊集T*的子集。Kruskal算法正確性證明算法正確性證明l由于TT*，若T*包含e，則T=Te T*；l若T*不包含e，則T*e必定包含以e為一條邊的

22、回路；le=(x,y)連接了X中的一個頂點和V-X中的另一個頂點，則T*中必定存在另一條邊e=(w,z)，其中wX，zV-X；l由于e在e之前添加，故cost(e) cost(e)；l構(gòu)造T*=T*-ee，則TT*，且T*是最小生成樹邊的集合。Kruskal算法時間效率分析算法時間效率分析l第1和第2步分別花費 O(mlogm) 和(n), m = |E|; l第7步執(zhí)行n-1次，需要花費O(n);l第9步花費(1), 最多執(zhí)行m次,總共花費 O(m);lUnion操作執(zhí)行n-1 次，而find 操作最多執(zhí)行 2m 次.，兩個操作總的花費為O(mlog*n);l算法總的運(yùn)行時間取決于排序算法，

23、即O(mlogm);l定理8.3：在一個有m條邊的含權(quán)無向圖中， Kruskal算法可在O(mlogm)時間內(nèi)找出最小生成樹最小生成樹問題（最小生成樹問題（Prim算法）算法）l設(shè)G=(V,E), V取整數(shù)集合1,2,n. l算法從建立兩個頂點集開始: X=1和Y=2,n, 然后生長生成樹，每次生成一條邊。l生成的邊(x,y)具有以下性質(zhì)： xX, y Y， 且該邊是所有滿足上述條件的邊中權(quán)值最小者。l然后將y從Y集移到X集。l重復(fù)生成邊的步驟直到Y(jié)集為空為止。Prim算法算法1.T; X1; YV-12.while Y 3. Let (x,y) be of minimum weight su

24、ch that xX and yY4. XXy5. YY-y6. TT(x,y)7.end while 例：例：Prim算法生成生成樹算法生成生成樹61235412131139746Algorithm 8.4 PRIM Input: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G.1.T; X1; YV-12.for y2 to n3.if y adjacent to 1 then4.Ny

25、15.Cyc1,y6.else Cy7.end if 8.end for NEXT PAGEAlgorithm 8.4 PRIM9. for j1 to n-1 find n-1 edges10. Let yY be such that Cy is minimum11.TTy,Ny add edge (y,Ny) to T12.XXy add vertex y to X13. YY-y delete vertex y from Y14. for each vertex w Y that is adjacent to y15. if cy,wCw then16. Nwy17. Cwcy,w18.

26、 end if19. end for20. end for Prim算法的正確性證明算法的正確性證明l引理8.3：在含權(quán)無向圖中，Prim算法能正確地找出最小生成樹l證明：對T的大小實施歸納法，證明(X,T)是最小生成樹的子樹初始時，T=，命題成立；假設(shè)添加邊e=(x,y)之前命題成立， 其中xX, yY設(shè)X=Xy，T=Te，需證明G=(X,T)也是最小生成樹的子樹（參見P155）Prim算法的效率分析算法的效率分析l第1步花費(n); l第2步循環(huán)花費(n)時間.第3-6步花費O(n);l第10步搜索離X最近的頂點y，每次迭代花費時間(n). 搜索需執(zhí)行 n-1次，故第10步總體花費 (n2

27、); l第14步共執(zhí)行 2m 次，第15步測試執(zhí)行m次，第16、17步最多執(zhí)行m次；l因此，算法的時間復(fù)雜度為 (m+n2).Prim算法的改進(jìn)算法的改進(jìn)l利用最小堆數(shù)據(jù)結(jié)構(gòu)，使得可以在O(logn)時間內(nèi)取得Y集中的頂點y，這個y和V-Y集中一個頂點連接的邊的代價是最小的。改進(jìn)的改進(jìn)的Prim算法算法Input: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G. Assume that

28、we have an empty heap H at the beginning.1.T; YV-12.for y2 to n3. if y is adjacent to 1 then4.Ny15.key(y)c1,y6.INSERT(H,y)7. else key(y)8. end if9. end for NEXT PAGE改進(jìn)的改進(jìn)的Prim算法算法 10. for j1 to n-1 find n-1 edges11. yDELETEMIN(H)12. TT(y,N|y|) add edge (y,N|y|) to T13. YY-y delete vertex y from Y14.

29、 for each vertex w Y that is adjacent to y15. if cy,wkey(w) then16. Nwy17. key(w)cy,w18.end if19.if w H then INSERT(H,w)20.else SIFTUP(H,H-1(w)21. end for22. end for文件壓縮問題（文件壓縮問題（Huffman樹算法）樹算法）l設(shè)有100,000個字符的文件，其中只包含有 a, e, t, r, f, d 六種不同的字符，且字符出現(xiàn)的頻度不盡相同。計算機(jī)中能夠表達(dá)的信息只有0和1。怎樣編碼才能使文件的編碼長度最短？文件編碼文件編碼ae

30、trfd頻度(千字)4513121695等長等長編碼編碼000001010011100101變長變長編碼編碼1000101011011011100變長變長編碼編碼201011001111101110011011000110110001100110011001100前綴編碼前綴編碼前綴編碼前綴編碼a45e13t12r16d5f9000011111 00a45t12e13d5f9r160000011111用用二叉樹二叉樹表表示示前綴編碼前綴編碼等長等長編碼編碼變長變長編碼編碼CcTcdcfTB)()()(文件編碼長度文件編碼長度Huffman算法算法l貪心策略：將短的編碼分配給高頻字符，長的編碼分配給低頻字符構(gòu)造 n 棵只含根只含根結(jié)點的二叉樹選擇兩個權(quán)值最小權(quán)值最小的二叉樹，構(gòu)造新的二叉樹重復(fù)重復(fù)該過程，直到只剩一棵只剩一棵二叉樹為止Huffman算法的正確性算法的正確性l具有貪心選擇性質(zhì)設(shè)x和y是字母表C中具有最低頻度的兩個字符，則存在C的一種最優(yōu)前綴編碼，其中x和y的編碼長度相同但