第4章启发式搜索入门

第4章：启发式搜索入门

各位同学，今天我们来聊聊路径规划里一个特别有意思的话题——启发式搜索。说实话，我刚开始接触这个领域时，觉得搜索算法不就是暴力遍历嘛，顶多加点剪枝。直到我在一个仓储机器人项目里，面对一个1000×1000的栅格地图，用Dijkstra算一条路径等了快3秒……嗯，那时候我才意识到，没有启发式信息的搜索，就像蒙着眼睛找路。

4.1 什么是启发式函数？

启发式函数，说白了就是一个「估算值」。它告诉你：从当前节点到目标，大概还有多远。这个估算不一定准，但必须靠谱。

我个人习惯把启发式函数比作「导航里的预估到达时间」。你开车时，导航说「还有15分钟到」，这个15分钟就是启发式值。它可能因为堵车而不准，但至少给你一个方向感。

在路径规划里，启发式函数通常记作 h(n)，表示从节点 n 到目标节点的估计代价。它的核心要求是：不能高估实际代价。这个性质叫「可采纳性」（Admissible）。

核心原则：启发式函数必须满足 h(n) ≤ 实际代价，否则搜索可能找不到最优路径。

4.2 三种经典启发式函数

我在项目中用过不下十种启发式函数，但最基础、最常用的就这三种。你想想看，它们分别对应了不同的移动方式。

4.2.1 曼哈顿距离（Manhattan Distance）

适用于只能上下左右移动的场景（四方向网格）。公式很简单：

h(n) = |x1 - x2| + |y1 - y2|

我记得第一次做AGV小车项目时，用的就是曼哈顿距离。因为小车在仓库里只能沿货架走直线，不能斜着穿。当时我犯了个错——直接用欧几里得距离，结果规划出来的路径频繁撞墙。后来改成曼哈顿距离，问题就解决了。

我的经验：如果你做的是四方向移动的机器人（比如仓储AGV），曼哈顿距离是默认首选。计算快，效果稳。

4.2.2 欧几里得距离（Euclidean Distance）

适用于可以任意方向移动的场景（八方向或连续空间）。公式：

h(n) = sqrt((x1 - x2)² + (y1 - y2)²)

这个函数在RRT、PRM等采样算法里用得特别多。我曾经在无人机路径规划项目里用过它，效果不错。但要注意一点：欧几里得距离计算涉及开方，比曼哈顿距离慢一些。如果你在嵌入式设备上跑，建议用近似计算或者查表法。

避坑指南：我曾经在STM32上跑A*算法，用了欧几里得距离，结果每次计算h(n)都要开方，导致整体帧率下降。后来改成曼哈顿距离，速度提升了30%。所以，能不用开方就别用。

4.2.3 切比雪夫距离（Chebyshev Distance）

适用于允许对角线移动的网格（八方向移动）。公式：

h(n) = max(|x1 - x2|, |y1 - y2|)

这个函数很有意思。它假设你可以像国际象棋里的王一样，一次走一格，但可以斜着走。我一般在做游戏AI时用这个，比如《星际争霸》里的单位寻路。为什么？因为游戏地图通常是网格，单位可以八方向移动，切比雪夫距离正好匹配这种移动方式。

启发式函数	适用场景	计算复杂度	是否可采纳
曼哈顿距离	四方向网格	O(1)	是
欧几里得距离	连续空间/八方向	O(1)（含开方）	是
切比雪夫距离	八方向网格	O(1)	是

4.3 贪心最佳优先搜索（Greedy Best-First Search）

讲完启发式函数，我们来看看它的第一个应用——贪心最佳优先搜索。这个算法很简单：每次都选离目标最近的节点。

说白了，它只看启发式值 h(n)，完全不考虑已经走了多远。就像一个人只看远方，不看脚下。这样做的好处是：搜索速度极快。坏处是：可能找到一条很烂的路径。

我曾经在一个迷宫求解项目里对比过：用贪心最佳优先搜索，0.2秒就找到了一条路径，但长度是Dijkstra找到的2倍。为什么会这样？因为贪心算法容易被局部最优欺骗。它看到一条路离目标近，就一头扎进去，结果发现是死胡同，还得退回来。

4.3.1 算法流程

1. 将起点加入开放列表
2. 循环：
   a. 从开放列表中取出h(n)最小的节点
   b. 如果该节点是目标，结束
   c. 否则，扩展该节点的邻居
   d. 将邻居加入开放列表
3. 重复直到找到目标或开放列表为空

你看，这个流程和Dijkstra很像，唯一的区别是：Dijkstra用 g(n)（已走距离）来排序，而贪心最佳优先用 h(n)（估计距离）来排序。

关键区别：

Dijkstra：选 g(n) 最小的节点 → 保证最优
贪心最佳优先：选 h(n) 最小的节点 → 速度快但不保证最优

4.3.2 代码示例

下面是我写的一个简化版贪心最佳优先搜索。注意，这里只用了启发式函数，没有考虑实际代价。

def greedy_best_first_search(start, goal, grid):
    open_list = [(heuristic(start, goal), start)]
    closed_set = set()
    parent = {start: None}
    
    while open_list:
        # 取出h值最小的节点
        _, current = heapq.heappop(open_list)
        
        if current == goal:
            return reconstruct_path(parent, current)
        
        closed_set.add(current)
        
        for neighbor in get_neighbors(current, grid):
            if neighbor in closed_set:
                continue
            
            if neighbor not in parent:
                parent[neighbor] = current
                h = heuristic(neighbor, goal)
                heapq.heappush(open_list, (h, neighbor))
    
    return None  # 没找到路径

个人建议：贪心最佳优先搜索适合用在「路径质量要求不高，但速度要求极高」的场景。比如游戏里的NPC寻路，或者实时策略游戏里的单位移动。但如果你做的是自动驾驶、机器人导航这类对路径质量有要求的任务，还是老老实实用A*吧。

4.4 启发式函数的选择策略

讲了这么多，你可能会问：到底该选哪个启发式函数？我的经验是，没有万能答案，但有几条原则：

匹配移动方式：四方向用曼哈顿，八方向用切比雪夫，连续空间用欧几里得。
考虑计算开销：嵌入式设备上尽量用曼哈顿或切比雪夫，避免开方。
权衡精度与速度：启发式函数越精确，搜索节点越少，但计算每个节点的时间越长。

我记得有一次，我在一个农业机器人项目里，需要在果园里规划路径。果园里的树是网格状种植的，机器人只能沿树行走（四方向）。我一开始用了欧几里得距离，结果搜索了太多节点。后来改成曼哈顿距离，搜索节点数减少了40%，路径质量完全没变。

重要提醒：不要盲目追求「精确」的启发式函数。有时候，一个「差不多」的启发式函数，配合好的搜索策略，效果反而更好。我曾经见过有人用欧几里得距离做四方向网格的A*，结果因为启发式函数高估了实际代价，导致找不到最优路径。嗯，这就是典型的「好心办坏事」。

4.5 本章小结

这一章我们聊了启发式搜索的核心——启发式函数。三种经典函数各有适用场景，贪心最佳优先搜索则展示了启发式函数的威力（和局限）。下一章，我们会把Dijkstra和贪心最佳优先结合起来，这就是大名鼎鼎的A*算法。

最后留个思考题：如果在一个八方向网格里，用曼哈顿距离作为启发式函数，会发生什么？提示一下，想想可采纳性。

好了，今天就到这里。下次见。

📚 课程目录