摘要 八数码文献[5]给出了九宫重排问题是否有解的判别方法：九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi是第 i 个数之前比该数小的数字的个数,则 η=Σηi是该状态的逆序数,图2说明了逆序数计算的过程 。
本文介绍用JAVA编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性; 第3部分JAVA设计的基本思想和数据结构以及具体实现; 最后,分析系统的特点并总结全文。
2 A*算法
2．1 相关的概念
对于状态空间及状态空间的搜索,参考文献[1,2,4]给出了如下定义和定理:
定义1:状态:是描述问题求解过程中任一时刻状况的数据结构,一般用一组变量的有序组合表示：Sk=（Sk0,Sk1,…）当给每一个分量以确定的值时,就得到了一个具体的状态。
定义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
:对有限图,如果从初始节点S0到目标节点Sg有路径存在,则算法A*一定成功结束。
证明：
首先证明算法必定会结束。由于搜索图为有限图,如果算法能找到解,则会成功结束；如果算法找不到解,则必然会由于Open表变空而结束。因此,A*算法必然会结束。
然后证明算法一定会成功结束。由于至少存在一条由初始节点到目标节点的路径,设此路径
S0= n0,n1 ,…,nk =Sg
算法开始时,节点n0在Open表中,而且路径中任一节点ni离开Open表后,其后继节点ni+1必然进入Open表,这样,在Open表变为空之前,目标节点必然出现在Open表中。因此,算法必定会成功结束。
转贴于 范文论文吧 http://www.fwlw8.com[1] [2] 下一页
