算法设计与分析试验4报告

1、湖南科技学院实验报告系部数学与计算科学专业信息与计算科学成绩评定班级信计0902班学号200905002231姓名易丹课程名称算法设计与分析实验时间2012.5.18实验编号实验四实验名称回溯法5实验环境实验目的D315、一台电脑、Codeblocks10.051. 理解回溯法的深度优先搜索策略。2. 掌握用回溯法解题的算法框架。3. 掌握回溯法的设计策略。实验内容（算法、程序、步骤和方法输入、输出、实验结果实验结果分析）实验内容:1. 排兵布阵问题某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色1,2,.,n，需安排在某战区n个点上，角色i在j点上的攻击力为 Ai

2、j。试设计一个布阵方案，使总的攻击力最大。数据：防卫点604080506090608070203050405080904030709060809060501234123452. 0-1背包问题（选做）编程实现0-1背包问题的回溯算法。 数据文件见附件。实验要求:1. 实验报告只写实验。2. 写出算法思想、主要程序代码、算法复杂性分析。实验（1）的步骤、算法及运行结果:1.回溯法的总体思想回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方 法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树

3、的 任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐 层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2. 回溯法的实现。打开Codeblocks10.05，编辑头文件Queue.h和主程序main.cpp,利用参考程序，同时还设计了从文件读入 数据，使程序更清晰，其主要程序如下：Mai n.c pp#in elude <iostream> #in elude <sstream> #i nclude <fstream> #in elude <cstdlib> #defi ne INT_MA

4、X 90 using n ames pace std;temp late<ty pen ame Type/交换两个变量的值 void Swap(Type &a,T ype &b)Type t=b; b=a;a=t;temp late<ty pen ame Typ e> / 创建二维数组 void TwoDimArray(T yp e* &p ,i nt r,i nt c)p=new Type *r; for(i nt i=0; i<r; i+) p i=new Typ ec;for(i nt i=0; i<r; i+)for(i nt j=

5、0; j<c; j+) pij=0;temp late<ty pen ame Type/ 输出一维数组的元素 void Prin t1(T ype a,i nt n)for(i nt i=1; i<=n; i+)cout<<ai<<''cout<<e ndl;temp late<t ypen ame T>void Inp utData2(T *M,i nt r,int c,char *file name)ifstream in file;in file. open( file name);/ 打开文件if(!i

6、nfile)/测试是否已经成功地打开了文件cerr<<"文件打开失败！"<<e ndl;exit(1);结束程序stri ng s;for(i nt i=0; i<r; +i) / 读取矩阵数据getline(infile,s); / 读一行istringstream ss(s); /创建字符串流 ssfor(i nt j=0; j<c; +j)ss>>Mij;/从流中读取一个T类型的数赋给Mclass Flowsho pfrie nd int Flow(i nt *,i nt,i nt );p rivate:void Bac

7、ktrack(i nt i);int *M;/各作业所需的处理时间int *x; /当前位置安排int *bestx; 当前最优攻击力int *f2;机器2完成处理时间int f1;/机器1完成处理时间int f;/当前攻击力int bestf; /当前最优值int n;角色;void Flowsh op:Backtrack。nt i)if(i> n)int t=0;for(i nt i=1; i<=n; i+) t+=M xii;if(t>bestf)bestf=t;for(i nt j=1;j<=n ;j+) bestxj=xj;elsefor(int j=i; j

8、<=n; j+)/自 i 后，有i:n项作业Swap(xi,xj); /xj成为第 i 个作业 Backtrack(i+1);Swa p(xi,xj);int Flow(i nt *M,i nt n,i nt bestx)Flowshop X;/初始X对象的数据X.x=new in t n+1;X.f2=new in t n+1;X.M=M;X. n=n;X.bestx=bestx;X.bestf=0;X.f1=0;X.f=0;for(i nt i=0; i<=n; i+)X.f2i=0;X.xi=i;X.Backtrack(1); delete X.x;delete X.f2;r

9、eturn X.bestf;int mai n()Flowsho p X;int *M;int n;int *bestx;int bestf;TwoDimArray(M,5,5);X.x=new in t n+1;X.M=M;X. n=n;X.bestx =new intn+1;X.bestf=0;int s=Flow(M, n,bestf); cout<<s<<e ndl;Prin t1(bestx,5); return 0;运行结果:0 C;cuKent s and?e3070 be4ea2 540504080seQB403090se7B5670ee26se905Qi"et：urne(l 0ProcessKpgss any key to continue-execut ion t ine : 0_233 s今天主要学的是回溯法，由于上一次实验老师要求我们从文件输入数据，因此这一 次我同样利用了该种方式，将矩阵中的数据仍从文件输入，还挺好上手的，但是本该顺 畅的实验过程中却出现了一个笨错误，就是我的程序调试总是不正确，我还想着明明就 和别人的差不多，不应该啊-但是别的同学都可以