1、精選文檔貪心算法不在貪心中爆發，就在貪心中滅亡 武漢理工大學計算機科學與技術學院 班摘要本文介紹貪心算法的基本意義以及算法的使用范圍，并通過具體的案例來分析貪心算法的具體應用，從而指出其特點和存在問題。關鍵字：貪心算法，貪心策略，TSP、0/1背包引言我們用了13周的時間學完了算法設計與分析這本書。這本書中涵蓋了大量的常見算法，包括蠻力法、分治法、動態規劃法、貪心算法等等。我最有印象的就是貪心算法。貪心算法是一種有合理的數據組織和清晰高效的算法，它簡單有效。下面我們來詳細解讀一下這個算法。1. 貪心算法的含義貪心算法可以簡單描述為:對一組數據進行排序，找出最小值，進行處理，再找出最小值，再處理

2、。也就是說貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優的選擇，從而希望得到結果是最好或最優的算法。2. 貪心算法的基本思想貪心算法，法如其名，每次都貪心的選取當前最優解，一旦確定了當前解，不管將來有什么結果，之后都不會再修正，這一點與動態規劃法比起來稍有遜色。如果一個問題的最優解只能用蠻力法窮舉得到，則貪心法不失為尋找問題近似最優解的一個較好辦法。貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中

3、，直到把所有數據枚舉完，或者不能再添加算法停止。3. 貪心算法的基本要素3.1 貪心選擇貪心選擇是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇的性質，我們必須證明每一步所作的貪心選擇最終能得到問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規模更小的類似子問題。然后，用數學歸納法證明，通過每一

4、步貪心選擇，最終可得到問題的一個整體最優解。3.2 最優子結構當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。運用貪心策略在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動態規劃算法求解的關鍵特征。貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退;動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。動態規劃主要運用于二維或三維問題，而貪心一般是一維問題。4. 貪心算法的核心貪心算法的核心問題是選擇能產生問題最優解的最優度量標準，即具體的貪心策略。貪心策略決定著貪心算法是爆發或者是滅

5、亡。所以，選擇一個合理、正確的貪心策略是至關重要的。下面用例子說明：第一個例子我們選用大家熟知的0/1背包問題。給定種物品和一個背包。物品的重量是，其價值為，背包的容量為。在選擇物品裝入背包時，不可以選擇物品的一部分，一定要全部裝入背包， 。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?設表示物品裝入背包的情況，根據問題的要求，有如下約束條件和目標函數： 于是，背包問題歸結為尋找一個滿足約束條件式，并使目標函數式達到最大的解向量 。現在有一個容量為50的背包，共有三個物品，重量為別為20、30、10，價值分別為60、120、50。現使用貪心算法來放置物品，貪心策略也對應有三種，分別

6、是根據重量、價格、重量與價格比。根據重量的貪心策略，即優先放置重量小的物品，以此來達到放置更多個物品的目的。首先需要將物品按照重量從小到大重新排序，然后從小到大的放置物品，直至下個物品無法放進背包為止。偽代碼如下：public class worseGreedy public static void DepWeight(double a, double c, int ans) / depend/ on/ the/ weight to select/ goodsdouble w = new doublea0.length;System.arraycopy(a0, 0, w, 0, w.lengt

7、h);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(w);for (int i = 0; wi <= c && i < w.length; i+) c = c - wi;int j = sea.search(a0, wi);ansj = 1;程序的運行結果見附錄。根據價格的貪心策略，即優先放置價格比較高的物品，以此來達到背包價格更高的目的。首先需要將物品按照價格從大到小重新排序，然后依次放置物品，直至下個物品超出背包容量為止。偽代碼如下：public static void DepPrice(d

8、ouble a, double c, int ans) / depend on/ the price/ to select goodsdouble p = new doublea1.length;System.arraycopy(a1, 0, p, 0, p.length);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(p);int i = (p.length - 1);int j = sea.search(a1, pi);while (a0j <= c && i >= 0) c = c - a

9、0j;ansj = 1;i-;j = sea.search(a1, pi);程序的運行結果見附錄。根據重量與價格比值的貪心策略，即優先放置“性價比”高的物品，以此來達到背包價格最大的目的。首先需要求出各個物品的價格與重量的比值，然后按照這個參數來重新排序物品，價重比高的放前面。最后一次放入物品，直至下個物品超出背包容量為止。偽代碼如下：public static void DepWePr(double a, double c, int ans) / depend on/ the/ weight/ and pricedouble w = new doublea0.length; / the we

10、ight of goodsSystem.arraycopy(a0, 0, w, 0, w.length); / copy the arraydouble p = new doublea0.length; / the price of goodsSystem.arraycopy(a1, 0, p, 0, p.length); / copy the arraydouble pw = new doublew.length;for (int i = 0; i < w.length; i+)/ price/weightpwi = pi / wi;double wpw = new double2w.

11、length; / record the table of/ weight and pwSystem.arraycopy(w, 0, wpw0, 0, w.length);System.arraycopy(pw, 0, wpw1, 0, w.length);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(pw);int i = (pw.length - 1);int j = sea.search(wpw1, pwi);while (wpw0j <= c && i >= 0) c = c - wpw

12、0j;ansj = 1;i-;j = sea.search(wpw1, pwi);程序運行結果見附錄。根據程序運行的結果，我們分別得到三個答案。放置的物品方案分別為： 、 、 。如此看來，根據價格的貪心策略是最“貪心”的。其實不然，根據價格與重量比值的貪心策略的適應范圍更加廣闊，效果一般來說也更加的好。本例中受到小數據的局限性，無法發揮出其真正的效果。貪心策略之所以能成為貪心算法的核心，就是因為它決定著貪心算法是爆發還是滅亡，以及爆發的程度。上面的例子用三種不同的貪心策略，結果也截然不同。當擴大問題規模時，這種差距就更加的明顯。5. 貪心算法的特點貨郎擔問題(或稱旅行商問題或巡回售貨員問題)，

13、是NP問題中的著名問題。它通常的提法是：貨郎到各村去賣貨，再回到出發點處，每村到且僅到一次。為其設計一種路線，使得所用旅行售貨的時間最短。建立數學模型時，把村莊設為結點，村莊與村莊之間的路線設為結點之間的帶權的邊，則貨郎擔問題轉化為在圖上尋求最優圈問題。即在加權圖上求一個圈使得 貪心算法每選入一邊都保證了是當前可選邊中權值最小的邊，這便是“貪心”的含義。基本思想為首先選擇圖中任意頂點u，并將u置于頂點集合的子集S中。如果S是頂點集合V的真子集，就繼續選擇頂點j添加到子集S中， cij是權值最小的邊。按照同樣的步驟不斷進行貪心選擇，直到子集S=V為止。此時，選取到的所有的邊就構成了一棵最小生成樹

14、。偽代碼如下：public void find(int distance,int ans)int j=1;/starting cityfor(int i=0;i<distance.length;i+)ansi=j;j=min(distancej-1,ans);private int min(int a,int b)int minN=0;int temp=100;EnumerationSearch sea = new EnumerationSearch();for(int i=0;i<a.length;i+)if(sea.search(b, (i+1)=-1)if(ai<tem

15、p)temp=ai;minN=i;minN+;return minN;程序運行結果見附錄。同時我們運用動態規劃法來求解同樣的問題，問題規模為8個城市。動態求解過程需要使用10ms的時間，而貪心算法只需要使用1ms以內的時間即可完成計算，我們可以理解到貪心算法的爆發力了。但是，它們的結果并不相同。動態規劃法求解的答案為：，而貪心算法的答案為：。動態規劃法需要走的路程為21，而貪心算法需要走的路程為25。這就是貪心算法的特點，雖快但不一定準。貪心算法每次都是局部尋優，很容易會陷入局部最優解的波谷。所以，貪心算法總結起來一共有三個小缺點。1) 不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部

16、看來是最優的選擇，因此并不從整體上加以考慮。2) 貪心算法只能用來求某些最大或最小解的問題。從前面的討論中，背包問題要求得到最大價值是可行的，但是在另外一個求解最小路徑時采用貪心算法得到的結果并不是最佳。3) 貪心算法只能確定某些問題的可行性范圍。貪心算法的優點已經提到了，就是快，通常是線性到二次式，不需要多少額外的內存。一般二次方級的存儲要浪費額外的空間，而且那些空間經常得不出正解。但是，使用貪心算法時，這些空間可以幫助算法更容易實現且更快執行。如果有正確貪心性質存在，那么一定要采用!因為它容易編寫，容易調試，速度極快，并且節約空問。幾乎可以說，此時它是所有算法中最好的。6. 結束語貪心算法

17、是很常見的算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問題確定一個可行性范圍。貪心算法所作的選擇依賴于以往所作過的選擇，但決不依賴于將來的選擇，這使得算法在編碼和執行過程中都有一定的速度優勢。對于一個問題的最優解只能用窮舉法得到時，用貪心算法是尋找問題最優解的較好算法。對一個問題可以同時用幾種方法解決，貪心算法并不是對所有的問題都能得到整體最優解或是最理想的近似解時，就需判斷貪心性質的正確性了。與回溯法、動態規劃法等比較，它的適用區域相對狹窄許多。總之，如果一個貪心解決方案存在，就使用它。7. 參考文獻：1 肖衡.淺析貪心算法J.荊

18、楚理工學院學報.2009.092 常友渠,肖貴元,曾敏.貪心算法的探討與研究J. 重慶電力高等專科學校學報. 第13卷, 第3期3 汪瑩.論貪心算法在圖論中的應用J.南京郵電大學學報4 董軍軍.動態規劃算法和貪心算法的比較與分析J.軟件導刊. 第7卷 第2期5 林章美.貨郎擔問題的若干解法J.6 王紅梅.算法設計與分析M.北京：清華大學出版社.2006.77 江紅,余青松.程序設計教程M.8. 附錄源代碼：package Algorithm.ZeroPack.Console;import java.util.Scanner;import java.util.Arrays;import Algo

19、rithm.ZeroPack.Greedy.*;public class Console /* * param args */public static void main(String args) / TODO Auto-generated method stubScanner in = new Scanner(System.in);/ input somethingint num; / the number of itemsdouble c; / the capacity of the rucksackSystem.out.println("How big is this ruc

20、ksack capacity?");c = in.nextDouble();System.out.println("How manu items?");num = in.nextInt();int ans1 = new intnum; / the answerint ans2 = new intnum; / the answerint ans3 = new intnum; / the answerfor (int i = 0; i < num; i+) / initializationans1i = 0;ans2i = 0;ans3i = 0;double

21、table = new double2num; / the weight and priceSystem.out.println("please input the table");for (int i = 0; i < num; i+) /input the tableSystem.out.println("The weight of NO." + (i + 1) + " is:");table0i = in.nextDouble();System.out.println("The price of NO."

22、; + (i + 1) + " is:");table1i = in.nextDouble();worseGreedy.DepWeight(table, c, ans1);System.out.println("Depend on the weight"+Arrays.toString(ans1);worseGreedy.DepPrice(table, c, ans2);System.out.println("Depend on the price"+Arrays.toString(ans2);betterGreedy.DepWePr

23、(table, c, ans3);System.out.println("Depend on the weight and price"+Arrays.toString(ans3);System.out.println("over");package Algorithm.ZeroPack.Greedy;import QuickSort.Quick;import Search.EnumerationSearch;public class betterGreedy public static void DepWePr(double a, double c,

24、int ans) / depend on/ the/ weight/ and pricedouble w = new doublea0.length; / the weight of goodsSystem.arraycopy(a0, 0, w, 0, w.length); / copy the arraydouble p = new doublea0.length; / the price of goodsSystem.arraycopy(a1, 0, p, 0, p.length); / copy the arraydouble pw = new doublew.length;for (i

25、nt i = 0; i < w.length; i+)/ price/weightpwi = pi / wi;double wpw = new double2w.length; / record the table of/ weight and pwSystem.arraycopy(w, 0, wpw0, 0, w.length);System.arraycopy(pw, 0, wpw1, 0, w.length);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(pw);int i = (pw.length - 1);

26、int j = sea.search(wpw1, pwi);while (wpw0j <= c && i >= 0) c = c - wpw0j;ansj = 1;i-;j = sea.search(wpw1, pwi);package Algorithm.ZeroPack.Greedy;import QuickSort.Quick;import Search.EnumerationSearch;public class worseGreedy public static void DepWeight(double a, double c, int ans) / d

27、epend/ on/ the/ weight to select/ goodsdouble w = new doublea0.length;System.arraycopy(a0, 0, w, 0, w.length);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(w);for (int i = 0; wi <= c && i < w.length; i+) c = c - wi;int j = sea.search(a0, wi);ansj = 1;public static void Dep

28、Price(double a, double c, int ans) / depend on/ the price/ to select goodsdouble p = new doublea1.length;System.arraycopy(a1, 0, p, 0, p.length);EnumerationSearch sea = new EnumerationSearch();Quick.Sort(p);int i = (p.length - 1);int j = sea.search(a1, pi);while (a0j <= c && i >= 0) c

29、= c - a0j;ansj = 1;i-;j = sea.search(a1, pi);package QuickSort;public class Quick public static void Sort(double a) QuickSort(a,0,a.length-1);private static void QuickSort(double r, int first ,int end)int pivot;if(first<end)pivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot

30、+1,end);private static int Partition (double r,int first ,int end)int i=first;int j=end;double tmp;while(i<j)while(i<j&&ri<=rj)j-;if(i<j)tmp=ri;ri=rj;rj=tmp;i+;while(i<j&&ri<=rj)i+;if(i<j)tmp=ri;ri=rj;rj=tmp;j-;return i;package Search;public class EnumerationSear

31、ch public int search(double a,double goal)int add=-1;for (int i=0;i<a.length;i+)if (ai=goal)add=i;break;return add;public int search(int a,int goal)int add=-1;for (int i=0;i<a.length;i+)if (ai=goal)add=i;break;return add;package TSP.console;import java.util.Arrays;import TSP.find.*;public class console /* * param args */public static void main(String args) / TODO Auto-generated method stub int distance = /各個節點之間路徑長度的二維數組 0, 2, 1, 3, 4, 5, 5, 6, 1, 0, 4, 4, 2, 5, 5, 6, 5, 4, 0, 2, 2, 6, 5, 6, 5, 2, 2,