【转载】A*算法求解8数码问题
困扰我多日的八数码问题终于解决了，一度对八数码问题不知道该如何下手，网上很多都是用A*算法解的，但是版本可以说各有千秋，自己一时间看看各个版本的代码，也弄的头昏脑涨的，这两天一直研究A*算法，然后想通过一个实例来好好学习下A*问题，这样如果能够很好的解决典型的8数码问题，对自己也有个很好的提升。在网上看到的版本大部分都是c++的，然后我想自己就通过Java来实现，毕竟用java来实现算法要容易的多，同时也易于理解。
我想从以下几个方面来阐述解决8数码问题的方法
1 了解A*算法
2 A*算法的伪代码
3 如何在8数码问题中应用A*算法（即建立合适的启发式）
4 8数码问题比较特殊，需要判断是否有可行解
5 实现A*算法在8数码问题中的应用
1 了解A*算法
在网上看了很多文章，发现一篇感觉很好的阐述了A*算法的。连接如下：A*算法
1，从起始状态A开始，并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的其他状态，也可能不会。基本上，这是一个待检查方格的列表。
2，寻找起点周围通过上下左右移动所有可到达的状态。也把他们加入开启列表。为所有这些状态保存状态A作为“父方格”。当我们想描述路径的时候，父方格的资料是十分重要的。后面会解释它的具体用途。
3，从开启列表中删除状态A，把它加入到一个“关闭列表”。
4 取出开启列表中fvalue最低的状态，判断该状态性质
(1) 如果在开启列表中出现，那么判断该状态的gvalue通过当前节点（从open中取出，扩展出该节点的节点）作为父节点带来的gvalue 是否小于原先的父节点，若小于则需要更改它的父节点以及gvalue.
(2) 如果在关闭列表中出现，那么判断该状态的gvalue通过当前节点（从open中取出，扩展出该节点的节点）作为父节点带来的gvalue是否小于原先的父节，若小于则需要从关闭列表中删除该节点，并且将其加入开启列表，并更改其父节点为当前节点。
(3) 既不在开启列表，也不在关闭列表，这样就很简单，直接加入开启列表中就行（保持开启列表升序排列）
(4) 如果取出的节点为目标节点，则成功退出
2 A*算法的伪代码
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表;
while(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点){
break;
}
for(当前节点n 的每个子节点X)
{
算X的估价值;
if(X in OPEN)
{
if( X的估价值小于OPEN表的X估价值 ){
把n设置为X的父亲;
更新OPEN表中的估价值; //取最小路径的估价值
}
}
if(X inCLOSE) {
if( X的估价值小于CLOSE表的X估价值 ){
把n设置为X的父亲;
将该节点从close表中除去
把X节点放入OPEN //取最小路径的估价值
}
}
if(X not inboth){
把n设置为X的父亲;
求X的估价值;
并将X插入OPEN表中; //升序排列open
}
}//end for
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//end while(OPEN!=NULL)
保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
3 如何在8数码问题中应用A*算法（即建立合适的启发式）
A*算法有个计算公式 f(x) = g(x)+h(x)
其中g(x)为从起始状态到当前状态所消耗的步数，h(x)为一个启发值，估算从当前状态到目标状态所需的步数，一般h(x)小于等于实际需要步数为好，这样不会将最优解忽略，因为h(x)和解空间有一些关系，如果h(x)设置的比实际需要的步数多，那么解空间就有可能将最优解忽略。举个例子吧，宽度优先搜索就是h(x)=0带来的效果，深度优先搜索就是g(x)=0带来的效果，不过h(x)距离h*(x)[实际需要的步数]的程度不能过大，否则h(x)就没有过强的区分能力，算法效率并不会很高。对一个好的h(x)的评价是：h(x)在h*(n)[实际需要的步数]的下界之下，并且尽量接近h*(n)[实际需要的步数].
那么8数码问题g(x) 为经过上下左右移动空格附近的数字来得到新状态所需步数，h(x)为当前状态与目标状态的距离，就是所有不在目标位置的数字总和，必然小于h*(x)
4 8数码问题比较特殊，需要判断是否有可行解
网上的一般解法，就是通过逆序数的奇排列偶排列判断，可以在这看到逆序数介绍
当目标状态的奇偶性质和初始状态的奇偶性质相同时，才能够进行转换，具体原理我不清楚,还需要查查。
评论