算法笔记:使用A*算法解决八数码问题
coursera上普林斯顿大学算法课中第四周的作业,使用A*算法解决八数码问题。
作业的具体要求如下:https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/specification.php
我提交的作业(90分):https://github.com/caozixuan/AlgorithmLearning/tree/master/Exercise/8Puzzle/src
题目要求
八数码问题是一个十分经典的问题,我相信大家小时候肯定都玩过这个游戏。在这个问题中,我们需要设计一个算法,能够快速的找到通向答案的路径。把所有的标签放在应该放置的位子上(题目并不一定是九宫格)。
辅助知识
优先权队列
优先权队列的知识具体可见我的这篇博文 算法笔记:优先权队列
在本次作业中,我们利用优先权队列去储存每一个状态节点极其对应的权值。
A*搜索算法
提到搜索算法,我们首先要明白,搜索算法是干什么的?比较简单的说,搜索算法就像导航软件,是帮助我们找路的。当你站在街上茫然四顾,你就需要你的导航软件,告诉你,前面的几条路,你应该走哪一条。搜索算法也是如此,告诉你应该做什么决策,进入什么状态。
回想一下,我们之前学过哪些搜索算法,比如BFS,DFS,这两种算法告诉你基于宽度优先或者深度优先的原则进行搜索,A*算法要相对复杂一些,它是根据一个评估函数来进行决策的。在评估过程中,我们不断通过将与当前状态相邻的节点加入队列,每次取出评估函数最小的点,继续加入其相邻节点,直到找到其目标为止。下图展示了上述的过程:
下面我们来聊一聊这个评估函数。在A*算法中,这个评估函数被分成了两部分,我们目前已经付出的代价G和我们预计从当前点到目标点还要付出的代价H。已经付出的代价在这个问题中,我们可以认为G = the number of moves,走了一步G就是几,对于H,原链接中给了两种方案,一个是目前有几个数码块还不在它应该在的位置上,另一个是所有数码块与其应该在的位置的曼哈顿距离的和。
需要注意的地方
排除冗余状态
这个地方在原链接中讲的很清楚,大家可以思考一下,什么情况下会出现将相同的状态加入队列的情况。
无解的情况
这个地方困扰了我好久,资料中说到了一个定理,一个有界的状态随意交换两个数码,一定会变成无解的状态。无解的状态,随意交换两个数码,也就一定会变成有解的状态。我们要怎么根据这个定理去判断当前的状态可不可解呢?这个地方的难点是A*算法也没有给你一个范围,告诉你某个规模的问题在多少步内可以求解。后来发现其实很简单,在求解某个问题前,把这个问题变成两个问题,一个是旧问题,一个就是把旧问题中任意两个数码交换。两个问题同时求解。旧问题先得到答案,说明这个问题有解,如果新问题得到答案,就说明旧问题无解。KO!
关键代码
public Solver(Board initial){
GameTreeNode root = new GameTreeNode(initial, null);
GameTreeNode rootTwin = new GameTreeNode(initial.twin(),null);
MinPQ<GameTreeNode> q = new MinPQ<>();
MinPQ<GameTreeNode> qTwin = new MinPQ<>();
q.insert(root);
qTwin.insert(rootTwin);
while(true)
{
GameTreeNode curNode = q.delMin();
if(curNode.board.isGoal())
{
canSolve = true;
solveNode = curNode;
break;
}
else
{
for(Board b:curNode.board.neighbors())
{
if (curNode.father == null || !b.equals(curNode.father.board)) {
GameTreeNode node = new GameTreeNode(b, curNode);
q.insert(node);
}
}
}
GameTreeNode curNodeTwin = qTwin.delMin();
if(curNodeTwin.board.isGoal())
{
canSolve = false;
solveNode = null;
break;
}
else
{
for(Board b:curNodeTwin.board.neighbors())
{
if(curNodeTwin.father==null||!b.equals(curNodeTwin.father.board))
{
GameTreeNode node = new GameTreeNode(b,curNodeTwin);
qTwin.insert(node);
}
}
}
}
}