【學習課件】第4章貪心算法計算機算法設計與分析（第3版）教學

1、第4章 貪心算法1編輯ppt學習要點理解貪心算法的概念。掌握貪心算法的基本要素 （1）最優(yōu)子結構性質（2）貪心選擇性質理解貪心算法與動態(tài)規(guī)劃算法的差異通過應用范例學習貪心設計策略。（1）活動安排問題；（2）最優(yōu)裝載問題；（3）單源最短路徑；（4）多機調度問題。2編輯ppt解決問題類型局部最優(yōu)問題部分問題的整體近似最優(yōu)一般問題的整體最優(yōu)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似解。貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。3編輯ppt舉例硬幣問題一描述4枚硬幣

2、：面值分別為0.25、0.1、0.05、0.01，問構成0.63所需硬幣數最少，如何選擇其？結論：每次都做出最好的選擇，即每次確定一枚硬幣后，總使剩余金額最少。貪心算法可以得到本問題的最優(yōu)解。問題二描述3枚硬幣：面值分別為0.11、0.05、0.01，問構成0.15所需硬幣數最少，如何選擇其？貪心算法：1*0.11+4*0.01 共5枚硬幣、結論：不是整體最優(yōu)解，是近似最優(yōu)解。4編輯ppt4.1 活動安排問題問題描述 設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束

3、時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。問題：要在所給的活動集合中選出最大的相容活動子集合。5編輯ppt4.1 活動安排問題templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 下面給出解活動安排問題的貪心算法:各活動的起始時

4、間和結束時間存儲于數組s和f中且按結束時間的非減序排列 6編輯ppt4.1 活動安排問題 由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。 算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。 7編輯p

5、pt4.1 活動安排問題 例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011si130535688212fi45678910111213148編輯ppt4.1 活動安排問題 算法greedySelector 的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。9編輯ppt4.1 活動安排問題 若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題

6、，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。10編輯ppt4.2 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優(yōu)子結構性質。 11編輯ppt4.2 貪心算法的基本要素-貪心選擇性質貪心選擇性質:指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。與動態(tài)規(guī)劃算法的區(qū)別： （1）是否依賴子問題的解

7、；（2）求解過程（自下向上還是自上向下）判斷問題是否所具此性質：對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。12編輯ppt4.2 貪心算法的基本要素-最優(yōu)子結構性質 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。13編輯ppt4.2 貪心算法的基本要素相同點：最優(yōu)子結構性質不同點：通過組合優(yōu)化問題實例說明二者差別。貪心算法與動態(tài)規(guī)劃算法的差異14編輯ppt4.2 貪心算法的基本要素0-1背包問題： 問題描述 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝

8、入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。最優(yōu)子結構設第j個物品放入了背包中，原問題最優(yōu)解包含其中一個子問題的最優(yōu)解，即：集合：Aj=A-j，背包容量：c-wj15編輯ppt4.2 貪心算法的基本要素背包問題： 問題描述 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。最優(yōu)子結構設第j個物品放入了背包中，原問題最優(yōu)解包含其中一個子問題的最優(yōu)解，即：集合:Ajw=A-w，背包容量：c-w 結論：背包問題可以用貪心算法求解，而

9、0-1背包問題卻不能用貪心算法求解。 16編輯ppt4.2 貪心算法的基本要素（1）計算每種物品單位重量的價值Vi/Wi，（2）依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 用貪心算法解背包問題的基本步驟：17編輯ppt4.2 貪心算法的基本要素void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i=n;i+) xi=0;

10、 float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。18編輯ppt4.2 貪心算法的基本要素 實例如P107圖4-2對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問

11、題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。 19編輯ppt4.3 最優(yōu)裝載1、問題描述有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。2、算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。 20編輯ppt4.3 最優(yōu)裝載templatevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w,

12、 t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti;21編輯ppt4.3 最優(yōu)裝載3、貪心選擇性質 證明省略。思想：每處理完一個集裝箱，都要使得船的剩余容量盡可能大。即原問題的最優(yōu)解通過局部問題的最優(yōu)解得到。4、最優(yōu)子結構性質原問題的最優(yōu)解包含了子問題的最優(yōu)解，具有最優(yōu)子結構性質。算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。 22編輯ppt4.5 單源最短路徑問題描述：給定帶權有向圖G =(

13、V,E)，其中每條邊的權是非負實數。另外，還給定V中的一個頂點，稱為源?，F在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。23編輯ppt4.5 單源最短路徑Dijkstra算法基本思想基本思想：設置一初始為僅含源的頂點集合S，通過不斷地作貪心選擇擴充此集合，直至S包含所有頂點。設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數組dist作必要的修改。一旦S包含

14、了V中所有頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。24編輯ppt4.5 單源最短路徑例如，對右圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。25編輯ppt4.5 單源最短路徑迭代Sudist2dist3dist4dist5初始1-10maxint3010011,2210603010021,2,441050309031,2,4,331050306041,2,4,3,5510503060Dijkstra算法的迭代過程： 26編輯ppt4.5 單源最短路徑算法P113 27編輯ppt4.7 多機調度問題問題描述：有n個獨立的作業(yè)1，2，n，由m臺相同的機器進行加工處理。作業(yè)i所需的處理時間為ti。任何作業(yè)可以在任何一臺機器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成。28編輯ppt4.7 多機調度問題算法思想：采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。按此策略，當 時，只要將機器i的0, ti