实验四 回溯法

《实验四 回溯法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四回溯法（4学时）上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。一、实验目的与要求1.掌握回溯法的基本思想方法；理解回溯法的基本思想，理解回溯法算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的回溯法问题。2.了解适用于用回溯法求解的问题类型，并能设计相应回溯法

2、算法；3.掌握回溯法算法复杂性分析方法分析问题复杂性。二、实验内容（以下题目要求采用回溯法算法完成）：1、N皇后问题八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。如下图所示：其中图中的一个解为：468271357北京联合大学应用文理学院N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放

3、置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。1.运用回溯法，设计解决上述问题的算法，设计出用回溯法计算出在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，并返回每个皇后的位置。2.掌握回溯算法的应用。2、0-1背包问题给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi(ｘi=0或１，ｘi=0表示物

4、体ｉ不放入背包，ｘi＝1表示把物体ｉ放入背包），3、装载问题有两艘船，它们的可装载的货物重量分别为才c1，c2，给定一批货物，其重量保存在数组w【i】中了，问这批货物能否用此两艘船送出。三、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。四、实验要求1）上述题目任选两道做。2）独立完成程序代码的编写3）独立完成实验及实验报告附：实验报告的主要内容一．实验目的二．问题描述三．解题思路四．算法设计包含：数据结构与核心算法的设计描述、函数调用及主函数设计、

5、主要算法流程图等五.程序调试及运行结果分析7北京联合大学应用文理学院六.实验总结附录：程序清单（程序过长，只附主要部分）五、实验原理一、回溯法的基本思想：有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，先判断该结点是否包含问题的解:1)如果肯定不包含，则跳过这个结点；2)如果可能包含，进入该子树，继续按深度

6、优先策略搜索；3)若某结点i的所有子结点都不可能包含问题的解，则回溯到i的父结点，生成下一个结点，继续搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。在它求问题的一个解时，只要搜索到问题的一个解就结束。二、设计回溯法的步骤：(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 三、回溯法的求解过程：初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1=a11，如果X=(x

7、1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1=a12。依此类推，一般情况下，如果X=(x1,x2,…,xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：（1）如果X=(x1,x2,…,xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； （2）如果X=(x1,x2,…,xi＋1)是问题的部分解，则继续构造解向量的下一个分量； （3）如果X=(x1

8、,x2,…,xi＋1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况： ①如果xi+1=ai＋1,k不是集合Si＋1的最后一个元素，则令xi+1=ai＋1,k＋1，即选择Si+1的下一个元素作为解向量X的第i+