汽车加油问题实验报告

1、汽车加油问题实验报告一、实验名称：用贪心算法解决汽车加油次数最少问题。二、实验目的：一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指 出应在哪些加油站停靠加油才能使加油次数最少。输入数据中，第一行有2个正整数，分 别表示汽车加满油后可行驶n千米，旦旅途中有k个加油站。接下来的1行中，有k+1个 整数，表示第k个加油站与第k-l个加油站之间的距离。第。个加油站表示出发地，汽车 已加满油。第k+1个加油站表示目的地。输出为最少的加油次数，如果无法到达目的地， 则输出 “No Solution0 o实验提示：把两加油站的

2、距离放在数组中，表示从起始位置开始跑，经过k个加油站， ai表示第i l个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一 个站则不加油，否则要加油。输入数据示例7 71 2 3 4 5 1 6 6输出数据4三、使用的策略：贪心算法、回溯算法等。四、实验内容：（一）问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油 次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N,并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数 最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快 越好。(二)问题分析(前

3、提行驶前车里加满油)对于这个问题我们有以下几种情况：设 加油次数为k,每个加油站间距离为ai； i=0, 1, 2, 3?n1.始点到终点的距离小于N ,则加油次数k=0； 2.始点到终点的距离大于N,A加油站间的距离相等，即a i=aj=L=N,则加油次数最少k=n； B加油站间的 距离相等，BP a i=aj=L>N,则不可能到达终点；C加油站间的距离相等，BP a i=aj=LD加油站间的距离不相等,即ai!=aj,则加油次数k通过以下算法求解。(三)算法描述1.贪心算法解决方案？贪心 算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来 说，每个步骤的最优

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

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

6、题的求解。加油站贪心算法设计(C) ： includeinclude int add(int b , int m, int n) /求一个从 m 到 n 的数列的和 int sb; for (int i=m; iint Tanxin(int a Ln, int N) /an表示加油站的个数,N 为加满油能 行驶的最远距离 int bn; 若在ai加油站加油，则bi为1,否则为0 int m=0; if (ali>N) return ERROR; 如果某相邻的两个加油站间的距离大F N, 则不能到达终点if(add(ai, 0, n)如果这段距离小于N,则不需要加油bLi=O; retur

7、n add(bLi, 0, n) ; if (ai=a=N)如果每相邻的两个加油站间的距离都是N,则每个加油站都需要加油bi=l;return add(bEi, 0, n) ; if (ai=如果每相邻的两个加油站间的距离相等且都小于 Nif( add(ai,m, k) < N && add(ai, m, k+1) > N ) bEk=l;m+=k; return add(bi,0,n);) 如果每相邻的两个加油站间的距离不相等且都小于N if( add(aLi, m, k) < N && add(ali, m, k+1) > N )bk

8、=l;m+=k; return add(bi, 0, n); viod main( ) int a;scanf ( scanf ( scanf ( Tanxin(a , 0, n) ; )贪心算法正确性证明：？贪心选择 性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即 贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一 步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这 段路程上任取两个加油站A、B,且A距离始点比B距离始点近，则若在B加油不能到达 终点那么在A加油一定不能到达终点，如图：由图知：因为m+N当一

9、个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于(bl,b2,?bn是这段路程加油次数最少的一个满足贪心选择性质的最优解,则易 知若在第一个加油站加油时，知则(b若,b，？加)是从知2到an这段路程 上加油次数最少且这段路程上的加油站个数为(a2,a3,?an)的最优解,即每次汽 车中剩下的油不能在行裂到下一个加油站时我们才在这个加油站加一次油，每个过程从加 油开始行驶到再次加油满足贪心旦每一次加油后相当于与起点具有相同的条件，每个过程 都是相同旦独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分 析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所 以时间复杂度为0(n)。五、实验心得： 在贪心算法中，每次做出的选择仅在当前的 状态下做出的最好的选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子 问题。不是每个问题用贪心算法都可以一定得到最优解，除非该问题具有