欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法笔记:使用A*算法解决八数码问题

程序员文章站 2024-01-08 13:22:52
...

coursera上普林斯顿大学算法课中第四周的作业,使用A*算法解决八数码问题。

作业的具体要求如下:https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/specification.php

我提交的作业(90分):https://github.com/caozixuan/AlgorithmLearning/tree/master/Exercise/8Puzzle/src

题目要求

八数码问题是一个十分经典的问题,我相信大家小时候肯定都玩过这个游戏。在这个问题中,我们需要设计一个算法,能够快速的找到通向答案的路径。把所有的标签放在应该放置的位子上(题目并不一定是九宫格)。

算法笔记:使用A*算法解决八数码问题

辅助知识

优先权队列

优先权队列的知识具体可见我的这篇博文 算法笔记:优先权队列

在本次作业中,我们利用优先权队列去储存每一个状态节点极其对应的权值。

A*搜索算法

提到搜索算法,我们首先要明白,搜索算法是干什么的?比较简单的说,搜索算法就像导航软件,是帮助我们找路的。当你站在街上茫然四顾,你就需要你的导航软件,告诉你,前面的几条路,你应该走哪一条。搜索算法也是如此,告诉你应该做什么决策,进入什么状态。

回想一下,我们之前学过哪些搜索算法,比如BFS,DFS,这两种算法告诉你基于宽度优先或者深度优先的原则进行搜索,A*算法要相对复杂一些,它是根据一个评估函数来进行决策的。在评估过程中,我们不断通过将与当前状态相邻的节点加入队列,每次取出评估函数最小的点,继续加入其相邻节点,直到找到其目标为止。下图展示了上述的过程:

算法笔记:使用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);
                    }
                }
            }

        }



    }

 

上一篇:

下一篇: