一、实验名称：

    用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。   

二、实验目的： 

       课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的：

（1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；

（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；

（3）使学生提高对实际问题的分析、设计和实现能力；

（4）为学生后续课程的学习及课程设计打下坚实的实践基础。

 三、使用的策略：

      贪心算法、回溯算法等。

四、实验内容：

（一）问题描述

一辆汽车加满油后可以行驶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通过以下算法求解。

（三）算法描述

1.贪心算法解决方案

l  贪心算法的基本思想

该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。

l  贪心算法的适用的问题

贪心算法适用的问题必须满足两个属性：

（１）   贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。

（２）   最优子结构：问题的整体最优解包含着它的子问题的最优解。

l  贪心算法的基本步骤

（１）   分解：将原问题分解为若干相互独立的阶段。

（２）   解决：对于每一个阶段求局部的最优解。

（３）   合并：将各个阶段的解合并为原问题的解。

[问题分析]

由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。

提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。

加油站贪心算法设计（C）：

//肖萌的算法  加油站问题贪心算法

#include<iostream>

using namespace std;

int main()

{

       int i,j,n,k,l[10],c=0,m=0;

       bool A[10];

       cout<<"请输入加满油后可行驶的距离（km）： ";

       cin>>n;

       cout<<"请输入途中所经的加油站个数： ";

       cin>>k;

       cout<<"请输入每相邻两个加油站之间的距离： "<<endl;

       for(i=0;i<=k;i++)

              cin>>l[i];

       for(i=0;i<=k;i++)

              A[i]=false;

       for(j=0;j<=k;j++)

       {

              m+=l[j];

              if(m+l[j+1]>=7)

              {

                     A[j+1]=true;

                     m=0;

              }

       }

    cout<<"在第   ";

       for(int s=0;s<=k;s++)

           if(A[s]==true)

              {

                     c++;

                     cout<<s<<"   ";

              }

           cout<<"个加油站加油了! ^_^"<<endl;

              cout<<"最少加油次数为： "<<c<<endl;

              return 0;

}贪心算法正确性证明：

l  贪心选择性质

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

 

由图知：因为m+N<n+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。

l  最优子结构性质：

当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于（b[1],b[2],……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1,则（b[2],b[3],……b[n]）是从 a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2],a[3],……a[n]）的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。

贪心算法时间复杂度分析

由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。

}

 （四）贪心算法、动态规划与回溯算法比较

首先通过以上分析及证明，我们知道两种方法都能解决使汽车加油次数最少的问题。从证明算法的正确性上回溯算法要更简单，但从时间复杂度上分析贪心算法要更优于回溯算法在计算机上更容易实现，动态规划介于两者之间，并不是本题最优的选择方案。

五、实验心得：

   在贪心算法中，每次做出的选择仅在当前的状态下做出的最好的选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。不是每个问题用贪心算法都可以一定得到最优解，除非该问题具有贪心选择性质（所求问题的整体最优解可以通过一系列局部最优的选择而得到）和最优子结构性质。

在回溯算法中，我们学会了从多角度分析一个问题，通过解空间深度遍历来解决问题，得到最优解。在回溯算法我们想到可以通过使每次加油前汽车内剩下的油量之和最小的思路，我们又想到了动态规划算法，动态规划法也可以解决最优解问题，所以我们又分析得出了动态规划的算法程序。

通过实验对贪心算法和回溯算法以及动态规划算法有了更深一步的理解，知道了它们适合解决哪类的问题，锻炼和提高了我们分析问题解决问题的能力，同时让我们更体会到团结一致协作的重要性。      

第二篇：算法分析_贪心算法解汽车加油问题_实验报告

综合性、设计性实验报告

姓名     唐艳      学号  200908001124

专业计算机科学与技术班级2009级  班

实验课程名称      算法设计与分析     

指导教师及职称     吕兰兰 讲师      

开课学期 20## 至 2012  学年  上  学期

上课时间     2011年 10 月 18 日    

湖南科技学院教务处编印

一、实验设计方案

二、实验报告