算法設計與分析第05章貪心算法

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

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

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

4、整體最優(yōu)解中包含了子問題的最優(yōu)解；,背包問題,有一容量為W的背包，和單價分別為vi的物品塊（均為單位體積）各ni塊，i=1…n；問每種物品應各選擇多少塊裝入背包中，使得背包中的總價值最大？,0-1背包問題,有一容量為W的背包，和一批體積分別為wi，價值為vi的物品， i=1…n；問將哪些物品裝入背包，使得背包中的總價值最大？0-1背包問題不滿足最優(yōu)子結構性質，不能用貪心法來求解，而應用分治法求解。分治規(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)},哈夫曼算法的證明,貪心選擇性質的證明若葉結點x,y是被選中合并的結點，即x,y具有最小權值，則1. x、y是結果樹上深度最大的兩個結點，且互為兄弟；2. 必存在最優(yōu)二叉樹以x,y為深度最大的兩個結點，且互為兄弟（編碼最長，且只有最后一位編碼不同）；證明：顯然，總可通過交換x,y到最

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

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

8、該性質；I滿足交換性質，即若A∈I，B ∈I且|A|<|B|，則存在某一元素x ∈B-A，使得A∪{x} ∈I；,貪心算法的理論基礎,1、擬陣例如：S定義為一個無向圖的邊集，I定義為圖中不含回路的邊的集合的全體；即若A ∈I，則A中的邊構成一個森林；給定一個擬陣M=（S，I），對I中的一個獨立子集A ，若S中存在元素x不屬于A，使得A∪{x} ∈I，則稱x為A的一個可擴展元素；當S中的一個獨立子集A沒有可擴展元素時，稱

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

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

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

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

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

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

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