算法设计与分析实验指导4_回溯法.doc

《算法设计与分析》实验指导
实验四回溯法
一、实验目的：
1.理解回溯法的深度优先搜索策略。
2.掌握用回溯法解题的算法框架。
3.掌握回溯法的设计策略。
二、实验指导
1.回溯法的总体思想
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
2.贪心算法的基本步骤
⑴针对所给问题，定义问题的解空间；
⑵确定易于搜索的解空间结构；
⑶以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
3.程序参考
template<typenameType>//交换两个变量的值
voidSwap(Type&a,Type&b)
{
Typet=b;
b=a;
a=t;
}

template<typenameType>//创建二维数组
voidTwoDimArray(Type**&p,intr,intc)
{
p=newType*[r];
for(inti=0;i<r;i++)
p[i]=newType[c];
for(inti=0;i<r;i++)
for(intj=0;j<c;j++)
p[i][j]=0;
}

template<typenameType>//输出一维数组的元素
voidPrint1(Typea[],intn)
{
for(inti=1;i<=n;i++)
cout<<a[i]<<'';
cout<<endl;
}
三、实验内容及要求：
1.排兵布阵问题
某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。
数据：
防卫点角色123451604080506029060807020330504050804904030709056080906050
2.0-1背包问题（选做）
编程实现0-1背包问题的回溯算法。
数据文件见附件。
四、实验报告要求
1.实验报告只写实验⑴。
2.写出算法思想、主要程序代码、算法复杂性分析。