算法設計與分析2023年2月6日講授內容：貪心算法I

教師：胡學鋼、吳共慶綱要圖等表示最小擴展樹

最優(yōu)子結構貪婪選擇Prim’s貪婪

MST算法2/6/2023算法設計與分析-貪心算法I2有向圖

(digraph)G=(V,E)是一個有序對的集合，包括頂點V的集合

(singular:vertex),邊的集合EV×V.無向圖G=(V,E)中，邊集合E包括無序

的頂點對.任何情況下

均有

|E|=O(V2).另外，如果

G是連通的,那么

|E|≥|V|–1,這意味著

lg|E|=(lgV).圖

(復習)2/6/2023算法設計與分析-貪心算法I3鄰接矩陣表示法一個圖G=(V,E)的鄰接矩陣,

V={1,2,…,n},為矩陣

A[1..n,1..n]

A123412340110001000000010(V2)存儲空間

稠密表示法.A[i,j]=1if(i,j)

E,0if(i,j)E.2/6/2023算法設計與分析-貪心算法I4頂點

v

V的鄰接鏈表

Adj[v]是和頂點v相鄰的頂點的鏈表。Adj[1]={2,3}Adj[2]={3}Adj[3]={}Adj[4]={3}對于無向圖,|Adj[v]|=degree(v).對于有向圖,|Adj[v]|=out-degree(v).握手定理：對于無向圖∑v∈V

=2|E|

鄰接表使用的存儲空間為

(V+E)—是一種

稀疏

表示

(對兩種圖均適用).鄰接鏈表表示法2/6/2023算法設計與分析-貪心算法I5輸入:一個連通的,無向圖

G=(V,E)其加權函數(shù)

w:E→.為了簡化，假設所有邊的權各不相同.(CLRS包括了通用的情況.)輸出:擴展樹

T—連接所有頂點的樹—其權最小:最小擴展樹2/6/2023算法設計與分析-貪心算法I6MST舉例2/6/2023算法設計與分析-貪心算法I7MSTT:(G的其他頂點沒有畫出)去掉邊

(u,v)

T.然后,將T劃分為兩棵子樹T1

和T2.定理：子樹

T1

是

G1=(V1,E1)

的MST，

G1是由T1的頂點導出G的子圖

。V1=

T1的頂點,E1={(x,y)∈E:x,y∈V1}.T2類似.最優(yōu)子結構2/6/2023算法設計與分析-貪心算法I8證明：粘貼拷貝：w(T)=w(u,v)+w(T1)+w(T2).如果

T1是

G1中比T1加權更小的擴展樹，那么在G中T={(u,v)}T1

T2

將是一棵比T加權更小的擴展樹。我們得到了重疊子問題了嗎?

是的.很好，那么可以使用動態(tài)規(guī)劃!

是的，但是

MST表現(xiàn)出更強特征，可以使用更加有效的算法。證明最優(yōu)子結構2/6/2023算法設計與分析-貪心算法I9定理：令

T為

G=(V,E)

的

MST,

并且令

A

V。假設

(u,v)∈E是連接A和V–A的最小加權邊.那么,(u,v)∈T.貪婪選擇特征局部的最優(yōu)選擇全局范圍內也是最優(yōu)的.“貪婪”算法的特征2/6/2023算法設計與分析-貪心算法I10證明.假設

(u,v)

T.粘貼和拷貝.T:(u,v)=連接A和

V–A的最小加權邊

A

V–A定理的證明2/6/2023算法設計與分析-貪心算法I11T:

A

V–A考慮T中從u到v的唯一的簡單路徑.證明.假設

(u,v)

T.粘貼和拷貝.(u,v)=連接A和

V–A的最小加權邊證明.假設

(u,v)

T.粘貼和拷貝.(u,v)=連接A和

V–A的最小加權邊定理的證明2/6/2023算法設計與分析-貪心算法I12T:

A

V–A將(u,v)和這條路徑上的第一條邊交換，這個邊連接A中的一個頂點，同時連接V–A中的一個頂點。考慮T中從u到v的唯一的簡單路徑.證明.假設

(u,v)

T.粘貼和拷貝.(u,v)=連接A和

V–A的最小加權邊證明.假設

(u,v)

T.粘貼和拷貝.(u,v)=連接A和

V–A的最小加權邊定理的證明2/6/2023算法設計與分析-貪心算法I13T:

A

V–A將(u,v)和這條路徑上的第一條邊交換，這個邊連接A中的一個頂點，同時連接V–A中的一個頂點。一個比T加權更小的擴展樹產(chǎn)生了。考慮T中從u到v的的一的簡單路徑.證明.假設

(u,v)

T.粘貼和拷貝.(u,v)=連接A和

V–A的最小加權邊定理的證明2/6/2023算法設計與分析-貪心算法I14思路:用優(yōu)先隊列

Q維護

V–A。

將Q中的每個頂點按照其和A中的頂點連接的邊的最小權進行排序。Q←Vkey[v]←

forallv

Vkey[s]←0forsomearbitrarys

VwhileQ≠dou←EXTRACT-MIN(Q)foreachv

Adj[u]doifv

Qandw(u,v)<key[v]thenkey[v]←w(u,v)?

DECREASE-KEYπ[v]←u最后,{(v,π[v])}組成了

MST.Prim算法2/6/2023算法設計與分析-貪心算法I15∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I16∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I17∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I18∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I19∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I20∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I21∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I22∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I23∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I24∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I25∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I26∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I27∈A∈V–APrim算法舉例2/6/2023算法設計與分析-貪心算法I28(V)總和Q←Vkey[v]←∞

對所有

v∈Vkey[s]←0對某個任意的

s∈VwhileQ≠|V|次degree(u)次dou←EXTRACT-MIN(Q)foreachv∈Adj[u]doifv∈Qandw(u,v)<key[v]thenkey[v]←w(u,v)π[v]←u握手定理

隱含(E)次

DECREASE-KEY.時間

=(V)·TEXTRACT-MIN+(E)·TDECREASE-KEYPrim算法分析2/6/2023算法設計與分析-貪心算法I29時間

=(V)·TEXTRACT-MIN+(E)·TDECREASE-KEY