八数码问题的改进算法

1 八数码问题的改进算法八数码问题的改进算法 摘 要 搜索算法是人工智能研究的核心问题之一 搜索算法优劣的关键在于 搜索策略的好坏 采用较好搜索策略对提高算法效率和减少回溯次数至关重要 对于八数码问题 如果没有丛要 尽量不扩展已在目标位置上的节点 以减少 回溯次数和生成的节点数 根据这一理论基础 给出较好的搜索策略 关键字 搜索算法 信息引导 效率 成员及分工表 姓名学号负责工作 算法设计与实现 论文 演讲稿 软件测试 1 一 问题描述及通用算法问题描述及通用算法 1 1 问题描述 在九宫棋盘上摆有 8 个将牌 每一个将牌都刻有 1 8 数码中的某一个数码 棋盘中有一个空格 与空格相邻的可以向空格移动 通过不断移动将牌来改变 整个棋盘的布局 游戏求解的问题是 给定一种初始的将牌布局 称为初始状态 和 一个目标的布局 称作 目标状态 问如何移动将牌 实现从初始状态到目标状 态的转变 问题的解答其实就是给出一个合法的走步序列 如图 1 a 是八数码 问题的一个初始状态 b 是八数码问题的目标状态 283 164 75 a 123 84 765 b 图 1 八数码问题的描述 1 2 深度优先搜索 深度优先搜索策略是把扩展当前结点生成的子结点总是置于 OPEN 表的前 端 使其优先扩展 这样搜索向纵深方向发展 1 G G0 G0 s OPEN s CLOSED 2 LOOP IF OPEN THEN EXIT FAIL 3 n FIRST OPEN 4 IF GOAL n THEN EXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSED 6 IF DEPTH n Dm GO LOOP 7 EXPAND n mi G ADD mi G 8 IF 目标在 mi THEN EXIT SUCCESS 9 ADD mj OPEN 并标记 mj 到 n 的指针 1 3 宽度优先搜索 与深度优先算法相悖 宽度优先算法把扩展当前结点后生成的子结点置于 OPEN 表的末端 此时 OPEN 表形成队列 使搜索向横向方向发展 1 G G0 G0 s OPEN s CLOSED 2 LOOP IF OPEN THEN EXIT FAIL 3 n FIRST OPEN 4 IF GOAL n THEN EXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSED 6 EXPAND n mi G ADD mi G 7 ADD OPEN mj 并标记 mj到 n 的指针 把不在 OPEN 或 CLOSED 中的结点 放在 OPEN 表的后面 使深度浅的结点可优先扩展 8 GO LOOP 1 4 A 算法 2 当在算法 A 的评价函数中 使用的启发函数 h n 是处在 h n 的下界范围 也就是满足 h n h n 时 则把这个算法叫做 A 算法 A 算法实际上是分支 界限和动态规划原理及使用下界范围的 h 相结合的算法 用 LISP 语言描述为 1 OPEN s f s g s h s 2 LOOP IF OPEN THEN EXIT FAIL 3 n FIRST OPEN 4 IF GOAL n THEN EXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSE 6 EXPAND n mi 计算 f n mi g n mi h mi ADD Mj OPEN 标记 mj 到 n 的指针 IF f n mk f mk THEN f mk f n mk 标记 mk 到 n 的指针 IF f n m1 f m1 THEN f m1 f n m1 标记 m1 到 n 的指针 ADD m1 OPEN 7 OPEN 表中的结点按 f 值从小到大排列 8 GO LOOP 二 二 八数码问题的改进算法八数码问题的改进算法 在评价函数中 h n 表示从结点 n 到目标结点耗散值的估计值显然我们尽可 能地避免扩展当前结点后使得 h n 增大 就本例而言 在图 l a 中可以移动的将 牌有三个 标号分别为 6 7 和 5 与目标状态图 l b 做比较 标号为 7 和 5 将 牌已经在目标位置上 移动这两个将牌只会增大 h n 本算法提出的策略就是 八数码的下一个格局中每个棋子移动到正确位置所需要的步数要少于当前格局 中每个棋子移动到正确位置所需要的步数 首先来解释一下什么是棋子移动到正确位置的步数 283 164 75 a 123 84 765 b 图 2 假设图 2 b 右边的格局是最终状态 那么可以看出左边格局中正确位置 的数码就是红色字体标识的数码 分别是 3 4 5 7 我们把初始数码中的每 个未移动到正确位置的数码拿出来单独分析 我们拿数码 2 来分析 如下图 2 a 2 b 图 3 可以看出数码 2 移动到正确位置需要一步 我们再拿数码 8 来分析 3 8 a 8 b 8 c 图 4 从图 4 可以看出 数码 8 移动到正确位置为两步 因此 一次可以得出数 码 1 和数码 6 移动到正确位置都为一步 所以当前状态的每个棋子移动到正确 位置的步数总和为 1 2 1 1 5 步 那么当前状态的下一状态如下图所示 283 14 765 b 283 164 75 c 283 164 75 d 466 5 图 5 图 5 中 红色字体标识的是在正确位置的数码 八数码旁边的数字表示当 前数码格局中每个棋子移动到正确位置的步数总和为 n 步 由此可以看出图 5 b 的格局满足条件 一共要 4 步 所以图 5 b 的格局 为下一步格局 用 LISP 语言描述为 1 OPEN s f s g s h s 2 LOOP IF OPEN THEN EXIT FAIL 3 n FIRST OPEN 4 IF GOAL n THEN EXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSE 6 EXPAND n mi 计算 f n mi g n mi h mi ADD Mj OPEN 标记 mj 到 n 的指针 IF f n mk f mk THEN f mk f n mk 标记 mk 到 n 的指针 IF f n m1 f m1 THEN f m1 f n m1 标记 m1 到 n 的指针 ADD m1 OPEN 7 OPEN 表中的结点按 f 值从小到大排列 8 GO LOOP 三 三 改进算法的实现改进算法的实现 这算法类似与树节点的搜索 一旦搜索到相应的节点就会结束搜索 所以 实现起来也可以参考树的实现 但和树的实现起来不一样的是节点的展开 考 283 164 75 a 4 虑到八数码移动的特殊性 如果不对节点的子节点进行过滤 那么子节点就一 定会出现和该节点的父节点一样的子节点 这也是实现该算法的一个难点 为了解决这个算法实现的难点 就需要记录父节点的操作类型 由于只有 与空格相邻的数码可以向空格移动 所以能够移动的类型总共就只有 4 种 如 图 6 所示 2 31 0 图 6 这里为了实现方便 为每一种的移动类型分别对应编号 0 3 如表 1 所示 编号移动类型 0空格与下面的元素进行交换 1空格与右边的元素进行交换 2空格与上边的元素进行交换 3空格与左面的元素进行交换 表 1 为了提高本程序的人机交互性能 采用简便的输入方式 同时过滤用户的 一些输入错误 以免程序运行时发生错误 提高程序的容错性 用户输入错误 的情况主要有两种 一种是输入 0 8 数码以外的字符 另一种是 0 8 的数码重 复输入 过滤第一种的输入错误比较简单 而另外一种的输入错误 需要判断 是否重复输入 一般的方法是每个字符的输入都要遍历前面的已经输入字符 使用这样的算法判断重复容易得到时间复杂度是 O n2 级别的 显然选择这样的 算法是很不明智的 针对这种情况 本文提出一种以空间换取时间的算法 算 法描述如下 1 申请数码总数的数组 为布尔类型 全部标识 false 2 接收一个数字 查找以该数字为数组下标的值是否为 true 是 退出程序 否 把该值置为 false 3 检查数字接收完没有 是 退出 否 转到第二步 使用这种判重算法 很明显时间复杂度为 O 1 但空间复杂度为 O n 而 且还可以用位来存储 还是十分值得推广的 四 四 算法的不足与优点算法的不足与优点 在上面所示意的八数码问题中 初始布局是结构良好的 即与空格相邻的 将牌中至少有一个将牌不在目标位置 有一种最坏的情况 即八数码问题的初 始状态 图 7 a 和目标状态 图 7 b 非结构良好 283 164 75 a 328 461 75 b 图 7 5 与目标状态相对比来看 初始状态空格相邻的将牌都已经在目标状态中 这就是最坏情况 对于这种情况 可以采取前面所提到的几种经典算法加以解 决 对于结构良好的初始状态 如图 1 的八数码问题 下面是三种算法效