其他
A*算法
前几期推送详细介绍了比较常见的最短路径算法：
今天介绍最短路径的启发式算法。
01
算法介绍A*算法是一个目标导向的算法。为什么这么说了，这是因为A*在Dijkstra算法的基础上利用了一个启发式函数，该函数被定义为某个节点到目标点的距离（欧式距离、曼哈顿距离等），可以表示为h(u,t)，其中u是任意一个节点，t是目标点，所以A*算法的每个节点的优先值为f(u)=dist(s,u)+h(u,t)。这个启发式函数的作用就是能够让那些靠近目标点的节点先被访问到，从而驱动搜索方向朝目标点方向推进。就是这个小小的改进就可以让算法的效率有一定提升。
它的搜索空间是这样的：
02
算法原理A*算法的基本步骤和Dijkstra算法是一样的，也需要一个优先队列，唯一不一样的便是这个启发值，当你把启发值设为0时，也就是Dijkstra算法。
03
代码这是松弛函数，红色框中便是加入了欧式距离启发值。
04
算法测试测试部分比较了单向Dijkstra算法、双向Dijkstra算法以及A*算法的效率。随机从武汉路网中取了100对OD，分别记录每对OD最短路径计算的运行时间以及扩展节点数量。
为了方便阅读，两幅图中结果都根据Dijkstra算法的测试结果进行了排序。从图中，我们可以很清楚的看到A*的运行时间还是要优于Dijkstra算法的，搜索空间A*算法也是比Dijkstra算法要小，但是A*算法运行效率略慢于双向Dijkstra算法。