A*最短路径算法

图算法

A*算法是一种启发式搜索算法,通过结合Dijkstra算法和启发式估计,能够高效地找到从起点到目标点的最短路径。

时间复杂度:最佳 O(E) | 平均 O(E log V) | 最差 O(E log V)
空间复杂度:O(V)
图类型:加权图

应用场景/前提条件

  • 适用于边权重为非负值的图
  • 需要一个启发式函数估计到目标的距离

算法讲解

A*最短路径算法

介绍

A*(A-Star)算法是一种高效的启发式搜索算法,由Peter Hart、Nils Nilsson和Bertram Raphael于1968年提出。A*算法结合了Dijkstra算法的优势(保证找到最短路径)和贪心最佳优先搜索的启发式方法(提高搜索效率),被广泛应用于路径规划、图搜索和人工智能领域。

A*算法的核心思想是利用启发式函数来估计从当前顶点到目标顶点的距离,引导搜索朝着更有希望的方向进行,减少不必要的搜索,提高算法效率。在启发式函数满足一定条件(可接受性)时,A*算法总能找到最优解。

算法步骤

  1. 初始化两个集合:openSet(待探索顶点集合,初始只包含起始顶点)和closedSet(已探索顶点集合,初始为空)
  2. 对于每个顶点,记录三个值:
    • g(n):从起始顶点到当前顶点n的实际路径长度
    • h(n):从当前顶点n到目标顶点的估计距离(启发式函数)
    • f(n):f(n) = g(n) + h(n),表示经过顶点n的路径的总估计代价
  3. 循环执行以下步骤,直到找到目标顶点或openSet为空:
    • 从openSet中选取f值最小的顶点current
    • 如果current是目标顶点,则算法结束,返回路径
    • 将current从openSet移动到closedSet
    • 对于current的每个邻居顶点neighbor:
      • 如果neighbor在closedSet中,跳过
      • 计算通过current到达neighbor的新路径长度g_temp
      • 如果neighbor不在openSet中或g_temp小于neighbor的g值:

...