迷宫难点求解之

摘要:在迷宫难题求解之“穷举+回溯”(一)那篇小说中应用“穷举+回溯”的盘算,纵然能从迷宫的输入到讲话找出一条不难路径,不过找出来的不是最优路径。由此本文接纳A*搜索算法,求解迷宫难点的最优路径。

摘要:在迷宫难题求解之“穷举+回溯”(一)那篇小说中央银行使“穷举+回溯”的考虑,即使能从迷宫的输入到讲话找出一条不难路径,不过找出来的不是最优路径。因而本文采纳A*搜索算法,求解迷宫难点的最优路径。

1 A*搜索算法简介

A*搜索算法是一种启发式搜索算法。所谓启发式搜索算法,正是在盲目搜索算法中参预3个启迪函数,在当前节点搜索完成后,通过那个启发函数来展开测算,选取代价最少的节点作为下一步搜索的节点。通过如此的点子就可知找到最优解。

DFS,BFS那三种检索格局都属于盲目标追寻格局,它不会在选用下2个节点的时候进行代价总括,而是服从3个定点的法子选取,那样在命局糟糕的图景,会对拥有节点进行遍历。

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那二种检索格局都属于盲指标追寻格局,它不会在甄选下一个节点的时候举行代价计算,而是服从1个定点的不二法门选取,那样在命局不好的状态,会对拥有节点开始展览遍历。

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 对当前节点相邻的每2个节点依次执行以下步骤:(遍历) 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 财富和参考资料

参考资料:

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

源码地址:

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

5 能源和参考资料

参考资料:

莫水千流的博文A星寻路算法介绍
西芒xiaoP的博文A*搜索算法
yueming的博文A*路线寻找算法入门lovebet体育官网, 

源码地址:

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

相关文章