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

《算法设计与分析实验指导4_回溯法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验指导实验四回溯法一、实验目的：1.理解回溯法的深度优先搜索策略。2.掌握用回溯法解题的算法框架。3.掌握回溯法的设计策略。二、实验指导1.回溯法的总体思想回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入

2、该子树，继续按深度优先策略搜索。2.贪心算法的基本步骤⑴针对所给问题，定义问题的解空间；⑵确定易于搜索的解空间结构；⑶以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3.程序参考template//交换两个变量的值voidSwap(Type&a,Type&b){Typet=b;b=a;a=t;}template//创建二维数组voidTwoDimArray(Type**&p,intr,intc){p=newType*[r];for(

3、inti=0;i//输出一维数组的元素voidPrint1(Typea[],intn){for(inti=1;i<=n;i++)cout<

4、需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。数据：防卫点角色1234516040805060290608070203305040508049040307090560809060502.0-1背包问题（选做）编程实现0-1背包问题的回溯算法。数据文件见附件。四、实验报告要求1.实验报告只写实验⑴。2.写出算法思想、主要程序代码、算法复杂性分析。2