回溯法实验报告.doc

综合性、设计性实验报告姓名_学号_专业 计算机科学与技术 班级 级 班实验课程名称 算法设计与分析 指导教师及职称 讲师 开课学期 2009 至 2010 学年 上 学期上课时间 2010年 12 月 20 日 2一、实验设计方案实验名称：回溯法实例编程实验时间： 2010-12-20小组合作： 是 否小组成员：无1、实验目的： 1）理解回溯法的深度优先搜索策略2）掌握用回溯法解题的算法框架3）针对具体问题，能应用回溯法设计有效算法4）用C+实现算法，并且分析算法的效率2、实验设备及材料：硬件设备： pc机器配置： AMD Athlon(tm)II x2 240 2.80GHz 、2.0GB内存操作系统： Windows xp开发工具： vc+6.03、实验内容： 问题描述设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。编程任务设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。样例例如，现要将3件工作分配给3个人。将工作1分配给3个人所需的费用分别为￥10 、￥2、￥3；将工作2分配给3个人所需的费用分别为￥2、￥3、￥4；将工作3分配给3个人所需的费用分别为￥3 、￥4、￥5。那么，共有_3_种方案可使总费用达到最少。这些方案分别为：工作1分配给第二个人，工作2分配给第一个人，工作3分配给第三个人;工作1分配给第三个人，工作2分配给第一个人，工作3分配给第二个人;工作1分配给第三个人，工作2分配给第二个人，工作1分配给第一个人。上述方案都可使总费用达到最少，即￥9。4、实验方法步骤及注意事项：（注意：此部分为本实验的关键部分，请自行填写，不得雷同！）实验步骤（参考教材141页第4段自行填写）一、定义一个解空间，它包含问题的解。二、利用适于搜索的方法组织解空间。三、利用深度优先法搜索解空间。四、利用限界函数避免移动到不可能产生解的子空间。解题思路（注意：以下部分仅为提示，请自行填写；若表格不够，可自行拉伸。）1） 以n=3为例，解空间为（1,2,3）,(1,3,2),(2,1,3),(2,3,1),(3,1,2)(3,2,1)2） 以n=3为例，画出工作分配问题的解空间树。A1BCDEFGHIJK23233L2MNOP313121121) 给出使用递归回溯法求解工作分配问题的算法，用C+语言描述。#includeiostream#includefstreamusing namespace std; #define NUM 50int bestVNUM,jobNUM,valueNUMNUM; int MINCOST = 999999999; void swap(int &job1,int &job2) int t ;t= job1; job1 = job2; job2 = t; void fenpei(int n) int sum = 0; for(int i = 1; i sum ) MINCOST = sum; for(int i = 1;i n) fenpei(n); else for(int i = k;i = n;i+) swap(jobk,jobi); backtrack(k+1,n); swap(jobk,jobi); void main() int n,i,j; FILE *fp;if(fp=fopen(D:testsolutionsch5prog513testjob2.in,r)=NULL)printf(ERROR!); exit(0); fscanf(fp,%d,&n); for( i = 1;i = n;i+) for( j = 1;j = n;j+) fscanf(fp,%d,&valueij); for( i = 1;i = n;i+) for( j = 1;j = n;j+) printf(%d ,valueij); printf(n); for(i = 1;i = n;i+) jobi = i; backtrack(1,n); for( i = 1;i = n;i+) printf(第%d号工作安排给第%d个人n,bestVi,i); printf(最小费用：%dn,MINCOST); fclose(fp); 5实验数据处理方法：数据输入由文件input.txt给出输入数据。第一行有1 个正整数n (1n20)。接下来的n行，每行n个数，表示工作费用。结果输出将计算出的最小总费用和最佳的工作分配方案输出到文件output.txt。6参考文献：计算机算法设计与分析（第3版） 王晓东著 电子工业出版社算法设计与实验题解王晓东著 电子工业出版社指导老师对实验设计方案的意见：指导老师签名： 2010 年 12月 25 日 二、实验报告1、实验目的、设备与材料、实验内容、实验方法步骤见实验设计方案2、实验现象、数据及结果（请自行填写真实结果）序号输入文件(input.txt)输出文件(output.txt)0.310 2 32 3 43 4 591.550 43 1 58 60 87 22 5 62 71 62 98 97 27 38 56 57 96 73 71 92 36 43 27 951442.863 69 21 15 42 59 42 86 1 75 77 31 52 24 98 73 40 49 58 4 7 82 39 82 40 30 64 63 27 5 8 58 98 46 16 49 31 48 79 92 53 17 4 82 77 95 71 68 45 44 31 73 38 62 62 98 25 7 39 95 3 75 47 751813、对实验现象、数据及观察结果的分析与讨论： 当输入数据为3 10 2 3 2 3 4 3 4 5时，输出文件为9，表示将花费最小的工作分配出去了。 4、结论：算法能正确通过运行，且输出结果也测试结果，效率还较满意。5、实验总结1）、本次实验成败之处及其原因分析： 本次实验还是成功的，分析实验过程虽画出了解空间和解空间树，但是在考虑如何分配工作时，遇到了困难，后来参考网上资料解决。2）、本实验的关键环节及改进措施：做好本实验需要把握的关键环节：首先解空间树要画正确。然后就是考虑如何将花费最小的工作分配出去。若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善： 本实验是参考网上资料，还