汽車(chē)加油問(wèn)題之貪心算法

1、汽車(chē)加油問(wèn)題之貪心算法（一）問(wèn)題描述一輛汽車(chē)加滿(mǎn)油后可以行駛 N千米。旅途中有若干個(gè)加油站。指出若要使沿途的加油次 數(shù)最少，設(shè)計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站?？考佑?。給出N，并以數(shù)組的形式給出加油站的個(gè)數(shù)及相鄰距離，指出若要使沿途的加油次數(shù)最 少，設(shè)計(jì)一個(gè)有效的算法， 指出應(yīng)在那些加油站?？考佑?。要求：算法執(zhí)行的速度越快越好。（二）問(wèn)題分析（前提行駛前車(chē)?yán)锛訚M(mǎn)油）k，每個(gè)加油站間距離為ai; i=0, 1,對(duì)于這個(gè)問(wèn)題我們有以下幾種情況：設(shè)加油次數(shù)為2, 3n1始點(diǎn)到終點(diǎn)的距離小于N,則加油次數(shù)k=0 ；i=aj=L<N ，則加油次數(shù) k= n/N（n%N=O）或i ! =aj，則

2、加油次數(shù)k通過(guò)以下算法求解。2始點(diǎn)到終點(diǎn)的距離大于N ,A力啪站間的距離相等，即aB力啪站間的距離相等，即aC力啪站間的距離相等，即ak=n/N+1（n%N ! =0）;D力口油站間的距離不相等，即a（三）算法描述i=aj=L=N，則加油次數(shù)最少k=n;i=aj=L>N，則不可能到達(dá)終點(diǎn)；貪心算法的基本思想該題目求加油最少次數(shù)，即求最優(yōu)解的問(wèn)題，可分成幾個(gè)步驟，一般來(lái)說(shuō)，每個(gè)步驟的 最優(yōu)解不一定是整個(gè)問(wèn)題的最優(yōu)解，然而對(duì)于有些問(wèn)題，局部貪心可以得到全局的最優(yōu)解。 貪心算法將問(wèn)題的求解過(guò)程看作是一系列選擇，從問(wèn)題的某一個(gè)初始解出發(fā)，向給定目標(biāo)推進(jìn)。推進(jìn)的每一階段不是依據(jù)某一個(gè)固定的遞推式，

3、而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。不斷地將問(wèn)題實(shí)例歸納為更小的相似的子問(wèn)題，并期望做出的 局部最優(yōu)的選擇產(chǎn)生一個(gè)全局得最優(yōu)解。貪心算法的適用的問(wèn)題貪心算法適用的問(wèn)題必須滿(mǎn)足兩個(gè)屬性:(1) 貪心性質(zhì)：整體的最優(yōu)解可通過(guò)一系列局部最優(yōu)解達(dá)到，并且每次的選擇可以 依賴(lài)以前做出的選擇，但不能依賴(lài)于以后的選擇。(2) 最優(yōu)子結(jié)構(gòu)：?jiǎn)栴}的整體最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解。貪心算法的基本步驟(1)分解：將原問(wèn)題分解為若干相互獨(dú)立的階段。(2)解決：對(duì)于每一個(gè)階段求局部的最優(yōu)解。(3)合并：將各個(gè)階段的解合并為原問(wèn)題的解。問(wèn)題分析由于汽車(chē)是由始向終點(diǎn)方向開(kāi)的，我們最大的麻煩就是不

4、知道在哪個(gè)加油站加油可以使我 們既可以到達(dá)終點(diǎn)又可以使我們加油次數(shù)最少。提出問(wèn)題是解決的開(kāi)始為了著手解決遇到的困難，取得最優(yōu)方案。我們可以假設(shè)不到萬(wàn)不 得已我們不加油，即除非我們油箱里的油不足以開(kāi)到下一個(gè)加油站，我們才加一次油。在局部找到一個(gè)最優(yōu)的解。卻每加一次油我們可以看作是一個(gè)新的起點(diǎn)，用相同的遞歸方法進(jìn)行下去。最終將各個(gè)階段的最優(yōu)解合并為原問(wèn)題的解得到我們?cè)瓎?wèn)題的求解。加油站貪心算法設(shè)計(jì)(C):in clude<math.h>in clude<studio.h>int add(i nt b ,i nt m,i nt n) 求一個(gè)從 m到n的數(shù)列的和int sb;f

5、or(i nt i=m;i <n ;i+) sb+=bi;return sb;int Tanxin(int an, int N)an表示加油站的個(gè)數(shù)，N為加滿(mǎn)油能行駛的最遠(yuǎn)距離int bn;/若在ai加油站加油，則 bi為1,否則為0int m=0;if(ai>N) return ERROR;/如果某相鄰的兩個(gè)加油站間的距離大于N，則不能到達(dá)終點(diǎn)if(add(ai, 0, n )<N) /如果這段距離小于N，則不需要加油bi=0;return add(bi,0, n);if(ai=aj&&ai=N) /如果每相鄰的兩個(gè)加油站間的距離都是N，則每個(gè)加油站都需要加

6、油bi=1;return add(bi,O, n);if(ai=aj&&ai<N) /如果每相鄰的兩個(gè)加油站間的距離相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+1) > N )bk=1;m+=k;return add(bi,0, n);if(ai!=aj) /如果每相鄰的兩個(gè)加油站間的距離不相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+1) > N )bk=1;m+=k;return add(bi,0, n);viod mai n()int a

7、;scan f("%d",a);scan f("/n");scan f("/d",&N);Tanxin( a ,0, n);貪心算法正確性證明：貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心 選擇來(lái)達(dá)到。對(duì)于一個(gè)具體的問(wèn)題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。該題設(shè)在加滿(mǎn)油后可行駛的N千米這段路程上任取兩個(gè)加油站A、B,且A距離始點(diǎn)比E距離始點(diǎn)近，則若在E加油不能到達(dá)終點(diǎn)那么在A加油一定不能到達(dá)終點(diǎn)，因?yàn)閙+N<n+N，即在B點(diǎn)

8、加油可行駛的路程比在A點(diǎn)加油可行駛的路程要長(zhǎng) n-m千米，所以只要終點(diǎn)不在B、C之間且在C的右邊的話(huà)，根據(jù)貪心選擇，為使加油次數(shù)最少就會(huì)選擇距離加滿(mǎn)油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿(mǎn)足貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì):當(dāng)一個(gè)問(wèn)題大的最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由于(b1,b2,b)是這段路程加油次數(shù)最少的一個(gè)滿(mǎn)足貪心選擇性質(zhì)的最優(yōu)解，則 易知若在第一個(gè)加油站加油時(shí)，b1=1,則(b2,b3,bn是從a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個(gè)數(shù)為(a2,a3,an的最優(yōu)解，即每次汽車(chē)中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過(guò)程從加油開(kāi)始行駛到