汽车加油问题之贪心算法.docx

汽车加油问题之贪心算法
汽车加油问题之贪心算法
(一 ) 描述
一 汽 加 油后可以行 N 千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少 , 一个有效的算法 ,指出 在那些加油站停靠加油。
出 N,并以数 的形式 出加油站的个数及相 距离
一个有效的算法 ,指出 在那些加油站停靠加油。要求

,指出若要使沿途的加油次数最少
:算法 行的速度越快越好。

,
(二 )

分析

(前提行 前 里加 油

)
于 个 我 有以下几种情况 : 加油次数 k,每个加油站 距离
a[i];i=0,1,2,3 ⋯⋯n
1、始点到 点的距离小于Ｎ , 加油次数 k=0;
2、始点到 点的距离大于 N,
A
加油站 的距离相等
,即ａ [i]=a[j]=L=N,
加油次数最少 k=n;
B
加油站 的距离相等
,即ａ [i]=a[j]=L>N,
不可能到达 点 ;
C
加油站 的距离相等
,即ａ [i]=a[j]=L<N,
加油次数 k=n/N(n%N==0)
或
k=[n/N]+1(n%N ！ =0);
D
加油站 的距离不相等
,即ａ [i] ！ =a[j], 加油次数 k 通 以下算法求解。
(三 )算法描述
心算法的基本思想
目求加油最少次数 ,即求最 解的 ,可分成几个步 ,一般来 ,每个步 的最 解不一定就是整个 的最 解 ,然而 于有些 ,局部 心可以得到全局的最 解。 心算
法将 的求解 程瞧作就是一系列 ,从 的某一个初始解出 ,向 定目 推 。推
的每一 段不就是依据某一个固定的 推式 ,而就是在每一个 段都瞧上去就是一个最
的决策 (在一定的 准下 ) 。不断地将 例 更小的相似的子 ,并期望做出的局部最 的 生一个全局得最 解。
心算法的适用的
心算法适用的 必 足两个属性 :
(１) 心性 : 整体的最 解可通 一系列局部最 解达到 ,并且每次的 可以依 以前做出的 ,但不能依 于以后的 。
汽车加油问题之贪心算法
(２) 最优子结构 :问题的整体最优解包含着它的子问题的最优解。
贪心算法的基本步骤
(１) 分解 :将原问题分解为若干相互独立的阶段。
(２) 解决 :对于每一个阶段求局部的最优解。
(３) 合并 :将各个阶段的解合并为原问题的解。
[ 问题分析 ]
由于汽车就是由始向终点方向开的 ,我们最大的麻烦就就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。
提出问题就是解决的开始、为了着手解决遇到的困难 ,取得最优方案。我们可以假设不到
万不得已我们不加油 ,即除非我们油箱里的油不足以开到下一个加油站 ,我们才加一次油。在