📚 课程目录第4章 A星算法伪代码与流程

4. A星算法伪代码与流程

A星（A*）算法是路径规划中最经典的启发式搜索算法之一。它通过结合实际代价（g(n)）与启发式估计代价（h(n)），在保证最优性的前提下大幅减少搜索空间。本节将拆解A星算法的完整执行流程，从初始化到终止，并给出可直接用于工程实现的伪代码。

4.1 核心数据结构与初始化

在算法启动前，必须建立三个核心数据结构：

数据结构	类型	作用
OPEN 表	优先队列（最小堆）	存储待扩展的节点，按 f(n) = g(n) + h(n) 排序
CLOSED 表	集合 / 哈希表	记录已扩展过的节点，避免重复处理
came_from	字典 / 映射表	记录每个节点的父节点，用于最终路径回溯

初始化步骤：

将起点 start 加入 OPEN 表，设置 g(start) = 0，f(start) = h(start)。
将 came_from[start] = None。
CLOSED 表初始化为空。

工程要点：OPEN 表推荐使用 heapq（Python）或 priority_queue（C++）实现。f(n) 值相同时，可二次按 h(n) 排序以加速收敛。

4.2 主循环搜索流程

主循环是A星算法的核心引擎，持续从 OPEN 表中取出最优节点进行扩展，直到找到目标或 OPEN 表耗尽。

  循环终止条件（二选一触发）：

  条件A：当前节点 current == goal → 路径找到，进入回溯阶段。

  条件B：OPEN 表为空 → 无可行路径，算法终止。

单次循环详细步骤：

弹出节点：从 OPEN 表中取出 f(n) 最小的节点 current。
目标检测：若 current == goal，立即跳出循环，执行路径回溯。
移入 CLOSED：将 current 加入 CLOSED 表，表示已扩展。
遍历邻居：对 current 的每个可达邻居 neighbor：

若 neighbor 在 CLOSED 表中 → 跳过（已扩展）。
计算 tentative_g = g(current) + cost(current, neighbor)。
若 neighbor 不在 OPEN 表中 → 直接加入，设置 g(neighbor) = tentative_g，f(neighbor) = tentative_g + h(neighbor)，记录 came_from[neighbor] = current。
若 neighbor 已在 OPEN 表中且 tentative_g < g(neighbor) → 更新 g(neighbor)、f(neighbor) 和父节点（找到更优路径）。

循环继续：回到步骤1。

4.3 路径回溯

当主循环因找到目标节点而终止时，需要从目标节点反向追溯至起点，构建完整路径。

回溯步骤：

初始化空列表 path = []。
设置当前节点 node = goal。
当 node 不为 None 时循环：

将 node 插入 path 头部（或追加后反转）。
node = came_from[node]。

返回 path，即为从起点到目标的最优路径。

常见错误：若 came_from 映射不完整（例如在邻居更新时遗漏了父节点记录），回溯将提前终止或陷入死循环。务必在每次更新 g(n) 时同步更新父节点。

4.4 完整伪代码

以下为A星算法的标准伪代码，可直接映射为 Python 实现：

function AStar(start, goal, h_func)
    // 初始化
    open_set = PriorityQueue()
    open_set.put(start, f(start))
    came_from = dict()
    g_score = dict()
    g_score[start] = 0
    f_score = dict()
    f_score[start] = h_func(start)
    closed_set = set()

    while not open_set.empty()
        // 弹出 f(n) 最小的节点
        current = open_set.get()

        // 目标检测
        if current == goal
            return reconstruct_path(came_from, current)

        // 移入 CLOSED 表
        closed_set.add(current)

        // 扩展邻居
        for neighbor in get_neighbors(current)
            if neighbor in closed_set
                continue

            tentative_g = g_score[current] + cost(current, neighbor)

            if neighbor not in g_score or tentative_g < g_score[neighbor]
                // 更新或加入 OPEN 表
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + h_func(neighbor)
                if neighbor not in open_set
                    open_set.put(neighbor, f_score[neighbor])
                else
                    open_set.update(neighbor, f_score[neighbor])

    // OPEN 表为空，无路径
    return None

function reconstruct_path(came_from, current)
    total_path = [current]
    while current in came_from
        current = came_from[current]
        total_path.insert(0, current)
    return total_path

4.5 算法终止条件总结

终止条件	触发时机	结果
成功终止	从 OPEN 表弹出的节点 `current == goal`	调用 `reconstruct_path` 输出最优路径
失败终止	OPEN 表为空，且未找到目标	返回 `None` 或空路径，表示起点与目标之间无连通路径

  工程对比提示：在运费成本模型集成场景中，cost(current, neighbor) 不再是简单的欧氏距离，而是包含单位运费率、拥堵系数、装卸成本的复合函数。此时 A星 的 g(n) 更新逻辑不变，但代价计算模块需要替换为成本模型接口。

4.6 关键工程注意事项

启发式函数 h(n) 的可采纳性：必须保证 h(n) ≤ 实际代价，否则 A星退化为非最优搜索（如贪心最佳优先）。
OPEN 表更新效率：当发现更优 g(n) 时，需更新节点在优先队列中的优先级。Python 的 heapq 不支持直接更新，常用技巧是“允许重复入队 + 忽略旧条目”。
内存管理：在大规模地图（如 10000×10000 网格）中，came_from 和 g_score 字典可能占用大量内存，可考虑使用 array 或 numpy 矩阵优化。
成本模型集成接口：在运费成本场景中，cost(current, neighbor) 应设计为可插拔函数，便于切换不同运费策略（如重量计价、体积计价、阶梯运费）。