第4章启发式搜索

第4章：启发式搜索——A*算法核心思想与实战

各位同学，欢迎来到航迹规划的核心章节。今天我们要聊的A*算法，可以说是路径搜索领域的“万金油”。我在做机器人导航项目时，80%的场景第一反应就是上A*。为什么？因为它够聪明，够快，而且实现起来不复杂。

4.1 从Dijkstra到A*：我们为什么要“启发”

先回忆一下Dijkstra算法。它像个勤奋的扫地机器人，把每个角落都扫一遍，保证找到最短路径。但问题来了——它太“老实”了。明明目标在东北方向，它还要往西南方向探索一圈。

我当年第一次用Dijkstra做AGV调度时，地图稍微大一点，计算时间就飙到秒级。老板在旁边看着，我那个汗啊……

A*算法就是在Dijkstra的基础上，加了一个“方向感”。它用启发函数来估计当前点到目标点的距离，优先探索那些“看起来有希望”的节点。说白了，就是给搜索过程装了个指南针。

4.2 A*核心思想：f = g + h

A*的核心公式就一个：

f(n) = g(n) + h(n)

解释一下：

g(n)：从起点到当前节点n的实际代价。这个我们已经走过了，是确定值。
h(n)：从当前节点n到目标节点的估计代价。这是启发函数，是估计值。
f(n)：总代价，也就是我们用来排序的依据。

算法每次从open list中取出f值最小的节点进行扩展。嗯，这里要注意：h(n)必须满足可采纳性——它不能高估实际代价。否则A*就退化成不保证最优的贪心算法了。

核心要点：h(n)估计得越准，搜索效率越高；h(n)=0时，A*退化为Dijkstra。

4.3 启发函数设计：三种距离的抉择

启发函数怎么选？这取决于你的地图类型。我整理了一张表，方便你对照：

距离类型	计算公式	适用场景	特点
曼哈顿距离	\|x1-x2\| + \|y1-y2\|	四方向网格地图	计算快，但可能低估
欧氏距离	√((x1-x2)² + (y1-y2)²)	八方向或自由移动	最精确，但有开方运算
切比雪夫距离	max(\|x1-x2\|, \|y1-y2\|)	八方向网格（国王移动）	兼顾精度和速度

我在做仓储机器人项目时，一开始用了曼哈顿距离。结果发现机器人明明可以斜着走，但路径规划出来全是直角转弯，效率低了不少。后来换成切比雪夫距离，路径就顺滑多了。

我的建议：如果地图允许八方向移动，优先用切比雪夫距离。它比欧氏距离快（没有开方），比曼哈顿距离准。

4.4 A*算法代码实现（Python）

光说不练假把式。下面是我常用的A*实现模板，你直接拿去改改就能用：

import heapq

def astar(start, goal, grid):
    # 方向向量：四方向或八方向
    # 这里用四方向为例
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    
    open_list = []
    heapq.heappush(open_list, (0, start))
    
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    came_from = {}
    
    while open_list:
        current = heapq.heappop(open_list)[1]
        
        if current == goal:
            return reconstruct_path(came_from, current)
        
        for dx, dy in directions:
            neighbor = (current[0] + dx, current[1] + dy)
            
            # 检查边界和障碍物
            if not in_bounds(neighbor, grid) or grid[neighbor[0]][neighbor[1]] == 1:
                continue
            
            tentative_g = g_score[current] + 1  # 假设每步代价为1
            
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_list, (f_score[neighbor], neighbor))
    
    return None  # 无路径

def heuristic(a, b):
    # 曼哈顿距离
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

我曾经踩过的坑：open list用list+sort()而不是heapq。地图一大，排序开销直接让算法慢10倍。记住，优先队列是A*的标配。

4.5 优化技巧：让A*跑得更快

实际项目中，原始A*往往不够用。这里分享几个我常用的优化手段：

双向A*：从起点和终点同时搜索，相遇即停止。能减少约50%的探索节点。
JPS（跳点搜索）：在网格地图中，跳过那些“明显不需要探索”的节点。我做过测试，比普通A*快10倍以上。
权重启发式：把f = g + h改成f = g + w*h，其中w>1。虽然不保证最优，但搜索速度大幅提升。适合实时性要求高的场景。
分层规划：先在高精度地图上粗规划，再在局部细化。我做过一个城市级路径规划，用这招把计算时间从分钟级降到了秒级。

4.6 知识体系总览

下面这张图，是我梳理的本章知识结构。你把它存下来，复习时对着看：

你看，A*的核心其实就三块：公式理解、启发函数选择、代码实现。把这三点吃透了，大部分路径规划问题都能搞定。

实战建议：刚开始学A*时，别急着上优化技巧。先把基础版本跑通，用不同启发函数对比效果。我当年就是先跑通基础版，再一步步加JPS、双向搜索，这样理解才扎实。

好了，这一章的内容就到这里。A*算法说难不难，说简单也不简单。关键是多动手、多调试。下次遇到路径规划问题，不妨先问问自己：我的启发函数选对了吗？

📚 课程目录