蛮力0-1背包问题c语言实现,蛮力动规贪心回溯法的01背包和TSP问题

news/2024/11/29 9:55:08/

《蛮力动规贪心回溯法的01背包和TSP问题》由会员分享,可在线阅读,更多相关《蛮力动规贪心回溯法的01背包和TSP问题(8页珍藏版)》请在人人文库网上搜索。

1、华北科技学院计算机学院综合性实验实 验 报 告 课程名称 算法分析与设计 实验学期 2014 至 2015 学年 第 二 学期学生所在系部 计算机学院 年级 12级 专业班级 软件B122班 学生姓名 周辉 学号 4 任课教师 王德志 实验成绩 计算机学院制算法分析与设计课程综合性实验报告开课实验室: 计算机基础实验室 2015年 05 月 28 日实验题目回溯法应用编程一、 实验目的:(1)掌握回溯算法求解图问题和组合问题的方法和步骤。(2)理解回溯算法的基本思想。(3)提高学生的编程能力和分析问题、解决问题的能力。二、 实验设备及环境:微型计算机、Visual C+/JAVA三、 实验内容。

2、及要求:实验内容:(1)利用回溯算法,求解TSP问题。A.TSP问题伪代码:输入条件:城市个数n,邻接矩阵a。x为当前解,NoEdge=-1表示无穷大。x1,y1为城市的坐标,cc为当前解,bestc为最优解。BackTrack(t)回溯函数。(1)当t!=n时,BackTrack(1),表示从第一个城市出发。如果上一个节点和它此后的节点有边,并且费用不高于现有的最优费用(bestc=NoEdge表示第一次) ,交换xt与xi的值,cc=cc+axt-1xt,递归调用BackTrack(i+1)。(2)当t=n时,bestxi=xi,bestc=cc+axn-1xn+xn1.关键算法:void。

3、 BackTrack(int t) /t从2开始if(t=n) /到达第n个节点 if(axn-1xn!=NoEdge & (axn1!=NoEdge) & (cc+axn-1xn+axn1C,此时进入右子树,转第三步。(3)此时判断右子树的最大价值是否大于当前最优值bestp。若右子树的最大价值大于当前最优值。则递归backtrack(i+1)。当in的时候,则从backtrack(i+1)返回。(4)cw=cw-wi,cp=cp-vi,此时的cw n)/到达叶子节点bestp= cp ;return ;/返回上一节点if(cw + wi bestp)/符合条件搜索右子树k+ ;backtr。

4、ack(i+1);四、实验结果及分析1、实验运行过程及分析2、运行结果A、01背包问题当背包重量为200时当物品为4个的时候:当物品为10个的时候:TSP问题:当城市为4的时候:当城市为10的时候:01背包问题个算法的比较:TSP各算法的比较:3、心得体会通过这次的算法分析与设计的综合实验,我从中获益许多。我了解到不同算法时间性能上的差异。蛮力法是最简单但是时间复杂度又是最高的算法。贪心法只考虑现阶段利益最大的目标,所以求出来的解不一定是最优解而是近似解。回溯法则用到了递归的方法。对于n值如果比较小,蛮力法增长的趋势较小,但随着n的增大趋势越来越大。贪心法01背包问题则有三种贪心策略:1是按照。

5、重量最小的物品最先放。2按照价值最大的物品先放入背包。3按照单位价值重量比大的先放。综合考虑的话,第3种最接近最优解。在本次实验中,遇到了一些编程的问题,主要是在伪代码转化成代码的时候比较困难,在调试的过程中,遇到最多的问题是数组下标越界的问题。有的算法是从0开始计算,有的算法是从1开始计算,所以出现了混乱。其次是算法的逻辑性存在一定问题,得不到预期想要的结果。经本人不解努力最终完成4种算法的设计与比较。我深刻的体会到算法的重要性,在以后的学习或工作中,我会不断的自我完善,努力提高自我修养。教 师 评 价评定项目ABCD评定项目ABCD算法正确界面美观,布局合理程序结构合理操作熟练语法、语义正确解析完整实验结果正确文字流畅报告规范题解正确其他:评价教师签名:2015年 5 月 28 日。


http://www.ppmy.cn/news/526753.html

相关文章

大学物理:补充-能量

文章目录 知识点非保守力保守力动能势能机械能能量守恒 Some tips不能单独考虑某个质点的能量可以单独考虑某个质点的能量 杂项 知识点 非保守力 做功与路径有关的力如摩擦力等 保守力 做功与路径无关,只与位矢的起始点和终止点有关的力(只和位置有关…

我的人生感悟

我的人生感悟 年幼无知,只随父母脚步, 叛逆失落,迷茫整个高中; 收拾心情,寻答案于大学, 人间冷暖,重拾难为自信; 偏见自封,误把消极当理性, 固执狭隘&…

logo设计如何增加附加价值

如今,是品牌观念盛行的时代,logo以及标志设计对企业公司起着重要的作用。logo不仅是企业品牌传达,更是对企业文化以及企业理念的传达,因此,企业logo设计很重要。优秀的公司Logo设计可提高销售力,扩展品牌效…

学习坐标【javascript】拼图小游戏 -java教程

发一下牢骚和主题无关: 兴致才是学习的力动源泉。始终欢喜游戏类的编程,因为得觉好玩。。。 周末这2天预备写个拼图的小游戏,只为学习面向对象,虽然对面向对象里的很多西东还不太熟悉。 昨天(星期六)开始写…

云计算、系统-什么是云计算?-by小雨

最近研讨云计算、系统-,稍微总结一下,以后继续补充: 说到云盘算,大部份人都云里雾里。有人以为它是一台巨无霸电脑,供给了超级盘算能力;也有人将其比作物流系统,把云盘算带来的利便比作一个个包…

系统牛逼[置顶] 使用RAMP理解内在动机 Understanding Intrinsic Motivation with RAMP

最近应用开辟的进程中出现了一个小题问,顺便记录一下原因和方法--系统牛逼 应用RAMP解理在内念头 原文地址 关于Gamification中的外在励奖和在内念头我们探讨了很多了。这类探讨是总像在探讨好的和坏的式方。我对于之前这样探讨常常觉得忸怩!其实最好的是…

大学计算机科学系口号,各大学学院口号

电气学院:赛场竞技,唯我电气。以下是小编为大家准备的口号,希望大家能够喜欢! 1、【软件学院】:软件软件,创意无限; 2、【外国语学院】:青春飞扬,外院最强; 3、【软件学院】大喊&…

一般性的计算机安全事故受理,一般性的计算机安全事故和计算机违法案件可由_____受理...

需求需求的最大者本期者中和顾货两预计客订是指,般由受过程主生制定中划(产计。 计算机安计算机违件 全事个(是一。的是关于错误芽胞。学生做实验时,来近年,按照进行必须规程操作,相应全帽、安的手等防套、备佩戴和绝护设眼镜缘鞋…