【规划】A算法以及c++实现_a算法 c++

作者：从前慢现在也慢 | 2024-05-02 21:32:25

踩

a*算法 c++

A*算法

A*算法的核心在于估价函数的设计上，如下式所示：

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

其中 $g(n)$ 称为耗散函数，表示从起始节点 $n_{start}$ 到节点 n 的实际代价； $h(n)$ 称为启发函数，表示节点 $n$ 到目标节点 $n_{goal}$ 的估计代价； $f(n)$ 表示从起始节点经由节点 $n$ 到目标节点的估计代价。

同Dijkstra算法类似，A*算法也维持一个Open表。Open表中节点的优先级是依据 $f(n)$ 的大小排列的， $f(n)$ 值越小，被搜索到的优先级越高。为保证能搜索到最优解，启发函数 $h(n)$ 不能太大，不能大于节点 $n$ 到目标节点的实际代价；但如果 $h(n)=0$ ，则A*算法退化为Dijkstra算法，虽能保证得到最优路径，但算法效率低；如果 $h(n)$ 恰好等于节点 $n$ 到目标节点的实际代价，则A*算法探索的节点恰好就是最优路径上的节点。所以 $h(n)$ 的取值直接影响算法的速度和精确度，常见的 $h(n)$ 的取值有两点之间的欧几里得距离(Euclidean Distance)和曼哈顿距离(Manhattan Distance)等。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/526221

【规划】A*算法以及c++实现_a*算法 c++

A*算法

【规划】A算法以及c++实现_a算法 c++