《算法的乐趣》第六十五节

本节介绍切比雪夫距离：两个向量的切比雪夫距离是各分量差的绝对值中的最大值，二维平面上即两点横纵坐标差的最大值，并给出了对应的A*算法实现代码及其效果。

本节介绍切比雪夫距离：两个向量的切比雪夫距离是各分量差的绝对值中的最大值，二维平面上即两点横纵坐标差的最大值，并给出了对应的A*算法实现代码及其效果。

接着讨论启发函数H(n)与A*算法的关系：H(n)为0时A*退化为Dijkstra算法，速度慢但能保证最短路径；H(n)越大搜索范围越小、速度越快，但可能得不到最短路径；H(n)过大时A*演化为BFS算法。因此可通过调整G(n)与H(n)在速度与准确性之间折中，游戏中走近似最短路径即可。

A*算法的实现关键是维护OPEN表和CLOSE表，用STL的multiset作为有序的OPEN表，AStar()函数对应算法三个步骤，ExtractMiniFromOpen()取出F(n)最小的节点。总结部分指出：Dijkstra算法时间复杂度为O(n)，是无负权边有向图中最快的单源最短路径算法；含负权边可用Floyd-Warshall算法求任意两点最短距离。A*兼有Dijkstra与BFS的特点，可用二叉堆维护OPEN表，动态网络可用D*算法。Dijkstra广泛用于地图导航，A*广泛用于游戏寻径。