您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 资本运营 > 3汽车加油问题实验报告
#includeiostream.hintadd_station(intn,intk,inta[],intA[])//到达目的站时所需的最少加油站次数{inti,s=0;for(i=0;i=k;i++){if(a[i+1]n){coutNoSolutionendl;return0;break;}else{s+=a[i];if(s+a[i+1]n)A[i]=0;else{A[i]=1;s=0;}}}return1;}intmain(){inti,k,n,t,s=0;cout请输入汽车一次加油可行驶的最大距离:;cinn;cout请输入旅途中的加油站数目:;cink;int*a=newint[k+1+1];int*A=newint[k+1+1];a[0]=0;cout请输入各个站点的距离(以空格分隔)共k+1段:/n;for(i=1;i=k+1;i++)cina[i];for(i=0;ik+1;i++)A[i]=0;cout输出最少的加油次数:/n;t=add_station(n,k,a,A);if(t==0)return0;else{for(i=0;ik+1;i++)s+=A[i];coutsendl;}}一、实验名称:用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的:课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学,要达到以下目的:(1)使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法;(2)使学生掌握以抽象数据类型为模块的面向对象程序设计方法;(3)使学生提高对实际问题的分析、设计和实现能力;(4)为学生后续课程的学习及课程设计打下坚实的实践基础。三、使用的策略:贪心算法、回溯算法等。四、实验内容:(一)问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。(二)问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n1.始点到终点的距离小于N,则加油次数k=0;2.始点到终点的距离大于N,A加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n;B加油站间的距离相等,即a[i]=a[j]=LN,则不可能到达终点;C加油站间的距离相等,即a[i]=a[j]=LN,则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N!=0);D加油站间的距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案贪心算法的基本思想该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。贪心算法的适用的问题贪心算法适用的问题必须满足两个属性:(1)贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出的选择,但不能依赖于以后的选择。(2)最优子结构:问题的整体最优解包含着它的子问题的最优解。贪心算法的基本步骤(1)分解:将原问题分解为若干相互独立的阶段。(2)解决:对于每一个阶段求局部的最优解。(3)合并:将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油,即除非我们油箱里的油不足以开到下一个加油站,我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点,用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计(C):includemath.hincludestudio.hintadd(intb[],intm,intn){//求一个从m到n的数列的和intsb;for(inti=m;in;i++)sb+=b[i];returnsb;}intTanxin(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)N){//如果这段距离小于N,则不需要加油b[i]=0;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]==N){//如果每相邻的两个加油站间的距离都是N,则每个加油站都需要加油b[i]=1;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]N){//如果每相邻的两个加油站间的距离相等且都小于Nif(add(a[i],m,k)N&&add(a[i],m,k+1)N){b[k]=1;m+=k;}returnadd(b[i],0,n);}if(a[i]!=a[j]){//如果每相邻的两个加油站间的距离不相等且都小于Nif(add(a[i],m,k)N&&add(a[i],m,k+1)N){b[k]=1;m+=k;}returnadd(b[i],0,n);}viodmain(){inta[];scanf(%d,a);scanf(/n);scanf(/d,&N);Tanxin(a[],0,n);}贪心算法正确性证明:贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。对于一个具体的问题,要确定它是否具有贪心性质,我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站A、B,且A距离始点比B距离始点近,则若在B加油不能到达终点那么在A加油一定不能到达终点,如图:由图知:因为m+Nn+N,即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米,所以只要终点不在B、C之间且在C的右边的话,根据贪心选择,为使加油次数最少就会选择距离加满油得点远一些的加油站去加油,因此,加油次数最少满足贪心选择性质。最优子结构性质:当一个问题大的最优解包含着它的子问题的最优解时,称该问题具有最优子结构性质。由于(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)。2.回溯算法解决方案回溯算法的基本思想确定了解空间的组织结构后,回溯法就是从开始节点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。换句话说,这个节点,这个结点不再是一个活结点。此时,应往回(回溯)移动至最近一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索,直到找到所要求的解或解空间中以无活结点为止。回溯算法的解题基本步骤(1)首先要为问题定义一个解空间,这个节点包含问题的解(可能是最优解)。在汽车加油问题中,我们可以定义一个包含从始点到终点的所有加油站的解的空间。(2)组织解空间以便被顺利的搜索,同时搜索方法又能够避免移动到不可能产生解的子空间。(3)定义了解空间的组织方法,这个空间即可按深度优先地方法从开始节点开始搜索。在搜索过程中适用剪枝去掉不是最优的解。[问题分析]在该问题中,解空间用一棵树来表示,最优解,即数的深度值最小的情况。开始起点为a[0],开始节点既是一个活节点又是一个扩展节点,从扩展节点可以通到一个新节点,如果能从当前的扩展节点移动到一个新节点,如果这个节点在该节点的上一层没有出现,那么这个新节点就将成为一个活节点和新的扩展节点,继续向前行驶,如果这个节点在上一层出现过,那么这个节点就是一个死结点,需要结束此过程,回到它的上一个节点继续寻找直到终点为止。或者我们可以这样想这个问题,我们想要加油的次数最少,因为路程一定,要使加油次数最少,即在整个过程中每次加油时汽车里剩下的油之和最少。问题分析的两种思路都可以用回溯算法来解决。加油站回溯算法设计(C#):usingSystem;Namespacejiayouzhan{/**////summary///Class1的摘要说明。////summaryClassClass1{/**////summary///应用程序的主入口点。////summary///staticdoublesum=7;//加油站总数staticdoublecsum=0;//当前加油总数staticdoublebestsum=6;//最优解staticdoubles=100;//总路程staticdoublecs=0;//当前走过的路程10101010201010201010102020101010·20202010102010202020staticdoublen=30;//满油能走的路程staticdoublecn=30;//当前能走的路程staticdouble[]a={0,20,10,10,10,20,10,20};//加油站分布staticdouble[]b={0,0,0,0,0,0,0,0};staticdoublep=0;//记录临时CNPrivatestaticvoidjiayou(inti){if(isum&&(cn=s-cs)){if(bestsumcsum){bestsum=csum;Console.WriteLine({0},bestsum);for(intj=1;j7;j++)Console.Write({0},b[j]);Console.WriteLine();}}elseif(i=sum&&(cn=a[i+1])){p=cn;cn=n;cs+=a[i];csum+=1;b[i]=1;jiayou(i++);cn=p-a[i+1];csum-=1;b[i]=0;jiayou(i++);}}staticvoidMain(string[]args){jiayou(1);Console.Read();}}}回溯算法的正确性证明回溯法具有“通用的解题法”之称它的解空间包括了所有的可行解与不可行解我们通过剪枝比较最终得到的最优解,所以使用回溯算法一定是可以得到最优解,即回溯算法解该题具有正确性。回溯算法时间复杂
本文标题:3汽车加油问题实验报告
链接地址:https://www.777doc.com/doc-5051966 .html