A*算法讲解

路径规划
,
  • 什么是A*算法？A-Star算法是一种用于图搜索和路径规划的启发式搜索算法。它可以在一个图结构中找到从起点到目标点的最低成本路径。A_算法被广泛应用于机器人导航、游戏开发以及解决最短路径等问题。

在学习 A* 算法之前，需要了解 贪婪最佳优先搜索算法 和 Dijkstra 方法的基本思想，以及它们各自的优缺点。同时，还需要理解为什么 A* 算法能够结合两种方法的优点，并做到既高效又能保证找到最优解。

基本思想

  • 贪婪算法是一种以局部最优解为原则的搜索方式。
  • 在每一步决策时，优先选择离目标最近的节点，期望快速逼近目标点。
  • 使用启发式函数 (h(n)) 来估计当前节点 (n) 到目标节点的距离。
  • 贪婪算法的优先级完全由 (h(n)) 决定，而不考虑已走路径的代价 (g(n))。

评价函数

贪婪算法的评价函数为：
$${f(n) = h(n)}$$

  • ${h(n)}$：当前节点 ${n}$到目标节点的估计代价，通常是基于启发式计算的距离（如欧几里得距离、曼哈顿距离等）。

优点

  • 速度快：直接优先选择离目标最近的节点，能快速找到接近目标的路径，计算效率较高。
  • 简单易实现：只需要维护每个节点的启发式函数 ${h(n)}$ 值。

缺点

  • 有可能无法找到最优解：因为只考虑了目标的方向，而忽略了当前路径的总代价 ${g(n)}$。路径可能会绕远路。
  • 容易陷入局部最优：如果当前节点的 ${h(n)}$ 是最低的，但如果途中存在障碍，可能会使算法停滞。

举例说明

  • 假设地图中有一个从起点 (A) 到目标点 (B) 的任务，中间存在一个障碍物墙。
  • 贪婪算法可能会沿着直线接近目标点 (B)，但由于障碍物的存在，算法可能会长时间绕不开墙障碍，甚至陷入死锁。

2. Dijkstra 算法

基本思想

  • Dijkstra 是一种逐层扩展探索的算法，在每一步都优先选择当前路径代价最小的节点。
  • 与贪婪算法不同，它完全不考虑目标点的位置，而是从起点出发，逐一扩展所有可能的路径，最终保证找到的是全局最优路径。

评价函数

它的评价函数为：
$${f(n) = g(n)}$$

  • ${g(n)}$：从起点到当前节点 ${n}$ 的路径代价。通常表示路径长度（距离）或者实际行走的代价。

优点

  • 能够找到最优解：因为它以 ${g(n)}$为依据逐层扩展，最终能遍历所有可能的解空间，找到路径代价最小的解。
  • 具有稳定性：无论在什么设置下，总能保证路径是最优路径。

缺点

  • 计算开销较大：Dijkstra 必须访问所有可能的节点才能确定最终解，因此在较大的图中效率较低。
  • 不直观：算法并不关注目标点的位置，可能会遍历较远或无关的地方，增加开销。

举例

  • 假设从 (A) 到 (B) 的任务，中途有多个障碍物。
  • 即使目标点 (B) 离当前节点很近，Dijkstra 同样可能先探索远离 (B) 的其他可能路径。因此它的效率不如贪婪算法。

3. A* 算法：综合两种方法的改进

核心思路

A* 算法结合了贪婪算法和 Dijkstra 的优点，在每一步选择节点时，同时考虑：

  1. 当前节点到起点的路径代价 ${g(n)}$（确保路径是最优的）。
  2. 当前节点到目标的估计代价 ${h(n)}$（确保朝目标方向前进）。

通过这两项的加权和，A* 算法实现了兼顾效率和全局最优的平衡。

评价函数

A* 算法的评价函数为：
$${f(n) = g(n) + h(n)}$$

  • ${g(n)}$：从起点到当前节点的实际路径代价。这部分使得 A* 能够像 Dijkstra一样权衡整体路径的代价。
  • ${h(n)}$：从当前节点到目标节点的启发式估计代价。这部分使得 A* 有方向性，更快速地逼近目标。

优点

  • 保证最优解：如果${g(n)}$ 是可接受估计函数（admissible heuristic），A* 能够保证找到最优路径。
  • 效率高：相比 Dijkstra，A* 加入了启发式函数 (h(n))，减少了不必要的节点遍历。
  • 可以根据启发式函数调整：灵活地选择不同的启发式函数适配不同的问题。

缺点

  • 依赖启发式函数的选择：启发式函数设计不佳（如估计值过大或偏差）会导致准确性或效率下降。
  • 开销不小：虽然比 Dijkstra 更高效，但在某些复杂情况下也需要遍历大量节点，依旧存在性能瓶颈。

4. 启发式函数

在 A* 算法中，启发式函数 ${h(n)}$ 的选择至关重要。但是这存在一个问题：在不知道障碍物的情况下，如何设计启发式函数，或者说，如何去“猜测”到目标点的代价。

关键思路：尽量简单且高效
启发式函数只是一个估计，它不需要绝对准确，但需要具有一定的指导性。它的目标是为搜索提供方向，使你尽可能接近目标（在路径规划中叫“引导搜索过程”）。

常见的启发式函数

在没有障碍物或不知道障碍物分布的情况下，可以使用纯几何信息来设计启发式函数。以下是一些常见的几何估计方式：

1. 曼哈顿距离（Manhattan Distance）

  • 适用场景：当只能水平或垂直移动时，比如你在用栅格地图，且每一步只能沿网格的水平方向或垂直方向走。

  • 计算公式：
    $${ h(n) = |x_{\text{current}} - x_{\text{goal}}| + |y_{\text{current}} - y_{\text{goal}}|}$$

  • 特点：它总是估计当前位置和目标点之间的路径步数，忽略了对角移动和障碍物。

示例：

如果当前位置是 ( 1, 1 )，目标点是 ( 4, 3 )，曼哈顿距离为：
$${h(n) = |1-4| + |1-3| = 3 + 2 = 5}$$

2. 欧几里得距离（Euclidean Distance）

  • 适用场景：当机器人或者实体可以移动到任何方向（包括对角线）时，比如让机器人沿直线移动。
  • 计算公式：
    $${
    h(n) = \sqrt{(x_{\text{current}} - x_{\text{goal}})^2 + (y_{\text{current}} - y_{\text{goal}})^2}
    }$$
  • 特点：
    • 欧几里得距离给出当前位置到目标点的物理直线距离，因此在无障碍物场景中是最优估计。
    • 它不关心环境中的障碍物，但能提供“直线方向”的引导。
示例：

当前位置 ( 1, 1 )，目标点 ( 4, 3 )，欧几里得距离：
$${
h(n) = \sqrt{(1-4)^2 + (1-3)^2} = \sqrt{9 + 4} = \sqrt{13} \approx 3.6
}$$

3. 对角距离（Diagonal Distance）

  • 适用场景：适合栅格地图机器人能沿对角方向移动，同时垂直/水平/对角线步长不同的场景。
  • 计算公式：
    $${
    h(n) = D_{\text{straight}} \times (\Delta x + \Delta y) + (D_{\text{diagonal}} - 2 \times D_{\text{straight}}) \times \text{min}(\Delta x, \Delta y)
    }$$
    其中：
    • ${\Delta x = |x_{\text{current}} - x_{\text{goal}}|}$
    • ${\Delta y = |y_{\text{current}} - y_{\text{goal}}|}$
    • ${D_{\text{straight}}}$：代表水平/垂直移动代价（常常设为1）。
    • ${D_{\text{diagonal}}}$：代表对角移动代价（常常设为 ${\sqrt{2}}$）。
  • 特点：
    • 它类似欧几里得距离的简化版本，但是使用加法代替平方根计算，更快速。
    • 在环境允许对角线移动的情况下是一个优秀的估计方法。
示例：

当前位置 ( (1, 1) )，目标点 ( (4, 3) )，假设
${D_{\text{straight}} = 1}$ ，${D_{\text{diagonal}} = \sqrt{2} }$：
$${
h(n) = 1 \times (3+2) + (\sqrt{2} - 2 \times 1) \times \min(3, 2) = 5 + (\sqrt{2} - 2) \times 2
}$$

4. 加权启发式（Weighted Heuristic）

  • 适用场景：当知道 ${h(n)}$ 可能偏低而希望加快算法速度时，可以引入权重 w ：
    $${
    h(n) = w \cdot \text{启发式方法}
    }$$
    • 如果 ( w>1 )，启发式估计会更加“激进”，算法速度更快但可能牺牲最优解。
    • 如果 ( w<1 )，启发式估计更保守，但解会更准确。
示例：

假如欧几里得距离为 10，选择 ( w=1.5 )，则：
$${
h(n) = w \cdot h_{\text{euclidean}} = 1.5 \cdot 10 = 15
}$$

二、启发式函数的实际作用

1. 猜测如何快速接近目标

启发式函数不需要考虑障碍物，它只是用来让算法知道“往哪个方向走得更接近目标”。

2. 无障碍假设下的启发式

在没有障碍物时，最优的路径是直线路径（例如欧几里得距离）。即使有障碍物，启发式函数依然提供了一个大致方向，但会根据代价函数 ( g(n) ) 一步步调整路径。

3. 为什么不能太低估？

启发式函数如果估计过低，算法会更倾向于穷尽搜索，类似于 Dijkstra 算法，效率较低。因此，启发式函数应尽可能接近实际代价，但不得过高（否则可能找不到最优解）。

启发式函数的要求

  1. 可接受性（Admissible）：${h(n)}$ 永远不超过当前节点到目标节点的真实最优代价。
  2. 一致性（Consistent / Monotone）：对于任意两个相邻节点 ${(n, n’)}$，满足：
    $${
    h(n) \leq c(n, n’) + h(n’)
    }$$

其中 ${c(n, n’)}$ 是从 (n) 到 (n’) 的代价）
满足这两个条件时，A* 能够保证找到全局最优解。

三、实际应用时的选择建议

  1. 水平方向和垂直方向移动：
    • 曼哈顿距离是最常用的启发式。
    • 适用于简单的 2D 栅格地图。
  2. 对角线和任意方向移动：
    • 欧几里得距离是物理意义上最优的距离估计。
    • 更适用于机器人路径规划或飞行器导航。
  3. 复杂地图权重调整：
    • 使用启发式权重 ( w ) 来控制搜索效率和解的质量。
  4. 动态启发式调整（高级场景）：
    • 在搜索路径的过程中，动态更新 ( h(n) ) 以适应环境变化。例如，当检测到有障碍物时，切换策略。

5. 比较三种算法

算法 优先选择考虑 是否能找到最优解 假如图较大时效率
贪婪最佳优先搜索 距离目标点最近的节点 否 比较高
Dijkstra 距离起点代价最小的节点 是 低
A* 综合起点和目标的节点 是 中等偏高

小结：

  • 贪婪搜索速度快但无法找到全局最优解（局部最优性）。
  • Dijkstra 找到最优解，但效率较低。
  • A* 综合两者，能找到全局最优解，同时较高效，是目前最常用的路径规划算法之一。

6. 示例：网格地图上的路径规划

伪代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def A_star(grid, start, goal, heuristic):
    OPEN = PriorityQueue()  # 优先队列存储待探索节点
    CLOSED = set()          # 集合存储已探索节点

    g = {start: 0}          # 起点到当前点的总代价
    f = {start: heuristic(start, goal)}  # 估计总代价 f(n) = g(n) + h(n)

    OPEN.put((f[start], start))  # 插入起点到OPEN队列

    while not OPEN.empty():
        _, current = OPEN.get()  # 当前代价函数最小的节点

        if current == goal:
            return reconstruct_path(CLOSED, start, goal)  # 找到路径

        CLOSED.add(current)
        
        for neighbor in get_neighbors(grid, current):
            if neighbor in CLOSED:
                continue
            
            tentative_g = g[current] + move_cost(current, neighbor)  # 更新 g 值

            if neighbor not in g or tentative_g < g[neighbor]:
                g[neighbor] = tentative_g
                f[neighbor] = g[neighbor] + heuristic(neighbor, goal)
                OPEN.put((f[neighbor], neighbor))
    
    return None  # 未找到路径