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

华北科技学院计算机学院综合性实验 实 验 报 告 课程名称 算法分析与设计4 至 2015 学年 第 二 学期 学生所在系部 计算机学院 年级 12级 专业班级 软件B122班 学生姓名 周辉 学号 201207044224 任课教师 王德志 实验成绩 计算机学院制 《算法分析与设计 2015年 05 月 28 日 实验题目 回溯法应用编程1）掌握回溯算法求解图问题和组合问题的方法和步骤。 （2）理解回溯算法的基本思想。 （3）提高学生的编程能力和分析问题、解决问题的能力。 实验设备及环境： 微型计算机、Visual C++/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]. 关键算法： void BackTrack(int t){ //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(int i=1;i=n;i++){ bestx[i]=x[i]; } bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];//当前最优解 } }else{ for(int i=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。若右子树的最大价值大于当前最优值。则递归backtrack(i+1)。当in的时候，则从backtrack(i+1)返回。 （4）cw=cw-w[i],cp=cp-v[i],此时的cwC,随后回溯到上一个物品的右子树，随后转第3步。 输出条件：被装入物品的编号o[i],当前最优价值bestp，循环次数k。 关键代码： //回溯函数 public void backtrack(int i){ if(i n){//到达叶