Dijkstra算法和A*算法总结

2024-06-15 19:03| 来源: 网络整理| 查看: 265

Dijkstra算法和A*算法都是最短路径问题的常用算法，下面就对这两种算法的特点进行一下比较：

Dijkstra算法计算源点到其他所有点的最短路径长度，A*关注点到点的最短路径(包括具体路径)。Dijkstra算法建立在较为抽象的图论层面，A*算法可以更轻松地用在诸如游戏地图寻路中。Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。由第一点，当目标点很多时，A*算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得具体路径而只比较路径长度时，Dijkstra算法会成为更好的选择。

启发函数的性质

那么能不能综合上面Dijkstra算法得到最优解和贪心算法速度快的特点，有更好的办法呢？【注意一下这个地方，Dijkstra算法是适用于任何图算法找最短距离均可的，但是用到启发式算法的话，大部分情况下会是一个方格图，因为只有方格图才能比较好的估算从当前点到终点的距离】那么我们可以先定义一个估算函数

f(n)=g(n)+h(n) 其中 g(n) 表示起点到当前点 n 实际走的代价， h(n) 表示当前点 n 到终点的估算代价。所以上面两个合起来就是其走当前点到终点的总代价函数 f(n) 而 h(n) 这个估计函数不同的估计情况，结果也不会相同。

先考虑极端情况，如果 h(n)=0 的情况下，只有 g(n) 起作用，那么A*算法就是Dijkstra算法。如果 h(n) 始终小于等于实际 n 点到终点的距离，那么必然能够保证A*算法找的解就是最优解。而且 h(n) 越小，则A*扩展的节点也就越多，A*算法运行的也就越慢。如果 h(n) 始终都等于实际 n 点到终点的距离，那么A*算法只会严格走从起点到终点的最短路径。虽然这种情况一般不可能发生，当然一些特殊情况下会发生【比如没有障碍物的情况】。如果 h(n) 有时候大于实际 n 点到终点的距离，那么不能保证A*算法能够找到最短路径另外一种极端情况，就是如果只有 h(n) 发挥作用，则A*算法就相当于贪心算法。

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章