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

weblog 精帖
2344

a*搜索算法 动态演示分析 请参考   http://www.jiajiajia.club:8089/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*的实现原理就介绍完毕了。

猜你喜欢
  • blog asm例对象方的调用

    asm例对象方的调用1.需要的jar包2.我们需要通过asm生成的目标类如下:package club.jiajia.test3;public class Examp5 { public int method(){ Abc a=new
  • blog java五子棋(AI

    java五子棋人机对战package fir;import java.awt.*; import javax.swing.JPanel; /** * 有背景图片的Panel类 * @author tntxia */ publ
  • blog java完美html转pdf

    java完美html转pdf1.pom依赖:<dependency> <groupId>com.itextpdf</groupId> <artifactId>itext
  • blog -特别数的和

    问题描述:思路:遍历1-n个数,判断是否满足条件。代码:package club.test;public class TestMain11 { public static void main(String[] args) { int nu
  • blog websocketweb上传文件进度条

    上次我们说了spring集成websocket,用websocket通讯集成配置连接:http://www.jiajiajia.club/weblog/blog/artical/128下面来模拟一次上传文件的进度条
  • ofc 图解Dijkstra过程(java代码)

    图解Dijkstra过程(java代码)
  • blog 递归全排列 c++描述

    递归全排列 c++描述#includeusing namespace std;//交换void exchange(int *a,int i,int j){ if(i==j){ return ;
  • blog spring aop操作日志记录

    spring aop操作日志记录 此次的目的是 对 controller中的方执行情况进行记录,记录的有方执行时间,操作人,请求的路径,方的入参,模块,功能等。并利用注解的方式对被操作方的简单注释(模块
  • blog java使用欧几里得比例的方

    java使用欧几里得比例的方 public static void main(String[] args) { System.out.println(bili(2,6)); } public static Strin
  • blog 初步探究cglib动态代

    初步探究cglib动态代之前我们说了一下jdk动态代 http://www.jiajiajia.club/weblog/blog/artical/60本章说一下cglib动态代,做个笔记1.按照国际惯例,先来个HelloW