《贪心算法,实验总结》由会员分享，可在线阅读，更多相关《贪心算法,实验总结（12页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划贪心算法,实验总结福建工程学院计算机与信息科学系实验报告12345实验报告题目实验四贪心算法开课实验室：数学实验室指导老师：韩逢庆时间：学院：理学院专业：信息与计算科学班级：XX级2班姓名：古月学号：一、实验目的1加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2提高学生利用课堂所学知识解决实际问题的能力；3提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目见P143:4-16,4-23.三、实验要求用分治法求解最少加油次数和最少硬币个数问题；再选择自
2、己熟悉的其它方法求解本问题；上机实现所设计的所有算法；四、实验过程设计最少加油次数实验题目一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。过程设计贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距
3、离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下：for(i=0,s=0;in)sum+;s=ai;最少硬币个数问题实验题目考虑下面的用最少硬币个数找出n分钱的问题：当使用2角5分，1角，5分和1分四种硬币面值
4、时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。过程设计贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角
5、，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。五、实验结果分析最少加油次数当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下：当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下：时间复杂性：该算法的时间复杂度为O(n)空间复杂性分析：该算法的空间复杂度为O(1)最少硬币问题当输入的找零钱数为正常的时候的运行情况如下：当输入的找零钱数为不正常的时候的运行情况如下：时间复杂性：该算法的时间复杂性为O(n)空间复杂性分析：该算法的空间复杂性
6、为O(1)六、实验体会贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题算法分析与设计实验报告完成日期：实验目的(1)了解贪心算法思想(2)掌握贪心法典型问题，如背包问题、作业调度问题等。实验内容(1)编写一个简单的程序，实现单源最短路径问题。(2)编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最
7、佳方案。(3)编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。算法思想分析所谓单源最短路径问题是指：已知图G，我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。Dijkstra算法对于图G，如果所有Wij0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。例1
8、已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，以例1
9、为例说明一下这个方法的基本思想。例1中，s=1。因为所有Wij0，故有d(v1,v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1,v2),(v1,v3)和(v1,v4)。如果某人从v1出发沿(v1,v2)到达v2，这时需要d(v1,v1)+w12=6单位的费用；如果他从v1出发沿(v1,v3)到达v3，这时需要d(v1,v1)+w13=3单位的费用；类似地，若沿(v1,v4)到达v4，这时需要d(v1,v1)+w14=1单位的费用。因为mind(v1,v1)+w12，d(v1,v1)+w13，d(v1,v1)+w14=d(v1,v1)+w14=1，可以断言，他从v1到v
10、4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1,v4)，d(v1,v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1,v4)，则必是先从v1沿(v1,v2)到达v2，或者沿(v1,v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij0)。因而推知d(v1,v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1,v2)、(v1,v3)到达v2,v3，需要的费用分别为6与3，而从v4出发沿(v4,v6)到达v6所需的费用是d
11、(v1,v4)+w46=1+10=11单位。因mind(v1,v1)+w12，d(v1,v1)+w13，d(v1,v4)+w46=d(v1,v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1,v3)，d(v1,v3)=3。这样又可以使点v3变成具P标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个值，算法终止时(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果
12、(v)=，表示图G中不含从Vs到v的路；(Vs)=0。Dijstra方法的具体步骤：初始化i=0S0=Vs，P(Vs)=0(Vs)=0对每一个vVs，令T(v)=+，(v)=+，k=s开始如果Si=V，算法终止，这时，每个vSi，d(Vs,v)=P(v)；否则转入考察每个使(Vk,vj)E且vjSi的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把(vj)修改为k。令如果，则把的标号变为P标号，令，k=ji，i=i+1，转，否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个。找零问题根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的
13、，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。问题的算法设计与实现：先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，99253，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。多机调度1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作
14、业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。分析与代码1.单源最短路径分析：基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源节点。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，用数组Di记录顶点i当前所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组D作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。代码如下：#includeusingnamespacestd;intconstVEX=5;/定义结点的个数intconstmaxpoint=15;intgraphmaxpoint=0,10,-1,30,100,-1,0,50,-1,-1,-1,-1,0,-1,10,-1,-1,20,0,60,-1,-1,-1,-1,0;/邻接矩阵intRmaxpoint=0;intBmaxpoint;intDVEX;intPVEX;/定义数组D用来存放结点特殊距离，P数组存放父亲结点/初始时，红点集中仅有源结点0voidinst
