算法笔记：A*算法

A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度

1 中心思路

• A*算法通过下面这个函数来计算每个节点n的优先级
  • f(n)=g(n)+h(n)
    • f(n)是节点n的综合优先级。当选择下一个要遍历的节点时，总会选取综合优先级最高（f(n)值最小）的节点。
    • g(n) 是节点n距离起点的代价
    • h(n)是节点n距离终点的预计代价，这也就是A*算法的启发函数
• A*算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。

1.1  伪代码

• A*算法使用两个集合来表示待遍历的节点（open_set），与已经遍历过的节点（close_set）

• 初始化open_set和close_set
• 将起点n0加入open_set中，并设置f(n0)=0（优先级最高）
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点：
    • 从终点开始逐步追踪parent节点，一直达到起点
    • 返回找到的结果路径，算法结束
  • 如果节点n不是终点：
    • 将节点n从open_set中删除，并加入close_set中
    • 遍历节点n所有的邻近节点
      • 如果邻近节点m在close_set中（已经访问过来），则：
        • 跳过，选取下一个邻近节点
      • 如果邻近节点m也不在open_set中，则=
        • 设置节点m的parent为节点n
        • 计算节点m的优先级f(n)
        • 将节点m加入open_set中

2 启发函数

• 在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法
  • ntu 课程笔记 ：MAS714(7) 最短路径和优先队列_UQI-LIUWJ的博客-CSDN博客
• 如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。
  • 但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
• 如果h(n)完全等于节点n到终点的代价，则A*算法将找到最佳路径，并且速度很快。
  • 可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
• 如果h(n)的值比节点n到终点的代价要大，则A*算法不能保证找到最短路径，不过此时会很快
  • 
  • 比如这种情况最短路路径应该是下路
  • 但如果我们估计的h(n)为实际路径的两倍
    • 那么选择中间节点的时候，A*算法会选择上路 （5+3*2=11，4+3.6*2=11.2）

   

2.1 一些经验启发函数

• 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离
  • 
• 如果图形中允许朝八个方向移动，则可以使用对角距离
  • 
• 如果图形中允许朝任何方向移动，则可以使用欧几里得距离
  •