上一篇文章我介绍了A*算法,A*用于找到从起始状态到目标状态的一条最短路径,而且根据估价函数的不同,其搜索效率也会有所不同。其实我们只要找到一个估价函数h(s) > 0,那么这个A*算法最后至少要比BFS强。
我们今天来做一个A*算法的实战演练,借此来更透彻的理解A*算法。我们要解决的问题就如题目所述——八数码问题
八数码问题其实非常容易理解,你我在儿时肯定都玩过这样的游戏。
这是一个九宫格,其中有八个格子有数字,还有一个格子是空位,和空位相邻的数字格子可以和空位相互交换,游戏的最终目的就是让这些数字形成一个有序的局面。假如说我们有左边这样一个初始状态,我们现在就是想找到一种最快捷的方法,使左边的初始状态转换为右边的最终状态。


如果按照BFS的思路,我们每次扩展四个节点,分别是空格上移、下移、左移和右移(当然,大多数节点是无法完全扩展这四个方向的),一层层搜索之后,若发现了目标状态,则从目标状态节点开始向父节点回溯,由此就可以得到一个步数最少的解法了。
在之前的文章中也提到了,BFS是盲目的,因此在搜索过程中它搜索了很多“意义不大”的节点。于是我们开始设计一个加入了一定启发信息的A*算法。
在进行算法设计之前,我们先考虑这个算法所需要用到的数据结构,由于我们要解决的问题就是一个简单的九宫格,所以我们可以考虑用一个长度为9的字符串来表示它,并且用数字0表示空位。
我们在搜索过程是不断向下的,因此我们用一个非常大的数组来存储这些状态在搜索树中的情况,并且在每个节点中都加入一个前驱结点的标志pre,方便找到目标状态之后回溯结果。因此我们构成下面这样一个状态的数据结构:

这之中有个状态指针p,它用于标记下一次写入状态数组的位置,当然如果你要是用C++ STL的Vector来保存这些状态的话,就不用考虑这个了。

接下来我们思考一下,如果是我们自己来玩这个游戏,通常会怎么做呢?如果你觉得你的解法非常的无章法,但是最后总是能成功的话,那么请你思考最后你成功前的最后一步,在那个时候,你会观察整个局面,然后吃惊的发现,我只需要将空白位置和其旁边的一个数字对换就可以完成游戏了,其实我们的大脑在思考的时候是这样工作的,如果我挪动了这一步,那么处于不正确位置的数字的个数就变成0。如果按照这个思路,就是说我让我每一步都使尽可能多的数字处于正确的位置,当全部的数字都处于正确位置的时候,我们就达成了目标。
据此,我们来写出解决这个问题的启发函数f(s):

输入的s表示一个状态,index用于查找在搜索树中的此状态,以便获取其深度。
然后我们参看前一篇文章中给出的A*算法模板,写出这个算法:

上面的算法并没有检测扩展结点是否出现在OPEN表中,这也是因为我选用的优先队列实现的表一难以检索,在多数情况下这并不影响什么。
算法中出现了比如isMove的判别函数,由于非常简单,而且和我们算法没有太大的关系,我这里就不给出了。
至此我们的八数码问题就算是解决完毕了~^ ^,是不是对A*算法有了新的认识呢?

8
说点什么

4 Comment threads
4 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
  Subscribe  
最新 最旧 得票最多
提醒
hellomisaki

博主,你的tableone和tabletwo是用普通的栈的么

hack

没检测是否出现在open表中,影响很大吧.

匿名

说实话,看的不是很明白

匿名

h函数很不好啊