【正文】 第四章 .貪心算法 (Greed method) 例 題 算法設(shè)計(jì)與分析 貪心算法 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的 局部最優(yōu) 選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。 目的：用以求解最優(yōu)化問題 將問題的求解過程看作是一系列選擇 ,每次選擇一個輸入 ,每次選擇都是當(dāng)前狀態(tài)下的最好選擇 (局部最優(yōu)解).每作一次選擇后 ,所求問題會簡化為一個規(guī)模更小的子問題 .從而通過每一步的最優(yōu)解逐步達(dá)到整體的最優(yōu)解。 基本思想 [算法優(yōu)點(diǎn) ]求解速度快 ,時間復(fù)雜性有較低的階 . [算法缺點(diǎn) ]需證明是最優(yōu)解 . [常見應(yīng)用 ] 背包問題 ,最小生成樹 ,最短路徑 ,作業(yè)調(diào)度等等 [適用問題 ] 具備 貪心選擇 和 最優(yōu)子結(jié)構(gòu) 性質(zhì)的最優(yōu)化問題 貪心選擇 性質(zhì)： 整體的最優(yōu)解可通過一系列局部最優(yōu)解達(dá)到，即貪心選擇到達(dá)。 貪心算法通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求解的問題化簡為規(guī)模更小的問題 對于一個具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的最優(yōu)解。通?？梢允紫茸C明問題的一個整體最優(yōu)解，是從 貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體 最優(yōu)解。 最優(yōu)子結(jié)構(gòu)性質(zhì) ： 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 A(1) A(2) … A(n1) A(n) 某一問題的 n個輸入 B1(1) B1(2) … B1(m) 該問題的一種解（可行解） 是 A的一 個子集 滿足一定 的條件 約束條件 Bk(1) Bk(2) … Bk(m) … 目標(biāo)函數(shù) 取極值 最優(yōu)解 算法設(shè)計(jì)與分析 貪心算法 算法設(shè)計(jì)與分析 貪心算法 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。 [問題陳述 ]設(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)不相交，則稱活動 i與活動 j是相容的。也就是說，當(dāng) si≥f j或 sj≥f i時，活動 i與活動 j相容。 1 2 3 4 5 6 7 8 9 10 11 [例 ] 1 3 0 5 3 5 6 8 8 2 12 4 5 6 7 8 9 10 11 12 13 14 i s[i] f[i] 設(shè)待安排的 11個活動起止時間按結(jié)束時間的非減序排列 最大相容活動子集 (1, 4, 8, 11), 也可表示為等長 n元數(shù)組 :(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1) [算法思路 ]將 n個活動按結(jié)束時間非減序排列 ,依次考慮活動 i, 若 i與已選擇的活動相容 ,則添加此活動到相容活動子集 . 活動安排問題貪心算法 template class Type void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] ) { A[ 1 ] = true。 int j = 1。 //從第二個活動開始檢查是否與前一個相容 for (int i=2。i =n。i+ +) { if (s[i]=f[j]) { A[i] = true。 j=i。} else A[ i] = false。} } 算法設(shè)計(jì)與分析 貪心算法 各活動的起始時間和結(jié)束時間存儲于數(shù)組 s和 f中且按結(jié)束時間的非減序排列 算法 greedySelector 的計(jì)算過程 如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。 由于輸入的活動以其完成時間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時間 的相容活動加入集合 A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是 使剩余的可安排時間段極大化 ，以便安排盡可能多的相容活動。 算法 greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需 O(n)的時間安排 n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用 O(nlogn)的時間重排。 T(n)=O(nlogn) (未排序時 ) [算法分析 ] T(n)=O(n) (排序時 ) [算法證明 ] 算法達(dá)到最優(yōu)解 . [問題描述 ] 輸入 :(x1,x2,...xn), xi=0,貨箱 i不裝船 。 xi=1,貨箱 i裝船 可行解 : 滿足約束條件 ≤c 的輸入 優(yōu)化函數(shù) : 最優(yōu)解 :使優(yōu)化函數(shù)達(dá)到最大值的一種輸入 . ini ixw??1??ni ix1 最優(yōu)裝載 算法設(shè)計(jì)與分析 貪心算法 [算法思路 ] 將裝船過程劃為多步選擇，每步裝一個貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱 .如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。 [例 ] 設(shè) n=8， [w1， …w 8]=[100, 200, 50, 90, 150, 50, 20, 80]， c=400。 所考察貨箱的次序?yàn)? :7, 3, 6, 8, 4, 1, 5, 2。貨箱 7, 3, 6, 8, 4, 1的 總重量為 390個單位且已被裝載 , 剩下的裝載能力為 10 ,小于任意 貨箱 .所以得到解 [x1,...x8]=[ 1, 0, 1, 1, 0, 1, 1, 1] 最優(yōu)裝載的貪心算法 算法設(shè)計(jì)與分析 貪心算法 template class Type void Loading(int x[], Type w[], Type c, int n ) { int *t = new int [n + 1]。 Sort(w, t, n) 。 //按貨箱重量排序 / for (int i = 1。 i = n。 i ++) x[i] = 0。 for (int i = 1。i= n amp。amp。 w[t[i]] = c。 i++) { x[t[i]] = 1。 c= w[t[i]]。 //調(diào)整 剩余空間 } } ? 貪心選擇性質(zhì) ? 可以證明最優(yō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ì)，容易證明算法 loading的正確性。 ? 算法分析 :算法 loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時間為 O(nlogn)。 [最優(yōu)化描述 ] 找一個 n元 向量 (x1,…x n) 0? xi ?1 使得 且 .其中 C, Wi, vi0 , 1 ? i ? n 44 背包問題 (Knapsack Problem) cxwniii ???1??niii xv1m ax[問題描述 ]設(shè)有 n個物體和一個背包 ,物體 i的重量為 wi ,價(jià)值為 vi ,背包的容量為 i的 xi部分 (1?i?n, 0?xi?1)裝入背包 ,則具有價(jià)值為 vi xi. 目標(biāo)是找到一個方案 ,使放入背包的物體總價(jià)值最高 . 約 束 條 件 優(yōu)化函 數(shù) 算法設(shè)計(jì)與分析 貪心算法 背包問題實(shí)例 ? 考慮下列情況的背包問題 – n=3,M=20,(v1,v2,v3)=(25,24,15), (w1,w2,w3)=(18,15,10) – 其中的 4個可行解是： (x1,x2,x3) ∑ wi xi ∑ vixi ① (1/2,1/3,1/4) ② (1,2/15,0) 20 ③ (0,2/3,1) 20 31 ④ (0,1,1/2) 20 算法設(shè)計(jì)與分析 貪心算法 貪心方法的數(shù)據(jù)選擇策略 (1) 用貪心策略求解背包問題時 ， 首先要選出最優(yōu)的度量標(biāo)準(zhǔn) 。 可以 選取目標(biāo)函數(shù)為量度標(biāo)準(zhǔn) ， 每裝入一件物品就使背包獲得最大可能的效益值增量 。 在這種量度標(biāo)準(zhǔn)下的貪心方法就是 按效益值的非增次序?qū)⑽锲芬患诺奖嘲?。 如上面的實(shí)例所示 ， 可 將物品按效益量非增次序排序： (v1,v2,v3)=(25,24,15)。 先裝入物品 1重量為 18， 即x1=1；然后再裝物品 2， 由于約束條為 ∑ wi xi ≤ M=20，所以物品 2只能裝入重量為 2的一小部分 ， 即 x2=2/15。 按上述的數(shù)據(jù)選擇策略 ， 裝入順序是按照物品的效益值從大到小的輸入 ， 由剛才的方法可得這種情況下的總效益值為 ∑ vixi = 25+24*2/15=， 顯然是一個次優(yōu)解 ， 原因是背包容量消耗過快 。 算法設(shè)計(jì)與分析 貪心算法 貪心方法的數(shù)據(jù)選擇策略 (2) 若以容量作為量度 ， 可讓背包容量盡可能慢地被消耗 。 這就要求 按物品重量的非降次序來把物品放入背包 ， 即 (w3,w2,w1)=(10,15,18)。 先裝入物品 3, x3=1, p3x3 =15，再裝入重量為 10的物品 2， ∑ vixi =15+24*10/15=31。 由剛才的方法可得這種情況下的總效益值為 31， 仍是一個次優(yōu)解 ， 原因是容量在漫漫消耗的過程中 ， 效益值卻沒有迅速的增加 。 算法設(shè)計(jì)與分析 貪心算法 貪心方法的數(shù)據(jù)選擇策略 (3) 采用在效益值的增長速率和容量的消耗速率之間取得平衡的量度標(biāo)準(zhǔn) 。 即每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益 。 這就需 使物品的裝入次序按 vi/wi比值的非增次序來考慮 。 這種策略下的量度是已裝入物品的累計(jì)效益值與所用容量之比。 (v2/w2 , v3/w3 , v1/w1 )=(24/15,15/10, 25/18) 先裝入重量為 15的物品 2，在裝入重量為 5的物品 3， ∑ pixi =24+15*5/10=。此結(jié)果為最優(yōu)解。 算法設(shè)計(jì)與分析 貪心算法 [算法思路 ]1).將各物體按單位價(jià)值由高到低排序 . 2).取價(jià)值最高者放入背包 . 3).計(jì)算背包剩余空間 . 4).在剩余物體中取價(jià)值最高者放入背包 . 若背包剩余容量 =0或物體全部裝入背包為止 [例 ] n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) ??ni iixw1??ni iixv1{x1,x2,x3} { 0,2/