迷宫问题求解的“A*搜索”(二)迷宫问题求解的“A*搜索”(二)

摘要:在迷宫问题求解的“穷举+回溯”(一)眼看篇稿子中利用“穷举+回溯”的思索,虽然能够打迷宫的输入到讲话找有同样条简单路径,但是找出来的免是极度精良路径。因此本文采用A*搜索算法,求解迷宫问题的极度精彩路径。

摘要:在迷宫问题求解的“穷举+回溯”(一)立即篇稿子中采用“穷举+回溯”的思辨,虽然会由迷宫的入口到提找来同长达简单路径,但是找出来的匪是绝理想路径。因此本文采用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)$函数。

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表,将开始节点(开始节点的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算法。

2 A*搜索算法描述

A*算法的流水线如下:

A*搜索算法需要简单独附加的存储空间,OPEN表和CLOSE表。

  1. 初始化OPEN和CLOSE表,将开始节点(开始节点的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 程序实现

下用使用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.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.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 与“穷举+回溯”算法的职能较

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

lovebet体育官网 1

lovebet体育官网 2

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

采取同样的迷宫地图比较少栽算法查找的门径,上结果图代表“穷举+回溯,下结果图代表本程序

lovebet体育官网 3

lovebet体育官网 4

4 总结

由此上面的可比可发现,A*搜索算法寻找的路线比“穷举+回溯”算法的若少很多,和自家计划迷宫地图时所想的途径是同等,是同等长太帅的路径。

4 总结

经者的较足发现,A*搜索算法寻找的门道比“穷举+回溯”算法的假设少很多,和自家计划迷宫地图时所想的不二法门是同,是同长条最精彩的途径。

5 资源和参考资料

lovebet体育官网参考资料:

并未水千淌的博文A星寻路算法介绍
西芒xiaoP的博文A*搜索算法
yueming的博文A*途径寻找算法入门 

源码地址:

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

5 资源以及参考资料

参考资料:

从没水千淌的博文A星寻路算法介绍
西芒xiaoP的博文A*搜索算法
yueming的博文A*路寻找算法入门 

源码地址:

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