贪心算法解汽车加油问题实验报告.doc

计算机算法与分析设计报告班级：信管一班 信管二班姓名（学号）：赵立贺(060340219) 赵艳（060340114） 刘辉（060340125）王勇（060340116）万玉琪（060340213）刘旺（060340205）指导教师：赵晓峰 姚天祥设计地点：信息系统实验室信息管理系2008年12月13日一、实验名称： 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。 二、实验目的： 课程设计是计算机算法与设计课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的：（1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；（3）使学生提高对实际问题的分析、设计和实现能力；（4）为学生后续课程的学习及课程设计打下坚实的实践基础。 三、使用的策略： 贪心算法、回溯算法等。四、实验内容：（一） 问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。（二） 问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为ai；i=0，1，2，3n1.始点到终点的距离小于，则加油次数k=0；2.始点到终点的距离大于N， A 加油站间的距离相等，即i=aj=L=N，则加油次数最少k=n；B 加油站间的距离相等，即i=aj=LN，则不可能到达终点；C 加油站间的距离相等，即i=aj=LN，则加油次数k=n/N(n%N=0)或k=n/N+1(n%N！=0)；D 加油站间的距离不相等，即i！=aj，则加油次数k通过以下算法求解。（三）算法描述1.贪心算法解决方案l 贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。l 贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（） 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。（） 最优子结构：问题的整体最优解包含着它的子问题的最优解。l 贪心算法的基本步骤（） 分解：将原问题分解为若干相互独立的阶段。（） 解决：对于每一个阶段求局部的最优解。（） 合并：将各个阶段的解合并为原问题的解。问题分析由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计（C）：includeincludeint add(int b ,int m,int n) /求一个从m到n的数列的和 int sb; for(int i=m;iN) return ERROR; /如果某相邻的两个加油站间的距离大于N，则不能到达终点 if(add(ai, 0, n)N) /如果这段距离小于N，则不需要加油 bi=0; return add(bi,0,n); if(ai=aj&ai=N) /如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油 bi=1; return add(bi,0,n); if(ai=aj&aiN) /如果每相邻的两个加油站间的距离相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); if(ai!=aj) /如果每相邻的两个加油站间的距离不相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); viod main( ) int a ; scanf(%d,a); scanf(/n); scanf(/d,&N); Tanxin(a ,0,n);贪心算法正确性证明：l 贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站、，且距离始点比距离始点近，则若在加油不能到达终点那么在加油一定不能到达终点，如图：由图知：因为m+Nn+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。l 最优子结构性质：当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于（b1,b2,bn）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b1=1,则（b2,b3,bn）是从 a2到an这段路程上加油次数最少且这段路程上的加油站个数为（a2,a3,an）的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。2.回溯算法解决方案l 回溯算法的基本思想确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。l 回溯算法的解题基本步骤（） 首先要为问题定义一个解空间，这个节点包含问题的解（可能是最优解）。在汽车加油问题中，我们可以定义一个包含从始点到终点的所有加油站的解的空间。（） 组织解空间以便被顺利的搜索，同时搜索方法又能够避免移动到不可能产生解的子空间。（） 定义了解空间的组织方法，这个空间即可按深度优先地方法从开始节点开始搜索。在搜索过程中适用剪枝去掉不是最优的解。问题分析在该问题中，解空间用一棵树来表示，最优解，即数的深度值最小的情况。开始起点为a0，开始节点既是一个活节点又是一个扩展节点，从扩展节点可以通到一个新节点，如果能从当前的扩展节点移动到一个新节点，如果这个节点在该节点的上一层没有出现，那么这个新节点就将成为一个活节点和新的扩展节点，继续向前行驶，如果这个节点在上一层出现过，那么这个节点就是一个死结点，需要结束此过程，回到它的上一个节点继续寻找直到终点为止。或者我们可以这样想这个问题，我们想要加油的次数最少，因为路程一定，要使加油次数最少，即在整个过程中每次加油时汽车里剩下的油之和最少。问题分析的两种思路都可以用回溯算法来解决。1010101020101020101010202010101020202010102010202020加油站回溯算法设计（C#）： using System; Namespace jiayouzhan /*/ / Class1 的摘要说明。 / Class Class1 /*/ / 应用程序的主入口点。 / / static double sum=7;/加油站总数 static double csum=0;/当前加油总数 static double bestsum=6;/最优解 static double s=100;/总路程 static double cs=0;/当前走过的路程 static double n=30;/满油能走的路程 static double cn=30;/当前能走的路程 static double a=0,20,10,10,10,20,10,20;/加油站分布 static double b=0,0,0,0,0,0,0,0; static double p=0;/记录临时CN Private static void jiayou (int i) if (isum&(cn=s-cs) if(bestsumcsum) bestsum=csum; Console.WriteLine(0,bestsum); for(int j=1;j7;j+) Console.Write(0 ,bj); Console.WriteLine(); else if(i=ai+1) p=cn; cn=n; cs+=ai; csum+=1; bi=1; jiayou(i+); cn=p-ai+1; csum-=1; bi=0; jiayou(i+); static void Main(string args) jiayou(1); Console.Read(); 回溯算法的正确性证明回溯法具有“通用的解题法”之称它的解空间包括了所有的可行解与不可行解我们通过剪枝比较最终得到的最优解，所以使用回溯算法一定是可以得到最优解，即回溯算法解该题具有正确性。回溯算法时间复杂度分析由于回溯算法得到所有的解，最坏的情况在每个加油站都加油即n次，其次加油次数为n-1次，n-2次，n-3次1次，0次。又由于加油地点不同根据不同的组合，我们分析得出时间复杂度为2的n次方。3.动态规划算法解决方案l 动态规划基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。l 设计一个动态规划算法，通常可按以下几个步骤进行：（1） 找出最优解的性质，并刻画其结构特征。（2） 递归地定义最优值。（3） 以自底向上的方式计算出最优值。（4） 根据计算最优值时得到的信息，构造一个最优解。【问题分析】：因为每次加油时剩余油量可知，在最少加油次数情况下，剩余油量的总和Add(b ,m,0)与到达终点时剩余油量D之和是一定的且无论是哪种最少加油次数情况Add(b ,m,0)+D 是相同的。因为最后一次加油时总剩余油量为Add(b ,m,0)；倒数第二次加油时总剩余油量为Add(b ,m,0)-bm-1； 第一次加油时总剩余油量为Add(b ,m,0)- Add(b ,m,1)=b0；根据每次加满油行驶的距离最远可知最少加油次数m。动态规划算法程序（C）#include#includeint Add(int a , int n, int k) int sb=0; for(int i=k;in;i+) sb+=ai; return sb;int dongtai(int a,int n,int N) int j=0; int *b=new int m; /数组bi表示第i次加油时剩余油量，总加油次数为 m int D /到达终点时剩余油量 if(Add(a,n,0)-Add(a,k,0) N ) b+j=N-Add(a,n,k); /每次加油时剩余油量 Add(b,m,0)-=bj; / 倒数第j次加油后剩余的总油量 n=k; if( Add(b,m,0)=b1 ) return (m-1)=j; void main() int a; int N; scanf(%d,a); scanf(/n); scanf(%d,&N); dongtai(a,n,N); （四）贪心算法、动态规划与回溯算法比较首先通过以上分析及证明，我们知道两种方法都能解决使汽车加油次数最少的问题。从证明算法的正确性上回溯算法要更简单，但从时间复杂度上分析贪心算法要更优于回溯算法在计算机上更容易实现，动态规划介于两者之间，并不是本题最优的选择方案。五、实验心得： 在贪心算法中，每次做出的选择仅在当前的状态下做出的最好的选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。不是