算法 第4章 貪心算法

1、1第4章 貪心算法2基本思想3基本思想4基本思想5基本思想例子：例子：如果面值改為1分、5分和11分，現(xiàn)要找給顧客15分，則用貪心算法，找錢方法：11 + 1 + 1 + 1 + 111 + 1 + 1 + 1 + 1顯然，找顯然，找3 3個個5 5分解決問題！分解決問題！兩種情況下可采用貪心算法：兩種情況下可采用貪心算法：1 1、利用貪心算法能夠找到原問題的整體最優(yōu)解；、利用貪心算法能夠找到原問題的整體最優(yōu)解；2 2、利用貪心算法找到的解是原問題解的近似解。、利用貪心算法找到的解是原問題解的近似解。不是整體最不是整體最優(yōu)解優(yōu)解6活動安排問題設有n個活動的集合E=1,2,n，其中每個活動都要求

2、使用同一資源，如演講會場等，而在同一時間內只有一個活動同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的相容的。也就是說，當sifj或sjfi時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出活動安排問題就是要在所給的活動集合中選出最大的相容活最大的相容活動子集合動子集合。7活動安排問題假設個活動的假設個活動的起始時間起始時間和和結束時間結束時間存儲于存儲于數(shù)組數(shù)組s s和和f

3、 f中且中且按按照結束時間的非遞減序排列照結束時間的非遞減序排列。注意：如果所給出的活動未按此序排列，注意：如果所給出的活動未按此序排列，可以用可以用O(nlognO(nlogn) )的時間重排。的時間重排。void GreedySelectorGreedySelector(int n, int s, int f, bool A) A1=true; int j=1; for (int i=2; i = = fjfj) Ai=true; j=i; else Ai=false;8活動安排問題由于輸入的活動以其完成時間的非減序非減序排列，所以算法GreedySelectorGreedySelecto

4、r每次總是選擇具有最早完成時間具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義貪心選擇的意義是使剩余的可安排使剩余的可安排時間段極大化時間段極大化，以便安排盡可能多的相容活動。 9活動安排問題 例：例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i12345678910 11Si 130535688212fi45678910 11 12 13 1410活動安排問題算法算法GreedySelectorGreedySelector 的計的計算過程算過程如左圖所示。圖中每行相應于算法的一次迭

5、代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。11活動安排問題貪心算法并不總能并不總能求得問題的整體最優(yōu)解整體最優(yōu)解。但對于活動安排問題，貪心算法GreedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可這個結論可以用數(shù)學歸納法證明以用數(shù)學歸納法證明。12貪心算法的基本要素對于一個具體的問題，怎么知道是否是否可用貪心算法解此問題，以及能否能否得到問題的最優(yōu)解呢？這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質貪心選擇性質和最優(yōu)子結構性質最

6、優(yōu)子結構性質。 13貪心算法的基本要素1.1.貪心選擇性質貪心選擇性質所謂貪心選擇性質貪心選擇性質是指所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質，必須必須證明證明每一步所作的貪心選擇最終導致問題的整體最每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。優(yōu)解。

7、14貪心算法的基本要素2.2.最優(yōu)子結構性質最優(yōu)子結構性質當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。 15貪心算法的基本要素3.貪心算法與動態(tài)規(guī)劃算法的差異貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結構最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解？是否是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?16貪心算法的基本要素n 0-1 0-1背包問題：背包問題： 給定n種物品和一個背包。物品i的重量是wi，其價值為vi，背

8、包的容量為c。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品在選擇裝入背包的物品時，對每種物品i i只有只有2 2種選擇，種選擇，即裝入背包或不裝入背包。不能將物品即裝入背包或不裝入背包。不能將物品i i裝入背包多裝入背包多次，也不能只裝入部分的物品次，也不能只裝入部分的物品i i。動態(tài)規(guī)劃算法可解動態(tài)規(guī)劃算法可解17貪心算法的基本要素n 背包問題：背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可可以選擇物品以選擇物品i i的一部分的一部分，而不一定要全部裝入背包，1in。這2類問題都具有最優(yōu)子結構最優(yōu)子結構性質，極為相似，但

9、背包問題可但背包問題可以用貪心算法求解以用貪心算法求解，而而0-10-1背包問題卻不能用貪心算法求解背包問題卻不能用貪心算法求解。 18貪心算法的基本要素用貪心算法解用貪心算法解背包問題背包問題的基本步驟：的基本步驟： 首先，計算每種物品單位重量的價值單位重量的價值v vi i/ /w wi i;然后，依貪心選擇策略，將盡可能多的單位重量價值單位重量價值最高最高的物品裝入背包;若將這種物品全部裝入背包后，背包內的物品總重量未超過c，則選擇單位重量價值次高次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。19貪心算法的基本要素void KnapsackKnapsack(i

10、nt n, float M, float v, float w, float x) Sort(n,v,wSort(n,v,w); ); for(int i=1; i=n; i+) xi = 0; float c = M; for(int i=1; ic) break; xi = 1; c -= wi; if(i=n) xi = c/wi;/將各物品根據單位重量的價值從大到小排序將各物品根據單位重量的價值從大到小排序時間復雜性：時間復雜性：O(nlogn)20貪心算法的基本要素0-10-1背包問題不能使用貪心算法求解：背包問題不能使用貪心算法求解： 1060120100230120350Bag2

11、010貪貪心心算算法法3020動動態(tài)態(tài)規(guī)規(guī)劃劃算算法法X100+120=22060+100=16021最優(yōu)裝載有一批集裝箱要裝上一艘載重量為載重量為c c的輪船。其中集裝箱i的重量為wi。最優(yōu)裝載問題要求確定在裝載體積不受限制裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船盡可能多的集裝箱裝上輪船。算法描述算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪采用重量最輕者先裝的貪心選擇策略心選擇策略，可產生最優(yōu)裝載問題的最優(yōu)解。22最優(yōu)裝載void LoadingLoading(int x, float w, float c, int n) Sort(nSort(n, w); ,

12、w); for(int i=1; i=n; i+) xi = 0; for(int i=1; i=n & wi = c; i+) xi = 1; c -= wi; /將各集裝箱根據重量從小到大排序將各集裝箱根據重量從小到大排序時間復雜性：時間復雜性：O(nlogn)23最小生成樹 設G =(V,E)是無向連通帶權圖，即一個網絡網絡。E中每條邊(v,w)的權為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹最小生成樹。網絡的最小生成樹在實際中有廣泛應用。例如例如，在設計

13、通信網絡時，用圖的頂點表示城市，用邊(v,w)的權cvw表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網絡的最經濟的方案。 24最小生成樹1.1.最小生成樹性質最小生成樹性質用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質最小生成樹性質：設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權cuv最小，那

14、么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質有時也稱為MSTMST性質性質。 25最小生成樹2.Prim2.Prim算法算法 設G=(V,E)是連通帶權圖，V=1,2,n。構造G的最小生成樹的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選貪心選擇擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小最小生成樹生成樹。 26最小生成樹利用最小生成樹性質和數(shù)學歸納法容易證明，上述算法中的邊集合邊集合T T始終始終包含包含G G的某棵最小生成

15、樹中的某棵最小生成樹中的邊的邊。因此，在算法結束時，T中的所有邊構成G的一棵最小生成樹。 例如例如，對于右圖中的帶權圖，按PrimPrim算法算法選取邊的過程如下頁圖所示。27最小生成樹28最小生成樹在上述Prim算法中，還應當考慮如何有效地找出滿如何有效地找出滿足條件足條件i i S,jS,j V V-S-S，且權，且權cijcij 最小的邊最小的邊( (i,ji,j) )。實現(xiàn)這個目的的較簡單的辦法是設置2個數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據數(shù)組closest選取邊(j,closestj)，最后將j添加到S中

16、，并對closest和lowcost作必要的修改。用這個辦法實現(xiàn)的Prim算法所需的計算時間計算時間為 )(2nO29最小生成樹3.Kruskal3.Kruskal算法算法Kruskal算法構造G的最小生成樹的基本思想基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接

17、再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。 30最小生成樹例如，例如，對前面的連通帶權圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。31最小生成樹關于集合的一些基本運算集合的一些基本運算可用于實現(xiàn)Kruskal算法。 按權的遞增順序查看等價于對優(yōu)先隊列優(yōu)先隊列執(zhí)行removeMinremoveMin運算?？梢杂枚讯褜崿F(xiàn)這個優(yōu)先隊列。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據類型并查集并查集UnionFindUnionFind所支持的基本運算。當圖的邊數(shù)為e時，Kruskal算法所需的計算時間計算時間是 。當 時，Kruskal算法比Prim

18、算法差，但當 時，Kruskal算法卻比Prim算法好得多。)log(eeO)(2ne)(2noe 32哈夫曼編碼哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。1.1.前綴碼前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼前綴碼。33哈夫曼編碼 編碼的前綴性質可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹完全二叉樹，即樹中任一結點都有2個兒子結點。平均碼長平均碼長定義為：使平均碼長達到最小