GreedyAlgorithm--精品PPT課件.ppt

第五章 Greedy Algorithm,鄒權(quán)（博士） 計(jì)算機(jī)科學(xué)系,5.1 Elements of Greedy Algorithms 5.2 An activity-selection problem 5.3 Huffman codes 5.4 Minimal spanning tree problem,提要,5.1 Elements of Greedy Algorithms,Greedy算法的基本概念 Greedy選擇性 優(yōu)化子結(jié)構(gòu) 與動(dòng)態(tài)規(guī)劃方法的比較 Greedy算法正確性證明方法,4,Optimal,Local Optimal,Greedy算法的基本思想 求解最優(yōu)化問(wèn)題的算法包含一系列步驟 每一步都有一組選擇 作出在當(dāng)前看來(lái)最好的選擇 希望通過(guò)作出局部?jī)?yōu)化選擇達(dá)到全局優(yōu)化選擇 Greedy算法不一定總產(chǎn)生優(yōu)化解 Greedy算法是否產(chǎn)生優(yōu)化解，需嚴(yán)格證明 Greedy算法產(chǎn)生優(yōu)化解的條件 Greedy-choice-property Optimal substructure,Greedy算法的基本概念,Greedy選擇性,Greedy選擇性 若一個(gè)優(yōu)化問(wèn)題的全局優(yōu)化解可以通過(guò) 局部?jī)?yōu)化選擇得到，則該問(wèn)題稱為具有 Greedy選擇性. 一個(gè)問(wèn)題是否具有Greedy選擇性需證明,若一個(gè)優(yōu)化問(wèn)題的優(yōu)化解包含它的 子問(wèn)題的優(yōu)化解，則稱其具有優(yōu)化 子結(jié)構(gòu),優(yōu)化子結(jié)構(gòu),與動(dòng)態(tài)規(guī)劃方法的比較,動(dòng)態(tài)規(guī)劃方法可用的條件 優(yōu)化子結(jié)構(gòu) 子問(wèn)題重疊性 子問(wèn)題空間小 Greedy方法可用的條件 優(yōu)化子結(jié)構(gòu) Greedy選擇性 可用Greedy方法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用 可用動(dòng)態(tài)規(guī)劃方法時(shí)，Greedy方法可能不適用,證明算法所求解的問(wèn)題具有優(yōu)化子結(jié)構(gòu) 證明算法所求解的問(wèn)題具有Greedy選擇性 證明算法確實(shí)按照Greedy選擇性進(jìn)行局部?jī)?yōu)化選擇,Greedy算法正確性證明方法,5.2 An activity-selection problem,問(wèn)題的定義 優(yōu)化解的結(jié)構(gòu)分析 算法設(shè)計(jì) 算法復(fù)雜性 算法正確性證明,問(wèn)題的定義,活動(dòng) 設(shè)S=1,2,n是n個(gè)活動(dòng)的集合，各個(gè)活動(dòng)使 用同一個(gè)資源，資源在同一時(shí)間只能為一個(gè)活動(dòng)使用 每個(gè)活動(dòng)i有起始時(shí)間si，終止時(shí)間fi，si fi 相容活動(dòng) 活動(dòng)i和j是相容的，若sjfi或sifj，即,Sj,fj,Si,fi,問(wèn)題定義 輸入：S=1, 2, , n，F(xiàn)= si，fi ，ni1 輸出：S的最大相容集合,貪心思想: 為了選擇最多的相容活動(dòng)，每次選fi最小的活動(dòng)，使我們能夠選更多的活動(dòng),引理1 設(shè)S=1,2,n是n個(gè)活動(dòng)集合，si，fi 是活動(dòng) 的起始終止時(shí)間，且f1f2.fn，S的活動(dòng)選 擇問(wèn)題的某個(gè)優(yōu)化解包括活動(dòng)1. 證 設(shè)A是一個(gè)優(yōu)化解，按結(jié)束時(shí)間排序A中活動(dòng)， 設(shè)其第一個(gè)活動(dòng)為k，第二個(gè)活動(dòng)為j. 如果k=1，引理成立. 如果k1，令B=A-k1, 由于A中活動(dòng)相容，f1fk sj , B中活動(dòng)相容. 因?yàn)锽=A, 所以B是一個(gè)優(yōu)化解，且包括活動(dòng)1.,優(yōu)化解結(jié)構(gòu)分析,引理2.設(shè)S=1, 2, , n是n個(gè)活動(dòng)集合，si，fi是活動(dòng)i 的起始終止時(shí)間，且f1f2.fn，設(shè)A是S的調(diào) 度問(wèn)題的一個(gè)優(yōu)化解且包括活動(dòng)1，則A=A-1 是S=iS|sif1的調(diào)度問(wèn)題的優(yōu)化解. 證.顯然，A中的活動(dòng)是相容的. 我們僅需要證明A是最大的. 設(shè)不然，存在一個(gè)S 的活動(dòng)選擇問(wèn)題的優(yōu)化解 B，BA. 令B=1B. 對(duì)于iS, si f1, B中活動(dòng)相容. B是S的一個(gè)解. 由于|A|=|A|+1, B=B+1A+1=A，與A最 大矛盾.,引理2說(shuō)明活動(dòng)選擇問(wèn)題具有優(yōu)化子結(jié)構(gòu),Greedy選擇性 引理3.設(shè) S=1, 2, ., n 是 n 個(gè)活動(dòng)集合，f0=0, li 是 Si = jS | sj fi-1 中具有最小結(jié)束時(shí)間 fli 的活 動(dòng).設(shè)A是S的包含活動(dòng)1的優(yōu)化解, 其中 f1 fn，則A= 證.對(duì)A作歸納法. 當(dāng)A=1時(shí), 由引理1，命題成立. 設(shè)Ak時(shí)，命題成立. 當(dāng)A=k時(shí),由引理2，A=1A1, A1是 S2 = jS | sj f1 的優(yōu)化解. 由歸納假設(shè)，A1= . 于是, A= .,貪心思想 為了選擇最多的相容活動(dòng)，每次選fi最小的活動(dòng)，使我們能夠選更多的活動(dòng),算法的設(shè)計(jì),算法 （設(shè)f1f2.fn已排序） Greedy-Activity-Selector(S, F) nlenyth(S); A1 j1 For i2 To n Do If si fj Then AAi；ji； Return A,如果結(jié)束時(shí)間已排序 T(n)=(n) 如果 結(jié)束時(shí)間未排序 T(n)=(n)+(nlogn)=(nlogn),復(fù)雜性設(shè)計(jì),需要證明 活動(dòng)選擇問(wèn)題具有Greedy選擇性 活動(dòng)選擇問(wèn)題具有優(yōu)化子結(jié)構(gòu) 算法按照Greedy選擇性計(jì)算解,算法正確性證明,定理. Greedy-Activity-Selector算法能夠產(chǎn) 生最優(yōu)解. 證. Greedy-Activity-Selector算法按照引 理3的Greedy選擇性進(jìn)行局部?jī)?yōu)化選 擇.,5.3 Huffman codes,問(wèn)題的定義 優(yōu)化解的結(jié)構(gòu)分析 算法設(shè)計(jì) 算法復(fù)雜性分析 算法正確性證明,二進(jìn)制字符編碼 每個(gè)字符用一個(gè)二進(jìn)制0、1串來(lái)表示. 固定長(zhǎng)編碼 每個(gè)字符都用相同長(zhǎng)的0、1串表示. 可變長(zhǎng)編碼 經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的用長(zhǎng)碼 前綴編碼 無(wú)任何字符的編碼是另一個(gè)字符編碼的前綴,問(wèn)題的定義,編碼樹(shù),葉結(jié)點(diǎn): 用字符及其出現(xiàn)頻率標(biāo)記,內(nèi)結(jié)點(diǎn): 用其子樹(shù)的葉結(jié)點(diǎn)的頻率和標(biāo)記,邊標(biāo)記: 左邊標(biāo)記0，右側(cè)邊標(biāo)記1,編碼樹(shù)T的代價(jià) 設(shè)C是字母表,cC f(c)是c在文件中出現(xiàn)的頻率 dT(c)是葉子c在樹(shù)T中的深度，即c的編碼長(zhǎng)度 T的代價(jià)是編碼一個(gè)文件的所有字符的代碼位數(shù): B(T)=,優(yōu)化編碼樹(shù)問(wèn)題 輸入: 字母表 C = c1, c2, , cn ， 頻率表 F = f(c1), f(c2), ., f(cn) 輸出: 具有最小B(T)的C前綴編碼樹(shù),貪心思想： 循環(huán)地選擇具有最低頻率的兩個(gè)結(jié)點(diǎn)， 生成一棵子樹(shù)，直至形成樹(shù),我們需要證明 優(yōu)化前綴樹(shù)問(wèn)題具有優(yōu)化子結(jié)構(gòu) 優(yōu)化前綴樹(shù)問(wèn)題具有Greedy選擇性,優(yōu)化解的結(jié)構(gòu)分析,優(yōu)化子結(jié)構(gòu) 引理1.設(shè)T是字母表C的優(yōu)化前綴樹(shù)，cC，f(c) 是c在文件中出現(xiàn)的頻率.設(shè)x、y是T中任意 兩個(gè)相鄰葉結(jié)點(diǎn)，z是它們的父結(jié)點(diǎn)，則z作 為頻率是f(z)=f(x)+f(y)的字符，T=T-x,y是 字母表C=C-x,yz的優(yōu)化前綴編碼樹(shù).,證. 往證B(T)=B(T)+f(x)+f(y). vC-x,y, dT(v)=dT(v), f(v)dT(v)=f(v)dT(v). 由于 dT(x)=dT(y)=dT(z)+1, f(x)dT(x)+f(y)dT(y) =(f(x)+f(y)(dT(z)+1) =(f(x)+f(y)dT(z)+(f(x)+f(y) 由于 f(x)+f(y)=f(z), f(x)dT(x)+f(y)dT(y)=f(z)dT(z)+(f(x)+f(y). 于是B(T)=B(T)+f(x)+f(y). 若T不是C的優(yōu)化前綴編碼樹(shù)， 則必存在T，使B(T)B(T). 因?yàn)閦是C中字符，它必為T(mén)中的葉子. 把結(jié)點(diǎn)x與y加入T，作為z的子結(jié)點(diǎn)， 則得到C的一個(gè)如下前綴編碼樹(shù)T：,T代價(jià)為： B(T)= +(f(x)+f(y)(dT(z)+1) = +f(z)dT(z)+(f(x)+f(y) (dT(z)=dT(z) = B(T)+f(x)+f(y)B(T)+f(x)+f(y)= B(T) 與T是優(yōu)化的矛盾，故T是C的優(yōu)化編碼樹(shù).,Greedy選擇性 引理2. 設(shè)C是字母表，cC，c具有頻率f(c), x、y 是C中具有最小頻率的兩個(gè)字符，則存在一 個(gè)C的優(yōu)化前綴樹(shù)，x與y的編碼具有相同長(zhǎng) 度，且僅在最末一位不同.,不失一般性，設(shè)f(b)f(c), f(x)f(y). 因x與y是具有 最低頻率的字符, f(b)f(x), f(c)f(y).交換T的b和x, 從T構(gòu)造T :,證: 設(shè)T是C的優(yōu)化前綴樹(shù)，且b和c是具有最大深度的 兩個(gè)兄弟字符:,交換y和c 構(gòu)造T,往證T是最優(yōu)化前綴樹(shù). B(T)-B(T) = = f(x)dT(x) + f(b)dT(b) - f(x)dT(x) - f(b)dT(b) = f(x)dT(x) + f(b)dT(b) - f(x)dT(b) - f(b)dT(x) = (f(b)-f(x)(dT(b)-dT(x). f(b)f(x), dT(b)dT(x) (因?yàn)閎的深度最大) B(T)-B(T)0, B(T)B(T) 同理可證B(T)B(T). 于是B(T)B(T). 由于T是最優(yōu)化的，所以B(T)B(T). 于是, B(T)=B(T)，T是C的最優(yōu)化前綴編碼樹(shù). 在T中, x和y具有相同長(zhǎng)度編碼, 且僅最后一位不同.,基本思想 循環(huán)地選擇具有最低頻率的兩個(gè)結(jié)點(diǎn)，生成一棵子樹(shù)，直至形成樹(shù) 初始: f:5, e:9, c:12, b:13, d:16, a:45,算法的設(shè)計(jì),Greedy算法(使用堆操作實(shí)現(xiàn)) Huffman(C，F(xiàn)) 1. nC; 2. QC; /* 用BUILD-HEAP建立堆 */ 3. FOR i1 To n-1 Do 4. zAllocate-Node( ); 5. xleftzExtract-MIN(Q); /* 堆操作*/ 6. yrightzExtract-MIN(Q); /* 堆操作*/ 7. f(z)f(x)+f(y); 8. Insert(Q, z); /* 堆操作*/ 9. Return,設(shè)Q由一個(gè)堆實(shí)現(xiàn) 第2步用堆排序的BUILD-HEAP實(shí)現(xiàn): O(n) 每個(gè)堆操作要求O(logn)，循環(huán)n-1次: O(nlogn) T(n)=0(n)+0(nlogn) =0(nlogn),復(fù)雜性分析,定理. Huffman算法產(chǎn)生一個(gè)優(yōu)化前綴編碼樹(shù) 證. 由于引理1、引理2成立,而且Huffman算 法按照引理2的Greedy選擇性確定的規(guī) 則進(jìn)行局部?jī)?yōu)化選擇，所以Huffman算 法產(chǎn)生一個(gè)優(yōu)化前綴編碼樹(shù)。,正確性證明,5.4 Minimal spanning tree problem,問(wèn)題的定義 優(yōu)化解結(jié)構(gòu)分析 Greedy選擇性 Kruskal算法 算法復(fù)雜性 算法正確性證明,問(wèn)題的定義,生成樹(shù) 設(shè)G=(V, E)是一個(gè)邊加權(quán)無(wú)向連通圖. G的生成 樹(shù)是無(wú)向樹(shù)S=(V, T), TE, 以下用T表示S. 如果 W: E實(shí)數(shù) 是G的權(quán)函數(shù), T的權(quán)值定 義為W(T)=(u,v)TW(u,v). 最小生成樹(shù) G的最小生成樹(shù)是W(T)最小的G之生成樹(shù). 問(wèn)題的定義 輸入: 無(wú)向連通圖G=(V, E), 權(quán)函數(shù)W 輸出: G的最小生成樹(shù),實(shí)例,算法思想,B,C,A,E,D,70,60,80,50,定理1. 設(shè)T是G的最小生成樹(shù). 如果T包含子樹(shù)T1和 T2, T1是G的子連通圖G1的生成樹(shù)，T2是G 的子連通圖G2的生成樹(shù)，則T1是G1的最小 生成樹(shù)，T2是G2的最小生成樹(shù). 證.,優(yōu)化解的結(jié)構(gòu)分析,Greedy選擇性,一般算法 初始: A為空集合 反復(fù)擴(kuò)展邊集合A, 直至A成為最小生成樹(shù) 循環(huán)不變命題 每次循環(huán)算法要保持下邊循環(huán)不變命題為真 “在每次循環(huán)前，A必是某個(gè)最小生成樹(shù)的子集” 在每次循環(huán)中, 如果A(u, v)是某個(gè)最小生成樹(shù) 的子集，則稱邊(u, v)是安全邊,一般算法的定義 Generic-MST(G, W) 1. A=; /* 不變命題真 */ While A 不是生成樹(shù) Do /* 不變命題真 */ 尋找一個(gè)安全邊(u, v); A=A (u, v) ; Return A /* 不變命題真 */,算法的關(guān)鍵是第三步, 尋找安全邊(u, v),尋找安全邊的規(guī)則 定義1. 無(wú)向圖G=(V, E)的一個(gè)劃分是V的一個(gè)劃分 (S, V-S). 定義2. 如果uS, vV-S, 則邊(u, v)稱為劃分(S, V-S) 的交叉邊. 定義3. 如果邊集合A中沒(méi)有邊是劃分(S, V-S)的交 叉邊, 則稱劃分(S, V-S)尊重A. 定義4. 劃分(S, V-S)的交叉邊(u, v)稱為輕邊, 如果在 所有(S, V-S)的交叉邊中, (u, v)的權(quán)值最小. 定義5. 邊(u, v)是滿足某性質(zhì)的輕邊, 如果在滿足該性 質(zhì)的邊中, (u, v)的權(quán)值最小.,示例,紅結(jié)點(diǎn)集合是S 淺藍(lán)結(jié)點(diǎn)集合是V-S 藍(lán)邊是交叉邊, 權(quán)為7的邊是輕邊 紅邊集合是受尊重的邊集合,定理1. 設(shè)G=(V, E)是具有邊加權(quán)函數(shù)W的無(wú)向連通圖, AE是包含在G的某個(gè)最小生成樹(shù)中的邊集合, (S,V-S)是G的尊重A的任意劃分, (u,v)是(S,V-S) 的交叉輕邊, 則(u, v)對(duì)A是安全的. 證. 令T是包含A的最小生成樹(shù). 如果(u, v)屬于T, 則(u, v)對(duì)A是安全的. 設(shè)(u, v)不屬于T. 我們構(gòu)造一個(gè)G的最小生成樹(shù) T, 使其包含A(u, v), 從而證明(u, v)安全.,由于u和v在劃分(S, V-S) 的兩邊, T至少存在一條交叉邊在p中, 設(shè)為(x, y). 由于劃分尊重A, (x, y)不在A中. 刪除 p中的