汽车加油问题

《汽车加油问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、汽车加汕问题一、实验名称：1二、使用的策略：1三、实验内容：1（―）问题描述1（二）问题分析（前提行驶前车里加满油）2（三）算法描述21.贪心算法解决方案22.递归与分治算法6一、实验名称：用贪心算法、冋溯算法、动态规划等解决汽车加油次数最少问题。二、使用的策略：贪心算法、回溯算法等。贪心算法（又称贪婪算法）是指，在对问题求解吋，总是做岀在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所宥问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或

2、者是整体最优解的近似解。回溯算法也叫试探法，它足一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退冋来，换一条路再试。用冋溯算法解决问题的一般步骤为：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。三、实验内容：（一）问题描述一辆汽车加满油后可以行驶NT米。旅途屮有若干个加油站。指出若要使沿途的加油次数最少

3、，设计一个宥效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指岀应在那些加油站停靠加油。要求：算法执行的速度越快越好。0123(二)问题分析(前提行驶前车里加满油)对于这个问题我们有以下儿种情况：没加油次数为k,每个加油站间距离为a[i]；i=0，1，2，3n1.始点到终点的距离小于N，则加汕次数k=0；2.始点到终点的距离大于N,A加油站间的距离相等，即a[i]=a[j]=L=N，则加油次数最少k=n;B加汕站间的距离相等，即a[

4、i]=a[j]=L〉N,则不可能到达终点；C加油站间的距离相等,即a[i]=a[j]=L

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

6、(1)分解：将原问题分解为若干相互独立的阶段。(2)解决：对于每一个阶段求局部的最优解。(3)合并：将各个阶段的解合并为原问题的解。［问题分析］由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加汕次数最少。提出问题是解决的开始.为了着手解决遇到的困难，取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的

7、最优解合井为原问题的解得到我们原问题的求解。加油站贪心算法设计(C++):include"stdafx.h"#include’’vector"#include’’iostreamn#include//foroperationonfilesusingnamespacestd;intgreedy(vectorx，intn){intsum=0,k=x.size();for(intj=O;jn)cout«"NoSolution!"«endl;return-1;}for(i

8、nti=O，s=O;in){sum++;s=x[i】；}}cout«sum«endl;returnsum;_tmain(intargc,_TCHAR*argv[])intn,k;ints,a;vector