A* 搜索算法

A* 搜索算法（A* search algorithm）是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上。

该算法综合了最良优先搜索和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。

在此算法中，如果以 $g(n)$ 表示从起点到任意顶点 n 的实际距离，$h(n)$ 表示任意顶点 n 到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么 A*算法 的估算函数为：

${\displaystyle f(n)=g(n)+h(n)}$

这个公式遵循以下特性：

• 如果 $g(n)$ 为0，即只计算任意顶点 n 到目标的评估函数 $h(n)$，而不计算起点到顶点 n 的距离，则算法转化为使用贪心策略的最良优先搜索，速度最快，但可能得不出最优解；
• 如果 $h(n)$ 不大于顶点 n 到目标顶点的实际距离，则一定可以求出最优解，而且 $h(n)$ 越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
• 如果 $h(n)$ 为 0，即只需求出起点到任意顶点 n 的最短路径 $g(n)$，而不计算任何评估函数 $h(n)$，则转化为最短路问题问题，即 Dijkstra 算法，此时需要计算最多的顶点；

A*算法在运算过程中，每次从优先队列中选取$f(n)$值最小（优先级最高）的节点作为下一个待遍历的节点。

另外，A*算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_set和close_set。

• 初始化open_set和close_set；
• 将起点加入open_set中，并设置优先级为0（优先级最高）；
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点，则：
    • 从终点开始逐步追踪parent节点，一直达到起点；
    • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点，则：
    • 将节点n从open_set中删除，并加入close_set中；
    • 遍历节点n所有的邻近节点：
      • 如果邻近节点m在close_set中，则：
        • 跳过，选取下一个邻近节点
      • 如果邻近节点m在open_set中，则：
        • 判断节点n到节点m的 F(n) + cost[n,m] 值是否 < 节点m的 F(m)。来尝试更新该点，重新设置f值和父节点等数据
      • 如果邻近节点m也不在open_set中，则：
        • 设置节点m的parent为节点n
        • 计算节点m的优先级
        • 将节点m加入open_set中