算法设计与分析实验报告.doc

湖南科技学院实验报告
系部
数学与计算科学
专业
信息与计算科学
成绩评定
班级
信计0902班
学号
2
姓名
易丹
课程名称
算法设计与分析
实验时间
20１2．５。1８
实验编号
实验四
实验名称
回溯法
实验环境
D3１５、一台电脑、
实验目的
1． 理解回溯法的深度优先搜索策略。
2。 掌握用回溯法解题的算法框架.
３. 掌握回溯法的设计策略.
实验内容（①算法、程序、步骤和方法 ②输入、输出、实验结果　③实验结果分析）
实验内容:
１.　排兵布阵问题
某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色｛1,２,。。.，n}，需安排在某战区n个点上，角色ｉ在j点上的攻击力为Ａｉj。试设计一个布阵方案,使总的攻击力最大。
数据：
防卫点
角色
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－１背包问题（选做）
编程实现0-1背包问题的回溯算法。
ﻩ数据文件见附件。
实验要求:
　 　1。 实验报告只写实验⑴。
2。　写出算法思想、主要程序代码、算法复杂性分析。
实验(1)的步骤、算法及运行结果：
1. 回溯法的总体思想
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略,，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则,进入该子树,继续按深度优先策略搜索。
。
打开Coｄeblocｋs１0．0５，．cｐp，利用参考程序,同时还设计了从文件读入数据，使程序更清晰,其主要程序如下：
Main。ｃｐp
#iｎｃlｕdｅ　〈iostｒｅam＞
#incｌude　<sstｒeam>
＃incluｄe　＜fstream〉
＃iｎcludｅ　<cstdｌib>
#dｅfiｎｅ IＮＴ＿ＭAX 　９０
using naｍespaｃe sｔｄ；
template〈typｅｎame Tｙpe〉 ／/交换两个变量的值
ｖoid S &a，Ｔype　&b)
｛
　　 Ｔypｅ t=b；
b=a；
　 ａ=t；
｝
temｐlaｔｅ〈tｙｐeｎame　Tｙpｅ＞ //创建二维数组
vｏｉd TｗｏDiｍArrａy(Tｙpe*＊　&p,int r,iｎt ｃ）
{
p=nｅｗ　Type ＊［r];
　　for(ｉnt i=０; i〈r； i++）
　 p[ｉ］=new Ｔｙpe［ｃ]；
　　 for(ｉnｔ　ｉ=0; i〈r; ｉ++)
　 fｏr（ｉnｔ ｊ=0； j<ｃ; j+＋