貪心算法結(jié)課論文

貪心算法求解汽車加油問題1引言隨著科學的發(fā)展，人們生活中面臨的大數(shù)據(jù)量越來越多。生活的快節(jié)奏要求人們對這些龐大的數(shù)據(jù)進行簡單快速的處理，在這種實際需求的背景下，計算機算法設(shè)計得到了飛速發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型越來越多被應用到計算機算法學中。當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時，可用動態(tài)規(guī)劃法來解決。但是貪心算法通常會給出一個更簡單、直觀和高效的解法。貪心算法通過一系列的選擇來得到一個問題的解。盡管貪心算法對許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最短路徑問題、最小生成樹問題，以及哈夫曼編碼問題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)解，而且所給出的算法一般比動態(tài)規(guī)劃算法更加簡單、直觀和高效[1]。2貪心算法2.1貪心算法概述貪心算法又稱貪婪算法，是指在求解問題時，總是做出在當前看來是最好的選擇，也就是說，貪心算法并不要求從整體上最優(yōu)考慮，它所作的僅是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。貪心算法并不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法可以簡單描述為：對一組數(shù)據(jù)進行排序，找出最小值，進行處理，再找出最小值，再處理。也就是說貪心算法是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪婪算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)。用貪婪法設(shè)計算法的特點是一步一步地進行，常以當前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間，它采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題,通過每一步貪心選擇,可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的。貪婪算法是一種改進了的分級處理方法。其核心是根據(jù)題意選取一種量度標準。然后將這多個輸入排成這種量度標準所要求的順序，按這種順序一次輸入一個量。如果這個輸入和當前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優(yōu)解的分級處理方法稱為貪婪算法。對于一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數(shù)量度標準作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標準是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標準并不是一件容易的事，但對某問題能選擇出最優(yōu)量度標準后，用貪婪算法求解則特別有效。最優(yōu)解可以通過一系列局部最優(yōu)的選擇即貪婪選擇來達到,根據(jù)當前狀態(tài)做出在當前看來是最好的選擇，即局部最優(yōu)解選擇，然后再去解做出這個選擇后產(chǎn)生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規(guī)模更小的子問題，最終可得到問題的一個整體最優(yōu)解。2.2貪心算法的基本要素貪心算法通過一系列的選擇得到問題的解，它所做的每一個選擇都是當前狀態(tài)下局部最好選擇，即貪心選擇。但是對于一個問題，怎么知道是否可以用貪心算法解決此問題，以及能否得到問題的最優(yōu)解呢？這個問題難以給予肯定的回答。但是，我們從許多可以用貪心算法求解的問題中看到這類問題一般具有兩個重要的性質(zhì)：貪心選擇性和最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇得到。因此，對于一個具體問題，它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終可以得到整體最優(yōu)的結(jié)果，即通過貪心選擇后，原問題被簡化為規(guī)模更小的類似子問題。而最優(yōu)子結(jié)構(gòu)性質(zhì)，主要是指原問題的最優(yōu)解包含子問題的最優(yōu)解。2.3貪心算法的特性通過對比能夠用貪心算法解決的諸多問題，我們不難總結(jié)出貪心算法能夠解決的問題的一系列特性：（1）存在一個最優(yōu)的方法來解決的問題。為了構(gòu)造問題的解決方案,有一個候選的對象是一個集合：比如不同面值的硬幣。（2）隨著算法的進行，將產(chǎn)生兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但是被丟棄的候選對象。（3）算法中將產(chǎn)生一個用來檢查一個候選對象是否提供了問題的解答的函數(shù)。當然，該函數(shù)并不考慮此時的解決方法是否最優(yōu)。（4）算中法另一個函數(shù)檢查是否一個候選對象的集合是可行的,也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣,此時不考慮解決方法的最優(yōu)性。（5）選擇函數(shù)指出哪一個剩余的候選對象可能構(gòu)成問題的解。（6）最后返回解的值。為了解決原問題,需要尋找一個構(gòu)成解的候選對象集合,它可以優(yōu)化目標函數(shù),使得貪婪算法一步一步的進行。起初,算法選出的候選對象的集合為空，接下來的每一步中,根據(jù)選擇函數(shù),算法從剩余候選對象中選出最有希望構(gòu)成解的對象，然后加入到一個集合中，如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮。每一次都擴充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優(yōu)的。2.4貪心算法的基本思路用局部解構(gòu)造全局解，即從問題的某一個初始解逐步逼近給定的目標，以盡可能快地求得更好的解。當某個算法中的某一步不能再繼續(xù)前進時，算法停止。貪心算法思想的本質(zhì)就是分治，或者說：分治是貪心的基礎(chǔ)。每次都形成局部最優(yōu)解，換一種方法說，就是每次都處理出一個最好的方案。利用貪心策略解題，需要解決兩個問題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標準，以得到問題的最優(yōu)/較優(yōu)解。具體的實現(xiàn)過程如下：（1）建立數(shù)學模型來描述問題。（2）應用同一規(guī)則F，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題。（3）對每一子問題求解，得到子問題的局部最優(yōu)解。（4）把子問題的解局部最優(yōu)解合成原來解問題的一個解。實現(xiàn)的算法的過程如下：從問題的某一初始解出發(fā)；while（能朝給定總目標前進一步）do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。3經(jīng)典例子分析3.10-1背包問題0-1背包問題：給定n種物品和一個背包。物品i的重量和價值分別是wi和vi，背包的容量為C。要求正確的選取裝入背包的物品，使得裝入背包的物品價值之和最大。例如：C=30物品：ABC重量：281212價值：302020根據(jù)貪心選擇策略，首先選擇A，然后再比較B、C，無法再裝入?？梢钥闯?，最終的結(jié)果是將A裝入背包中。但是，如不按貪心算法求解，實際是裝入B和C最好。因此，對于0-1背包問題，貪心選擇不能達到結(jié)果最優(yōu)，這是因為在這種情況下，無法保證最終將背包裝滿，部分閑置的空間使得每公斤背包的價值下降了。因此，在考慮此類的背包問題時，應該比較選擇該物品呵不選擇該物品所導致的最終方案，然后再做出最好的選擇，此時可用動態(tài)規(guī)劃算法求解。顯然，對于以上例子，如果不要求選擇物品的全部裝入背包，允許我們只選擇部分裝入背包，此問題及轉(zhuǎn)化為普通背包問題。此時即可用貪心選擇算法求解。一般步驟為：首先選擇將每公斤價值最大的物品裝入背包，如果背包未滿，再選擇每公斤價值次大的物品裝入，以此類推。3.2加油站問題（習題4-16）（一）問題描述一輛汽車加滿油后可行駛N公里。旅途中有若干個加油點。設(shè)計一個有效算法，指出應在哪些加油站加油，使得旅途中加油次數(shù)最少，并證明算法能產(chǎn)生一個最優(yōu)解。（二）問題分析設(shè)汽車在起點已經(jīng)為加滿油的狀態(tài)，記加油的次數(shù)為k，起點與終點距離為S，加油站的個數(shù)為n，加油站i與加油站i+1之間的距離存放在一個數(shù)組a[i]中（i=0、1、2、3…..n），其中a[0]表示汽車位于起始點,a[n+1]表示汽車到達終點。對于原問題，主要有以下幾種情況：A當S<N或S=N時，無需加油，即k=0；B當S>N時：（1）各加油站之間的距離相等且等于N，即a[i]=N，需要加油次數(shù)至少為k=n；（2）各加油站之間的距離相等且大于N，即a[i]>N，則不可能到達終點。（3）各加油站之間的距離相等且小于N，即a[i]<N，則加油次數(shù)k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；（4）各加油站之間的距離不相等，即a[i]!=a[j]，則加油次數(shù)k可以通過以下算法得到。具體算法描述如下：intadd(intb[],intm,intn){//求一個從m到n的數(shù)列的和intsb;for(inti=m;i<n;i++)sb+=b[i];returnsb;}intTanxin(inta[n],intN)//a[n]表示加油站的個數(shù)，N為加滿油能行駛的最遠距離{intb[n];//若在a[i]加油站加油，則b[i]為1，否則為0intm=0;if(a[i]>N)returnERROR;//如果某相鄰的兩個加油站間的距離大于N，則不能到達終點if(add(a[i],0,n)<N){//如果這段距離小于N，則不需要加油b[i]=0;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]==N){//如果每相鄰的兩個加油站間的距離都是N，則每個加油站都需要加油b[i]=1;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]<N){//如果每相鄰的兩個加油站間的距離相等且都小于Nif(add(a[i],m,k)<N&&add(a[i],m,k+1)>N){b[k]=1;m+=k;}returnadd(b[i],0,n);}if(a[i]!=a[j]){//如果每相鄰的兩個加油站間的距離不相等且都小于Nif(add(a[i],m,k)<N&&add(a[i],m,k+1)>N){b[k]=1;m+=k;}returnadd(b[i],0,n);}viodmain(){inta[];scanf("%d",a);scanf("/n");scanf("/d",&N);Tanxin(a[],0,n);}由于貪心算法適用的問題必須滿足連個屬性：貪心性質(zhì)和最優(yōu)子結(jié)構(gòu)，因此，對于該汽車加油的問題是否適合用貪心算法，要先判定其是否具有這兩個性質(zhì)?！褙澬倪x擇性質(zhì)對于一個具體的問題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優(yōu)解。該題設(shè)在加滿油后可行駛的N千米這段路程上任取兩個加油站Ａ、Ｂ，且Ａ距離始點比Ｂ距離始點近，則若在Ｂ加油不能到達終點那么在Ａ加油一定不能到達終點，因為m+N<n+N，即在B點加油可行駛的路程比在A點加油可行駛的路程要長n-m千米，所以只要終點不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會選擇距離加滿油得點遠一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)?！褡顑?yōu)子結(jié)構(gòu)由于（b[1]，b[2]，……b[n]）是這段路程加油次數(shù)最少的一個滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個加油站加油時，b[1]=1，則（b[2]，b[3]，……b[n]）是從a[2]到a[n]這段路程上加油次數(shù)最少且這段路程上的加油站個數(shù)為（a[2]，a[3]，……a[n]）的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當于與起點具有相同的條件，每個過程都是相同且獨立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)?？偨Y(jié)與心得貪心算法是常見的算法之一，是一種重要的算法涉及策略，有簡單、直接、高效的特點。按照貪心算法設(shè)計出來的許多算法均能得到結(jié)果的最優(yōu)，雖然它不能保證對每一個問題最后的解都是最優(yōu)的。貪心算法所作出的選擇依賴于以往所做過的選擇，絕不依賴將來的選擇，這使得算法在編碼和執(zhí)行過程中都有一定的速度優(yōu)勢。對于一個問題的最優(yōu)解只能用窮舉法得到時，用貪心算法是尋找問題最優(yōu)解的較好算法。對一個問題可以同時用幾種方法