GreedyAlgorithm--精品PPT課件.ppt

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