回溯法实验报告.docx

实验 04 回溯法
班级： 0920561 姓名：宋建俭 学号： 20
一 、实验目的
掌握回溯法的基本思想。
掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子 集树与排列树的递归算法结构等内容。
掌握回溯法求解具体问题的方法。
二 、实验要求
. 认真阅读算法设计教材 , 了解回溯法思想及方法 ;
.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序
三 、实验内容
. 有一批共 n 个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船， 其中集装箱
i的重量为wi,且汇wi&C1+C2装载问题要求确定是否有一个合理的装载 方案可将这个集装箱装上这 2 艘轮船。如果有，找出一种装载方案。
.在nx n格的棋盘上放置彼此不受攻击的 n个皇后。按照国际象棋的规则，
皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 后问题等价 于在nxn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列 或同一斜线上。
.给定无向连通图G和m种不同的颜色。用这些颜色为图 G的各顶点着色，每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 这个问题是图的m可着色判定问题。
四、算法原理
1、装载问题
用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪
去不满足约束条件(w1x1+w2x2+ ••+wnxn)<=c1的子树。在子集权t的第j+1层结点 Z处，用cw记当前的装载重量，即 cw=(w1x1+w2x2+・・+wjxj),当cw>c1时，以 结点 Z 为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可
行解，故可将该子树剪去。
解装载问题的回溯法中，方法 maxLoading返回不超过c的最大子集和，但未给 出达到这个最大子集和的相应子集。
算法 maxLoading 调用递归方法 backtrack(1) 实现回溯搜索。 Backtrack(i) 搜索
子集树中第 i 层子树。类 Loading 的数据成员记录子集树结点信息，以减少传
给 backtrack 的参数。 cw 记录当前结点相应的装载重量， bestw 记录当前最大
装载重量。
在算法 backtrack 中，当 i>n 时，算法搜索至叶结点，其相应的装载重量 cw。
如果 cw>bestw, 则表示当前解优于当前最优解 , 此时应更新 bestw 。
当i<二n时，当前扩展结点Z是子集树的内部结点。该结点有 x[i]=1和x[i]=0
两个儿子结点。其左儿子结点表示 x[i]=1 的情形，仅当 cw+w[i]<=c 时进入左
子树，对左子树递归搜索。其右儿子结点表示 x[i]=0 的情形。由于可行结点的
右儿子结点总是可行的，故进入右子树时不需检查可行性。
算法 backtrack 动态地生成问题的解空间树。 在每个结点处算法花费 O(1) 时间。
子集树中结点个数为 O(2 的 n 次方 ) ，故 backtrack 所需的计算时间为 O(2 的 n 次方)。另外backtrack还需要额外的O(n)递归栈空间。
2、 n 后问题
用 n 元祖 x[1:n] 表示 n 后问题的解。其中 x[i] 表示皇后 i 放在棋盘的