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

湖南科技学院实验报告系部数学与计算科学专业信息与计算科学成绩评定班级信计 0902 班学号200905002231 姓名易丹课程名称算法设计与分析实验时间2012.5.18 实验编号实验四实验名称回溯法实验环境D315、一台电脑、 Codeblocks10.05 实验目的1. 理解回溯法的深度优先搜索策略。2. 掌握用回溯法解题的算法框架。3. 掌握回溯法的设计策略。实验内容 （①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）实验内容 ：1. 排兵布阵问题某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n 个不同兵种的角色{1,2,...,n} ，需安排在某战区n 个点上，角色i 在 j 点上的攻击力为A ij。试设计一个布阵方案，使总的攻击力最大。数据：防卫点角色1 2 3 4 5 1 60 40 80 50 60 2 90 60 80 70 20 3 30 50 40 50 80 4 90 40 30 70 90 5 60 80 90 60 50 2. 0-1 背包问题（选做）编程实现 0-1 背包问题的回溯算法。数据文件见附件。实验要求：1. 实验报告只写实验⑴。2. 写出算法思想、主要程序代码、算法复杂性分析。实验（ 1）的步骤、算法及运行结果：1. 回溯法的总体思想回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2.回溯法的实现。打开 Codeblocks10.05，编辑头文件Queue.h 和主程序 main.cpp,利用参考程序， 同时还设计了从文件读入数据，使程序更清晰，其主要程序如下：Main.cpp #include #include #include #include #define INT_MAX 90 using namespace std; template // 交换两个变量的值void Swap(Type &a,Type &b) { Type t=b; b=a; a=t; } template //创建二维数组void TwoDimArray(Type** &p,int r,int c) { p=new Type *[r]; for(int i=0; i // 输出一维...