算法设计与分析实验指导4 - 回溯法

《算法设计与分析》实验指导

实验四 回溯法

一、实验目的：

1. 理解回溯法的深度优先搜索策略。 2. 掌握用回溯法解题的算法框架。 3. 掌握回溯法的设计策略。

二、实验指导

1. 回溯法的总体思想

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

2. 贪心算法的基本步骤

⑴ 针对所给问题，定义问题的解空间； ⑵ 确定易于搜索的解空间结构；

⑶ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

3. 程序参考

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

for(int j=0;j

1

template //输出一维数组的元素 void Print1(Type a[],int n) {

for(int i=1; i<=n; i++) cout<

三、实验内容及要求：

1. 排兵布阵问题

某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。

数据：

防卫点

1 角色

2 3 4 5

2. 0-1背包问题（选做） 编程实现0-1背包问题的回溯算法。 数据文件见附件。

1 60 90 30 90 60 2 40 60 50 40 80 3 80 80 40 30 90 4 50 70 50 70 60 5 60 20 80 90 50 四、实验报告要求

1. 实验报告只写实验⑴。

2. 写出算法思想、主要程序代码、算法复杂性分析。

2

本文来源：https://www.bwwdw.com/article/zwip.html