+18888889999
诚信为本:市场永远在变,诚信永远不变。

A* 算法及优化思路

你的位置: 首页 > 门徒平台资讯

A* 算法及优化思路

2024-04-22 14:16:21

在介绍A星算法之前,先聊聊Dijkstra算法与最佳优先算法(BFS)

Dijkstra算法

Dijkstra算法的思路是从起点开始,向外扩散搜索,从树结构上观察就是广度优先搜索,把每一层的节点都尝试搜索一下,直到搜索到目标节点,则搜索完毕,认为找到了最短路径,出于广度优先的搜索方式,意味着搜索过程中效率并非是最高的,因为整个搜索过程,很多节点都是无意义的搜索。

下图是Dijkstra算法执行的示意图


最佳优先算法(BFS)

最佳优先算法(BFS)是带有启发式的,它评估的是任意节点到目标节点所需要的代价,这与选择离起始节点代价最小不同的是,它选择的是离目标点代价最小,所以这不能保证搜索的路径是最短的,但是却可以保证搜索效率是最快的,当然找到的路径可能不是期望的。因为它未把从起始点的代价算进去,进行的是贪心算法的搜索,所求出来的路径不是最佳路径。

下图是BFS算法搜索的示意图

BFS算法的搜索得到非最优解

下图得到的解是非最优解,搜索过程中,直接搜索到死胡同中去了。

下图是BFS搜索示意图,虽然效率不高,但是确实找到了最优解。

A星算法

启发式搜索就是在状态空间中的搜索,首先对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
启发中的估价是用估价函数表示的,如:f(n)=g(n) + h(n)
其中f(n) 是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。如果说详细点,g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时,可以省略g(n),而提高效率。

考虑到Dijkstra算法与BFS算法都有缺点,因此结合两个算法的优点,得到的就是A星算法。

表示方程式如下

f(n)=g(n) + h(n)

g(n)表示 从起始节点到 n 节点所需要的代价。

h(n)表示 从n节点到目标节点所需要的代价。

f(n)点的价值全取决于 g(n) 与 h(n)

h(n) 对A星算法的影响

  • h(n) 等于0,那么意味着 f(n)=g(n) , A星算法变成了Dijkstra算法
  • 如果h(n) 小于 实际 cost(n) 代价,A星算法可以找到最短路径,但是搜索效率略低,h(n)越小,意味着搜索节点越多,效率上越低,但是精度上越准确,越接近最优解,因为趋近于Dijkstra算法。(cost(n) 表示实际从n节点到目标节点的代价 )
  • h(n) 等于 cost(n),是A星最优状态。
  • h(n) 远远大于 g(n) ,那么 f(n)的值就主要取决于 h(n),A星就演变成了BFS算法。

A星算法的优化

  • 动态衡量启发式f(n)=g(n) + w(n) * h(n) , 其中 w(n) >=1 。与传统的A星不同的是,原本的h(n) ,变成了 w(n) * h(n) , w(n) 可以影响评估值。在搜索过程中,我们可以通过改变w(n) 来影响搜索过程如上面提到的 h(n) 对A星算法的影响。可以推理出,w(n) 越大,越趋近于BFS算法,而 w(n) 相对越小,则相对于趋近于Dijkstra算法。


  • 简化搜索空间:传统的A星算法是效率并不高的算法,常常会因为搜索空间的太大,而影响搜索效率。
    • 分级寻径:把搜索过程拆分开了,如查找空间A中的p1点到空间B中的p2点最短路径,那么可以分为两部分,先查找p1点到空间B的路径,再搜索到p2的路径,整个过程分为了两步,甚至是将计算一次的消耗,拆分成了两次,计算压力也变小了
  • 优化Open表:传统的Open表,因为语言的不同,可能选择的是:Array、List、Queue等等结构来存储。而在A星搜索过程中,随着搜索深度越深,意味着可能要查找的节点越多,后期Open表中存储的节点越点。在数据结构的选择上,我们希望所选择的节点带有“可参照性”,而不是单单的直接从Open表中取。如果Open表在放入数据之前,我们就让它按照一定顺序,那么我们从Open表中取数据时,这些数据就是具备顺序的,是有“可参照性的”。可以选择优先队列的方式。

地址:海南省海口市玉沙路58号  电话:0898-66889888  手机:18888889999
Copyright © 2012-2018 门徒-门徒娱乐-注册登录站 版权所有 ICP备案编:琼ICP备88889999号 

平台注册入口