1、数码迷题求解算法的比较及数码迷题求解算法的比较及 A*A*算法的算法的简单介绍简单介绍 毕智超 摘 要：数码谜题源于一古老的智力游戏，是人工智能领域中的经典问题。本文着眼于 8 数码问题求解的具体实现。分析了数码迷题求解的搜索策略。对三种搜索算法进行了比较权衡，并对经典启发式搜索算法 A*算法进行了简单介绍，介绍了该算法框架下的启发函数及 Open 表结构。关键词：数码迷题；启发式搜索；A*算法；定理化判断 中图分类号：O14 文献标识码：A 文章编号：1009-0118（2011）-03-0018-01 一、引言 8 数码迷题又称重排九宫，问题描述如下：用数字 18 标注的棋子摆放在一个33
2、 共 9 个格子的棋盘上，空出一个格子使棋子能在盘内水平滑动，8 个符号在棋盘上的排列称为 8 数码的状态，游戏要求给定一个初始的状态和一个终止状态，且每次只能移动一个棋子，求从任一初始棋局变化到另一目标棋局是否有解，以及有解时的解法。二、定理化判定可解性 按从左往右，从上到下的顺序将棋局状态表示为一个数列 P=a1a2a3a4a5a6a7a8，ai 为 1,28 八个数码中的一个，P 是 1,28 的一个排列，称 P 是该棋局的状态数列。在序列 P 中对 iaj，则称 aj 出现了一个逆序，元素 aj 的逆序数记为R(aj)。于是序列 P 的逆序数记为 R(P)，定义为除元素 0 外所有元素
3、的逆序个数之和。序列 P 的元素存放在数组 S1nn中。三、搜索算法的分析比较（一）三种搜索算法的数据结构分析。首先简单介绍下 Open 表和 Closed 的动态数据结构，前者记录当前未考察的结点，后者记录考察过的结点。扩展所得子结点按其估值的大小插入 Open 表中合适的位置，每次从中选出估值最小的加以扩展。每个结点都保留父结点的信息，这保证了搜索完毕后，能通过 Closed表返回完整的搜索路径。一般图的搜索算法中，提高效率的关键在于 Open 表中结点的排列方式，若每次排在表首的结点都最终搜索到解的路径上，则算法不需扩展任何多余的结点就可快速结束搜索。所以排列方式成为研究搜索算法的焦点，
4、并由此形成了多种搜索策略。（二）三种搜索算法的比较及适用范围。对于，实际问题，深度优先搜索一般不能保证找到最优解，虽然通过与回溯结合可以找到最优解，但是在最坏的情况下，搜索空间等同于穷举。而且对于许多问题，其状态空间的搜索樹的深度可能无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径，往往给出一个结点扩展的最大深度，称深度界限。任何结点如果达到了深度界限，那么都将把它们作为后继结点处理。即便应用了深度界限的规定，由于一个有解的问题树可能含有无穷分支，深度优先搜索如果误入无穷分支，或解出现在深度界限之外，则不可能找到目标结点。所以，深度优先搜索策略是不完备的
5、。另外，应用此策略得到的解不一定是最佳解，如果深度限制过小的话，甚至得不到解。因此这里就有了一个如何定义深度的问题，太小得不到结果，太大就很容易引起“结点爆炸”。三种搜索算法运用于八数码问题的求解时，对于深度优先搜索有时候会得不到解答，而且具有不确定的时间效率；对于宽度优先搜索，虽然得到的都是最优解，但是由于生成了大量的结点，因此每次生成的结点要判断是否为全新结点都要对已经生成的结点进行遍历和比较，不但损失了空间效率，甚至还会影响时间效率；对于 A*算法，理论上是能够扩展最少的结点，最快的找到解答，但是如果评估函数选的不好，也会影响效率。因此对启发式搜索的启发函数的研究就显得特别有意义了。四、
6、启发式搜索策略 A*算法的简单介绍（一）算法估价函数简介。数码重排最简单的启发函数 h(n)就是计算当前状态与目标状态相比位置不符的数码数目。该方法虽然计算量较小，但其结点扩展量大，搜索效率低。所以将 g(n)定义为从初始结点到 n 结点移动的数码数目，即搜索树中 n 结点的深度；h(n)定义为在 n 结点状态下各数码到达目标状态的距离之和，即h(n)=(|xi1-xi2|+|yi1-yi2|)，xi1、xi2 分别为数码 i 在当前状态和目标状态下的横坐标，同理 y 为纵坐标。（二）算法的实现框架。A*算法是指满足条件 h(n)h*(n)的启发式搜索，h*(n)为从 n 结点到目标结点的实际
7、最优代价，多数情况下 h*(n)无法计算，但要判定 h(n)是否大于 h*(n)是可能的。求解数码的 A*算法框架流程如下：1、判断问题可解性；若无解，则退出。2、初始化，将初始结点放入 Open 表，令 Closed 表为空。3、若 Open 表不为空，循环执行以下操作：（1）选取 Open 表的表头作为当前结点；若该结点是目标结点，跳转至 Step4。（2）将当前结点从 Open 表中移除，放入 Closed 表中。（3）求出当前结点的所有子结点。（4）计算子结点的估价值。（5）如果子结点不在 Open 表和 Closed 表中，将其插入到 Open 表。（6）按照结点的估价值，以递增顺序重排 Open 表。4、回溯得解。五、结束语 本文对于问题首先直接应用定理进行可解化判定，其次对深度、广度优先搜索与 A*算法搜索进行了分析比较，得出三者的性能特点。最后着重于介绍启发式搜索策略 A*算法，为进一步研究奠定下坚实的基础。由于笔者的能力有限，文章中有叙述不透彻的地方望各位读者海涵，期待通过更加深入的研究和实验能得到更好的掌握。参考文献：1许精明.智能搜索中启发函数的选择及启发能力分析J.昆明理工大学学报,2007,32(5):31-34.2黄沛杰.重排九宫问题的分析与实现J.现代计算机,2003,(12).3陈世福,陈兆乾.人工智能与知识工程M.南京大学出版社,1997.
