汽车加油问题之贪心算法

1、汽车加油问题之贪心算法(一 )问题描述一辆汽车加满油后可以行驶 N 千米。旅途中有若干个加油站、 指出若要使沿途得加油次数最少 ,设计一个有效得算法 ,指出应在那些加油站停靠加油、给出 N,并以数组得形式给出加油站得个数及相邻距离设计一个有效得算法,指出应在那些加油站停靠加油。要求,指出若要使沿途得加油次数最少:算法执行得速度越快越好、,(二 )问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况,2,3 n:设加油次数为k,每个加油站间距离为 ;i=0,1。始点到终点得距离小于,则加油次数k=0;2。始点到终点得距离大于N,A加油站间得距离相等,即 ai a =L= ,则加油次数最

2、少k n;B 加油站间得距离相等 ,即 a a =L N, 则不可能到达终点 ;C 加油站间得距离相等 ,即 a i=a =L N,则加油次数 = /N(n =0) 或 = nN +1(n% ! 0);D加油站间得距离不相等,即 ai ！ a , 则加油次数k 通过以下算法求解。(三 )算法描述贪心算法得基本思想该题目求加油最少次数 ,即求最优解得问题 ,可分成几个步骤 ,一般来说 ,每个步骤得最优解不一定就是整个问题得最优解 ,然而对于有些问题 ,局部贪心可以得到全局得最优解、贪心算法将问题得求解过程瞧作就是一系列选择,从问题得某一个初始解出发,向给定目标推进。推进得每一阶段不就是依据某一个

3、固定得递推式,而就是在每一个阶段都瞧上去就是一个最优得决策 (在一定得标准下 ) 。不断地将问题实例归纳为更小得相似得子问题 ,并期望做出得局部最优得选择产生一个全局得最优解。贪心算法得适用得问题贪心算法适用得问题必须满足两个属性:(1) 贪心性质 :整体得最优解可通过一系列局部最优解达到 ,并且每次得选择可以依赖以前做出得选择 ,但不能依赖于以后得选择、()最优子结构 :问题得整体最优解包含着它得子问题得最优解。贪心算法得基本步骤(1) 分解 :将原问题分解为若干相互独立得阶段。()解决 :对于每一个阶段求局部得最优解。(3) 合并 :将各个阶段得解合并为原问题得解、问题分析由于汽车就是由始

4、向终点方向开得 ,我们最大得麻烦就就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题就是解决得开始。为了着手解决遇到得困难,取得最优方案。我们可以假设不到万不得已我们不加油,即除非我们油箱里得油不足以开到下一个加油站,我们才加一次油。在局部找到一个最优得解、却每加一次油我们可以瞧作就是一个新得起点,用相同得递归方法进行下去。最终将各个阶段得最优解合并为原问题得解得到我们原问题得求解。加油站贪心算法设计(C):inclu e nt add(int b ,i t ,intsb;?for( nt m;i ;i+ )n)? /求一个从 m 到 n 得数列得与 b+=b

5、 i ;? r u n b;? nt nt远距离m=0; ? a xn(inta n , inN)/a n表示加油站得个数,N 为加满油能行驶得最?int n;/ 若在加油站加油,则 b为 ,否则为 0?intif( i N)r urnERR R;/如果某相邻得两个加油站间得距离大于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);贪心算法正确性证明:贪心选择性质所谓贪心选

7、择性质就是指所求问题得整体最优解可以通过一系列局部最优得选择,即贪心选择来达到、对于一个具体得问题,要确定它就是否具有贪心性质,我们必须证明每一步所作得贪心选择最终导致问题得一个整体最优解。该题设在加满油后可行驶得N 千米这段路程上任取两个加油站、B, 且 A 距离始点比B 距离始点近 ,则若在 B 加油不能到达终点那么在 A 加油一定不能到达终点,因为 m+N +,即在 B 点加油可行驶得路程比在点加油可行驶得路程要长n-m 千米 ,所以只要终点不在B 、 C 之间且在C 得右边得话 ,根据贪心选择,为使加油次数最少就会选择距离加满油得点远一些得加油站去加油,因此 ,加油次数最少满足贪心选择性质、最优子结构性质:当一个问题大得最优解包含着它得子问题得最优解时,称该问题具有最优子结构性质。由于(b 1 ,b2 , b )就是这段路程加油次数最少得一个满足贪心选择性质得最优解,则易知若在第一个加油站加油时, =1,则 (b 2 ,b3, bn )就是从a到n这段路程上加油次数最少且这段路程上得加油站个数为( 2 ,a 3, n )得最优解 ,即每次汽车中剩下得油不能在行驶到下一个加油站时我们才在这个加油站加一次油 ,每个过程从加油开始行驶到再次加油满足贪心且每一次加油