算法設(shè)計與分析第05章貪心算法

1、《算法設(shè)計與分析》第05章 貪心算法,基本思想,通過作出在當(dāng)前看來最優(yōu)的選擇（貪心選擇），將原問題規(guī)模縮小，如此反復(fù)，直至得到最終解。貪心算法并非對所有問題都能得到整體最優(yōu)解。,活動安排問題,設(shè)有n個活動E={e1, e2, …, en}，其中每個活動都需要使用某一資源，而在同一時間內(nèi)該資源只能由一個活動使用，每個活動都有開始時間si和結(jié)束時間fi(si<fi)，若ei和ej滿足si≥fj或sj≥fi，則稱這兩個活動相容，

2、要求找出最多相容活動集合A。,活動安排問題,貪心解法：將所有活動按結(jié)束時間排序，得到活動集合E={e1,e2…en}；先將e1選入結(jié)果集合A中，即A={e1}；依次掃描每一個活動ei：如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei；,活動安排問題,解法證明：若E={e1,e2…en}是按結(jié)束時間排序的活動集合，則e1具有最早的結(jié)束時間，設(shè)存在一個最優(yōu)安排A不包含e1，并以ei開始，則易

3、見：A-{ei}∪{e1}也是最優(yōu)的活動安排；依此類推。,結(jié)果：選中的任務(wù)為：1、4、8、11,貪心算法的基本要素,1、貪心選擇性質(zhì)所求問題的整體最優(yōu)解可由一系列局部最優(yōu)選擇得到；動態(tài)規(guī)劃是由子問題的解得到當(dāng)前問題的解；貪心算法則是由當(dāng)前問題的局部最優(yōu)解導(dǎo)出子問題；確定一個問題是否具有貪心選擇性質(zhì)，需要證明問題的一個整體最優(yōu)解是從貪心選擇開始的；2、最優(yōu)子結(jié)構(gòu)性質(zhì)通過局部最優(yōu)選擇，原問題將被化簡為類似的子問題；亦即是說，

4、整體最優(yōu)解中包含了子問題的最優(yōu)解；,背包問題,有一容量為W的背包，和單價分別為vi的物品塊（均為單位體積）各ni塊，i=1…n；問每種物品應(yīng)各選擇多少塊裝入背包中，使得背包中的總價值最大？,0-1背包問題,有一容量為W的背包，和一批體積分別為wi，價值為vi的物品， i=1…n；問將哪些物品裝入背包，使得背包中的總價值最大？0-1背包問題不滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，不能用貪心法來求解，而應(yīng)用分治法求解。分治規(guī)則為：S(w1..n, v1.

5、.n, W) = max{S(w1..n-1, v1..n-1, W-wn)+vn, S(w1..n-1, v1..n-1, W)},哈夫曼算法的證明,貪心選擇性質(zhì)的證明若葉結(jié)點x,y是被選中合并的結(jié)點，即x,y具有最小權(quán)值，則1. x、y是結(jié)果樹上深度最大的兩個結(jié)點，且互為兄弟；2. 必存在最優(yōu)二叉樹以x,y為深度最大的兩個結(jié)點，且互為兄弟（編碼最長，且只有最后一位編碼不同）；證明：顯然，總可通過交換x,y到最

6、深的一對兄弟結(jié)點，得到滿足條件的最優(yōu)二叉樹；,哈夫曼算法的證明,最優(yōu)子結(jié)構(gòu)性質(zhì)的證明若葉結(jié)點x,y分別具有最小權(quán)值，而且是互為兄弟結(jié)點的最深的葉子結(jié)點，證明：取x,y的父結(jié)點代替x,y結(jié)點，取x,y的權(quán)值和作為其父結(jié)點的權(quán)值，得到的仍是一棵最優(yōu)二叉樹；證明：設(shè)原二叉樹的權(quán)值為W = W’+x*d+y*d，d為x,y的深度，則用x,y的父結(jié)點取代x,y后的二叉樹的權(quán)值為W’+(x+y)*(d-1)，易見，若存在一個更優(yōu)的二叉樹，將x

7、,y再替換回來也應(yīng)是一棵更優(yōu)的二叉樹；,,,X,Y,,,證明：取x,y的父結(jié)點代替x,y結(jié)點，取x,y的權(quán)值和作為其父結(jié)點的權(quán)值，得到的仍是一棵最優(yōu)二叉樹。,W = W’+x*d+y*d,W’+(x+y)*(d-1),貪心算法的理論基礎(chǔ),1、擬陣擬陣定義為滿足以下條件的有序?qū)Γ⊿，I）；S是一個非空有限集合；I是S的具有某種遺傳性質(zhì)的獨立子集的全集；一個集合是具有遺傳性質(zhì)的獨立集合是指，若一個集合具有某種性質(zhì)，則其任意子集也具有

8、該性質(zhì)；I滿足交換性質(zhì)，即若A∈I，B ∈I且|A|<|B|，則存在某一元素x ∈B-A，使得A∪{x} ∈I；,貪心算法的理論基礎(chǔ),1、擬陣?yán)纾篠定義為一個無向圖的邊集，I定義為圖中不含回路的邊的集合的全體；即若A ∈I，則A中的邊構(gòu)成一個森林；給定一個擬陣M=（S，I），對I中的一個獨立子集A ，若S中存在元素x不屬于A，使得A∪{x} ∈I，則稱x為A的一個可擴(kuò)展元素；當(dāng)S中的一個獨立子集A沒有可擴(kuò)展元素時，稱

9、A為一個極大獨立子集；極大獨立子集性質(zhì)：擬陣M中所有的極大獨立子集具有相同大??；,貪心算法的理論基礎(chǔ),2、帶權(quán)擬陣的貪心算法對擬陣M=（S，I）的S指定一個權(quán)函數(shù)W，使對x∈S，有W(x)>0，稱M為帶權(quán)擬陣，S的子集A的權(quán)定義為A中全部元素的權(quán)值和；問題：求解最大權(quán)獨立子集，即確定A∈I，且W(A)達(dá)到最大；A稱為M的一個最優(yōu)子集；最優(yōu)子集也是極大獨立子集；,貪心算法的理論基礎(chǔ),2、帶權(quán)擬陣的貪心算法算法如下：初始化A

10、為空集；將S中的元素依權(quán)值從大到小排序；依序取出S中的所有元素x：如果A∪{x}∈I，則將x并入A中，否則放棄x；算法時間復(fù)雜性：O( nlogn + nf(n) )，其中f(n)為判定A∪{x}是否屬于I所需的時間；,貪心算法的理論基礎(chǔ),3、帶權(quán)擬陣的貪心算法的證明：貪心選擇性質(zhì)的證明：設(shè)帶權(quán)擬陣M=（S，I），S按權(quán)值大于排序，設(shè)S中的x中第一個使得{x}是獨立子集的元素，證明：存在S的一個最優(yōu)子集A，使得x∈A；

11、證明：在選擇x前被舍棄的元素，容易證明，它們不可能是S中任一獨立子集的可擴(kuò)展元素，可以永遠(yuǎn)舍棄；若最優(yōu)子集B不包含x，則可設(shè)A={x}，利用交換性質(zhì)，將B中的元素?fù)Q入A中，直至|A|=|B|，這時A和B只相差一個元素，設(shè)B中未被換入A的元素為y，則W(A)=W(B)-W(y)+W(x)，又W(x)≥W(y)，則A亦為最優(yōu)子集，得證。,貪心算法的理論基礎(chǔ),3、帶權(quán)擬陣的貪心算法的證明：最優(yōu)子結(jié)構(gòu)性質(zhì)的證明：從M=（S，I）中選出x后

12、，原問題簡化為M’=（S’，I’），S’由所有x的可擴(kuò)展元素組成；I’是可以以x為可擴(kuò)展元素的全部獨立子集；設(shè)A是M的最優(yōu)子集，則A’=A-{x}是M’的一個獨立子集，由W(A) = W(A’)+W(x)可知，M的包含x的最優(yōu)子集包含M’的一個最優(yōu)子集；綜上所述，可推知對帶權(quán)擬陣用貪心算法可以求得其最優(yōu)子集；,任務(wù)時間表問題,問題：有一組單位時間任務(wù)S={1,2,…,n}，每個任務(wù)i有指定的要求完成時間di，若任務(wù)i在指定完成時間

13、之后完成，則將受到誤時懲罰ωi；要求安排活動的時間表，使得總的誤時懲罰最??；分析：由于誤時任務(wù)不會因為誤時時間的延長而加大懲罰，因此，問題等價于確定S的一個最優(yōu)及時任務(wù)子集；將最優(yōu)子集中的活動按完成時間排序，再排列所有誤時任務(wù)，即得到所需的任務(wù)時間表；,任務(wù)時間表問題,定義S的子集A，若A中的所有任務(wù)都是及時任務(wù)，則稱A為S的一個獨立任務(wù)子集；顯然A是具有遺傳性質(zhì)的獨立子集；定義I為S的所有獨立子集的集合；①若A是獨立子集，則A中在

14、時間t之前必須完成的任務(wù)必不超過t個；②若A在時間t之前必須完成的任務(wù)不超過t個，則A中的任務(wù)按完成時間排序后，所有任務(wù)都是及時的；③若A中的所有任務(wù)都是及時的，則A是獨立子集；即①②③是等價的；由此可以根據(jù)②來判斷一個子集是否是獨立子集；要使誤時任務(wù)的懲罰最小，相當(dāng)于使及時任務(wù)的懲罰最大，因此問題相當(dāng)于確定一個具有最大總懲罰的獨立任務(wù)子集A；,任務(wù)時間表問題,按照擬陣貪心算法，首先按各任務(wù)的懲罰值從大到小進(jìn)行排序；初始化A

15、為空集；依次掃描所有的任務(wù)i：若任務(wù)i加入A中，仍能構(gòu)成獨立子集（可以及時完成），則將任務(wù)i并入A中，否則暫時放棄該任務(wù)（列為 誤時任務(wù)）；將A中的任務(wù)按完成時間排序，再排列上所有的誤時任務(wù)，即得到任務(wù)時間表；可通過輔助向量t來記錄A中每個任務(wù)可容忍插隊的任務(wù)數(shù)來判斷是否可以有新任務(wù)加入；,結(jié)論：2，4，1，3，7，5，6,,3,2 1,1 1 1,0 1 0 1,0 1 0