a* 搜索算法实现原理( a-star )

weblog 3040 0 0

a*搜索算法 动态演示分析 请参考   http://photo.jiajiajia.club/item/a-star.html

什么是a*搜索算法

        A*搜寻算法,俗称A星算法,作为启发式搜索算法中的一种,这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。

--------来自百度百科

a*搜索算法的核心公式(启发式函数)也即路径评分

F(n)= G(n) + H(n)

G(n)是开始节点到当前节点实际的移动代价

H(n)是当前节点到目标节点的预估移动代价(文章后边使用的是平方后的欧几里得距离来计算,或曼哈顿距离)

F(n)是G(n)和H(n)代价的总和

那么根据找个公式,可以首先想到搜索路径的过程中总是要F(n)值较小的那个  (即走的路径较近,距离目标节点也较近,那么遍历这个节点的价值就高)。

算法描述

首先有两个集合1.优先队列openList【后面搜索过程中将要被关注的集合元素】,2.closeList搜索过程中后面不需要关注的集合

1.将开始节点放进优先队列

2.如果优先队列中还有元素

3.从优先队列中取出一个元素(F(n)值最小的元素)

4.遍历该元素的相邻元素(上下左右四个方向,条件是该节点没有被遍历过,即不是openList或closeList中的数据),计算其fn,gn,hn的值。并将其加入优先队列。

5.如果该元素是目标节点,即结束算法,找出最短路径(输出)

6.如果该元素不是目标节点,将此元素加入closed【此后搜索过程中不需要被关注的集合元素】列表,然后继续执行过程 2 

那么了解了启发式函数,和算法描述以后就已一个例子来可以大致分析一下算法过程

案例:求红色节点到蓝色节点的路径

        根据对上述算法的理解,开始先将红色节点加入优先队列中,然后从优先队列中取出一个元素(如果队列中有元素),那么当前节点明显不是目标节点,那么将其加入closeList列表,然后遍历其周围的四个方向的节点,并且计算出fn【左上角】,gn【左下角】,hn【右下角】的值,而且还要记住他的父节点是哪一个(即从来过来的)一会还要反过来推他的路径,最后将其加入优先队列中。

        此时优先队列中的有四个元素(不为空),然后取出一个fn值最小的元素,即取出fn值为100的元素,然后执行的过程和上边执行的过程一样。执行完以后如下图

        此时优先队列中有5个元素【五个黄色的节点,橘红色节点为closeList中的节点,即已经遍历过的节点】,但是目前还没有到达目标节点。继续搜索,那么此时openList中有两个fn值最小的元素,选哪一个呢?随缘吧~

按照算法描述继续搜索

此处省略3张图........

直到最后遍历到下边这样

就快找到答案了,此时优先队列中有12个元素,fn值最小的是80那个节点的元素,也是目标节点元素。那么下一步将是~

最终遍历到了目标节点,算法结束。

        因为每次加入openList结合中的节点都记录了父节点的信息,那么就可以通过目标节点开始往前推,最终到达开始节点,那么这条路径就是我们要找的那条路径。

a*的实现原理就介绍完毕了。

猜你喜欢
数据结构与算法 835 上一篇:广度优先(bfs、广)java-数据结构和用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 799 广度优先(dfs、深)java-数据结构和用邻接矩阵表示图的定点之间的关系如下图的数据结构:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
weblog 3544 前言了解a*请参考:http://www.jiajiajia.club/official/weblog/32a*动态演示分析,及代码,请参考:http
数据结构与算法 8053 问题描述思路:典型的广度优先,根据字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口的一条路径就是符合
java基础 581 java集合之TreeMapTreeMap集合的说简单也简单说复杂也复杂,说简单是因为TreeMap底层完全依靠红黑树这个数据结构,相比与HashMap来说TreeMap不用考虑
数据结构与算法 1240 ; publicNode(intvalue,Nodenext){ super(); this.value=value; this.next=next; }}packageclub.test;/***
数据结构与算法 5055 科普:第一篇二分论文是1946年发表,然而第一个没有bug的二分查找却是在1962年才出,中间用了16年的时间。定义在计机科学中,二分查找(英语:binarysearch),也称折半
official 166 进程互斥的软件单标志,双标志先检查、双标志后检查、Peterson学习提示:解各个的思想、结合上小节学习的“互斥的四个逻辑部分”,重点解各在进入区、退出区都做了什么
目录