汽車加油問題之貪心算法

1、汽車加油問題之貪心算法(一 )問題描述一輛汽車加滿油后可以行駛 n 千米。旅途中有若干個加油站、 指出若要使沿途得加油次數(shù)最少 ,設(shè)計(jì)一個有效得算法 ,指出應(yīng)在那些加油站?？考佑汀⒔o出 n,并以數(shù)組得形式給出加油站得個數(shù)及相鄰距離設(shè)計(jì)一個有效得算法,指出應(yīng)在那些加油站?？考佑汀Ｒ?指出若要使沿途得加油次數(shù)最少:算法執(zhí)行得速度越快越好、,(二 )問題分析(前提行駛前車?yán)锛訚M油)對于這個問題我們有以下幾種情況,2,3 n:設(shè)加油次數(shù)為k,每個加油站間距離為 ;i=0,1。始點(diǎn)到終點(diǎn)得距離小于,則加油次數(shù)k=0;2。始點(diǎn)到終點(diǎn)得距離大于n,a加油站間得距離相等,即 ai a =l= ,則加油次數(shù)最

2、少k n;b 加油站間得距離相等 ,即 a a =l n, 則不可能到達(dá)終點(diǎn) ;c 加油站間得距離相等 ,即 a i=a =l n,則加油次數(shù) = /n(n =0) 或 = nn +1(n% ! 0);d加油站間得距離不相等,即 ai ！ a , 則加油次數(shù)k 通過以下算法求解。(三 )算法描述貪心算法得基本思想該題目求加油最少次數(shù) ,即求最優(yōu)解得問題 ,可分成幾個步驟 ,一般來說 ,每個步驟得最優(yōu)解不一定就是整個問題得最優(yōu)解 ,然而對于有些問題 ,局部貪心可以得到全局得最優(yōu)解、貪心算法將問題得求解過程瞧作就是一系列選擇,從問題得某一個初始解出發(fā),向給定目標(biāo)推進(jìn)。推進(jìn)得每一階段不就是依據(jù)某一個

3、固定得遞推式,而就是在每一個階段都瞧上去就是一個最優(yōu)得決策 (在一定得標(biāo)準(zhǔn)下 ) 。不斷地將問題實(shí)例歸納為更小得相似得子問題 ,并期望做出得局部最優(yōu)得選擇產(chǎn)生一個全局得最優(yōu)解。貪心算法得適用得問題貪心算法適用得問題必須滿足兩個屬性:(1) 貪心性質(zhì) :整體得最優(yōu)解可通過一系列局部最優(yōu)解達(dá)到 ,并且每次得選擇可以依賴以前做出得選擇 ,但不能依賴于以后得選擇、()最優(yōu)子結(jié)構(gòu) :問題得整體最優(yōu)解包含著它得子問題得最優(yōu)解。貪心算法得基本步驟(1) 分解 :將原問題分解為若干相互獨(dú)立得階段。()解決 :對于每一個階段求局部得最優(yōu)解。(3) 合并 :將各個階段得解合并為原問題得解、問題分析由于汽車就是由始

4、向終點(diǎn)方向開得 ,我們最大得麻煩就就是不知道在哪個加油站加油可以使我們既可以到達(dá)終點(diǎn)又可以使我們加油次數(shù)最少。提出問題就是解決得開始。為了著手解決遇到得困難,取得最優(yōu)方案。我們可以假設(shè)不到萬不得已我們不加油,即除非我們油箱里得油不足以開到下一個加油站,我們才加一次油。在局部找到一個最優(yōu)得解、卻每加一次油我們可以瞧作就是一個新得起點(diǎn),用相同得遞歸方法進(jìn)行下去。最終將各個階段得最優(yōu)解合并為原問題得解得到我們原問題得求解。加油站貪心算法設(shè)計(jì)(c):inclu e nt add(int b ,i t ,intsb;?for( nt m;i ;i+ )n)? /求一個從 m 到 n 得數(shù)列得與 b+=b

5、 i ;? r u n b;? nt nt遠(yuǎn)距離m=0; ? a xn(inta n , inn)/a n表示加油站得個數(shù),n 為加滿油能行駛得最?int n;/ 若在加油站加油,則 b為 ,否則為 0?intif( i n)r urnerr r;/如果某相鄰得兩個加油站間得距離大于n,則不能到達(dá)終點(diǎn) f( d(a i, 0, ) ) / 如果這段距離小于 n, 則不需要加油b i=0;re uradd(b ,0,n);?離都就是 (a a j n, 則每個加油站都需要加油?i =n) ? bi=1; /如果每相鄰得兩個加油站間得距return dd(b i ,0, );if(a i =a &

6、 ai n) ?/如果每相鄰得兩個加油站間得距離相等且都小于 nif( ?(i ,m,k) k=1; ?m+= ;& (a,m,k+1)n )return add(b i ,0,n); ? ( !=a j )如果每相鄰得兩個加油站間得距離不相等且都小于n? f( d (a i ,m,k) n & ad ( i ,m,k+1) n) ?b k=1; =k; ? eturn add(bi ,0, );? ?vi m n( ) ? int ;? san (% ,a); scanf(/n ” ); c nf( ” d”,n); ?tanxin(a ,0,n);貪心算法正確性證明:貪心選擇性質(zhì)所謂貪心選

7、擇性質(zhì)就是指所求問題得整體最優(yōu)解可以通過一系列局部最優(yōu)得選擇,即貪心選擇來達(dá)到、對于一個具體得問題,要確定它就是否具有貪心性質(zhì),我們必須證明每一步所作得貪心選擇最終導(dǎo)致問題得一個整體最優(yōu)解。該題設(shè)在加滿油后可行駛得n 千米這段路程上任取兩個加油站、b, 且 a 距離始點(diǎn)比b 距離始點(diǎn)近 ,則若在 b 加油不能到達(dá)終點(diǎn)那么在 a 加油一定不能到達(dá)終點(diǎn),因?yàn)?m+n +,即在 b 點(diǎn)加油可行駛得路程比在點(diǎn)加油可行駛得路程要長n-m 千米 ,所以只要終點(diǎn)不在b 、 c 之間且在c 得右邊得話 ,根據(jù)貪心選擇,為使加油次數(shù)最少就會選擇距離加滿油得點(diǎn)遠(yuǎn)一些得加油站去加油,因此 ,加油次數(shù)最少滿足貪心選擇性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì):當(dāng)一個問題大得最優(yōu)解包含著它得子問題得最優(yōu)解時,稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于(b 1 ,b2 , b )就是這段路程加油次數(shù)最少得一個滿足貪心選擇性質(zhì)得最優(yōu)解,則易知若在第一個加油站加油時, =1,則 (b 2 ,b3, bn )就是從a到n這段路程上加油次數(shù)最少且這段路程上得加油站個數(shù)為( 2 ,a 3, n )得最優(yōu)解 ,即每次汽車中剩下得油不能在行駛到下一個加油站時我們才在這個加油站加一次油 ,每個過程從加油開始行駛到再次加油滿足貪心且每一次加油