骑士巡游问题的回溯法分析

算法设计与分析课程论文算法设计与分析课程论文 骑士巡游问题的回溯法分析骑士巡游问题的回溯法分析 学院 信息工程学院学院 信息工程学院 姓名 姓名 学号 学号 指导老师 指导老师 问题描述 问题描述 骑士巡游 knight s tour 问题是指在有 8 8 方格的国际象棋棋盘上进行奇异的骑士 L 型 L shaped 移动的问题 在国际象棋棋盘 8 8 方格上的某个格子上放置一个骑士 然后这个骑士只能以马跳的方式前进 要求这个骑士相继地到达所有的 64 个方格 进入 每个方格一次且仅进入一次 问题分析 问题分析 L 型型 移动 移动 骑士的步进方式是按照 L 型 移动的 即如下图所示 假设骑士的当前位于粉色格 子的位置 那么它的下一步可能出现的合法位置为绿色格子的位置 如此 我们定义坐标系 棋盘左上角格子为坐标原点 0 0 横坐标 X 轴以右为正方向 Y 轴以下为正方向 当前骑士位置为 x y 则可能出现的位置为 x 2 y 1 x 1 y 2 x 1 y 2 x 2 y 1 x 2 y 1 x 1 y 2 x 1 y 2 x 2 y 1 如此 骑士没进一步都按照此方式步进 直至整个棋盘都被 游走 一遍则完成 边界情况分析 边界情况分析 在骑士 巡游 的过程中难免会游走到棋盘的边缘 那么此时下一步的坐标位置可能 超出棋盘边界 此种情况下 需要相关的限定代码予以限制 此外 因为要求棋盘每个位置要巡游且只巡游一次 所以当骑士巡游到某一位置时 可能会出现 棋盘没有被巡游完全 但不存在合法的下一步坐标点 此种情况下 则涉及 到回溯的问题 回溯算法的相关介绍 回溯算法的相关介绍 回溯法总述 回溯法总述 回溯法 探索与回溯法 是一种选优搜索法 按选优条件向前搜索 以达到目标 但当 探索到某一步时 发现原先选择并不优或达不到目标 就退回一步重新选择 这种走不通 就退回再走的技术为回溯法 而满足回溯条件的某个状态的点称为 回溯点 回溯法的深度优先搜索策略 回溯法的深度优先搜索策略 回溯法的基本做法是搜索 或是一种组织得井井有的 能避免不必要搜索的穷举式搜 索法 这种方法适用于解一些组合数相当大的问题 回溯法在问题的解空间树中 按深度优先策略 从根结点出发搜索解空间树 算法搜 索至解空间树的任意一点时 先判断该结点是否包含问题的解 如果肯定不包含 则跳过 对该结点为根的子树的搜索 逐层向其祖先结点回溯 否则 进入该子树 继续按深度优 先策略搜索 回溯法的主要思想 回溯法的主要思想 回溯法在搜索解空间树时 通常采用两种策略避免无效搜索 其一是用约束函数在扩展结 点处剪去不满足约束的子树 其二是用限界函数剪去得不到最优解的子树 这两类函数统称为 剪枝函数 回溯法的解题步骤 回溯法的解题步骤 1 针对所给问题 定义问题的解空间 2 确定易于搜索的解空间结构 3 以深度优先方式搜索解空间 并在搜索过程中用剪枝函数避免无效搜索 骑士巡游问题的回溯法分析 骑士巡游问题的回溯法分析 骑士巡游问题中骑士每进一步都会面临下一步的多种选择 最终解也由 N 步的单步 解构成 若尝试到某一步时发现已经无法继续 就返回到前一步 修改已经做出的上一步 然后再继续向后步进 这样 直到回溯到第一步 并且已经将第一步的所有可能情况都尝 试过之后 即可得出问题的全部解 而边界情况是得到解的约束条件 即可据此获得剪枝 函数 由此问题分析我们发现 骑士巡游问题求解过程恰与回溯法求解问题的思路相符合 则此问题可以用回溯法来求解 算法设计 算法设计 算法描述 算法描述 把棋盘左上角看作坐标原点 往右是 x 坐标正方向 往下是 y 坐标正方向 输入开始 巡游的坐标 把每个格子初始化为没走过 visited i j false 把初始坐标记做第 1 步 step 1 第 1 个格子标记为走过 visited row 1 col 1 true 开始计算走法 首先计算 每个格子下一步可能的走法 一共有 8 种 用循环把每一种走法都进行计算 判断是否超 出棋盘和是否被标记走过 is legal x y 最近一次的方向 无返回值函数init direction 方位具体表示 无返回值函数init status int x int y 初始状态 无返回值函数print 打印结果 包括格式控制 返回值 Int 型函数is legal int x int y 判断点是否合法 返回值 Int 型函数is end 判断是否巡游完毕 返回值 Int 型函数select direction 选择前进方向 无返回值函数forward 前进至下一步 无返回值函数backward 回溯至上一步 返回值 Int 型函数tourist 巡游函数 根据情况调用以 上两函数 返回值 Int 型函数main 主函数 程序流程图 程序流程图 开始 输入起始坐标 程序代码 程序代码 include include define WIDTH 8 define MAX DIR 8 表示没有 方向可选 int chessboard WIDTH WIDTH 0 棋盘数组 int direction WIDTH WIDTH int 开始巡游 tourist 计算走法 select direction 判断是否合法 is legal x y 判断巡游是否完 成 is end 打印巡游过程 print 结束 N N Y Y visited WIDTH WIDTH MAX DIR 0 初始时为 0 表明各个位 置的各个方向都未访问过 int cur x cur y 当前坐标 int step 已走的步数 int last direction 上一次走的 方向 下面两个数组用来记住选择 某个方向后 推进到下一位置 时 x 方向和 y 方向的值的变化 int var x MAX DIR int var y MAX DIR 八个方向的坐标变化情况 void init direction var x 0 2 var y 0 1 var x 1 1 var y 1 2 var x 2 1 var y 2 2 var x 3 2 var y 3 1 var x 4 2 var y 4 1 var x 5 1 var y 5 2 var x 6 1 var y 6 2 var x 7 2 var y 7 1 设置初始状态 void init status int x int y step 1 chessboard x y step step cur x x cur y y direction x y MAX DIR 每个位置都没有选择方向 last direction MAX DIR 上一次方向也没有 init direction 输出巡游结果 void print int x y printf for x 0 x WIDTH x printf printf n for x 0 x WIDTH x printf for y 0 y WIDTH y printf 3d chessboard x y printf n printf for y 0 y WIDTH y printf printf n 判断走这一步是否可行 int is legal int x int y if x WIDTH return 0 if y WIDTH return 0 if chessboard x y 0 return 0 return 1 判断是否遍历完成 int is end if step WIDTH WIDTH return 1 else return 0 判断是否回到起点 int is back to start if step 1 return 1 else return 0 int select direction int try x try y next x next y int i j int count min dir min dir MAX DIR last direction MAX DIR for i 0 i MAX DIR i try x cur x var x i try y cur y var y i if is legal try x try y 1 for j 0 j MAX DIR j next x try x var x j next y try y var y j if is legal next x next y if count min dir last direction i min dir count if last direction MAX DIR return 0 没有方向 可选 else return 1 有方向可 选 void forward 该位置的这个方向已经 试探过了 visited cur x cur y last di rection 1 cur x var x last direction cur y var y last direction chessboard cur x cur y step step direction cur x cur y last direction last direction MAX DIR void backward int i step chessboard cur x cur y 0 将 last direction 置为上 一位置到 curr x curr y 所选择 的方向 last direction direction cur x cur y 把这个位置的各个方向 都置为未访问过 for i 0 i MAX DIR i visited cur x cur y i 0 根据这个方向回溯到上 一位置 同时回溯到上一位置 之后 在上一位置再试探时应 该从 last direction 1 的方向 开始 cur x var x last direction cur y var y last direction int tourist do if select direction forward else backward while is back to start if is back to start return 0 else return 1 int main int start x 1 start y 1 起始位置坐标 printf