贪心算法解汽车加油问题实验报告(1)下载_Word模板_13

is_833902

暂无简介

贪心算法解汽车加油问题实验报告(1)贪心算法解汽车加油问题实验报告(1) 计算机算法与分析设计报告班级:信管一班信管二班姓名(学号):赵立贺(060340219) 赵艳(060340114) 刘辉(060340125) 王勇(060340116)万玉琪(060340213)刘旺(060340205) 指导教师:赵晓峰姚天祥设计地点:信息系统实验室信息管理系 2008年12月13日一、实验名称: 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的: 课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节...

贪心算法解汽车加油问题实验报告(1) 计算机算法与分析

设计

领导形象设计圆作业设计 ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

报告班级:信管一班信管二班姓名(学号):赵立贺(060340219) 赵艳(060340114) 刘辉(060340125) 王勇(060340116)万玉琪(060340213)刘旺(060340205) 指导教师:赵晓峰姚天祥设计地点:信息系统实验室信息管理系 2008年12月13日一、实验名称: 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的: 课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的: (1)使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现

方法

快递客服问题件处理详细方法山木方法pdf 计算方法pdf 华与华方法下载八字理论方法下载

; 2)使学生掌握以抽象数据类型为模块的面向对象程序设计方法; ( (3)使学生提高对实际问题的分析、设计和实现能力; (4)为学生后续课程的学习及课程设计打下坚实的实践基础。三、使用的策略: 贪心算法、回溯算法等。四、实验内容: (一) 问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。 (二) 问题分析(前提行驶前车里加满油) 对于这个问题我们有以下几种情况:设加油次数为k，每个加油站间距离为a[i];i=0，1，2，3„„n 1.始点到终点的距离小于,，则加油次数k=0; 2.始点到终点的距离大于N， A 加油站间的距离相等，即,[i]=a[j]=L=N，则加油次数最少k=n; B 加油站间的距离相等，即,[i]=a[j]=L>N，则不可能到达终点; C 加油站间的距离相等，即,[i]=a[j]=L方案

气瓶现场处置方案 .pdf 气瓶现场处置方案 .doc 见习基地管理方案.doc 关于群访事件的化解方案建筑工地扬尘治理专项方案下载

, 贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策(在一定的

标准

excel标准偏差 excel标准偏差函数 exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载

下)。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。 , 贪心算法的适用的问题贪心算法适用的问题必须满足两个属性: (,) 贪心性质:整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。 (,) 最优子结构:问题的整体最优解包含着它的子问题的最优解。 , 贪心算法的基本步骤 (,) 分解:将原问题分解为若干相互独立的阶段。 (,) 解决:对于每一个阶段求局部的最优解。 (,) 合并:将各个阶段的解合并为原问题的解。 [问题分析] 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计(C): include include int add(int b[ ],int m,int n) { //求一个从m到n的数列的和 int sb; for(int i=m;iN) return ERROR; //如果某相邻的两个加油站间的距离大于N，则不能到达终点 if(add(a[i], 0, n) N ) { b[k]=1; m+=k; } return add(b[i],0,n); } if(a[i]!=a[j]) { //如果每相邻的两个加油站间的距离不相等且都小于N if( add(a[i],m,k) < N && add(a[i],m,k+1) > N ) { b[k]=1; m+=k; } return add(b[i],0,n); } viod main( ) { int a[ ]; scanf("%d",a); scanf("/n"); scanf("/d",&N); Tanxin(a[ ],0,n); } 贪心算法正确性证明: , 贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站,、,，且,距离始点比,距离始点近，则若在,加油不能到达终点那么在,加油一定不能到达终点，如图: 由图知:因为m+N /// 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 (i>sum&&(cn>=s-cs)) { if(bestsum>csum) { bestsum=csum; Console.WriteLine("{0}",bestsum); for(int j=1;j<7;j++) Console.Write("{0} ",b[j]); Console.WriteLine(); } } else if(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++); } } static void Main(string[] args) { jiayou(1); Console.Read(); } } } 回溯算法的正确性证明回溯法具有“通用的解题法”之称它的解空间包括了所有的可行解与不可行解我们通过剪枝比较最终得到的最优解，所以使用回溯算法一定是可以得到最优解，即回溯算法解该题具有正确性。回溯算法时间复杂度分析由于回溯算法得到所有的解，最坏的情况在每个加油站都加油即n次，其次加油次数为n-1次，n-2次，n-3次„„1次，0次。又由于加油地点不同根据不同的组合，我们分析得出时间复杂度为2的n次方。 3.动态规划算法解决方案 , 动态规划基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。 , 设计一个动态规划算法，通常可按以下几个步骤进行: (1) 找出最优解的性质，并刻画其结构特征。 (2) 递归地定义最优值。 (3) 以自底向上的方式计算出最优值。 (4) 根据计算最优值时得到的信息，构造一个最优解。【问题分析】: 因为每次加油时剩余油量可知，在最少加油次数情况下，剩余油量的总和Add(b[ ],m,0)与到达终点时剩余油量D之和是一定的且无论是哪种最少加油次数情况Add(b[ ],m,0)+D 是相同的。因为最后一次加油时总剩余油量为Add(b[ ],m,0); 倒数第二次加油时总剩余油量为Add(b[ ],m,0)-b[m-1]; „„ 第一次加油时总剩余油量为Add(b[ ],m,0)- Add(b[ ],m,1)=b[0]; 根据每次加满油行驶的距离最远可知最少加油次数m。动态规划算法程序(C) #include #include int Add(int a[ ], int n, int k) { int sb=0; for(int i=k;i N ) { b[++j]=N-Add(a[],n,k); //每次加油时剩余油量 Add(b[],m,0)-=b[j]; // 倒数第j次加油后剩余的总油量 n=k; if( Add(b[],m,0)==b[1] ) return (m-1)=j; } } void main() { int a[]; int N; scanf("%d,",a); scanf("/n"); scanf("%d",&N); dongtai(a[],n,N); } (四)贪心算法、动态规划与回溯算法比较首先通过以上分析及证明，我们知道两种方法都能解决使汽车加油次数最少的问题。从证明算法的正确性上回溯算法要更简单，但从时间复杂度上分析贪心算法要更优于回溯算法在计算机上更容易实现，动态规划介于两者之间，并不是本题最优的选择方案。五、实验心得: 在贪心算法中，每次做出的选择仅在当前的状态下做出的最好的选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。不是每个问题用贪心算法都可以一定得到最优解，除非该问题具有贪心选择性质(所求问题的整体最优解可以通过一系列局部最优的选择而得到)和最优子结构性质。在回溯算法中，我们学会了从多角度分析一个问题，通过解空间深度遍历来解决问题，得到最优解。在回溯算法我们想到可以通过使每次加油前汽车内剩下的油量之和最小的思路，我们又想到了动态规划算法，动态规划法也可以解决最优解问题，所以我们又分析得出了动态规划的算法程序。通过实验对贪心算法和回溯算法以及动态规划算法有了更深一步的理解，知道了它们适合解决哪类的问题，锻炼和提高了我们分析问题解决问题的能力，同时让我们更体会到团结一致协作的重要性。

本文档为【贪心算法解汽车加油问题实验报告(1)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

贪心算法解汽车加油问题实验报告(1)

热门搜索

历史搜索

贪心算法解汽车加油问题实验报告&#40;1&#41;

热门搜索

历史搜索

贪心算法解汽车加油问题实验报告(1)