欢迎来到天天文库
浏览记录
ID:21885901
大小:59.50 KB
页数:5页
时间:2018-10-25
《汽车加油问题实验报告》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、一、实验名称:用贪心算法解决汽车加油次数最少问题。二、实验目的:一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加汕站停靠加油才能使加汕次数最少。输入数据中,第一行有2个正整数,分别表示汽车加满油后可行驶n千米,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加汕站之间的距离。第0个加汕站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出为最少的加油次数,如果无法到达目的地,则输出“NoSolution”
2、。实验提75:把两加油站的距离放在数组中,a[l..k]表示从起始位置开始跑,经过k个加油站,a[i]表示第i一1个加油站到第i个加油站的距离。汽车在运行的过程屮如果能跑到下一个站则不加油,否则要加油。输入数据示例7712345166输出数据4三、使用的策略:贪心算法、冋溯算法等。实验内容:(一)问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。给出N,并以数组的形式给出加汕站的个数及相邻距离,指出若要使沿途的加汕次数最少,设计一个有效的算法,指
3、出应在那些加汕站停靠加汕。要求:算法执行的速度越快越好。(二)问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3n1.始点到终点的距离小于N,则加油次数k=0:2.始点到终点的距离大于N,A加油站间的距离相等,即a[i>a[j>L=N,则加油次数最少k=n;B加油站间的距离相等,即a[i】=a[j>L>N,则不可能到达终点;C加油站间的距离相等,即a[i>a[j】=L4、离不相等,即a[i]!=a[jb则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案•贪心算法的基本思想该题目求加汕最少次数,即求最优解的问题,可分成儿个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得5、最优解。•贪心算法的适用的问题贪心算法适用的问题必须满足两个属性:(1)贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出的选择,但不能依赖于以后的选择。(2)最优子结构:问题的整体最优解包含着它的子问题的最优解。•贪心算法的基本步骤解决并分解合:将原问题分解为若干相互独立的阶段。:对于每一个阶段求局部的最优解。:将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手6、解决遇到的困难,取得最优方案。我们可以假设不到万不得己我们不加汕,即除非我们汕箱里的汕不足以开到下一个加汕站,我们才加一次汕。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点,用相同的递归方法进行下去。S终将各个阶段的S优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计(C):includeincludeintadd(intb[],intm,intn){//求一个从m到n的数列的和intsb;for(inti=m;i7、anxin(inta[n],intN)//a[n]表示加汕站的个数,N为加满汕能行驶的最远距离{intb[n];//若在a[i】加油站加油,则b[i]为1,否则为0intm=0;if(a[i]>N)returnERROR;//如果某相邻的两个加油站间的距离大于N,则不能到达终点if(add(a[i],0,n)8、turnadd(b[i],O,n);}if(a[i]==a[j]&&a[i]N){b[k]=
4、离不相等,即a[i]!=a[jb则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案•贪心算法的基本思想该题目求加汕最少次数,即求最优解的问题,可分成儿个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得
5、最优解。•贪心算法的适用的问题贪心算法适用的问题必须满足两个属性:(1)贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出的选择,但不能依赖于以后的选择。(2)最优子结构:问题的整体最优解包含着它的子问题的最优解。•贪心算法的基本步骤解决并分解合:将原问题分解为若干相互独立的阶段。:对于每一个阶段求局部的最优解。:将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手
6、解决遇到的困难,取得最优方案。我们可以假设不到万不得己我们不加汕,即除非我们汕箱里的汕不足以开到下一个加汕站,我们才加一次汕。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点,用相同的递归方法进行下去。S终将各个阶段的S优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计(C):includeincludeintadd(intb[],intm,intn){//求一个从m到n的数列的和intsb;for(inti=m;i7、anxin(inta[n],intN)//a[n]表示加汕站的个数,N为加满汕能行驶的最远距离{intb[n];//若在a[i】加油站加油,则b[i]为1,否则为0intm=0;if(a[i]>N)returnERROR;//如果某相邻的两个加油站间的距离大于N,则不能到达终点if(add(a[i],0,n)8、turnadd(b[i],O,n);}if(a[i]==a[j]&&a[i]N){b[k]=
7、anxin(inta[n],intN)//a[n]表示加汕站的个数,N为加满汕能行驶的最远距离{intb[n];//若在a[i】加油站加油,则b[i]为1,否则为0intm=0;if(a[i]>N)returnERROR;//如果某相邻的两个加油站间的距离大于N,则不能到达终点if(add(a[i],0,n)8、turnadd(b[i],O,n);}if(a[i]==a[j]&&a[i]N){b[k]=
8、turnadd(b[i],O,n);}if(a[i]==a[j]&&a[i]N){b[k]=
此文档下载收益归作者所有