贪心算法解汽车加油问题实验报告

《贪心算法解汽车加油问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、实验名称：用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的：课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的：（1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；（3）使学生提高对实际问题的分析、设计和实现能力；（4）为学生后续课程的学习及课程设计打下坚实的实践基础。三、使用的策略：贪心算法、回溯算法等。四、实验内容：（一）问

2、题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n1.始点到终点的距离小于Ｎ，则加油次数k=0；2.始点到终点的距离大于N，A加油站间的距

3、离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；B加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；C加油站间的距离相等，即ａ[i]=a[j]=L

4、可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。l贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（１）贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。（２）最优子结构：问题的整体最优解包含着它的子问

5、题的最优解。l贪心算法的基本步骤（１）分解：将原问题分解为若干相互独立的阶段。（２）解决：对于每一个阶段求局部的最优解。（３）合并：将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同

6、的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计（C）：//肖萌的算法加油站问题贪心算法#includeusingnamespacestd;intmain(){inti,j,n,k,l[10],c=0,m=0;boolA[10];cout<<"请输入加满油后可行驶的距离（km）：";cin>>n;cout<<"请输入途中所经的加油站个数：";cin>>k;cout<<"请输入每相邻两个加油站之间的距离："<

7、+)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(ints=0;s<=k;s++)if(A[s]==true){c++;cout<

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