迷宫难点求解之

摘要:在迷宫难点求解之“穷举+回溯”(一)那篇文章中运用“穷举+回溯”的思辨,纵然能从迷宫的输入到讲话寻找一条轻易路线,可是寻找来的不是最优路线。因而本文选用A*找出算法,求解迷宫难点的最优路线。

1 A*寻觅算法简单介绍

A*寻找算法是一种启发式搜索算法。所谓启发式找出算法,正是在盲目寻找算法中参预四个启迪函数,在日前节点寻觅落成后,通过这么些启发函数来进展计算,选用代价最少的节点作为下一步寻觅的节点。通过如此的秘诀就可以找到最优解。

DFS,BFS那二种检索格局都属于盲目标查找方式,它不会在增选下二个节点的时候实行代价总括,而是遵守三个定位的办法选拔,那样在时局糟糕的意况,会对具有节点开始展览遍历。

A*寻找算法的焦点就在于怎么着筹算叁个好的诱导函数,启发函数的表明格局一般如下:
$$
f(n)=g(n)+h(n)
$$
当中$f(n)$是每种节点恐怕的估值可能代价值,它由两有些构成。

  • $g(n)$:它象征从源点到寻觅点的代价。
  • $h(n)$:它表示从寻觅点到对象点的代价,$h(n)$设计的好坏,直接影响到该A*算法的功能。

一种具备$f(n)=g(n)+h(n)$攻略的启发式算法能成为A*算法的尽量标准是:

  1. 寻觅树上存在着从先导点到终了点的最优路线。

  2. 难题域是少数的。

  3. 具有结点的子结点的追寻代价值都当先零。

  4. h(n)=<h*(n) (h*(n)为实在难点的代价值)。

很扎眼,1,2,3点都很轻松满意的。关键是计划多少个好的$h(n)$函数。

2 A*寻觅算法描述

A*算法的流水生产线如下:

A*寻觅算法须要七个附加的积存空间,OPEN表和CLOSE表。

  1. 早先化OPEN和CLOSE表,将启幕节点(起第4节点的H和G的值都视为0)放入OPEN表中。

  2. 再也下边步骤:(循环)

    2.1
    在起来列表中寻觅具备最小F值的节点,并把查找到的节点作为当下节点;

    2.2 把目前节点从OPEN列表中删去,并投入到CLOSE列表中;

    2.3 对当下节点相邻的每二个节点依次推行以下步骤:(遍历) i
    假如相邻节点不可通行也许该节点已经在CLOSE列表中,则什么操作也不实行;
    ii
    如若该相近节点不在OPEN列表中,则将该节点加多到OPEN列表中,并将该相邻节点的父节点设置当前节点,同不经常间总括保存相邻节点的F值;iii
    假如该相近节点在OPEN表中, 则剖断若经由当前节点达到该相近节点的F值是不是低于原本保存的F值,若小于,则将该周边节点的父节点设为近来节点,并再次安装该周边节点的F值.

    2.4
    若当终点节点被投入到支付列表作为待查验节点时,表示路线已找到,此时应适可而止循环;若当开放列表为空,表示并未中起首节点到极限节点的门道,此时轮回甘休;

  3. 循环终止后,从终端节点伊始沿着父节点往前遍历,从后到前输出寻觅的路径。

其间,步骤2.3
ii中的棕色部分进一步首要,设置相邻节点的父节点为当前节点是为着记录从早先节点到终止节点路线,方便寻觅到了巅峰节点后进行路线输出。

在采用A*
算法对迷宫路线求解中,$g(n)$和$h(n)$函数都施用曼哈顿距离,曼哈顿距离代表四个点在行业内部坐标系上的相对化轴距总和。
$$
d(i,j)=|x1-x2|+|y1-y2|
$$
即每一回获得的此时此刻通道块,都会对其到进口通道快和出口通道块的曼哈顿距离进行测算。求算当前通道块的F值举办保存。该函数满意启发式算法成为A*算法的放量标准的1,2,3,4。

还亟需注意的少数是:使用A*求解迷宫路线算法中,要求把2.3手续上边包车型地铁遍历操作进行改变,如下:

i
假若相邻节点不可通行大概该节点已经在CLOSE也许OPEN列表中,则什么操作也不推行。

ii
若是该周边节点不在OPEN和CLOSE列表中,则将该节点增添到OPEN列表中,并将该相邻节点的父节点设置当前节点,同有时候总括保存相邻节点的F值。

在迷宫求解中使用A*寻找算法不供给去创新OPEN表中的已存在节点的F值,因为各种节点的岗位都以规定的,所以曼哈顿距离就定位的。如若是带权值的路网求解最短路线,那么就供给去立异OPEN表中节点的F值,如Dijkstra算法。

3 程序达成

上面选择使用c#语言,实现A*算法求解迷宫最优的渠道。关键代码如下:

3.1 节点实体类

class PathNode
{
    public PathNode(int row, int col)
    {
        this.Row = row;
        this.Col = col;
    }
    public int Row;
    public int Col;
    public int F=int.MaxValue;
    public PathNode Father=null;//该节点的前继节点
}

3.2 A*搜索类

class AStartSolution
{
    int [,]map;
    int startX;
    int startY;
    int endX;
    int endY;
    public AStartSolution (int [,]map,int startX,int startY,int endX,int endY)
    {
        this.map=map;
        this.startX =startX;
        this.startY=startY;
        this.endX=endX;
        this.endY=endY ;
    }
    /*路径寻找*/
    public  PathNode FindPath()
    {
        PathNode endNode = null;//终点
        List<PathNode> openList = new List<PathNode>();
        List<PathNode> closeList = new List<PathNode>();
        //把起点放入open列表中
        PathNode startNode = new PathNode(startX, startY);
        openList.Add(startNode);
        int tryCount = 0;
        while (openList.Count != 0)
        {
            tryCount++;
            PathNode curMinFNode = GetMinFPathNode(openList);
            openList.Remove (curMinFNode );//从open列表中移除
            closeList .Add (curMinFNode );//加入到close列表中
            if (curMinFNode.Row == endX && curMinFNode.Col == endY)//当前节点是目标节点
            {
                endNode = curMinFNode;
                break;
            }
            else//搜索4个方向并进行处理
            {

                //东
                HandleChildNode(curMinFNode, curMinFNode.Row, curMinFNode.Col + 1, openList, closeList);
                //南
                HandleChildNode(curMinFNode, curMinFNode.Row+1, curMinFNode.Col, openList, closeList);
                //西
                HandleChildNode(curMinFNode, curMinFNode.Row, curMinFNode.Col-1, openList, closeList);
                //北
                HandleChildNode(curMinFNode, curMinFNode.Row-1, curMinFNode.Col, openList, closeList);
            }
        }
        return endNode;
    }

    /*处理每个方向的子节点*/
    private  void HandleChildNode(PathNode curMinFNode,int row, int col, List<PathNode> openList, List<PathNode> closeList)
    {
        PathNode child = null;
        if (Pass(row, col))//能通过
        {
            child = new PathNode(row, col);
            if (!IsExistList(child, closeList) && !IsExistList(child, openList))//
            {
                child.F = GetF(row,col);
                child.Father = curMinFNode;
                openList.Add(child);
            }
        }
    }
    private PathNode GetMinFPathNode(List<PathNode> openList)
    {
        int minF= openList.Min(node =>node.F);
        foreach (PathNode node in openList)
        {
            if (node.F == minF)
            {
                return node;
            }    
        }
        return null;
    }
    /*该通道块是否可通行*/
    private  bool Pass(int row,int col)
    {
        int rowCount = map.GetLength(0);
        int colCount = map.GetLength(1);
        //边界判断
        if (row >= 0 && row < rowCount && col >= 0 && col < colCount)
        {
            //障碍判断
            if (map[row, col] == 2)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
        else
        {
            return false;
        }
    }

    /*当前通道块是否在OPEN或者CLOSE表中*/
    private  bool IsExistList(PathNode childNode, List<PathNode> list)
    {
        foreach (PathNode node in list)
        {
            if (node.Row == childNode.Row && node.Col == childNode.Col)
            {
                return true;
            }
        }
        return false;
    }

    /*计算当前节点的F值*/
    private  int GetF(int curRow, int curCol)
    {
        int g = Math.Abs(startX - curRow) + Math.Abs(startY - curCol);
        int h = Math.Abs(endX - curRow) + Math.Abs(endY - curCol);
        return g + h;
    }
}

3.3 与“穷举+回溯”算法的效能相比

利用同样的迷宫地图相比二种算法查找的路子,上结果图代表“穷举+回溯,下结果图代表本程序

图片 1

图片 2

4 总结

经过地点的可比可以窥见,A*寻觅算法搜索的门路比“穷举+回溯”算法的要短非常多,和自家布署迷宫地图时所想的门径是同等,是一条最优的渠道。

5 财富和参照他事他说加以考察资料

参照他事他说加以考察资料:

莫水千流的博文A星寻路算法介绍
西芒xiaoP的博文A*搜索算法
yueming的博文A*门路搜索算法入门 

源码地址:

http://download.csdn.net/download/mingge38/9655373