算法設(shè)計(jì)與分析論文

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

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

3、，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止。3. 貪心算法的基本要素3.1 貪心選擇貪心選擇是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終能得到問(wèn)題的最優(yōu)解。通常可以首先證明問(wèn)題的一個(gè)整體最優(yōu)解，是從貪心選擇開(kāi)始的，而且作了貪心選擇后，原問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一

4、步貪心選擇，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。3.2 最優(yōu)子結(jié)構(gòu)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運(yùn)用貪心策略在每一次轉(zhuǎn)化時(shí)都取得了最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，而動(dòng)態(tài)規(guī)劃則不是。貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退;動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題，而貪心一般是一維問(wèn)題。4. 貪心算法的核心貪心算法的核心問(wèn)題是選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)度量標(biāo)準(zhǔn)，即具體的貪心策略。貪心策略決定著貪心算法是爆發(fā)或者是滅

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

6、是根據(jù)重量、價(jià)格、重量與價(jià)格比。根據(jù)重量的貪心策略，即優(yōu)先放置重量小的物品，以此來(lái)達(dá)到放置更多個(gè)物品的目的。首先需要將物品按照重量從小到大重新排序，然后從小到大的放置物品，直至下個(gè)物品無(wú)法放進(jìn)背包為止。偽代碼如下：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;程序的運(yùn)行結(jié)果見(jiàn)附錄。根據(jù)價(jià)格的貪心策略，即優(yōu)先放置價(jià)格比較高的物品，以此來(lái)達(dá)到背包價(jià)格更高的目的。首先需要將物品按照價(jià)格從大到小重新排序，然后依次放置物品，直至下個(gè)物品超出背包容量為止。偽代碼如下：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);程序的運(yùn)行結(jié)果見(jiàn)附錄。根據(jù)重量與價(jià)格比值的貪心策略，即優(yōu)先放置“性價(jià)比”高的物品，以此來(lái)達(dá)到背包價(jià)格最大的目的。首先需要求出各個(gè)物品的價(jià)格與重量的比值，然后按照這個(gè)參數(shù)來(lái)重新排序物品，價(jià)重比高的放前面。最后一次放入物品，直至下個(gè)物品超出背包容量為止。偽代碼如下：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);程序運(yùn)行結(jié)果見(jiàn)附錄。根據(jù)程序運(yùn)行的結(jié)果，我們分別得到三個(gè)答案。放置的物品方案分別為： 、 、 。如此看來(lái)，根據(jù)價(jià)格的貪心策略是最“貪心”的。其實(shí)不然，根據(jù)價(jià)格與重量比值的貪心策略的適應(yīng)范圍更加廣闊，效果一般來(lái)說(shuō)也更加的好。本例中受到小數(shù)據(jù)的局限性，無(wú)法發(fā)揮出其真正的效果。貪心策略之所以能成為貪心算法的核心，就是因?yàn)樗鼪Q定著貪心算法是爆發(fā)還是滅亡，以及爆發(fā)的程度。上面的例子用三種不同的貪心策略，結(jié)果也截然不同。當(dāng)擴(kuò)大問(wèn)題規(guī)模時(shí)，這種差距就更加的明顯。5. 貪心算法的特點(diǎn)貨郎擔(dān)問(wèn)題(或稱旅行商問(wèn)題或巡回售貨員問(wèn)題)，

13、是NP問(wèn)題中的著名問(wèn)題。它通常的提法是：貨郎到各村去賣貨，再回到出發(fā)點(diǎn)處，每村到且僅到一次。為其設(shè)計(jì)一種路線，使得所用旅行售貨的時(shí)間最短。建立數(shù)學(xué)模型時(shí)，把村莊設(shè)為結(jié)點(diǎn)，村莊與村莊之間的路線設(shè)為結(jié)點(diǎn)之間的帶權(quán)的邊，則貨郎擔(dān)問(wèn)題轉(zhuǎn)化為在圖上尋求最優(yōu)圈問(wèn)題。即在加權(quán)圖上求一個(gè)圈使得 貪心算法每選入一邊都保證了是當(dāng)前可選邊中權(quán)值最小的邊，這便是“貪心”的含義?；舅枷霝槭紫冗x擇圖中任意頂點(diǎn)u，并將u置于頂點(diǎn)集合的子集S中。如果S是頂點(diǎn)集合V的真子集，就繼續(xù)選擇頂點(diǎn)j添加到子集S中， cij是權(quán)值最小的邊。按照同樣的步驟不斷進(jìn)行貪心選擇，直到子集S=V為止。此時(shí)，選取到的所有的邊就構(gòu)成了一棵最小生成樹(shù)

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;程序運(yùn)行結(jié)果見(jiàn)附錄。同時(shí)我們運(yùn)用動(dòng)態(tài)規(guī)劃法來(lái)求解同樣的問(wèn)題，問(wèn)題規(guī)模為8個(gè)城市。動(dòng)態(tài)求解過(guò)程需要使用10ms的時(shí)間，而貪心算法只需要使用1ms以內(nèi)的時(shí)間即可完成計(jì)算，我們可以理解到貪心算法的爆發(fā)力了。但是，它們的結(jié)果并不相同。動(dòng)態(tài)規(guī)劃法求解的答案為：，而貪心算法的答案為：。動(dòng)態(tài)規(guī)劃法需要走的路程為21，而貪心算法需要走的路程為25。這就是貪心算法的特點(diǎn)，雖快但不一定準(zhǔn)。貪心算法每次都是局部尋優(yōu)，很容易會(huì)陷入局部最優(yōu)解的波谷。所以，貪心算法總結(jié)起來(lái)一共有三個(gè)小缺點(diǎn)。1) 不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部

16、看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮。2) 貪心算法只能用來(lái)求某些最大或最小解的問(wèn)題。從前面的討論中，背包問(wèn)題要求得到最大價(jià)值是可行的，但是在另外一個(gè)求解最小路徑時(shí)采用貪心算法得到的結(jié)果并不是最佳。3) 貪心算法只能確定某些問(wèn)題的可行性范圍。貪心算法的優(yōu)點(diǎn)已經(jīng)提到了，就是快，通常是線性到二次式，不需要多少額外的內(nèi)存。一般二次方級(jí)的存儲(chǔ)要浪費(fèi)額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時(shí)，這些空間可以幫助算法更容易實(shí)現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用!因?yàn)樗菀拙帉?，容易調(diào)試，速度極快，并且節(jié)約空問(wèn)。幾乎可以說(shuō)，此時(shí)它是所有算法中最好的。6. 結(jié)束語(yǔ)貪心算法

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

18、楚理工學(xué)院學(xué)報(bào).2009.092 常友渠,肖貴元,曾敏.貪心算法的探討與研究J. 重慶電力高等?？茖W(xué)校學(xué)報(bào). 第13卷, 第3期3 汪瑩.論貪心算法在圖論中的應(yīng)用J.南京郵電大學(xué)學(xué)報(bào)4 董軍軍.動(dòng)態(tài)規(guī)劃算法和貪心算法的比較與分析J.軟件導(dǎo)刊. 第7卷 第2期5 林章美.貨郎擔(dān)問(wèn)題的若干解法J.6 王紅梅.算法設(shè)計(jì)與分析M.北京：清華大學(xué)出版社.2006.77 江紅,余青松.程序設(shè)計(jì)教程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 = /各個(gè)節(jié)點(diǎn)之間路徑長(zhǎng)度的二維數(shù)組 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,