算法設(shè)計(jì)與分析2023年2月6日講授內(nèi)容：貪心算法I

教師：胡學(xué)鋼、吳共慶綱要圖等表示最小擴(kuò)展樹(shù)

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

MST算法2/6/2023算法設(shè)計(jì)與分析-貪心算法I2有向圖

(digraph)G=(V,E)是一個(gè)有序?qū)Φ募?，包括頂點(diǎn)V的集合

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

的頂點(diǎn)對(duì).任何情況下

均有

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

G是連通的,那么

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

lg|E|=(lgV).圖

(復(fù)習(xí))2/6/2023算法設(shè)計(jì)與分析-貪心算法I3鄰接矩陣表示法一個(gè)圖G=(V,E)的鄰接矩陣,

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

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

A123412340110001000000010(V2)存儲(chǔ)空間

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

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

v

V的鄰接鏈表

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

=2|E|

鄰接表使用的存儲(chǔ)空間為

(V+E)—是一種

稀疏

表示

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

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

w:E→.為了簡(jiǎn)化，假設(shè)所有邊的權(quán)各不相同.(CLRS包括了通用的情況.)輸出:擴(kuò)展樹(shù)

T—連接所有頂點(diǎn)的樹(shù)—其權(quán)最小:最小擴(kuò)展樹(shù)2/6/2023算法設(shè)計(jì)與分析-貪心算法I6MST舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I7MSTT:(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)出G的子圖

。V1=

T1的頂點(diǎn),E1={(x,y)∈E:x,y∈V1}.T2類(lèi)似.最優(yōu)子結(jié)構(gòu)2/6/2023算法設(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加權(quán)更小的擴(kuò)展樹(shù)。我們得到了重疊子問(wèn)題了嗎?

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

是的，但是

MST表現(xiàn)出更強(qiáng)特征，可以使用更加有效的算法。證明最優(yōu)子結(jié)構(gòu)2/6/2023算法設(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)的.“貪婪”算法的特征2/6/2023算法設(shè)計(jì)與分析-貪心算法I10證明.假設(shè)

(u,v)

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

V–A的最小加權(quán)邊

A

V–A定理的證明2/6/2023算法設(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)邊定理的證明2/6/2023算法設(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)=連接A和

V–A的最小加權(quán)邊證明.假設(shè)

(u,v)

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

V–A的最小加權(quán)邊定理的證明2/6/2023算法設(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)邊定理的證明2/6/2023算法設(shè)計(jì)與分析-貪心算法I14思路:用優(yōu)先隊(duì)列

Q維護(hù)

V–A。

將Q中的每個(gè)頂點(diǎn)按照其和A中的頂點(diǎn)連接的邊的最小權(quán)進(jìn)行排序。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算法設(shè)計(jì)與分析-貪心算法I15∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I16∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I17∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I18∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I19∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I20∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I21∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I22∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I23∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I24∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I25∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I26∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I27∈A∈V–APrim算法舉例2/6/2023算法設(shè)計(jì)與分析-貪心算法I28(V)總和Q←Vkey[v]←∞

對(duì)所有

v∈Vkey[s]←0對(duì)某個(gè)任意的

s∈VwhileQ≠|(zhì)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.時(shí)間

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

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