算法2013s-貪心算法I

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析2022年4月22日講授內(nèi)容：貪心算法貪心算法I教師：胡學(xué)鋼、吳共慶胡學(xué)鋼、吳共慶綱要綱要 圖等表示 最小擴(kuò)展樹(shù) 最優(yōu)子結(jié)構(gòu) 貪婪選擇 Prims 貪婪 MST算法4/22/2022算法設(shè)計(jì)與分析-貪心算法I2 有向圖有向圖 (digraph)G = (V, E) 是一個(gè)有序?qū)Φ募希旤c(diǎn)頂點(diǎn)V 的集合 (singular: vertex),邊邊的集合E V V . 無(wú)向圖無(wú)向圖G = (V, E) 中，邊集合E包括無(wú)序 的頂點(diǎn)對(duì). 任何情況下 均有 |E| =O(V 2) . 另外，如果 G 是連通的, 那么 |E| |V| 1, 這意味著 lg |E| =

2、(lgV).圖圖 (復(fù)習(xí)復(fù)習(xí))4/22/2022算法設(shè)計(jì)與分析-貪心算法I3鄰接矩陣表示法鄰接矩陣表示法 一個(gè)圖G = (V, E)的鄰接矩陣鄰接矩陣, V = 1, 2, , n, 為矩陣 A1 . . n, 1 . . nA 1 2 3 41234 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0(V 2) 存儲(chǔ)空間 稠密稠密表示法.Ai, j =1 if (i, j) E, 0 if (i, j) E.4/22/2022算法設(shè)計(jì)與分析-貪心算法I4頂點(diǎn) v V 的鄰接鏈表鄰接鏈表 Adjv是和頂點(diǎn)v相鄰的頂點(diǎn)的鏈表。Adj1 = 2, 3Adj2 = 3Adj3 = Adj

3、4 = 3對(duì)于無(wú)向圖, |Adjv| = degree(v).對(duì)于有向圖, |Adjv| = out-degree(v).握手定理：握手定理：對(duì)于無(wú)向圖vV = 2|E| 鄰接表使用的存儲(chǔ)空間為 (V + E) 是一種 稀疏稀疏 表示 (對(duì)兩種圖均適用).鄰接鏈表表示法鄰接鏈表表示法4/22/2022算法設(shè)計(jì)與分析-貪心算法I5輸入輸入: 一個(gè)連通的, 無(wú)向圖 G = (V, E)其加權(quán)函數(shù) w : E .為了簡(jiǎn)化，假設(shè)所有邊的權(quán)各不相同. (CLRS 包括了通用的情況.)輸出輸出: 擴(kuò)展樹(shù)擴(kuò)展樹(shù) T 連接所有頂點(diǎn)的樹(shù) 其權(quán)最小:最小擴(kuò)展樹(shù)最小擴(kuò)展樹(shù)4/22/2022算法設(shè)計(jì)與分析-貪心算法I

4、6MST舉例舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I7MST T:(G的其他頂點(diǎn)沒(méi)有畫(huà)出)去掉邊 (u, v) T. 然后,將T劃分為兩棵子樹(shù)T1 和T2.定理：定理：子樹(shù) T1 是 G1 = (V1, E1) 的MST， G1是由T1的頂點(diǎn)導(dǎo)出導(dǎo)出G的子圖 。 V1 = T1的頂點(diǎn), E1 = (x, y) E : x, y V1 .T2類(lèi)似.最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)4/22/2022算法設(shè)計(jì)與分析-貪心算法I8證明：粘貼拷貝：w(T) = w(u, v) + w(T1) + w(T2).如果 T1 是 G1中比T1加權(quán)更小的擴(kuò)展樹(shù)，那么在G中T= (u, v)T1 T2 將是一棵比T加

5、權(quán)更小的擴(kuò)展樹(shù)。我們得到了重疊子問(wèn)題了嗎? 是的.很好，那么可以使用動(dòng)態(tài)規(guī)劃! 是的，但是 MST 表現(xiàn)出更強(qiáng)特征，可以使用更加有效的算法。證明最優(yōu)子結(jié)構(gòu)證明最優(yōu)子結(jié)構(gòu)4/22/2022算法設(shè)計(jì)與分析-貪心算法I9定理：定理：令 T 為 G = (V, E) 的 MST, 并且令 A V。假設(shè) (u, v) E是連接A和V A的最小加權(quán)邊.那么, (u, v) T.貪婪選擇特征貪婪選擇特征局部的最優(yōu)選擇全局范圍內(nèi)也是最優(yōu)的.“貪婪貪婪”算法的特征算法的特征4/22/2022算法設(shè)計(jì)與分析-貪心算法I10證明. 假設(shè) (u, v) T. 粘貼和拷貝.T:(u, v) =連接A 和 V A的最小加

6、權(quán)邊 A V A定理的證明定理的證明4/22/2022算法設(shè)計(jì)與分析-貪心算法I11T: A V A考慮T中從u到v的唯一的簡(jiǎn)單路徑.證明. 假設(shè) (u, v) T. 粘貼和拷貝.(u, v) =連接A 和 V A的最小加權(quán)邊證明. 假設(shè) (u, v) T. 粘貼和拷貝.(u, v) =連接A 和 V A的最小加權(quán)邊定理的證明定理的證明4/22/2022算法設(shè)計(jì)與分析-貪心算法I12T: A V A將(u, v) 和這條路徑上的第一條邊交換，這個(gè)邊連接A中的一個(gè)頂點(diǎn)，同時(shí)連接V A中的一個(gè)頂點(diǎn)?？紤]T中從u到v的唯一的簡(jiǎn)單路徑.證明. 假設(shè) (u, v) T. 粘貼和拷貝.(u, v) =連接

7、A 和 V A的最小加權(quán)邊證明. 假設(shè) (u, v) T. 粘貼和拷貝.(u, v) =連接A 和 V A的最小加權(quán)邊定理的證明定理的證明4/22/2022算法設(shè)計(jì)與分析-貪心算法I13T: A V A將(u, v) 和這條路徑上的第一條邊交換，這個(gè)邊連接A中的一個(gè)頂點(diǎn)，同時(shí)連接V A中的一個(gè)頂點(diǎn)。一個(gè)比T加權(quán)更小的擴(kuò)展樹(shù)產(chǎn)生了?？紤]T中從u到v的的一的簡(jiǎn)單路徑.證明. 假設(shè) (u, v) T. 粘貼和拷貝.(u, v) =連接A 和 V A的最小加權(quán)邊定理的證明定理的證明4/22/2022算法設(shè)計(jì)與分析-貪心算法I14思路思路: 用優(yōu)先隊(duì)列 Q維護(hù) V A。 將Q中的每個(gè)頂點(diǎn)按照其和A中的頂

8、點(diǎn)連接的邊的最小權(quán)進(jìn)行排序。Q Vkeyv for all v Vkeys 0 for some arbitrary s Vwhile Q do u EXTRACT-MIN(Q) for each v Adju do if v Q and w(u, v) keyv then keyv w(u, v) DECREASE-KEY v u最后, (v, v) 組成了 MST.Prim算法算法4/22/2022算法設(shè)計(jì)與分析-貪心算法I15 A V APrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I16 A V APrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I

9、17 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I18 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I19 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I20 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I21 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I22 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I23 A V APrimPrim算法舉例算法舉例

10、4/22/2022算法設(shè)計(jì)與分析-貪心算法I24 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I25 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I26 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I27 A V APrimPrim算法舉例算法舉例4/22/2022算法設(shè)計(jì)與分析-貪心算法I28(V)總和Q Vkeyv 對(duì)所有 v Vkeys 0 對(duì)某個(gè)任意的 s Vwhile Q |V|次degree(u)次do u EXTRACT-MIN(Q)for each v Adju do if v Q and w(u, v) keyvthenkeyv w(u, v)v u握手定理 隱含(E) 次 DECREASE-KEY.時(shí)間 = (V)TEXTRACT-MIN + (E)TDECREASE-KEYPrim算法分析算法分析4/22/2022算法設(shè)計(jì)與分析-貪心算法I29時(shí)間 = (V)TEXTRACT-MIN + (E)TDE