原创文章，作者：tloinny，如若转载，请注明出处：古月居 https://www.guyuehome.com/6560

书接上回，上一次我们讲完了Dijkstra，如果小伙伴们有印象的话，肯定还记得在上一篇的文末，我们提到了Dijkstra的致命缺点：处理大地图时效率低下。那么今天我们就来看看Dijkstra的近亲A*究竟做出了哪些改变来解决效率问题？

1. A*原理详解

我们知道，Dijkstra之所以效率低下，就是因为Dijkstra对地图里所有的相邻栅格都“一视同仁”，所以Dijkstra在运行的时候会花费很多精力去访问一些对规划结果没有贡献的节点。形象地说，Dijkstra就像是洪水一般四处扩散，缺乏目的性。而A恰恰就是在目的性这一点上下了功夫，在我看来A就是一波有目的、有梦想的洪水，它知道自己该往哪个地方流。

那么A*究竟是做了什么改变而变得高效的呢？

完整博文请移至古月居：https://www.guyuehome.com/6560