汽車加油問題之貪心算法

1、汽車加油問題之貪心算法(一 )問題描述一輛汽車加滿油后可以行駛 n 千米。旅途中有若干個(gè)加油站、 指出若要使沿途得加油次數(shù)最少 ,設(shè)計(jì)一個(gè)有效得算法 ,指出應(yīng)在那些加油站?？考佑?、給出 n,并以數(shù)組得形式給出加油站得個(gè)數(shù)及相鄰距離設(shè)計(jì)一個(gè)有效得算法,指出應(yīng)在那些加油站?？考佑汀Ｒ?指出若要使沿途得加油次數(shù)最少:算法執(zhí)行得速度越快越好、,(二 )問題分析(前提行駛前車?yán)锛訚M油)對(duì)于這個(gè)問題我們有以下幾種情況,2,3 n:設(shè)加油次數(shù)為k,每個(gè)加油站間距離為 ;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)解得問題 ,可分成幾個(gè)步驟 ,一般來說 ,每個(gè)步驟得最優(yōu)解不一定就是整個(gè)問題得最優(yōu)解 ,然而對(duì)于有些問題 ,局部貪心可以得到全局得最優(yōu)解、貪心算法將問題得求解過程瞧作就是一系列選擇,從問題得某一個(gè)初始解出發(fā),向給定目標(biāo)推進(jìn)。推進(jìn)得每一階段不就是依據(jù)某一個(gè)

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

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

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

6、 ai n) ?/如果每相鄰得兩個(gè)加油站間得距離相等且都小于 nif( ?(i ,m,k) k=1; ?m+= ;& (a,m,k+1)n )return add(b i ,0,n); ? ( !=a j )如果每相鄰得兩個(gè)加油站間得距離不相等且都小于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á)到、對(duì)于一個(gè)具體得問題,要確定它就是否具有貪心性質(zhì),我們必須證明每一步所作得貪心選擇最終導(dǎo)致問題得一個(gè)整體最優(yōu)解。該題設(shè)在加滿油后可行駛得n 千米這段路程上任取兩個(gè)加油站、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ù)最少就會(huì)選擇距離加滿油得點(diǎn)遠(yuǎn)一些得加油站去加油,因此 ,加油次數(shù)最少滿足貪心選擇性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì):當(dāng)一個(gè)問題大得最優(yōu)解包含著它得子問題得最優(yōu)解時(shí),稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于(b 1 ,b2 , b )就是這段路程加油次數(shù)最少得一個(gè)滿足貪心選擇性質(zhì)得最優(yōu)解,則易知若在第一個(gè)加油站加油時(shí), =1,則 (b 2 ,b3, bn )就是從a到n這段路程上加油次數(shù)最少且這段路程上得加油站個(gè)數(shù)為( 2 ,a 3, n )得最優(yōu)解 ,即每次汽車中剩下得油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油 ,每個(gè)過程從加油開始行駛到再次加油滿足貪心且每一次加油