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

摘要  八数码问题（Eight-puzzle Problem）是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。关键词  九宫重排, 状态空间, 启发式搜索, A*算法1  引言      九宫重排问题（即八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态(例如图1)。状态转换的规则：空格周围的数移向空格,我们可以看作是空格移动,它最多可以有４个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。

    图1 初始状态和目标状态 

                            图2 逆序数的示例       许多学者对该问题进行了有益的探索^[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有９！＝362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题：每个初始状态都存在解路径吗？^[5]给出了九宫重排问题是否有解的判别方法：九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi是第 i 个数之前比该数小的数字的个数,则 η=Σηi是该状态的逆序数,图2说明了逆序数计算的过程 。      本文介绍用JAVA编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性; 第3部分JAVA设计的基本思想和数据结构以及具体实现; 最后,分析系统的特点并全文。2 A^*算法2．1 相关的概念        对于状态空间及状态空间的搜索,文献^[1,2,4]给出了如下定义和定理:       定义1:状态:是描述问题求解过程中任一时刻状况的数据结构,一般用一组变量的有序组合表示：S_k=（S_k0,S_k1,…）当给每一个分量以确定的值时,就得到了一个具体的状态。       定义2：算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符。       定义3：状态空间：由问题的全部状态及一可用算符所构成的集合称为问题的状态空间。一般用一个三元组表示：（S,F,G）。其中,S是问题所有初始状态的集合,F是算符的集合,G是问题所有目标状态的集合。       定义4：状态空间图:状态空间的图示形式称为状态空间图,其中,节点表示状态,有向边表示算符。      状态空间搜索的基本思想就是通过搜索引擎寻找一个操作算子的调用序列,使问题从初始状态变迁到目标状态之一,而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的解路径。搜索引擎可以设计为任意实现搜索算法的控制系统。 2．2 A*算法以及可采纳性A*算法是一个很重要的启发式搜索算法。如果一般图搜索过程（见文献1,2）进行如下限制,则它就成为A*算法：      （1）    把OPEN表中的节点按估价函数f(x)= g(x)+h(x)的值从小到大进行排序；      （2）    g(x)是对g*(x)的估计,g(x)>0；      （3）    h(x)是h*(x)的下界,即对所有的x均有：h(x)≤ h*(x)       其中,g*(x)是从初始节点到节点x 的最小代价,h*(x)是节点x到目标节点的最小代价,若有多个目标节点,则为其中最小的一个。       定义5：算法的可采纳性(Admissibility)         一般来说,对任意一个状态空间图,当从初始节点到目标节点有路径存在时,如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径,并在此路径上结束,则称该搜索算法是可纳的。A*算法是可纳的,即它能在有限步内终止并找到最优解。我们分三步用以下三个定理来证明这一结论^[1,2]。       定理1:对有限图,如果从初始节点S₀到目标节点S_g有路径存在,则算法A*一定成功结束。证明：      首先证明算法必定会结束。由于搜索图为有限图,如果算法能找到解,则会成功结束；如果算法找不到解,则必然会由于Open表变空而结束。因此,A*算法必然会结束。然后证明算法一定会成功结束。由于至少存在一条由初始节点到目标节点的路径,设此路径                  S₀= n0,n1 ,…,nk =Sg       算法开始时,节点n0在Open表中,而且路径中任一节点ni离开Open表后,其后继节点ni+1必然进入Open表,这样,在Open表变为空之前,目标节点必然出现在Open表中。因此,算法必定会成功结束。       引理1：       对无限图,如果从初始节点S₀到目标节点Sg有路径存在,且A*算法不终止的话,则从Open表中选出的节点必将具有任意大的f值。证明：略。        引理2       ：在A*算法终止前的任何时刻,Open表中总存在节点n’,它是从初始节点S0到目标节点的最佳路径上的一个节点,且满足：f(n’) ≤ f^*(S₀)       证明：略。        定理2 对无限图,若从初始节点S₀到目标节点t有路径存在,则A*算法必然会结束。       证明：（反证法）假设A*算法不结束,又引理1知Open表中的节点有任意大的f值,这与引理2的结论相矛盾,因此,A*算法只能成功结束。      定理3：      A*算法是可采纳的,即若存在从初始节点S₀到目标节点S_g的路径,则A*算法必能结束在最佳路径上。      证明：证明过程分以下两步进行：      先证明A*算法一定能够终止在某个目标节点上。由定理1和定理2可知,无论是对有限图还是无限图,A*算法都能够找到某个目标节点而结束。再证明A*算法只能终止在最佳路径上（反证法）。      假设A*算法未能终止在最佳路径上,而是终止在某个目标节点t处,则有f(t)=g(t)>f*(S₀)      但由引理2可知,在A*算法结束前,必有最佳路径上的一个节点n’在Open表中,且有f(n’) ≤  f*(S₀)<f(t),       这时,A*算法一定会选择n’来扩展,而不可能选择t,从而也不会去测试目标节点t,这就与假设A*算法终止在目标节点t相矛盾。因此,A*算法只能终止在最佳路径上。3八数码问题的JAVA设计与实现3．1 数据结构和设计框架      主要设计思路：(1)用长度为9的一维数组来存储一个状态；一个状态构造一个节点。节点需要保存：状态信息—一维数组,状态数组的长度及状态显示的格局的维数,邻接节点信息,与搜索相关的信息;状态转换的操作算符为空格的上、下、左、右移动。(2)用链表来有的存放已经搜索过的状态和待搜索的状态；(3)用一个显示类来显示初始状态、目标状态及需要显示的中间状态；(4)分别用宽度优先算法和A*算法进行问题求解；(5)在A*算法中设置估价函数：f(n)=g(n)+h(n),其中g(n)状态的深度,h(n)所有数码到目标位置的距离,又称为曼哈顿距离；(6) 终止情况的判断。      自定义的类:PuzzleE类（主类）: 是整个系统执行的入口,包含main方法,继承（extends）JFrame类、实现（implements）MouseListener、ActionListener等接口,完成主界面的设计和监听所有事件（包括JButton事件和Mouse事件）；SNode类定义了节点的构造方法及操作；linkedList类定义了搜索过程中用到的链表结构及相关操作；toolFunc类定义了系统中要用到的一些公用函数；displayStatePanel类定义了问题状态的显示。Java API中的类: JButton类,完成与用户的交互,实现随机生成初始状态、设置初始状态、单步演示和手动游戏; List类,显示单步演示时每一步的具体的操作; JtextField类显示系统工作状态及其它信息；JLabel类,显示标题。       对于一个初始状态,首先计算其逆序数,判断是否有解,若无解,则退出；若有解,则根据某种搜索策略进行求解,在求解过程中,找到解,则在显示“找到解”后退出；若已访问的节点数超过预定值,则在显示“找不到解”退出。通过计算可以得出,本程序设定的目标状态的逆序数是21,为奇数。图3是搜索算法的流程图和图4我们所设计总体结构。图3  求解函数流程图                     图4  系统的总体结构图3．2 具体实现      用户运行程序进入主界面（见图5）和系统初始界面（见图6）。                      图5 系统主界面                                        图6 系统初始界面      在主界面中,用户首先选择搜索策略。然后可选择“初始化”或“设置状态”按钮而执行设置初始状态并按照选定的搜索策略执行相应的状态空间搜索算法,求得结果并在状态显示区进行相应的结果显示。对某一初始状态求得其解的主界面,见图七。其中,点击“初始化”是系统随机生成一初始状态并对其求解；点击“设置状态”是将初始状态设置为用户想要的状态并进行求解。设置初始状态后,用户可用手工移动数码方块的方式进行游戏。整个系统包括: 类调用PuzzleE类实现主界面的设计和监听所有事件（包括JButton事件、JRadioButton事件和Mouse事件）。处理（“手动游戏”）事件包括mousePressed（处理鼠标按下事件）、mouseReleased(处理鼠标松开事件)它们二者共同完成手动游戏过程。 public void mousePressed(MouseEvent e){记录按下鼠标左键的位置；}public void mouseReleased(MouseEvent e){记录鼠标键松开时的位置；计算鼠标键按下和松开时位置的数码块的位置号；如果两位置相邻且其一为空格,则交换此数码和空格的位置,并重画显示区。} 4 系统分析       本文用目前流行的JAVA语言动态地实现了九宫重排问题,系统对任一初始状态进行是否有解的,并对有解情况进行求解。用户可以“自动演示”方式来观看状态转换过程。用户还可通过鼠标来进行游戏。采用面向对象设计,即类（包括属性和方法）的声明,并用到了其线程的相关知识。特别是捕获异常的try-catch结构,这是其它语言所不具有的,体现了JAVA语言的精髓。但是,系统简单、界面不够美观, 仅仅用两种算法实现了我们的想法, 还有许多有价值的算法没有实现,将来会逐步学习完善。  : [1] George F Luger人工智能—复杂问题求解的结构和策略（版·第四版）。机械出版社,2004年。[2] Nils J。Nilsson。 Artificial Intelligence A New Synthesis。机械工业出版社2002（第4版）。[3] Ralph Morelli。Java面向对象程序设计。工业出版社,2004年。[4] 王永庆。人工智能原理与方法。西安大学出版社,2001年。[5] Terry。人工智能经典问题：八数码问题。 。[6] 尚福华。A* Algorithm。http://mitlab。hit。edu。cn/