A star 寻路

简介

1968年，的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此，一种精巧、高效的算法------A*算法横空出世了，并在相关领域得到了广泛的应用。

启发式搜索算法

启发式搜索算法就是当前搜索节点在选择下一步节点时，可以用过一个启发函数进行计算代价，选择代价最小的节点作为下一步搜索节点

A*估值函数

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

  • f(n):从初始状态经由状态n到目标状态的代价估计

  • g(n):是在状态空间中从初始状态到状态n的实际代价

  • h(n):是从状态n到目标状态的最佳路径的估计代价

路径搜索问题中，状态就是节点，代价就是距离

运行机制

  • 使用两个状态表Open和Clodes。Open表由待考察的节点组成，Closed表由已经考察过的节点组成

  • 当一个节点已经被检查过所有与它相邻的节点，计算出了这些节点的f(n)，并把其放入Open表，那么这个节点就放入Closed表

  • 开始时，Closed表为空，Open表仅包含起始节点，每次迭代中，将Open表中最小代价的节点进行检查，如果不是目标节点，则进行以下处理：

    1. 如果相邻节点不在两个表中，则将其插入Open表中

    2. 如果相邻节点在Open表中，则对比新旧路径的代价值并取最低的存入Open表

    3. 如果相邻节点在Close表中，则对比新旧路径的代价值，如果新路径更低，则移出Closed表，加入Open表

  • 重复以上步骤，如果到达目标节点前，Open表为空，则意味着没有可达的路径

寻路方式

  • 基于单元格的导航图

  • 基于可视点的导航图

  • 导航网络

估价算法

曼哈顿距离(Manhattan distance)

  • 不考虑斜向移动的情况，直线运动的代价为 P/单位

h(n)=P×(ABS(n.x−goal.x)+ABS(n.y−goal.y))h(n)=P × (ABS(n.x-goal.x) + ABS(n.y-goal.y))

切比雪夫距离(Chebyshev distance)

  • 对于对角线和直线运动的代价都为 P/单位 的时候（类似西洋棋中的王）

h(n)=P×MAX(ABS(n.x−goal.x),ABS(n.y−goal.y))h(n)=P × MAX(ABS(n.x-goal.x),ABS(n.y-goal.y))

  • 对角线(diagonal)运动在实际生活中运动的代价跟直线(straight)运动的代价(P/单位)并不同，对角线运动的代价一般类似于

    P0=2PP_0=\sqrt{2}P
h(n)=P0×hdiagonal(n)+P×(hstraight(n)−2×hdiagonal(n))h(n)=P_0 × h_{diagonal}(n)+P × (h_{straight}(n) - 2 × h_{diagonal}(n))

欧几里得距离(Euclidean distance)

  • 欧氏距离就是两点之间直线距离

h(n)=P×(n.x−goal.x)2+(n.y−goal.y)2h(n)=P × \sqrt{(n.x-goal.x)^2 + (n.y-goal.y)^2}

  • 注意：计算平方根将会消耗资源比较多，所以此方法基本不被使用

参考资料

https://www.redblobgames.com/pathfinding/a-star/introduction.html

Previous一致性哈希分布Next蓄水池抽样 Reservoir Sampling

Last updated

Was this helpful?