第4章 貪心算法1

1、第第4章章 貪心算法貪心算法Greedy Algorithms Software College, NEU2 活動安排問題活動安排問題 An Activity-Selection Problem 貪心算法的基本要素貪心算法的基本要素 Elements of the greedy strategy 最優(yōu)裝載最優(yōu)裝載 Maximum Loading 單源最短路徑單源最短路徑 Single-Source Shortest Paths 多機調(diào)度問題多機調(diào)度問題 A task-scheduling problem Software College, NEU3什么是貪心方法什么是貪心方法 假設(shè)有假設(shè)有4種

2、面值的錢幣：角、角、種面值的錢幣：角、角、5 5分分和分。和分。 要找給某顧客要找給某顧客5角角3分錢。分錢。 通常是拿出通常是拿出2個個2角，角，1個個1角和角和3個個1分的錢分的錢幣交給顧客幣交給顧客(把幣值從大到小排序把幣值從大到小排序量度標量度標準準)。 這種找錢的方法與其它的找法相比，所拿這種找錢的方法與其它的找法相比，所拿出的錢幣個數(shù)是最少的。出的錢幣個數(shù)是最少的。Software College, NEU4什么是貪心方法什么是貪心方法 上面的找?guī)潘惴ㄊ牵荷厦娴恼規(guī)潘惴ㄊ牵?首先選出首先選出1個不超過個不超過5角角3分的面值最大分的面值最大的錢幣，即的錢幣，即2角；角； 然后從然后

3、從5角角3分中減去分中減去2角，剩下角，剩下3角角3分；分； 再選出再選出1個不超過個不超過3角角3分的面值最大的分的面值最大的錢幣，即又一個錢幣，即又一個2角，如此一直做下去。角，如此一直做下去。 這個找錢幣的算法就是這個找錢幣的算法就是貪心方法貪心方法。Software College, NEU5什么是貪心方法什么是貪心方法 對于一個問題把滿足條件的任何一組解稱對于一個問題把滿足條件的任何一組解稱為為可行解可行解。 如上面找錢幣問題：拿出如上面找錢幣問題：拿出1個個2角角，3個個1角角和和3個個1分分；五個；五個1角角和和3個個1分分；10個個五分五分和和3個個1分分等等都是等等都是可行解

4、可行解。 使目標取極值（極大或極?。┑目尚薪猓鼓繕巳O值（極大或極?。┑目尚薪猓Q為稱為最優(yōu)解最優(yōu)解。 如上面找錢幣問題：拿出如上面找錢幣問題：拿出2個個2角，角，1個個1角角和和3個個1分的可行解就是分的可行解就是最優(yōu)解最優(yōu)解。Software College, NEU6什么是貪心方法什么是貪心方法 求圖著色問題近似解：求圖著色問題近似解： 先用一種顏色給盡可能多的結(jié)點上色，先用一種顏色給盡可能多的結(jié)點上色， 然后再用另一種顏色在未著色的結(jié)點中給然后再用另一種顏色在未著色的結(jié)點中給盡可能多的結(jié)點上色，如此反復直到所有盡可能多的結(jié)點上色，如此反復直到所有結(jié) 點 都 被 著 色 為 止 ， 這

5、 也 是結(jié) 點 都 被 著 色 為 止 ， 這 也 是 貪 心 法貪 心 法(greedy)。V1V2V4V5V3V6Software College, NEU7什么是貪心方法什么是貪心方法 A greedy algorithm always makes the choice that looks best at the moment. 貪心方法是作出在貪心方法是作出在當前看來最好的選擇當前看來最好的選擇，即所作的選擇只是即所作的選擇只是局部最優(yōu)選擇局部最優(yōu)選擇。 That is, it makes a locally optimal choice in the hope that this

6、choice will lead to a globally optimal solution. 希望從希望從局部的最優(yōu)選擇局部的最優(yōu)選擇得到得到整體最優(yōu)解整體最優(yōu)解。Software College, NEU8什么是貪心方法什么是貪心方法 如果硬幣面值為如果硬幣面值為1角角1分分、7分分、5分分、和、和1分分。 要找給顧客要找給顧客2角角6分分錢，錢， 按貪心方法找出的硬幣個數(shù)是：按貪心方法找出的硬幣個數(shù)是：2個個1角角1分和分和四個四個1分，共分，共6枚，枚， 這比這比1個個1角角1分和分和3個個5分多了分多了2枚；因此，從枚；因此，從局部的最優(yōu)選擇局部的最優(yōu)選擇得到的解得到的解并不總是問

7、題的最并不總是問題的最優(yōu)解優(yōu)解。 Software College, NEU9 貪心算法貪心算法總是作出在當前看來最好的選擇?？偸亲鞒鲈诋斍翱磥碜詈玫倪x擇。也就是說貪心算法也就是說貪心算法并不從整體最優(yōu)并不從整體最優(yōu)考慮，它所考慮，它所作出的選擇只是在某種意義上的作出的選擇只是在某種意義上的局部最優(yōu)選擇局部最優(yōu)選擇。當然，當然，希望希望貪心算法得到的最終結(jié)果也是整體貪心算法得到的最終結(jié)果也是整體最優(yōu)的。最優(yōu)的。 雖然貪心算法不能對所有問題都得到整雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路徑問題，最小生成樹問

8、題等。在如單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。解，其最終結(jié)果卻是最優(yōu)解的很好近似。Software College, NEU10算法思想算法思想 采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。標準下）。決策一旦作出，就不可再更改。Software College, NEU114.1 活動安排問題活動安排問題An Activity-Selec

9、tion Problem 已知已知n個活動個活動 E = 1, 2, , n 要求使用同要求使用同一資源，第一資源，第k個活動要求的開始和結(jié)束時間個活動要求的開始和結(jié)束時間為為sk , fk , 其中其中sk fk , k = 1, 2, , n 。如果。如果sk fj 或者或者sj fk ，則稱活動，則稱活動k與活動與活動j為相容為相容的。的?；顒影才艈栴}就是要在所給的活動集合中選活動安排問題就是要在所給的活動集合中選出最大的相容活動子集。出最大的相容活動子集。問題提出：問題提出：Software College, NEU12基本思路基本思路 在安排時應(yīng)該將結(jié)束時間早的活動盡量往前安排，在安

10、排時應(yīng)該將結(jié)束時間早的活動盡量往前安排，好給后面的活動安排留出更多的空間，從而達到好給后面的活動安排留出更多的空間，從而達到安排最多活動的目標。安排最多活動的目標。 貪心準則應(yīng)當是：貪心準則應(yīng)當是：在未安排的活動中挑選結(jié)束時在未安排的活動中挑選結(jié)束時間最早的活動安排。間最早的活動安排。4.1活動安排問題活動安排問題Software College, NEU13例 設(shè)待安排的設(shè)待安排的11個活動的開始時間和結(jié)束時間如下：個活動的開始時間和結(jié)束時間如下：k1234567891011sk 8 83 33 35 50 05 512128 81 12 26 6fk 12125 58 87 76 69 9

11、141411114 4131310104.1活動安排問題活動安排問題Software College, NEU14例 設(shè)待安排的設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)個活動的開始時間和結(jié)束時間按結(jié)束時間的非減次序排列如下：束時間的非減次序排列如下：k1234567891011sk 130535688212fk 45678910111213144.1活動安排問題活動安排問題Software College, NEU150123456789 101112 13 141isifi1142353064575386597610881198121021311121421314141461471481

12、4891481014811148114.1活動安排問題活動安排問題5Software College, NEU16 在貪心算法中，將各項活動的開始時間和結(jié)在貪心算法中，將各項活動的開始時間和結(jié)束時間分別用兩個數(shù)組束時間分別用兩個數(shù)組 start_time 和和 fin_time存儲。存儲。 使得數(shù)組中元素的順序按結(jié)束時間非減排列：使得數(shù)組中元素的順序按結(jié)束時間非減排列：fin_time1 fin_time2 fin_timen。 如果所給出的活從未按此序排列，我們可以如果所給出的活從未按此序排列，我們可以用用O(nlogn)的時間將它重排。的時間將它重排。4.1活動安排問題活動安排問題Soft

13、ware College, NEU17活動安排貪心算法偽代碼活動安排貪心算法偽代碼 templatevoid GreedySelector(int n, Type starttime , Type fintime , bool A ) A1 = true; /用集合用集合A來存儲所選擇的活動，活動來存儲所選擇的活動，活動i在集合在集合A中，中， /當且僅當當且僅當Ai的值為的值為true int join=1; /變量變量join用以記錄最近一次加入到用以記錄最近一次加入到A中的活動中的活動 for(int i =2; i=finishtimejoin) /如果第如果第i個任務(wù)和第個任務(wù)和第j

14、個相容個相容 Ai = true; join = i ; else Ai = false; 4.1活動安排問題活動安排問題Software College, NEU18算法的效率算法的效率 當輸入的活動已按結(jié)束時間的非減序排列當輸入的活動已按結(jié)束時間的非減序排列時，算法只需時，算法只需(n)的時間來安排的時間來安排n個活動，個活動，使最多的活動能相容地使用公共資源。使最多的活動能相容地使用公共資源。 貪心算法并不總能求得問題的整體最優(yōu)解，貪心算法并不總能求得問題的整體最優(yōu)解，但對于活動安排問題，貪心算法但對于活動安排問題，貪心算法GreedySelector卻總能求得整體最優(yōu)解，卻總能求得整體

15、最優(yōu)解，即它最終所確定的相容活動集合即它最終所確定的相容活動集合A的規(guī)模最的規(guī)模最大。大。4.1活動安排問題活動安排問題Software College, NEU19證明證明The optimal substructure of the activity-selection problem 總存在一個以貪心選擇開始的最優(yōu)活動安總存在一個以貪心選擇開始的最優(yōu)活動安排方案。排方案。 每一步所作的貪心選擇都將問題簡化為一每一步所作的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。個更小的與原問題具有相同形式的子問題。4.1活動安排問題活動安排問題Software College, NE

16、U20 設(shè)設(shè) A E是所給的活動安排問題的一個最優(yōu)解，且是所給的活動安排問題的一個最優(yōu)解，且A中活動也按結(jié)束時間非減序排列，中活動也按結(jié)束時間非減序排列，A中的第一個中的第一個活動是活動活動是活動k。 若若k1，則，則A就是一個以貪心選擇開始的最優(yōu)解。就是一個以貪心選擇開始的最優(yōu)解。若若k 1，則我們設(shè)，則我們設(shè)B = A - k 1。由于。由于f1 0, wi0, 1in1inin1inin目標函數(shù)4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU39背包問題問題描述背包問題問題描述 要得到最優(yōu)解，必須把背包裝滿，即

17、裝入要得到最優(yōu)解，必須把背包裝滿，即裝入背包的總重量等于背包的總重量等于c。 背包問題滿足背包問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)。 選擇合適的量度標準。選擇合適的量度標準。4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU40最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu) 背包問題：若它的一個最優(yōu)解包含物品背包問題：若它的一個最優(yōu)解包含物品j，則從該最優(yōu)解中拿出所含的物品則從該最優(yōu)解中拿出所含的物品j的那部的那部分重量分重量w，剩余的將是，剩余的將是n - 1個原重物品個原重物品1，2，j - 1, j + 1,，n,以及重為以及重為wj

18、- w的的物品物品j中可裝入容量為中可裝入容量為c - w的背包的背包,且具有且具有最大價值的物品。最大價值的物品。4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU41背包問題實例 考慮下列情況的背包問題考慮下列情況的背包問題 n=3，c=20，(v1,v2,v3)=(25,24,15)，(w1,w2,w3)=(18,15,10) 其中的其中的4個可行解是：個可行解是：(x1,x2,x3)wi xivixi(1/2,1/3,1/4)16.524.25(1,2/15,0)2028.2(0,2/3,1)2031(0,1,

19、1/2)2031.54.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU42最優(yōu)量度標準最優(yōu)量度標準選擇策略選擇策略(1)1先取目標函數(shù)為量度標準，先取目標函數(shù)為量度標準， 按物品價值按物品價值vi 由大到小排序由大到小排序n=3，c=20，(v1,v2,v3)=(25,24,15)，(w1,w2,w3)=(18,15,10)4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU43最優(yōu)量度標準最優(yōu)量度標準選擇策略選擇策略(1) 可行解可行解是以物品

20、價值是以物品價值vi 為量度標準進行為量度標準進行裝包的結(jié)果。裝包的結(jié)果。 先將物品先將物品1 裝入背包裝入背包(v1=25，w1=18)，這，這時時x1=1，獲得，獲得25的效益值。背包中剩下的效益值。背包中剩下2個個單位容量。單位容量。 將物品將物品2的的2/15裝入背包正好裝滿。這時裝入背包正好裝滿。這時x2= 2/15 ，獲得，獲得3.2的效益值。的效益值。 得到的總價值是得到的總價值是28.2 ，不是最優(yōu)解不是最優(yōu)解。 4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU44最優(yōu)量度標準最優(yōu)量度標準選擇策略選擇

21、策略(2) 以目標函數(shù)為量度標準，使背包容量消耗以目標函數(shù)為量度標準，使背包容量消耗過快。過快。2 2 按物品重量按物品重量wi由小到大的順序由小到大的順序 n=3，c=20，(v3,v2, v1)=(15,24, 25)，(w3,w2, w1)=(10,15, 18)4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU45最優(yōu)量度標準最優(yōu)量度標準選擇策略(2) 可行解可行解是以物品重量是以物品重量wi 為量度標準進行為量度標準進行裝包的結(jié)果。裝包的結(jié)果。 裝入物品裝入物品3 的重量的重量10及物品及物品2的重量的重量1

22、0，剛，剛好滿包，得到的總價值是好滿包，得到的總價值是31 ，也不是最優(yōu)也不是最優(yōu)解解。 原因是容量在漫漫消耗的過程中，效益值原因是容量在漫漫消耗的過程中，效益值卻沒有迅速的增加卻沒有迅速的增加。4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU46最優(yōu)量度標準最優(yōu)量度標準選擇策略(3)3. 按按pi/wi比值由大到小次序。比值由大到小次序。n=3，c=20，(v1,v2,v3)=(25,24,15)，(w1,w2,w3)=(18,15,10)4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的

23、基本要素Software College, NEU47最優(yōu)量度標準最優(yōu)量度標準選擇策略(3) 可行解可行解是以物品單位重量價值是以物品單位重量價值pi wi 為量為量度標準進行裝包的結(jié)果。度標準進行裝包的結(jié)果。 由于由于 p2 w2=1.6 ，p3 w3=1.5 ， p1 w1=1.39 ，因此選擇裝入物品，因此選擇裝入物品2 的重量的重量15及物品及物品3的重量的重量5，剛好滿包，得到的總，剛好滿包，得到的總價值是價值是31.5 。 得到的解是整體最優(yōu)解。得到的解是整體最優(yōu)解。 4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software Colleg

24、e, NEU48貪心解背包問題貪心解背包問題 首先計算每種物品單位重量的價值首先計算每種物品單位重量的價值vi / wi，然后，將盡可能多的，然后，將盡可能多的單位重量價值最高的物品裝入背包。單位重量價值最高的物品裝入背包。 void Knapsack(int n, float M, float v , float w , float x ) Sort (n, v, w);/將各種物品按單位重量價值排序?qū)⒏鞣N物品按單位重量價值排序 int i; for ( i = 1; i = n; i + ) xi = 0;/將解向量初始化為零將解向量初始化為零 float c = M; / 是背包剩余容量

25、初始化為是背包剩余容量初始化為M for ( i = 1;i = n; i + ) if ( ) break; x i = 1; c ; if ( i c- = w i x i = c / w i 4.2貪心算法的基本要素貪心算法的基本要素4.2貪心算法的基本要素貪心算法的基本要素Software College, NEU49算法復雜度算法復雜度 該算法的主要計算時間在于將各種物品依該算法的主要計算時間在于將各種物品依其單位重量的價值從大到小順序。因此算其單位重量的價值從大到小順序。因此算法的計算時間上界為法的計算時間上界為O(nlogn)。4.2貪心算法的基本要素貪心算法的基本要素4.2貪心

26、算法的基本要素貪心算法的基本要素Software College, NEU50貪心選擇對貪心選擇對0-1背包不適用背包不適用 背包容量為背包容量為50千克，物品千克，物品1重重10千克；價值千克；價值60元；物品元；物品2重重20千克，價值千克，價值100元；物品元；物品3重重30千克；價值千克；價值120元。元。4.3 最優(yōu)裝載最優(yōu)裝載 Maximum Loading4.3 最優(yōu)裝載最優(yōu)裝載Software College, NEU52 有一艘大船用來裝載貨物。假設(shè)有有一艘大船用來裝載貨物。假設(shè)有n個貨箱，個貨箱，它們的體積相同，重量分別是它們的體積相同，重量分別是 貨船的最大載重量貨船的最

27、大載重量是是c。目標是在船上裝最多貨。目標是在船上裝最多貨箱該怎樣裝？箱該怎樣裝？如果用如果用 表示不裝第表示不裝第i個貨箱，而個貨箱，而 表示裝表示裝第第i個貨箱，則上述問題是解優(yōu)化問題：求個貨箱，則上述問題是解優(yōu)化問題：求x1, x2,， xn，問題提出0 ix1 ixcxinii 1w niix1max滿足滿足使得使得nwww,214.3 最優(yōu)裝載最優(yōu)裝載Software College, NEU531.算法描述算法描述 采用重量最輕者先裝的貪心選擇策略采用重量最輕者先裝的貪心選擇策略. template void Loading ( int x , Type w ,Type c, in

28、t 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 & w t i = c; i + + ) x ti = 1; c - = w ti ; ti中存儲第中存儲第i輕物品在輕物品在原來序列中的下標。原來序列中的下標。4.3 最優(yōu)裝載最優(yōu)裝載Software College, NEU54例物品重量分別為物品重量分別為15，10，27，18，船載重為，船載重為50w =15, 10, 27, 18T = 1 , 0, 3, 2C=50wT0=1

29、0c, c= c-10=40wT1=15c, c=c-15=25wT2=18c4.3 最優(yōu)裝載最優(yōu)裝載552.貪心選擇性質(zhì)貪心選擇性質(zhì) 設(shè)貨箱已經(jīng)從小到大排序，設(shè)貨箱已經(jīng)從小到大排序， 是最優(yōu)裝載問是最優(yōu)裝載問題的一個最優(yōu)解，又設(shè)題的一個最優(yōu)解，又設(shè)),(21nxxx1|min1 inixik如果給定的最優(yōu)裝載問題有解，則如果給定的最優(yōu)裝載問題有解，則1kn（1）當）當k =1時，時， 是一個滿足貪婪選擇是一個滿足貪婪選擇性質(zhì)的最優(yōu)解。性質(zhì)的最優(yōu)解。（2）當）當k 1時，取時，取 則則 因此因此 ， 是所給最優(yōu)裝載問題的一個是所給最優(yōu)裝載問題的一個可行解，且是最優(yōu)解?？尚薪?，且是最優(yōu)解。),(21nxxx,1 ,;0;11kinixyyyiik cxwxwwwywiniiiniikinii 1111),(21nyyy