算法设计与分析实验4报告.doc
- 文档编号:8458818
- 上传时间:2023-05-13
- 格式:DOC
- 页数:5
- 大小:70.50KB
算法设计与分析实验4报告.doc
《算法设计与分析实验4报告.doc》由会员分享,可在线阅读,更多相关《算法设计与分析实验4报告.doc(5页珍藏版)》请在冰点文库上搜索。
湖南科技学院实验报告
系部
数学与计算科学
专业
信息与计算科学
成绩评定
班级
信计0902班
学号
200905002231
姓名
易丹
课程名称
算法设计与分析
实验时间
2012.5.18
实验编号
实验四
实验名称
回溯法
实验环境
D315、一台电脑、Codeblocks10.05
实验目的
1.理解回溯法的深度优先搜索策略。
2.掌握用回溯法解题的算法框架。
3.掌握回溯法的设计策略。
实验内容(①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析)
实验内容:
1.排兵布阵问题
某游戏中,不同的兵种处在不同的地形上其攻击能力不一样,现有n个不同兵种的角色{1,2,...,n},需安排在某战区n个点上,角色i在j点上的攻击力为Aij。
试设计一个布阵方案,使总的攻击力最大。
数据:
防卫点
角色
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
#defineINT_MAX90
usingnamespacestd;
template
voidSwap(Type&a,Type&b)
{
Typet=b;
b=a;
a=t;
}
template
voidTwoDimArray(Type**&p,intr,intc)
{
p=newType*[r];
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 实验 报告