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

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