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

汽车加油问题之贪心算法（一） 问题描述    一辆汽车加满油后可以行驶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

贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解    贪心算法的适用的问题    贪心算法适用的问题必须满足两个属性：    （１）   贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择    （２）   最优子结构：问题的整体最优解包含着它的子问题的最优解    贪心算法的基本步骤    （１）   分解：将原问题分解为若干相互独立的阶段    （２）   解决：对于每一个阶段求局部的最优解    （３）   合并：将各个阶段的解合并为原问题的解    [问题分析]    由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少    提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。

在局部找到一个最优的解却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解    加油站贪心算法设计（C）：    include    include    int add(int b[ ],int m,int n)    {  //求一个从m到n的数列的和    int sb;    for(int i=m;iN) return ERROR;  //如果某相邻的两个加油站间的距离大于N，则不能到达终点    if(add(a[i], 0, n) N )    {    b[k]=1;    m+=k;    }    return add(b[i],0,n);    }    if(a[i]!=a[j])    { //如果每相邻的两个加油站间的距离不相等且都小于N    if( add(a[i],m,k) < N && add(a[i],m,k+1) > N )    {    b[k]=1;    m+=k;    }    return add(b[i],0,n);    }    viod main( )    {    int a[ ];    scanf("%d",a);    scanf("/n");    scanf("/d",&N);    Tanxin(a[ ],0,n);    }    贪心算法正确性证明：    贪心选择性质    所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为m+N

    贪心算法时间复杂度分析    由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)原文链接: 。