汽車加油問題之貪心算法

1、汽車加油問題之貪心算法（一） 問題描述 一輛汽車加滿油后可以行駛N千米。旅途中有若干個加油站。指出若要使沿途的加油次數最少，設計一個有效的算法，指出應在那些加油站?？考佑?。 給出N，并以數組的形式給出加油站的個數及相鄰距離，指出若要使沿途的加油次數最少，設計一個有效的算法，指出應在那些加油站停靠加油。要求：算法執(zhí)行的速度越快越好。 （二） 問題分析（前提行駛前車里加滿油） 對于這個問題我們有以下幾種情況：設加油次數為k，每個加油站間距離為ai；i=0，1，2，3n 1.始點到終點的距離小于，則加油次數k=0； 2.始點到終點的距離大于N， A 加油站間的距離相等，即i=aj=L=N，則加油次數

2、最少k=n； B 加油站間的距離相等，即i=aj=LN，則不可能到達終點； C 加油站間的距離相等，即i=aj=LN，則加油次數k=n/N(n%N=0)或k=n/N+1(n%N！=0)； D 加油站間的距離不相等，即i！=aj，則加油次數k通過以下算法求解。 （三）算法描述貪心算法的基本思想 該題目求加油最少次數，即求最優(yōu)解的問題，可分成幾個步驟，一般來說，每個步驟的最優(yōu)解不一定是整個問題的最優(yōu)解，然而對于有些問題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問題的求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目標推進。推進的每一階段不是依據某一個固定的遞推式，而是在每一個階段都看上去

3、是一個最優(yōu)的決策（在一定的標準下）。不斷地將問題實例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產生一個全局得最優(yōu)解。貪心算法的適用的問題 貪心算法適用的問題必須滿足兩個屬性： （） 貪心性質：整體的最優(yōu)解可通過一系列局部最優(yōu)解達到，并且每次的選擇可以依賴以前做出的選擇，但不能依賴于以后的選擇。 （） 最優(yōu)子結構：問題的整體最優(yōu)解包含著它的子問題的最優(yōu)解。貪心算法的基本步驟 （） 分解：將原問題分解為若干相互獨立的階段。 （） 解決：對于每一個階段求局部的最優(yōu)解。 （） 合并：將各個階段的解合并為原問題的解。問題分析 由于汽車是由始向終點方向開的,我們最大的麻煩就是不知道在哪個加油站加

4、油可以使我們既可以到達終點又可以使我們加油次數最少。 提出問題是解決的開始.為了著手解決遇到的困難,取得最優(yōu)方案。我們可以假設不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個加油站，我們才加一次油。在局部找到一個最優(yōu)的解。卻每加一次油我們可以看作是一個新的起點，用相同的遞歸方法進行下去。最終將各個階段的最優(yōu)解合并為原問題的解得到我們原問題的求解。加油站貪心算法設計（C）： include include int add(int b ,int m,int n) /求一個從m到n的數列的和 int sb; for(int i=m;iN) return ERROR; /如果某相鄰的兩個加

5、油站間的距離大于N，則不能到達終點 if(add(ai, 0, n)N) /如果這段距離小于N，則不需要加油 bi=0; return add(bi,0,n); if(ai=aj&ai=N) /如果每相鄰的兩個加油站間的距離都是N，則每個加油站都需要加油 bi=1; return add(bi,0,n); if(ai=aj&aiN) /如果每相鄰的兩個加油站間的距離相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); if(ai!=aj) /如果每相鄰的兩個加油站間的距離不相等且都小于N if( add(ai,m,k) N )

6、bk=1; m+=k; return add(bi,0,n); viod main( ) int a ; scanf(%d,a); scanf(/n); scanf(/d,&N); Tanxin(a ,0,n); 貪心算法正確性證明：貪心選擇性質 所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。對于一個具體的問題，要確定它是否具有貪心性質，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優(yōu)解。該題設在加滿油后可行駛的N千米這段路程上任取兩個加油站、，且距離始點比距離始點近，則若在加油不能到達終點那么在加油一定不能到達終點，因為m+Nn+N，即在B

7、點加油可行駛的路程比在A點加油可行駛的路程要長n-m千米，所以只要終點不在B、C之間且在C的右邊的話，根據貪心選擇，為使加油次數最少就會選擇距離加滿油得點遠一些的加油站去加油，因此，加油次數最少滿足貪心選擇性質。最優(yōu)子結構性質： 當一個問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。由于（b1,b2,bn）是這段路程加油次數最少的一個滿足貪心選擇性質的最優(yōu)解，則易知若在第一個加油站加油時，b1=1,則（b2,b3,bn）是從 a2到an這段路程上加油次數最少且這段路程上的加油站個數為（a2,a3,an）的最優(yōu)解,即每次汽車中剩下的油不能在行駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每