算法设计与分析实验4报告(共6页).doc

《算法设计与分析实验4报告(共6页).doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验4报告(共6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2.回溯法的实现。打开Codeblocks10.05，编辑头文件Queue.h和主程序main.cpp,利用参考程序，同时还设计了从文件读入数据，使程序更清晰，其主要程序如下：Main.cpp#include #include #include #include #define INT_MAX 90using namespace std;template /交换两个变量的值void Swap(Type &a,Type &b)

4、Type t=b; b=a; a=t;template /创建二维数组void TwoDimArray(Type* &p,int r,int c) p=new Type *r; for(int i=0; ir; i+) pi=new Typec; for(int i=0; ir; i+) for(int j=0; jc; j+) pij=0;template /输出一维数组的元素void Print1(Type a,int n) for(int i=1; i=n; i+) coutai ; coutendl;templatevoid InputData2(T *M,int r,int c,ch

5、ar *filename) ifstream infile; infile.open(filename); /打开文件 if(!infile) /测试是否已经成功地打开了文件 cerr文件打开失败！endl; exit(1); /结束程序 string s; for(int i=0; ir; +i) /读取矩阵数据 getline(infile,s); /读一行 istringstream ss(s); /创建字符串流ss for(int j=0; jMij; /从流中读取一个T类型的数赋给M class Flowshop friend int Flow(int *,int,int );pri

6、vate: void Backtrack(int i); int *M; /各作业所需的处理时间 int *x; /当前位置安排 int *bestx; /当前最优攻击力 int *f2; /机器2完成处理时间 int f1; /机器1完成处理时间 int f; /当前攻击力 int bestf; /当前最优值 int n; /角色;void Flowshop:Backtrack(int i) if(in) int t=0; for(int i=1; ibestf) bestf=t; for(int j=1;j=n;j+) bestxj=xj; else for(int j=i; j=n; j

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

8、.bestf;int main() Flowshop X; int *M; int n; int *bestx; int bestf; TwoDimArray(M,5,5); X.x=new intn+1; X.M=M; X.n=n; X.bestx=new intn+1; X.bestf=0; int s=Flow(M,n,bestf); coutsendl; Print1(bestx,5); return 0;运行结果：实验总结今天主要学的是回溯法，由于上一次实验老师要求我们从文件输入数据，因此这一次我同样利用了该种方式，将矩阵中的数据仍从文件输入，还挺好上手的，但是本该顺畅的实验过程中却出现了一个笨错误，就是我的程序调试总是不正确，我还想着明明就和别人的差不多，不应该啊但是别的同学都可以运行了，我很纠结，又反复看了很多遍，后面才知道是头文件的引用不正确，我汗！改好头文件，程序一下子就顺利运行了，有种山重水复疑无路的感觉，虽然那个错误很白痴额最后是算法时间复杂度分析，因为算法Backtrack在每个结点处耗费O(1)计算时间，故最坏情况下，整个算法的时间复杂性为O(n!)专心-专注-专业