第4章路径搜索算法

第4章：路径搜索算法：A*算法原理与实现、Dijkstra算法、JPS算法、算法对比与选型

各位同学，欢迎来到路径搜索算法的核心章节。

说实话，做无人机航迹规划这么多年，我见过太多新手一上来就抱着A*不放。但实际项目中，选错算法的代价往往是炸机或者算力爆炸。今天咱们就把A*、Dijkstra、JPS这三兄弟掰开揉碎了讲清楚。

4.1 算法家族图谱

先给大家画个知识框架。这三种算法本质上都是在解决同一个问题：在带权重的图中，找到从起点到终点的最优路径。但它们的脾气秉性完全不同。

4.2 Dijkstra算法：最朴素的探索者

Dijkstra算法，说白了就是「地毯式搜索」。它从起点开始，一层一层往外扩散，直到找到终点。我刚开始做航迹规划时，第一个用的就是它。

核心思想很简单：维护一个距离表，每次选当前距离最小的节点去扩展。就像你站在迷宫中心，拿粉笔在地上画圈，一圈一圈往外画，直到画到出口。

算法精髓：贪心策略 + 动态规划。每次选「当前已知最短路径」的节点进行松弛操作。

// Dijkstra 伪代码
function Dijkstra(graph, start, end):
    dist[start] = 0
    for each node v != start:
        dist[v] = INF
    
    while priority_queue is not empty:
        u = queue.pop()  // 取距离最小的节点
        if u == end: break
        
        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                queue.push(v, alt)
    
    return dist[end]

注意：Dijkstra要求所有边的权重非负。我曾经在一个项目中忽略了这一点，结果路径规划出来全是负数权重绕圈圈，差点把无人机导到禁飞区去。

4.3 A*算法：带指南针的探索者

A*算法就是在Dijkstra的基础上加了个「指南针」——启发式函数。这个启发式函数告诉算法：「嘿，往这个方向走更有可能找到终点」。

我个人习惯用欧几里得距离作为启发式，但在栅格地图上，曼哈顿距离往往更实用。为什么？因为无人机在栅格地图上只能上下左右移动，直线距离反而会误导。

// A* 伪代码
function AStar(graph, start, end):
    openSet = {start}
    gScore[start] = 0
    fScore[start] = heuristic(start, end)
    
    while openSet is not empty:
        current = node in openSet with lowest fScore
        if current == end: return reconstruct_path(cameFrom, current)
        
        openSet.remove(current)
        for each neighbor of current:
            tentative_g = gScore[current] + weight(current, neighbor)
            if tentative_g < gScore[neighbor]:
                cameFrom[neighbor] = current
                gScore[neighbor] = tentative_g
                fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, end)
                if neighbor not in openSet:
                    openSet.add(neighbor)
    
    return failure

避坑指南：我曾经在复杂地形中直接用欧几里得距离做启发式，结果A*绕了远路。后来改用「对角线距离」——允许斜向移动时，这个启发式更准确。你想想看，无人机又不是只能走直线，斜着飞更省时间。

4.4 JPS算法：会跳的搜索者

JPS（Jump Point Search）算法，说白了就是A*的「加速版」。它利用栅格地图的对称性，跳过那些「没必要探索」的格子。

核心思想：在开阔区域，很多格子其实不用一个个看。比如你面前是一条笔直的走廊，你只需要看走廊尽头，中间那些格子直接跳过。

// JPS 核心：寻找跳跃点
function jump(current, direction, end):
    next = current + direction
    if next is obstacle or out of bounds: return null
    if next == end: return next
    
    // 检查强制邻居
    if has_forced_neighbor(next, direction):
        return next
    
    // 对角线移动时，检查水平和垂直方向
    if direction is diagonal:
        if jump(next, (direction.x, 0), end) or jump(next, (0, direction.y), end):
            return next
    
    return jump(next, direction, end)

关键点：JPS只在栅格地图上有效。如果你的地图是路网图或者连续空间，JPS就派不上用场了。我记得有次在三维空域规划中硬套JPS，结果算法直接崩溃——因为三维空间没有「对称性」可以利用。

4.5 算法对比与选型

好了，三个算法都讲完了。咱们来做个对比，方便你选型。

特性	Dijkstra	A*	JPS
启发式	无	有（需设计）	有（同A*）
最优性	保证	保证（可采纳启发式）	保证
时间复杂度	O(V²) 或 O(E log V)	O(E log V) 实际更快	O(E log V) 实际最快
适用地图	任意图	任意图	仅栅格地图
内存占用	高	中	低
实现难度	简单	中等	较难

选型建议：

小规模地图（100x100以内）：用Dijkstra就行，简单可靠。我早期做演示项目时就用它，客户看着路径一圈圈扩散，觉得「很专业」。
中等规模（1000x1000以内）：上A*。启发式函数选曼哈顿距离，大部分场景够用。
大规模栅格地图（10000x10000以上）：必须用JPS。我做过一个城市级无人机配送项目，地图20000x20000，A*跑一次要3秒，换成JPS后降到0.2秒。

重要提醒：JPS虽然快，但有个致命弱点——它依赖「规则障碍物」。如果地图中有大量不规则障碍（比如森林、建筑群），JPS的跳跃点会变得很少，性能优势就没了。我曾经在山区地形中吃过这个亏，后来老老实实换回A*。

4.6 实战经验总结

最后分享几个我踩过的坑：

启发式函数别太贪心：启发式越接近真实距离，A*越快。但如果你用「完美启发式」（比如预计算所有节点到终点的距离），那A*就退化成Dijkstra了。嗯，这里要注意平衡。
内存管理：JPS虽然搜索快，但跳跃点预处理需要额外内存。我建议在初始化阶段就把跳跃点算好存起来，别每次搜索都重新算。
动态障碍物：如果地图中有移动障碍物（比如其他无人机），JPS的预处理就失效了。这时候我建议用D* Lite或者RRT*，不过那是后面章节的内容了。

好了，路径搜索算法的核心就这些。记住：没有最好的算法，只有最合适的算法。选型时多想想你的地图长什么样、实时性要求多高、内存够不够用。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录