汽车加油问题

汽车加油问题一、实验名称：..............................................................................................................................1二、使用的策略：..........................................................................................................................1三、实验内容：..............................................................................................................................1（一）问题描述.....................................................................................................................1（二）问题分析（前提行驶前车里加满油）.....................................................................2（三）算法描述.......................................................................................................................21.贪心算法解决方案.......................................................................................................22.递归与分治算法...........................................................................................................6一、实验名称：用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、使用的策略：贪心算法、回溯算法等。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为:1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。三、实验内容：（一）问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n1.始点到终点的距离小于Ｎ，则加油次数k=0；2.始点到终点的距离大于N，A加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；B加油站间的距离相等，即ａ[i]=a[j]=LN，则不可能到达终点；C加油站间的距离相等，即ａ[i]=a[j]=LN，则加油次数k=nL/N(N%L==0&&nL/N==0)或k=[n/([N/L]+1)]+1(N%L！=0&&n/([N/L]+1)!=0)；D加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过以下算法求解。（三）算法描述1.贪心算法解决方案贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（１）贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。（２）最优子结构：问题的整体最优解包含着它的子问题的最优解。贪心算法的基本步骤（１）分解：将原问题分解为若干相互独立的阶段。（２）解决：对于每一个阶段求局部的最优解。（３）合并：将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计（C++）：#includestdafx.h#includevector#includeiostream#includefstream//foroperationonfilesusingnamespacestd;intgreedy(vectorintx,intn){intsum=0,k=x.size();for(intj=0;jk;j++)if(x[j]n){coutNoSolution!endl;return-1;}for(inti=0,s=0;ik;i++){s+=x[i];if(sn){sum++;s=x[i];}}coutsumendl;returnsum;}int_tmain(intargc,_TCHAR*argv[]){intn,k;ints,a;vectorintx;ifstreamfin(input.txt);ofstreamfout(output.txt);while(!fin){coutCannotread!endl;return-1;}while(!fout){coutCannotwrite!endl;return-1;}finnk;for(inti=0;i=k;i++){fina;x.push_back(a);coutaendl;}s=greedy(x,n);if(s!=-1){foutsendl;}else{foutNoSolution!endl;}return0;}贪心算法正确性证明贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，如图：由图知：因为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.递归与分治算法递归与分治算法程序（C++）#includestdafx.h#includevector#includeiostream#includefstream//foroperationonfilesusingnamespacestd;intgreedy(vectorintx,intn){intoil=n;intsum=0,k=x.size();for(intj=0;jk;j++){if(x[j]n){coutNoSolution!endl;return-1;}if(oilx[j]){oil=n;sum++;}if(oil=x[j]){oil=oil-x[j];}}coutsumendl;returnsum;}int_tmain(intargc,_TCHAR*argv[]){intn,k;ints,a;vectorintx;ifstreamfin(input.txt);ofstreamfout(output.txt);while(!fin){coutCannotread!endl;return-1;}while(!fout){coutCannotwrite!endl;return-1;}finnk;for(inti=0;i=k;i++){fina;x.push_back(a);coutaendl;}s=greedy(x,n);if(s!=-1){foutsendl;}else{foutNoSolution!endl;}return0;