您现在的位置:主页 > java教程 > 思维拓展 > >

A*算法原理图文详解



时间: 2015-03-04 10:04     来源 : IT学习者      点击:

关键词: java算法    A*   


 
目录页:《java算法一百天




首先了解一下A*算法的基本设计思想,以下是援引百度百科的解释 IT学习者(www.itxxz.com)

(A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索算法。之后涌现了很多预处理算法(ALT,CH,HL等等),在线查询效率是A*算法的数千甚至上万倍。
公式表示为: f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数,
g(n) 是在状态空间中从初始节点到n节点的实际代价,
h(n) 是从n到目标节点最佳路径的估计代价。
保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:
估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行, 此时的搜索效率是最高的。
官网:http://www.itxxz.com


然后我们通过图文结合的形式来解释下,如下图:




图中有这么几个要点先需要了解

1、类似迷宫图,分开始节点(start)、障碍物、结束节点(end),我们需要从start节点探寻一条到end节点的路线

2、对于探寻的每一步,都会以当前节点为基点,扫描其相邻的八个节点 内容来自www.itxxz.com

3、计算当前节点与start节点及到end的距离

4、计算出最短路径


如果明白了上面的场景描述,下面就可以进行分析了。

在A*算法中,核心思想是一个公式,上面已经提到过:
f(n)=g(n)+h(n)

仅通过文字可能有些朋友不是很了解,下面我们就举例说明:

以start节点为例,探寻相邻的八个节点,且只能上下左右移动,每移动到邻近的单元格,我们认为行走了一个距离。

比如从start移动到A节点,就移动了两个距离,从A节点移动到end节点(此时忽略障碍,仅计算距离)。

这时公式中的g(n)就可以理解为g(A)=2,h(n)就理解为h(A)=6,

内容来自www.itxxz.com



f(n)就是start节点到end节点的实际距离,公式描述为:f(A)=g(A)+h(A)=8。

于是就有了A节点的数字描述——f(n)位于左上方,g(n)位于左下方,h(n)位于右下方。

同理,可计算出f(B) = g(B) + h(B) = 1 + 5 = 6 

这时start相邻的其它节点变都可以计算出来了


现在理念明白了,该如何实现呢?

可以通过对相邻节点的便利及父节点的不断嵌套来形成一条路径。

比如我们把start相邻的所有节点进行便利比较,选出f(n)最小的一个节点(我们称为X节点),并设置X节点的父节点为start节点,并以X节点为当前节点,再判断X节点周围的有效节点(如障碍物完全可以忽略),选出f(n)最小的节点后设置X节点为其父节点,依次类推,就形成了一条节点线,这个算法也就完成了。
IT学习者(www.itxxz.com)


源码及打印结果见《
A*算法-java代码实现

这是用java swing做的一个迷宫的动态图形界面,就是用的A*算法,喜欢的朋友可以娱乐一下:《
java迷宫_A*算法实现

 






文章除注明转载外,均为IT学习者原创或编译
欢迎任何形式的转载,但务必请以超链接形式注明出处
本文出自:IT学习者
链接地址:http://www.itxxz.com



微信公众号:喝咖啡的螃蟹

喝咖啡的螃蟹
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
  • VVBear
    2017-02-23 22:05:04发表

    看这篇终于看懂A-Star算法了,感谢作者。

  • 老实憨厚的李狗蛋
    2016-12-22 15:31:40发表

    清晰易懂,比某些长篇大论有用得多

-->