算法設(shè)計(jì)與分析 ch5 學(xué)習(xí)課件

算法設(shè)計(jì)與分析第五講貪心算法哈爾濱工業(yè)大學(xué)王宏志wangzh@/pages/wang/提綱5.1貪心法的基本原理5.2任務(wù)安排問題5.3哈夫曼編碼問題5.4最小生成樹貪心算法的基本思想求解最優(yōu)化問題的算法包含一系列步驟每一步都有一組選擇作出在當(dāng)前看來最好的選擇希望通過作出局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇貪心算法不一定總產(chǎn)生優(yōu)化解貪心算法是否產(chǎn)生優(yōu)化解，需嚴(yán)格證明貪心算法產(chǎn)生優(yōu)化解的條件貪心選擇性優(yōu)化子結(jié)構(gòu)貪心算法的基本概念貪心選擇性

貪心選擇性若一個(gè)優(yōu)化問題的全局優(yōu)化解可以通過局部優(yōu)化選擇得到，則該問題稱為具有貪心選擇性.一個(gè)問題是否具有貪心選擇性需證明若一個(gè)優(yōu)化問題的優(yōu)化解包含它的子問題的優(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)子問題重疊性子問題空間小貪心方法可用的條件優(yōu)化子結(jié)構(gòu)貪心選擇性可用貪心方法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心方法可能不適用證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu)證明算法所求解的問題具有貪心選擇性證明算法確實(shí)按照貪心選擇性進(jìn)行局部優(yōu)化選擇貪心算法正確性證明方法提綱5.1貪心法的基本原理5.2任務(wù)安排問題5.3哈夫曼編碼問題5.4最小生成樹問題的定義

活動(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是相容的，若sj

fi或si

fj，即SifiSjfjSjfjSifiSiSjfifj問題定義輸入：S={1,2,…,n}，F(xiàn)={[si，fi]}，n

i

1輸出：S的最大相容集合貪心思想:為了選擇最多的相容活動(dòng)，每次選fi最小的活動(dòng)，使我們能夠選更多的活動(dòng)

引理1設(shè)S={1,2,…,n}是n個(gè)活動(dòng)集合，[si，fi]是活動(dòng)的起始終止時(shí)間，且f1

f2

….

fn，S的活動(dòng)選擇問題的某個(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，引理成立.如果k

1，令B=A-{k}∪{1},

由于A中活動(dòng)相容，f1

fk

sj,B中活動(dòng)相容.因?yàn)?/p>

B

=

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í)間，且f1

f2

….

fn，設(shè)A是S的調(diào)度問題的一個(gè)優(yōu)化解且包括活動(dòng)1，則A

=A-{1}是S

={i

S|si

f1}的調(diào)度問題的優(yōu)化解.

證.顯然，A’中的活動(dòng)是相容的.我們僅需要證明A

是最大的.設(shè)不然，存在一個(gè)S’

的活動(dòng)選擇問題的優(yōu)化解B’，

B’

>

A’

.令B={1}∪B’.對(duì)于

i

S’,si

f1,B中活動(dòng)相容.

B是S的一個(gè)解.由于|A|=|A’|+1,

B

=

B’

+1>

A’

+1=

A

，與A最大矛盾.引理2說明活動(dòng)選擇問題具有優(yōu)化子結(jié)構(gòu)貪心選擇性引理3.設(shè)S={1,2,….,n}是n個(gè)活動(dòng)集合，f0=0,li是Si={j

S|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è)

A<k時(shí)，命題成立.當(dāng)

A

=k時(shí),由引理2，A={1}∪A1,

A1是

S2={j

S|sj

f1}的優(yōu)化解.由歸納假設(shè)，A1=.于是,

A=.貪心思想為了選擇最多的相容活動(dòng)，每次選fi最小的活動(dòng)，使我們能夠選更多的活動(dòng)

算法的設(shè)計(jì)算法

（設(shè)f1

f2

….

fn已排序）

貪心-Activity-Selector(S,F)

n

lenyth(S);

A

{1}

j

1Fori

2TonDoIfsi

fjThenA

A∪{i}；j

i；ReturnA如果結(jié)束時(shí)間已排序T(n)=

(n)如果結(jié)束時(shí)間未排序T(n)=

(n)+

(nlogn)=

(nlogn)

復(fù)雜性設(shè)計(jì)需要證明活動(dòng)選擇問題具有貪心選擇性活動(dòng)選擇問題具有優(yōu)化子結(jié)構(gòu)算法按照貪心選擇性計(jì)算解算法正確性證明定理.

貪心-Activity-Selector算法能夠產(chǎn)生最優(yōu)解.

證.

貪心-Activity-Selector算法按照引理3的貪心選擇性進(jìn)行局部優(yōu)化選擇.

提綱5.1貪心法的基本原理5.2任務(wù)安排問題5.3哈夫曼編碼問題5.4最小生成樹二進(jìn)制字符編碼每個(gè)字符用一個(gè)二進(jìn)制0、1串來表示.固定長編碼每個(gè)字符都用相同長的0、1串表示.可變長編碼經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的用長碼前綴編碼無任何字符的編碼是另一個(gè)字符編碼的前綴問題的定義編碼樹葉結(jié)點(diǎn):

用字符及其出現(xiàn)頻率標(biāo)記內(nèi)結(jié)點(diǎn):

用其子樹的葉結(jié)點(diǎn)的頻率和標(biāo)記邊標(biāo)記:

左邊標(biāo)記0，右側(cè)邊標(biāo)記1100a:45553025c:12b:1314d:16e:9f:50000011111編碼樹T的代價(jià)設(shè)C是字母表,

c

Cf(c)是c在文件中出現(xiàn)的頻率dT(c)是葉子c在樹T中的深度，即c的編碼長度T的代價(jià)是編碼一個(gè)文件的所有字符的代碼位數(shù):

B(T)=優(yōu)化編碼樹問題輸入:字母表C={c1,c2,,cn}，

頻率表F={f(c1),f(c2),...,f(cn)}輸出:具有最小B(T)的C前綴編碼樹貪心思想：循環(huán)地選擇具有最低頻率的兩個(gè)結(jié)點(diǎn)，生成一棵子樹，直至形成樹優(yōu)化解的結(jié)構(gòu)分析我們需要證明優(yōu)化前綴樹問題具有優(yōu)化子結(jié)構(gòu)優(yōu)化前綴樹問題具有貪心選擇性優(yōu)化子結(jié)構(gòu)引理1.設(shè)T是字母表C的優(yōu)化前綴樹，

c

C，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,y}∪{z}的優(yōu)化前綴編碼樹.bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z證.往證B(T)=B(T’)+f(x)+f(y).

v

C-{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’).因?yàn)閦是C’中字符，它必為T’’中的葉子.把結(jié)點(diǎn)x與y加入T’’，作為z的子結(jié)點(diǎn)，則得到C的一個(gè)如下前綴編碼樹T’’’：bczT’0011f(c)f(b)f(x)+f(y)uvT’’0011f(v)f(u)zf(z)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)化編碼樹.uvxyT’’’000111f(x)f(v)f(y)f(u)zuvT’’0011f(v)f(u)zf(z)貪心選擇性引理2.

設(shè)C是字母表，

c

C，c具有頻率f(c),

x、y是C中具有最小頻率的兩個(gè)字符，則存在一個(gè)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是具有最大深度的兩個(gè)兄弟字符:xybcTbyxcT’交換y和c構(gòu)造T

bcxyT’’往證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)(因?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)化前綴編碼樹.在T’’中,x和y具有相同長度編碼,且僅最后一位不同.

基本思想循環(huán)地選擇具有最低頻率的兩個(gè)結(jié)點(diǎn)，生成一棵子樹，直至形成樹初始:

f:5,e:9,c:12,b:13,d:16,a:45

算法的設(shè)計(jì)貪心算法(使用堆操作實(shí)現(xiàn))

Huffman(C，F(xiàn))1.

n

C

;2.

Q

C;/*用BUILD-HEAP建立堆*/3.

FORi

1Ton-1Do4.

z

Allocate-Node();5.

x

left[z]

Extract-MIN(Q);/*堆操作*/

6.

y

right[z]

Extract-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)化前綴編碼樹

證.由于引理1、引理2成立,而且Huffman算法按照引理2的貪心選擇性確定的規(guī)則進(jìn)行局部優(yōu)化選擇，所以Huffman算法產(chǎn)生一個(gè)優(yōu)化前綴編碼樹。

正確性證明提綱5.1貪心法的基本原理5.2任務(wù)安排問題5.3哈夫曼編碼問題5.4最小生成樹問題的定義生成樹設(shè)G=(V,E)是一個(gè)邊加權(quán)無向連通圖.G的生成樹是無向樹S=(V,T),

T

E,以下用T表示S.如果W:E

{實(shí)數(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的最小生成樹實(shí)例BCAED706080509075300200BCAED705090300BCAED708050300BCAED70608050算法思想BCAED706080509075300200BCAED70608050Kruskal算法MST-Kruskal(G,W)1.A=;2.Forv

V[G]DoMake-Set(v);/*

按照W值的遞增順序排序E[G];For(u,v)E[G](按W值的遞增順序)DoIfFind-Set(u)Find-Set(v)ThenA=A{(u,v)};Union(u,v);ReturnA算法復(fù)雜性令n=|V|,m=|E|第4步需要時(shí)間:O(mlogm)第2-3步執(zhí)行O(n)個(gè)Make-Set操作第5-8步執(zhí)行O(m)個(gè)Find-Set和Union操作

需要時(shí)間:O((n+m)(n))mn-1(因?yàn)镚連通),(n)=logn=logm總時(shí)間復(fù)雜性：O(mlogm)定理1.設(shè)uv是G中權(quán)值最小的邊，則必有一棵最小生成樹包含邊uv.貪心選擇性yxuvT證明：設(shè)T是G的一棵MST

若uv∈T,結(jié)論成立；

否則，如右圖所示

在T中添加uv邊，產(chǎn)生環(huán)

刪除環(huán)中不同于uv的權(quán)值最小的邊xy,得到T’。

w(T’)=w(T)-w(xy)+w(uv)≤w(T)T’優(yōu)化子結(jié)構(gòu)收縮圖G的邊uv—G

uv用新頂點(diǎn)Cuv代替邊uv將G中原來與u或v關(guān)聯(lián)的邊與Cuv關(guān)聯(lián)刪除Cuv到其自身的邊上述操作的逆操作稱為擴(kuò)張定理1.給定加權(quán)無向連通圖G=(V,E),權(quán)值函數(shù)為

W:E

R,uv

E是G中權(quán)值最小的邊。設(shè)T是G的包含uv的一棵最小生成樹，則T

uv是G

uv的一棵最小生成樹.證明.由于T

uv是不含回路的連通圖且包含了G

uv的所有頂點(diǎn)，因此，T

uv是G

uv的一棵生成樹。下面證明T

uv是G

uv的代價(jià)最小的生成樹。

若不然，存在G

uv的生成樹T'使得W(T')<W(T

uv)。顯然，T'中包含頂點(diǎn)Cuv且是連通的，因此T''=T'

Cuv包含G的所有頂點(diǎn)且不含回路，故T''是G的一棵生成樹。但,W(T'')=W(T')+W(uv)<W(T

uv)+W(uv)=W(T),這與T是G的最小生成樹矛盾。算法正確性定理2.

MST-Kruskal(G,W)算法能夠產(chǎn)生圖G的最小生成樹.

證.

因?yàn)樗惴ò凑肇澬倪x擇性進(jìn)行局部優(yōu)化選擇.

算法思想Prim算法算法描述(1)MST-Prim(G,W,r)Input連通圖G，權(quán)值函數(shù)W，樹根rOutputG的一棵以r為根的生成樹1.C{r}，T;2.建堆Q維護(hù)C與V-C之間的邊WhileC

Vdo

uvExtract_Min(Q)//u

C,v

V-C

CC{v};T

T{uv};

6.forxAdj[v]do7.ifx

Cthen將vx從Q中刪除8.Else將vx插入Q9.ReturnTlogE2E遍logE算法描述(2)MST-Prim(G,W,r)Input連通圖G，權(quán)值函數(shù)W，樹根rOutputG的一棵以r為根的生成樹For

v

V[G]Dokey[v]+[v]nullkey[r]0Q

V[G]WhileQ

do

uExtract_Min(Q)forvAdj[u]doifv

Q

且w(u,v)<key[v]then

[v]ukey[v]w(u,v)//更新信息ReturnA={(v,

[v])|v