A* 搜索算法的应用实例分析

如你所知A* 算法就是在广度优先搜索算法的基础上进行了优化从而能够在保证算法正确性的前提下提前找到到达终点的最短路径。A* 算法的基本思想是通过启发式公式对当前搜索状态的下界进行估计并且优先搜索更有潜力的解根据估计的下界来确定。什么是当前搜索状态的下界呢就是当我访问到一个点时虽然不知道当前点是不是在最短路径上但是可以通过启发式方法来估计经过该点的路径到终点的距离最短是多少。在下面的示意图中我们已经知道当前点红色的点到起点的距离为 5同时我们知道从当前点到终点的距离不会少于 3因此可以确定经过当前点的路径最终长度不会小于 538。有了每个搜索状态的下界以后我们可以每次从队列中取出下界最优的解进行探索这需要使用到优先队列这一数据结构。优先队列和普通队列的区别就是优先队列中的元素始终是按照大小顺序排列的。优先队列通常是用堆来实现的由于大部分编程语言都提供了优先队列的实现这里就不再详细介绍优先队列的实现过程了。# A* 搜索算法伪代码 queue PriorityQueue() queue.put(start) while queue not empty: (_, cur) queue.get() # 这里的 hamiltonDistance 函数用于计算两点之间的哈密顿距离。 lower_bound hamiltonDistance(start, cur) hamiltonDistance(cur, end) if cur end: break for node in cur.neighbors(): if IsInGrid(node) and not IsVisited(node): queue.put((lower_bound, node)) MarkVisited(node)再看一下 A* 算法的运行动画优先队列里面的数字表示当前状态的下界值优先队列中的元素也是按照下界值从小到大的顺序进行排列。为了更加直观动画中新增了一个网格专门用来记录每个状态对应的预估下界值。可以看到算法会优先搜索下界值更小的点也能够更快的找到最短路径这就是 A* 算法的基本思想了。