文档介绍：《算法设计与分析》课程实验报告专业: 软件工程班级: 学号: 姓名: 日期: 2013 年 12月 11日一、实验题目回溯法二、实验目的 1. 掌握回溯法的基本思想。 2. 掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子集树与排列树的递归算法结构等内容。 3. 掌握回溯法求解具体问题的方法。三、实验内容 1. 有一批共 n 个集装箱要装上 2 艘载重量分别为 C1和 C2 的轮船,其中集装箱 i 的重量为 wi, 且∑ wi≤ C1+C2 。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有,找出一种装载方案。 ×n 格的棋盘上放置彼此不受攻击的 n 个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 后问题等价于在 n×n 格的棋盘上放置 n 个皇后, 任何 2 个皇后不放在同一行或同一列或同一斜线上。 3. 给定无向连通图 G和m 种不同的颜色。用这些颜色为图 G 的各顶点着色, 每个顶点着一种颜色。是否有一种着色法使 G 中每条边的 2 个顶点着不同颜色。这个问题是图的 m 可着色判定问题。四、实验步骤 1、装载问题【问题分析】例如,当 n=3,c1=c2=50, 且 w=[10,40,40] 时,可将集装箱 1 和集装箱 2 装上一艘轮船,而将集装箱 3 装在第二艘轮船;如果 w=[20,40,40], 则无法将这 3 个集装箱都装上轮船。容易证明,如果一个给定的装载问题有解,则采用如下的策略可以得到最优装载方案。 1. 首先将第一艘轮船尽可能装满。 2 2. 将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能的装满等价于选取全体集装箱的子集, 使该子集中集装箱的重量之和最接近 c1 。因此,等价于一个特殊的 0-1 背包问题。因此是一棵子集树。 max(w1x1+w2x2+...+wixi) (w1x1+w2x2+...+wixi)<= c1; xi @{0,1},1<=i<=n 用回溯法解装载问题时,用子集树表示其解空间显然是最合适的。可行性约束函数可剪去不满足约束条件( (w1x1+w2x2+...+wixi)<= 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]