4. 静态环境下的经典路径规划算法

在栅格海图中，静态路径规划的本质是在一张带权图上寻找从起点到终点的最优或近似最优路径。Dijkstra、A* 与 JPS 是三个层层递进的经典算法：Dijkstra 保证最短但盲目扩展；A* 引入启发式函数把搜索"拉向"目标；JPS 则在均匀代价栅格上跳过大量对称冗余节点，把 A* 的扩展量再压缩一个量级。理解三者的差异，关键不在于记住伪代码，而在于看清"扩展哪些节点、按什么顺序扩展、何时停止"这三件事。

统一的问题模型与坐标约定

本节统一采用如下约定：栅格以左上角为原点，列号 x 向右递增，行号 y 向下递增；每个可通行栅格为一个节点，八邻域连通，水平/垂直移动代价为 1，对角移动代价为 √2≈1.414（不允许穿角，即对角移动要求两个相邻正交格均可通行）。障碍格不可进入。启发式函数采用欧氏距离，与八邻域移动代价相容，因而 A* 可保持最优性。所有示例参数均为教学假设值，用于说明算法行为，不代表实测性能。

Dijkstra：按累计代价由近及远扩展

Dijkstra 维护一个开放集（优先队列），键值为从起点出发的累计代价 g。每次取出 g 最小的节点，松弛其全部邻居：若经当前节点到达邻居的代价更小，则更新邻居的 g 与前驱，并压入队列。当终点被取出时即得到最短路径。它的特点是"等代价面"呈同心圆扩散，在开阔海域会向四周均匀铺开，扩展节点数大致与搜索圆面积成正比。对 200×200 的栅格，若起终点相距较远，扩展量可达数万节点，实时性较差，但它是检验其他算法结果正确性的基准。

A*：用启发式函数引导方向

A* 把优先队列的键值改为 f = g + h，其中 h 为当前节点到终点的估计代价。h 越接近真实剩余代价，搜索越集中；h 恒为 0 时退化为 Dijkstra；h 高估真实代价时不再保证最优，但速度更快（加权 A*）。实现要点有三：其一，需维护 g 值表与"是否已关闭"标记，已关闭节点一般不再重新打开（在启发式一致时安全）；其二，邻居松弛时先算 tentative_g = g[cur] + step_cost，仅当小于已有 g 才更新；其三，优先队列需支持"减少键"或采用惰性删除（重复入队、出队时跳过过期项），后者实现更简单。下面给出核心循环的教学示例：

import heapq

def astar(grid, start, goal):
    # grid: 0 可通行, 1 障碍; 返回路径节点列表或 None
    open_heap = [(0.0, start)]
    g = {start: 0.0}
    parent = {start: None}
    closed = set()
    while open_heap:
        f, cur = heapq.heappop(open_heap)
        if cur in closed:
            continue
        if cur == goal:
            path = []
            while cur is not None:
                path.append(cur); cur = parent[cur]
            return path[::-1]
        closed.add(cur)
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)):
            nx, ny = cur[0]+dx, cur[1]+dy
            if not (0 <= ny < len(grid) and 0 <= nx < len(grid[0])):
                continue
            if grid[ny][nx] == 1:
                continue
            if dx and dy and (grid[cur[1]][nx] == 1 or grid[ny][cur[0]] == 1):
                continue  # 禁止穿角
            step = 1.41421356 if dx and dy else 1.0
            ng = g[cur] + step
            nb = (nx, ny)
            if ng < g.get(nb, float('inf')):
                g[nb] = ng
                parent[nb] = cur
                h = ((nx-goal[0])**2 + (ny-goal[1])**2) ** 0.5
                heapq.heappush(open_heap, (ng + h, nb))
    return None

在一张 120×120、障碍稀疏的示例海图中，若起点为 (10,10)、终点为 (110,110)，Dijkstra 的扩展量约为 A* 的 3～5 倍，而两者路径长度相同——这正是启发式函数的价值所在。实际工程中还可对 h 乘以权重 w（如 1.1～1.5）做加权 A*，以少量最优性换取明显加速，适合对实时性要求高的避碰局部重规划。

JPS：在均匀代价栅格上跳过对称节点

JPS（Jump Point Search）针对"所有可通行格代价相同"的栅格，利用路径对称性剪枝：在直线方向上，只有当某节点存在强制邻居（即因障碍导致必须在此转向才能保持最优）时，才把它作为跳点加入开放集；否则沿方向一直"跳"到障碍、边界或目标为止。这样 A* 中大量等价路径上的中间节点被整体跳过，开放集规模显著缩小。JPS 的最优性与 A* 一致，但要求代价均匀、栅格规则；若海图含潮流代价、禁航区软约束或不同水深代价，JPS 的对称性前提被破坏，需退回 A* 或改用带权变体。

性能对比与选型判断

三者的差异可以用一张对比表快速定位。需要强调的是，表中的量级关系来自算法复杂度与典型教学示例的观察，实际数值随地图尺寸、障碍密度、起终点距离和启发式质量而变，工程中应以目标硬件上的实测为准。

实战中的关键判断

第一，先验证正确性再谈性能：用同一张图分别跑 Dijkstra 与 A*，比较路径总代价是否一致，若不一致，多半是启发式高估或"已关闭节点被重复打开"导致。第二，注意浮点比较：对角代价 √2 会引入微小误差，g 值比较建议用 1e-9 容差，避免同一节点被反复入队。第三，路径后处理不可少：栅格路径呈锯齿状，需做视线简化（若两点连线不穿越障碍则直连），既缩短航程又便于船舶跟踪。第四，若海图含潮流、限速或不同水深代价，应放弃 JPS，改用 A* 并在 step_cost 中叠加环境代价，此时启发式需相应缩放以保持可容许性。