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

貪心選擇性若一個優化問題的全局優化解可以通過局部優化選擇得到，則該問題稱為具有貪心選擇性.一個問題是否具有貪心選擇性需證明若一個優化問題的優化解包含它的子問題的優化解，則稱其具有優化子結構優化子結構

與動態規劃方法的比較動態規劃方法可用的條件優化子結構子問題重疊性子問題空間小貪心方法可用的條件優化子結構貪心選擇性可用貪心方法時，動態規劃方法可能不適用可用動態規劃方法時，貪心方法可能不適用證明算法所求解的問題具有優化子結構證明算法所求解的問題具有貪心選擇性證明算法確實按照貪心選擇性進行局部優化選擇貪心算法正確性證明方法提綱5.1貪心法的基本原理5.2任務安排問題5.3哈夫曼編碼問題5.4最小生成樹問題的定義

活動設S={1,2,…,n}是n個活動的集合，各個活動使用同一個資源，資源在同一時間只能為一個活動使用每個活動i有起始時間si，終止時間fi，si

fi相容活動活動i和j是相容的，若sj

fi或si

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

i

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

引理1設S={1,2,…,n}是n個活動集合，[si，fi]是活動的起始終止時間，且f1

f2

….

fn，S的活動選擇問題的某個優化解包括活動1.證

設A是一個優化解，按結束時間排序A中活動，設其第一個活動為k，第二個活動為j.如果k=1，引理成立.如果k

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

由于A中活動相容，f1

fk

sj,B中活動相容.因為

B

=

A

,

所以B是一個優化解，且包括活動1.優化解結構分析引理2.設S={1,2,…,n}是n個活動集合，[si，fi]是活動i的起始終止時間，且f1

f2

….

fn，設A是S的調度問題的一個優化解且包括活動1，則A

=A-{1}是S

={i

S|si

f1}的調度問題的優化解.

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

是最大的.設不然，存在一個S’

的活動選擇問題的優化解B’，

B’

>

A’

.令B={1}∪B’.對于

i

S’,si

f1,B中活動相容.

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

B

=

B’

+1>

A’

+1=

A

，與A最大矛盾.引理2說明活動選擇問題具有優化子結構貪心選擇性引理3.設S={1,2,….,n}是n個活動集合，f0=0,li是Si={j

S|sj

fi-1}

中具有最小結束時間fli的活動.設A是S的包含活動1的優化解,其中

f1

…

fn，則A=

證.對

A

作歸納法.當

A

=1時,由引理1，命題成立.設

A<k時，命題成立.當

A

=k時,由引理2，A={1}∪A1,

A1是

S2={j

S|sj

f1}的優化解.由歸納假設，A1=.于是,

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

算法的設計算法

（設f1

f2

….

fn已排序）

貪心-Activity-Selector(S,F)

n

lenyth(S);

A

{1}

j

1Fori

2TonDoIfsi

fjThenA

A∪{i}；j

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

(n)如果結束時間未排序T(n)=

(n)+

(nlogn)=

(nlogn)

復雜性設計需要證明活動選擇問題具有貪心選擇性活動選擇問題具有優化子結構算法按照貪心選擇性計算解算法正確性證明定理.

貪心-Activity-Selector算法能夠產生最優解.

證.

貪心-Activity-Selector算法按照引理3的貪心選擇性進行局部優化選擇.

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

用字符及其出現頻率標記內結點:

用其子樹的葉結點的頻率和標記邊標記:

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

c

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

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

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

c

C，f(c)是c在文件中出現的頻率.設x、y是T中任意兩個相鄰葉結點，z是它們的父結點，則z作為頻率是f(z)=f(x)+f(y)的字符，T’=T-{x,y}是字母表C’=C-{x,y}∪{z}的優化前綴編碼樹.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’的優化前綴編碼樹，則必存在T’’，使B(T’’)<B(T’).因為z是C’中字符，它必為T’’中的葉子.把結點x與y加入T’’，作為z的子結點，則得到C的一個如下前綴編碼樹T’’’：bczT’0011f(c)f(b)f(x)+f(y)uvT’’0011f(v)f(u)zf(z)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是優化的矛盾，故T’是C’的優化編碼樹.uvxyT’’’000111f(x)f(v)f(y)f(u)zuvT’’0011f(v)f(u)zf(z)貪心選擇性引理2.

設C是字母表，

c

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

x、y是C中具有最小頻率的兩個字符，則存在一個C的優化前綴樹，x與y的編碼具有相同長度，且僅在最末一位不同.不失一般性，設f(b)

f(c),f(x)

f(y).因x與y是具有最低頻率的字符,f(b)

f(x),f(c)

f(y).交換T的b和x,從T構造T

:

證:設T是C的優化前綴樹，且b和c是具有最大深度的兩個兄弟字符:xybcTbyxcT’交換y和c構造T

bcxyT’’往證T

是最優化前綴樹.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是最優化的，所以B(T)

B(T’’).

于是,B(T)=B(T’’)，T’’是C的最優化前綴編碼樹.在T’’中,x和y具有相同長度編碼,且僅最后一位不同.

基本思想循環地選擇具有最低頻率的兩個結點，生成一棵子樹，直至形成樹初始:

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

算法的設計貪心算法(使用堆操作實現)

Huffman(C，F)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設Q由一個堆實現第2步用堆排序的BUILD-HEAP實現:O(n)每個堆操作要求O(logn)，循環n-1次:O(nlogn)

T(n)=0(n)+0(nlogn)=0(nlogn)復雜性分析

定理.

Huffman算法產生一個優化前綴編碼樹

證.由于引理1、引理2成立,而且Huffman算法按照引理2的貪心選擇性確定的規則進行局部優化選擇，所以Huffman算法產生一個優化前綴編碼樹。

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

T

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

{實數}

是G的權函數,T的權值定義為W(T)=

(u,v)TW(u,v).最小生成樹G的最小生成樹是W(T)最小的G之生成樹.

問題的定義輸入:

無向連通圖G=(V,E),權函數W輸出:

G的最小生成樹實例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算法復雜性令n=|V|,m=|E|第4步需要時間:O(mlogm)第2-3步執行O(n)個Make-Set操作第5-8步執行O(m)個Find-Set和Union操作

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

若uv∈T,結論成立；

否則，如右圖所示

在T中添加uv邊，產生環

刪除環中不同于uv的權值最小的邊xy,得到T’。

w(T’)=w(T)-w(xy)+w(uv)≤w(T)T’優化子結構收縮圖G的邊uv—G

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

W:E

R,uv

E是G中權值最小的邊。設T是G的包含uv的一棵最小生成樹，則T

uv是G

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

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

uv的所有頂點，因此，T

uv是G

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

uv是G

uv的代價最小的生成樹。

若不然，存在G

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

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

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

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

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

證.

因為算法按照貪心選擇性進行局部優化選擇.

算法思想Prim算法算法描述(1)MST-Prim(G,W,r)Input連通圖G，權值函數W，樹根rOutputG的一棵以r為根的生成樹1.C{r}，T;2.建堆Q維護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，權值函數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