图论 25. A*算法（A星算法，Astar算法）

127. 骑士的攻击

A * 算法精讲 （A star算法） | 代码随想录

卡码网无难度标识

• 思路：（摘录修改自代码随想录） ​

  • 题目背景：

    我们看到这道题目的第一个想法就是广搜，这也是最经典的广搜类型题目，但提交后会发现超时了。

    因为本题地图足够大，且 n 也有可能很大，导致有非常多的查询，以及很多无用的遍历。

    那我们能不能让遍历方向朝着终点的方向去遍历，从而避免很多无用遍历呢？

    这就要用到A*算法了

  • A*算法思路概述：

    Astar 是一种 广搜的改良版，也有人说Astar是 dijkstra 的改良版，其实只是场景不同而已。

    我们在搜索最短路的时候，

    如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多 （具体要取决于图的稠密）；

    如果是有权图（边有不同的权值） ，优先考虑 dijkstra。

    而 Astar 关键在于 启发式函数， 它会 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。

  • BFS版本的A*算法：

    • 在BFS中，我们想搜索从起点到终点的最短路径，要一层一层去遍历。

      BFS 是没有目的性的 一圈一圈去搜索， 而 A ***** 是有方向性的去搜索。

      那么 A * 为什么可以有方向性的去搜索，它是如何知道方向的呢？

      其关键在于 启发式函数。

    • 启发式函数是如何指引搜索方向的？

      对于BFS而言，其迭代是用一个队列维护的，

      当前从队列里取出什么元素，接下来就是从哪里开始搜索。

      所以 启发式函数 要影响的就是队列里元素的排序！

      这是影响BFS搜索方向的关键。

    • 对队列里节点进行排序，就需要给每一个节点权值（其实是给结点赋予一个启发式价值，用来评估其在指引搜索方向上的优秀程度），如何计算权值呢？

      每个节点的权值为F，给出公式为：F = G + H

      G：起点达到目前遍历节点的距离（实际的距离，在本题中为起点到当前节点的步数）

      H：目前遍历的节点到达终点的距离（启发式距离）

      ​起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离​ 就是起点到达终点的距离​。

      本题的图是无权网格状图，在计算两点距离时通常有如下三种计算方式：

      1. 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)​
      2. 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )​
      3. 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))​

      x1, x2 为起点坐标，y1, y2 为终点坐标 ，abs 为求绝对值，sqrt 为求开根号，

      选择哪一种距离计算方式 也会导致 A * 算法的结果不同。

    • 本题使用的（启发式）距离度量：

      本题一定要采用欧拉距离，才能（最大程度）体现 无权网格上点与点之间的距离。（否则可能反映不了真实距离，导致最终得到的不是最短路！）

      本题场景下使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。（路径可能不同，但路径上的节点数是相同的）

      计算出来 F 之后，按照 F 的 大小，来选取 当前出队列的节点。

      可以使用 优先级队列 帮我们排好序，每次出队列，就是F最小的节点。

  • A*算法复杂度分析：

    A * 算法的时间复杂度 其实是不好去量化的，因为他取决于 启发式函数怎么写。

    最坏情况下，A * 退化成广搜，算法的时间复杂度 是 O(n * 2) ，n 为节点数量。

    最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd) ，d 为起点到终点的深度。（因为在搜索的过程中也需要堆排序，所以是 O(dlogd)。）

    实际上 A * 的时间复杂度是介于 最优 和最坏 情况之间，

    可以 非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) ，n 为节点数量。

    A * 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度，b 是 图中节点间的连接数量，本题因为是无权网格图，所以 节点间连接数量b为 4。

• 代码：（启发式函数 采用 欧拉距离计算方式）

  import sys
  import heapq # 导入堆模块，用于实现优先队列（小根堆），方便按估计距离排序
  
  def distance(p1, p2):
      # p1，p2均为坐标，如p1是(a1, a2)
      # 返回两点之间的欧拉距离
      return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
  
  # 启发式bfs（a*算法）
  def heuristicBFS(startPoint, endPoint, moves):
      # startPoint，endPoint均为坐标，如startPoint是(a1, a2)
      # moves定义骑士在国际象棋中所有可能的移动方式
      # 返回题意中两点之间的最短步数（骑士最短路径长度）
  
      # 初始化优先队列 q。队列中的元素为元组：(估计距离, 当前坐标)
      # 估计距离 = 当前从起点到当前位置的实际步数（初始为 0）加上当前位置到目标的欧几里得距离
      q = [(distance(startPoint, endPoint), startPoint)]
      step = {startPoint: 0} # 使用字典 step 来记录从起点到各个坐标所需的最少步数，初始时起点的步数为 0
  
      while q:
          cur_d, cur_p = heapq.heappop(q) # 从优先队列中弹出具有最小估计距离的元素，得到当前估计距离 cur_d 和当前坐标 cur_p
          # 若抵达终点，说明找到了最短路径，返回所需步数
          if cur_p == endPoint:
              return step[endPoint]
  
          # 否则，将cur_p出发下一步可能抵达的点入队
          for move in moves: # 遍历所有可能的骑士移动方式
              new_p = (cur_p[0] + move[0], cur_p[1] + move[1]) # 新的点
              if 1 <= new_p[0] <= 1000 and 1 <= new_p[1] <= 1000: # 检查新坐标 new 是否在合法范围内（此处棋盘行和列均限制在 1 到 1000 之间）
                  new_g = step[cur_p] + 1 # 当前起点基于cur_p点抵达新点距离
                  # 如果 new_p 还没有被访问过，或者通过当前路径到 new_p 的步数更少，则更新记录
                  # step.get(new_p, float('inf')) 表示获取 new_p 的当前步数记录，如果不存在则视为无穷大
                  if new_g < step.get(new_p, float('inf')):
                      step[new_p] = new_g # 更新 new_p 的步数
                      # 将新状态 (估计距离, new_p) 推入优先队列中
                      # 估计距离 = 实际步数 new_g + 从 new_p 到目标 endPoint 的欧几里得距离
                      new_d = new_g + distance(new_p, endPoint)
                      heapq.heappush(q, (new_d, new_p))
      # 遍历结束q为空了都没找到endpoint，说明不存在路径
      return False
  
  
  
  if __name__ == '__main__':
      lines = sys.stdin.readlines()
      n = int(lines[0].strip()) # n个测试用例
      # 定义骑士在国际象棋中所有可能的移动方式，表示二维平面上的位移向量
      moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]
  
      # 遍历测试用例
      for i in range(1, len(lines)):
          # 骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)
          a1, a2, b1, b2 = map(int, lines[i].strip().split())
          print(heuristicBFS((a1, a2), (b1, b2), moves))
  
  

• 拓展：（摘录修改自代码随想录）

  • A*算法获得的路径一定是最短路吗？

    不一定！

    如果本题使用 曼哈顿距离 或者 切比雪夫距离 计算的话，有的最短路结果是并不是最短的。

    原因是 曼哈顿 和 切比雪夫这两种计算方式在 本题的网格地图中，都没有体现出点到点的真正距离！

    A * 算法 并不是一个明确的最短路算法，A ***** 算法搜的路径如何，完全取决于 启发式函数怎么写。

    A ***** 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。

    虽然本题中，A * 算法得到是最短路，也是因为本题 启发式函数 和 地图结构都是最简单的。

    例如在游戏中，在地图很大、不同路径权值不同、有障碍 且多个游戏单位在地图中寻路的情况，如果要计算准确最短路，耗时很大，会给玩家一种卡顿的感觉。

    而真实玩家在玩游戏的时候，并不要求一定是最短路，次短路也是可以的 （玩家不一定能感受出来，及时感受出来也不是很在意），只要奔着目标走过去 大体就可以接受。

    所以 在游戏开发设计中，保证运行效率的情况下，A ***** 算法中的启发式函数 设计往往不是最短路，而是接近最短路的 次短路设计。

  • A * 的缺点：

    大家看上述 A * 代码的时候，可以看到 我们向 队列里添加了很多节点，

    但真正从队列里取出来的 仅仅是 靠启发式函数判断 距离终点最近的节点。

    相对于 普通BFS，A * 算法只从 队列里取出 距离终点最近的节点。

    因此这就会导致：A * 在一次路径搜索中，大量不需要访问的节点都在队列里，会造成空间的过度消耗。

    IDA * 算法 对这一空间增长问题进行了优化。

    另外还有一种场景 是 A * 解决不了的：

    如果题目中，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A * 就不擅长了， A * 只擅长给出明确的目标 然后找到最短路径。

    如果是多个目标找最近目标（特别是潜在目标数量很多的时候），可以考虑 Dijkstra ，BFS 或者 Floyd。

‍