八数码问题的JAVA设计与实现

摘要 八数码问题（Eight-puzzle Problem）是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。

关键词 九宫重排, 状态空间, 启发式搜索, A*算法

九宫重排问题（即八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态(例如图1)。状态转换的规则：空格周围的数移向空格,我们可以看作是空格移动,它最多可以有４个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。

图1 初始状态和目标状态

图2 逆序数的计算示例

许多学者对该问题进行了有益的探索^[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有９！＝362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题：每个初始状态都存在解路径吗？文献^[5]给出了九宫重排问题是否有解的判别方法：九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi是第 i 个数之前比该数小的数字的个数,则 η=Σηi是该状态的逆序数,图2说明了逆序数计算的过程 。

本文介绍用JAVA编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性; 第3部分JAVA设计的基本思想和数据结构以及具体实现; 最后,分析系统的特点并总结全文。

对于状态空间及状态空间的搜索,参考文献^[1,2,4]给出了如下定义和定理:

定义1:状态:是描述问题求解过程中任一时刻状况的数据结构,一般用一组变量的有序组合表示：S_k=（S_k0,S_k1,…）当给每一个分量以确定的值时,就得到了一个具体的状态。

定义2：算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符。

定义3：状态空间：由问题的全部状态及一可用算符所构成的集合称为问题的状态空间。一般用一个三元组表示：（S,F,G）。其中,S是问题所有初始状态的集合,F是算符的集合,G是问题所有目标状态的集合。