数码迷题求解算法的比较及A*算法的简单介绍

毕智超

摘 要：数码谜题源于一古老的智力游戏，是人工智能领域中的经典问题。本文着眼于8数码问题求解的具体实现。分析了数码迷题求解的搜索策略。对三种搜索算法进行了比较权衡，并对经典启发式搜索算法A*算法进行了简单介绍，介绍了该算法框架下的启发函数及Open表结构。

关键词：数码迷题；启发式搜索；A*算法；定理化判断

中图分类号：O14 文献标识码：A 文章编号：1009-0118（2011）-03-0018-01

一、引言

8数码迷题又称重排九宫，问题描述如下：用数字1~8标注的棋子摆放在一个3×3共9个格子的棋盘上，空出一个格子使棋子能在盘内水平滑动，8个符号在棋盘上的排列称为8数码的状态，游戏要求给定一个初始的状态和一个终止状态，且每次只能移动一个棋子，求从任一初始棋局变化到另一目标棋局是否有解，以及有解时的解法。

二、定理化判定可解性

按从左往右，从上到下的顺序将棋局状态表示为一个数列P=a1a2a3a4a5a6a7a8，ai为1,2…8八个数码中的一个，P是1,2…8的一个排列，称P是该棋局的状态数列。在序列P中对iaj，则称aj出现了一个逆序，元素aj的逆序数记为R(aj)。于是序列P的逆序数记为R(P)，定义为除元素0外所有元素的逆序个数之和。序列P的元素存放在数组S[1∽n×n]中。

三、搜索算法的分析比较

（一）三种搜索算法的数据结构分析。首先简单介绍下Open表和Closed的动态数据结构，前者记录当前未考察的结点，后者记录考察过的结点。扩展所得子结点按其估值的大小插入Open表中合适的位置，每次从中选出估值最小的加以扩展。每个结点都保留父结点的信息，这保证了搜索完毕后，能通过Closed表返回完整的搜索路径。

一般图的搜索算法中，提高效率的关键在于Open表中结点的排列方式，若每次排在表首的结点都最终搜索到解的路径上，则算法不需扩展任何多余的结点就可快速结束搜索。所以排列方式成为研究搜索算法的焦点，并由此形成了多种搜索策略。

（二）三种搜索算法的比较及适用范围。对于，实际问题，深度优先搜索一般不能保证找到最优解，虽然通过与回溯结合可以找到最优解，但是在最坏的情况下，搜索空间等同于穷举。而且对于许多问题，其状态空间的搜索樹的深度可能无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径，往往给出一个结点扩展的最大深度，称深度界限。任何结点如果达到了深度界限，那么都将把它们作为后继结点处理。即便应用了深度界限的规定，由于一个有解的问题树可能含有无穷分支，深度优先搜索如果误入无穷分支，或解出现在深度界限之外，则不可能找到目标结点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解，如果深度限制过小的话，甚至得不到解。因此这里就有了一个如何定义深度的问题，太小得不到结果，太大就很容易引起“结点爆炸”。

三种搜索算法运用于八数码问题的求解时，对于深度优先搜索有时候会得不到解答，而且具有不确定的时间效率；对于宽度优先搜索，虽然得到的都是最优解，但是由于生成了大量的结点，因此每次生成的结点要判断是否为全新结点都要对已经生成的结点进行遍历和比较，不但损失了空间效率，甚至还会影响时间效率；对于A*算法，理论上是能够扩展最少的结点，最快的找到解答，但是如果评估函数选的不好，也会影响效率。因此对启发式搜索的启发函数的研究就显得特别有意义了。

四、启发式搜索策略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结点到目标结点的实际最优代价，多数情况下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.