蛮力动规贪心回溯法的01背包和TSP问题

华北科技学院计算机学院综合性实验实验报告课程名称算法分析与设计实验学期2014至2015学年第二学期学生所在系部计算机学院年级12级专业班级软件B122班学生姓名周辉学号201207044224任课教师王德志实验成绩计算机学院制华北科技学院计算机学院综合性实验报告第1页《算法分析与设计》课程综合性实验报告开课实验室：计算机基础实验室2015年05月28日实验题目回溯法应用编程一、实验目的：（1）掌握回溯算法求解图问题和组合问题的方法和步骤。（2）理解回溯算法的基本思想。（3）提高学生的编程能力和分析问题、解决问题的能力。二、实验设备及环境：微型计算机、VisualC++/JAVA三、实验内容及要求：实验内容：（1）利用回溯算法，求解TSP问题。A.TSP问题伪代码：输入条件：城市个数n，邻接矩阵a[][]。x[]为当前解，NoEdge=-1表示无穷大。x1[],y1[]为城市的坐标，cc为当前解，bestc为最优解。BackTrack（t）回溯函数。（1）当t!=n时，BackTrack(1),表示从第一个城市出发。如果上一个节点和它此后的节点有边,并且费用不高于现有的最优费用(bestc==NoEdge表示第一次)，交换x[t]与x[i]的值，cc=cc+a[x[t-1]][x[t]],递归调用BackTrack（i+1）。（2）当t==n时，bestx[i]=x[i],bestc=cc+a[x[n-1]][x[n]]+x[n][1].关键算法：voidBackTrack(intt){//t从2开始if(t==n){//到达第n个节点if(a[x[n-1]][x[n]]!=NoEdge&&(a[x[n]][1]!=NoEdge)&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]bestc||bestc==NoEdge)){for(inti=1;i=n;i++){bestx[i]=x[i];华北科技学院计算机学院综合性实验报告第2页}bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];//当前最优解}}else{for(inti=t;i=n;i++){//如果上一个节点和它此后的节点有边,并且费用不高于现有的最优费用(bestc==NoEdge表示第一次)if(a[x[t-1]][x[i]]!=NoEdge&&(cc+a[x[t-1]][x[i]]bestc||bestc==NoEdge)){swap(x[t],x[i]);//交换顺序值cc+=a[x[t-1]][x[t]];BackTrack(t+1);//递归调用cc-=a[x[t-1]][x[t]];swap(x[t],x[i]);}k++;}}}（2）利用回溯算法，求解0/1背包问题。B.01背包问题伪代码：输入条件：物品数n，背包重量C，物品重量w[i],价值v[i].（1）从n个物品中选取装入背包的物品，物品i的重量为w[i]，价值为v[i]。物品的最高单位重量价值比为p[i]=v[i]/w[i];使用冒泡排序法将p[i]排序。(2)i=0,判断第i个物品的重量是否小于背包重量。如果小于背包重量，将put[i]的值设为1，表示物品可放入背包。物品的总重量为cw=cw+w[i],总价值为cp=cp+v[i],背包C的容量为C-w[i],随后i++，继续将下一个物品装入背包（递归backtrack(i+1)）。直到第i个物品的重量装入背包时的重量cwC,此时进入右子树，转第三步。（3）此时判断右子树的最大价值是否大于当前最优值bestp。若右子树的最大价华北科技学院计算机学院综合性实验报告第3页值大于当前最优值。则递归backtrack(i+1)。当in的时候，则从backtrack(i+1)返回。（4）cw=cw-w[i],cp=cp-v[i],此时的cwC,随后回溯到上一个物品的右子树，随后转第3步。输出条件：被装入物品的编号o[i],当前最优价值bestp，循环次数k。关键代码：//回溯函数publicvoidbacktrack(inti){if(in){//到达叶子节点bestp=cp;return;//返回上一节点}if(cw+w[i]=C){//判断物品w[i]是否能装入背包中cw+=w[i];cp+=v[i];put[i]=1;//物品被装入到背包中。k++;backtrack(i+1);//递归调用cw-=w[i];//返回上一个物品的重量cp-=v[i];//返回上一个物品的价值}if(bound(i+1)bestp){//符合条件搜索右子树k++;backtrack(i+1);}}华北科技学院计算机学院综合性实验报告第4页四、实验结果及分析1、实验运行过程及分析2、运行结果A、01背包问题当背包重量为200时当物品为4个的时候：当物品为10个的时候：TSP问题：当城市为4的时候：当城市为10的时候：华北科技学院计算机学院综合性实验报告第5页01背包问题个算法的比较：TSP各算法的比较：华北科技学院计算机学院综合性实验报告第6页3、心得体会通过这次的算法分析与设计的综合实验，我从中获益许多。我了解到不同算法时间性能上的差异。蛮力法是最简单但是时间复杂度又是最高的算法。贪心法只考虑现阶段利益最大的目标，所以求出来的解不一定是最优解而是近似解。回溯法则用到了递归的方法。对于n值如果比较小，蛮力法增长的趋势较小，但随着n的增大趋势越来越大。贪心法01背包问题则有三种贪心策略：1是按照重量最小的物品最先放。2按照价值最大的物品先放入背包。3按照单位价值重量比大的先放。综合考虑的话，第3种最接近最优解。在本次实验中，遇到了一些编程的问题，主要是在伪代码转化成代码的时候比较困难，在调试的过程中，遇到最多的问题是数组下标越界的问题。有的算法是从0开始计算，有的算法是从1开始计算，所以出现了混乱。其次是算法的逻辑性存在一定问题，得不到预期想要的结果。经本人不解努力最终完成4种算法的设计与比较。我深刻的体会到算法的重要性，在以后的学习或工作中，我会不断的自我完善，努力提高自我修养。教师评价评定项目ABCD评定项目ABCD算法正确界面美观，布局合理程序结构合理操作熟练语法、语义正确解析完整实验结果正确文字流畅报告规范题解正确华北科技学院计算机学院综合性实验报告第7页其他：评价教师签名：2015年5月28日