文档介绍：实验04 回溯法
班级:0920561 姓名:宋建俭学号:20
一、实验目的
掌握回溯法的基本思想。
掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子集树与排列树的递归算法结构等内容。
掌握回溯法求解具体问题的方法。
二、实验要求
认真阅读算法设计教材,了解回溯法思想及方法;
设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序
三、实验内容
有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集装箱i的重量为wi,且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有,找出一种装载方案。
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。
四、算法原理
1、装载问题
用回溯法解装载问题时,用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第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放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列,所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题,这一隐约束条件可以化成显约束的形式。将n×n格棋盘看作二维方阵,其行号从上到下,列号从左到右依次编号为1,2,…,n。从棋盘左上