第4章貪心算法(new)

1、1第4章 貪心算法 顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)局部最優(yōu)選擇。當然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。2第4章 貪心算法本章主要知識點： 4.1 活動安排問題 4.2 貪心算法的基本要素 4.3 最優(yōu)裝載 4.4 哈夫曼編碼 4.5 單源最短路徑 4.6 最小生成樹 4.7 多機調(diào)度問題 4.8 貪心算

2、法的理論基礎(chǔ)34.1 活動安排問題 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。44.1 活動安排問題 設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱

3、活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。54.1 活動安排問題輸入實例：輸入實例：挑選過程是多步判斷，每步依據(jù)某種“短視”的策略進行活動選擇，選擇時注意滿足相容性條件.策略1：開始時間早的優(yōu)先排序使 s1s2sn，從前向，從前向后挑選后挑選策略2：占用時間少的優(yōu)先排序使得 f1s1 f2- s2fnsn，從前，從前向后向后挑選挑選策略3：結(jié)束早的優(yōu)先排序使 f1f2 fn，從前向后，從前向后挑挑選選i1234567891011Si130535688212Fi456789101112131464.1 活動安排問題策略1：開始早的優(yōu)先反例： S =1,2,3

4、s1=0, f1=20, s2=2, f2=5, s3=8, f3=1574.1 活動安排問題策略2：占時少的優(yōu)先反例： S = 1, 2, 3 s1=0, f1=8, s2=7, f2=9, s3=8, f3=1584.1 活動安排問題策略3：活動安排問題的貪心算法greedySelectorgreedySelector :public static int greedySelector(int s, int f, boolean a) int n=s.length-1; a1=true; int j=1; int count=1; for (int i=2;i=fj) ai=true; j

5、=i; count+; else ai=false; return count; 各活動的起始時間和結(jié)各活動的起始時間和結(jié)束時間存儲于數(shù)組束時間存儲于數(shù)組s s和和f f中且按結(jié)束時間的非減中且按結(jié)束時間的非減序排列序排列 94.1 活動安排問題 由于輸入的活動以其完成時間的非減序非減序排列，所以算法greedySelectorgreedySelector每次總是選擇具有最早完成時具有最早完成時間間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時使剩余的可安排時間段極大化間段極大化，以便安排盡可能多的相容活

6、動。 算法greedySelectorgreedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)O(nlogn)的時間重排。 104.1 活動安排問題 例：例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i1234567891011Si130535688212fi4567891011121314114.1 活動安排問題 算法算法greedySelector greedySelector 的的計算過程計算過程如左圖所示。圖

7、中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。124.1 活動安排問題 若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學歸納法證明。134.2 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得

8、到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 144.2 貪心算法的基本要素1.1.貪心選擇性質(zhì)貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為

9、規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。154.2 貪心算法的基本要素2.2.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 164.2 貪心算法的基本要素3.貪心算法與動態(tài)規(guī)劃算法的差異 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能

10、用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。174.2 貪心算法的基本要素 0-10-1背包問題：背包問題： 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品在選擇裝入背包的物品時，對每種物品i i只有只有2 2種選擇，即種選擇，即裝入背包或不裝入背包。不能將物品裝入背包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入背包多次，也不能只裝入部分的物品裝入部分的物品i i。184.2 貪心算法的基本要素 背包問

11、題：背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品可以選擇物品i i的一部分的一部分，而不一定要全部裝入背包，1in。 這2類問題都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 194.2 貪心算法的基本要素用貪心算法解背包問題的基本步驟： 首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背

12、包裝滿為止。 具體算法可描述如下頁： 204.2 貪心算法的基本要素public static float knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; opt+=di.v; c-

13、=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; 算法算法knapsackknapsack的的主要計算時間在于將主要計算時間在于將各種物品依其單位重各種物品依其單位重量的價值從大到小排量的價值從大到小排序。因此，算法的計序。因此，算法的計算時間上界為算時間上界為O O（nlognnlogn）。當然，）。當然，為了證明算法的正確為了證明算法的正確性，還必須證明背包性，還必須證明背包問題具有貪心選擇性問題具有貪心選擇性質(zhì)質(zhì)。214.2 貪心算法的基本要素 對于0-10-1背包問題背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況

14、下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃動態(tài)規(guī)劃算法算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。 224.3 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1.1.算法描述算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝

15、載問題的最優(yōu)解。具體算法描述如下頁。 234.3 最優(yōu)裝載 void loading(int x , Type w, Type c, int n) int *t = new intn+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti; 其中其中ElementElement類說明為參類說明為參見本書見本書P115P115244.3 最優(yōu)裝載2.2.貪心選擇性質(zhì)貪心選擇性質(zhì) 可以證明(數(shù)學歸納法)最優(yōu)裝載問題具有貪心選擇性質(zhì)。

16、 3.3.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loadingloading的正確性。算法loadingloading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)O(nlogn)。 254.4 哈夫曼編碼哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 應(yīng)用

17、：數(shù)據(jù)壓縮、數(shù)據(jù)傳輸和圖像壓縮應(yīng)用：數(shù)據(jù)壓縮、數(shù)據(jù)傳輸和圖像壓縮264.4 哈夫曼編碼1.1.前綴碼前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼前綴碼。例如：非例如：非前綴碼的例子前綴碼的例子 a: 001, b: 00, c: 010, d: 01 解碼解碼的歧義，例如字符串的歧義，例如字符串 0100001 解碼解碼1: 01, 00, 001 d, b, a 解碼解碼2: 010, 00, 01 c, b, d274.4 哈夫曼編碼前綴碼的二叉樹表示例如：前綴碼：例如：前綴碼：00000, 00001, 0001, 001

18、, 01,100,101,11構(gòu)造樹：0 -左子樹1-右子樹碼對應(yīng)一片樹葉最大位數(shù)為樹深284.4 哈夫曼編碼B=(5+5)B=(5+5)* *5+105+10* *4 4+ + ( (15+10+10)15+10+10)* *3 3+ + ( (25+20)25+20)* *2/2/100100 = =2.852.85使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼最優(yōu)前綴碼。 niiixdxfB1)()(294.4 哈夫曼編碼2.2.構(gòu)造哈夫曼編碼構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表

19、示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結(jié)點開始，執(zhí)行|C|1次的“合并”運算后產(chǎn)生最終所要求的樹T。 304.4 哈夫曼編碼算法算法 Huffman(C )輸入：輸入： C =x1, x2, xn, f(xi), i=1,2,n.輸出：輸出： Q / /隊列隊列1. n|C |2. QC /頻率遞增隊列頻率遞增隊列Q3. for i1 to n1 do4. zAllocate-Node() /生成結(jié)點生成結(jié)點 z5. z.leftQ中最小元中最小元 /最小作最小作z左兒子左兒子6. z.rightQ中最小元中最小元 /最小作最小作z右兒子右兒子7. f(z)f(x)+f(y)8. Inser

20、t(Q,z) / 將將 z 插入插入Q9. return Q314.4 哈夫曼編碼實例實例編碼：編碼：f-0000,e-0001,d-001,c-010,b011,a1平均位數(shù)：4(0.05+0.09)+3(0.16+0.12+0.13)+10.45=2.24324.4 哈夫曼編碼3.3.哈夫曼算法的正確性哈夫曼算法的正確性要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)334.4 哈夫曼編碼(1)(1)貪心選擇性質(zhì)貪心選擇性質(zhì)引理引理1: C是字符集，是字符集， cC, f(c)為頻率為頻率,

21、x,yC,f(x), f(y)頻率頻率最最小小, 那么存在最優(yōu)二元那么存在最優(yōu)二元前綴碼使得前綴碼使得 x, y 碼字等長且僅在碼字等長且僅在最后最后一一位不同位不同.f(x)f(a)f(x)f(a)f(y)f(b)f(y)f(b)344.4 哈夫曼編碼(2)最優(yōu)子結(jié)構(gòu)性質(zhì)354.5 單源最短路徑給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負實數(shù)。另外，還給定V中的一個頂點，稱為源源。現(xiàn)在要計算從源到所有其他各頂點的最短路長度最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題單源最短路徑問題。1.1.算法基本思想算法基本思想Dijkstra算法是解單源最短路徑問

22、題的貪心算法。364.5 單源最短路徑其基本思想基本思想是，設(shè)置頂點集合S并不斷地作貪心選擇貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。374.5 單源最短路徑例如例如，對右圖中的有向圖，應(yīng)用Dijkstra

23、算法計算從源頂點1到其他頂點間最短路徑的過程列在下頁的表中。384.5 單源最短路徑迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代過程： 394.5 單源最短路徑2.2.算法的正確性和計算復(fù)雜性算法的正確性和計算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計算復(fù)雜性對于具有n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表

24、示這個圖，那么Dijkstra算法的主循環(huán)體需要 時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要 時間。算法的其余部分所需要時間不超過 。)(nO)(2nO)(2nO404.6 最小生成樹 設(shè)G =(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹最小生成樹。網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如例如，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)cvw表示建立城市v和城市w之間的通信線路所需的

25、費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。 414.6 最小生成樹1.1.最小生成樹性質(zhì)最小生成樹性質(zhì)用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MSTMST性

26、質(zhì)性質(zhì)。 424.6 最小生成樹2.Prim2.Prim算法算法 設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。構(gòu)造G的最小生成樹的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選貪心選擇擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小最小生成樹生成樹。 434.6 最小生成樹設(shè)計思想設(shè)計思想輸入：圖 G=(V,E,W), V=1,2,n輸出：輸出：最小生成樹最小生成樹 T設(shè)計思想：設(shè)計思想：初始初始 S = 1，選擇連接選擇連接 S 與與 VS 集合的

27、最短邊集合的最短邊 e = i, j ，其中，其中 iS, jVS. 將將 e 加入樹加入樹T， j 加入加入 S.繼續(xù)執(zhí)行上述過程，直到繼續(xù)執(zhí)行上述過程，直到 S=V 為止為止444.6 最小生成樹算法 Prim ( G, E, W )1 S 1 2 while V S do3 從從VS中選擇中選擇 j 使得使得 j 到到 S中中頂點的頂點的邊權(quán)邊權(quán) 最小最小4 S S j 454.6 最小生成樹利用最小生成樹性質(zhì)和數(shù)學歸納法容易證明，上述算法中的邊集合邊集合T T始終始終包含包含G G的某棵最小生成樹中的某棵最小生成樹中的邊的邊。因此，在算法結(jié)束時，T中的所有邊構(gòu)成G的一棵最小生成樹。 例

28、如例如，對于右圖中的帶權(quán)圖，按PrimPrim算法算法選取邊的過程如下頁圖所示。464.6 最小生成樹474.6 最小生成樹在上述Prim算法中，還應(yīng)當考慮如何有效地找出滿如何有效地找出滿足條件足條件i i S,jS,j V-SV-S，且權(quán)，且權(quán)cijcij最小的邊最小的邊(i,j)(i,j)。實現(xiàn)這個目的的較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對closest和lowcost作必要的修改。用這個辦法實現(xiàn)的Prim算法所需的

29、計算時間計算時間為 )(2nO484.6 最小生成樹3.Kruskal3.Kruskal算法算法Kruskal算法構(gòu)造G的最小生成樹的基本思想基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。 494.6 最小生成樹算法 Kruskal輸入：連通圖G / 頂點數(shù)頂點數(shù)n，邊數(shù)，邊數(shù)m輸出：輸出： G 的最小生成樹的最小生成樹1. 權(quán)從小到大排序權(quán)從小到大排序E的邊的邊,