贪心最佳优先搜索(GBFS)原理与Python实现，从理论到工程避坑

我在给某导航系统的预研项目做路径规划方案时，第一次认真把贪心最佳优先搜索（Greedy Best-First Search，GBFS）从理论翻到了工程实现。当时的需求很直白：在几万个节点的路网里，要快，快地给出一个能用路线，而不是非最优不可——预算有限，推荐系统的响应时间也卡得紧。GBFS第一次进入视野时，我觉得它简单得不像话：完全不看已经走了多远，只看哪个节点看起来离目标最近。但真正把代码跑起来之后，才发现这套“急性子”逻辑里藏着一堆值得细讲的细节。这篇想把它完整说一遍：既讲清楚原理，也给出能直接参考的实现，还会把我在实际测试里踩过的坑和对比数据一并放出来。适合刚接触搜索算法的读者，也适合想快速落地一个启发式寻路原型的同学。

1. 贪心最佳优先搜索到底是什么

1.1 先看直觉：它为什么叫“贪心”又是怎么“最佳”的

我先把话说得直白一点。你站在一个陌生城市的十字路口，想去某个地标建筑。手里只有一张模糊的方向信息，没有全图，也没有导航。大多数人的做法是：看看哪个路口在物理上离目标更近，就直接往那个方向走。至于这条路绕不绕、堵不堵、前面有没有断头路，不管。

GBFS干的就是这件事。它维护一个“待考察节点”列表，每次从中挑出一个在所有候选中“看起来离目标最近”的节点，然后从这个节点继续扩展到它的邻居。这里的“看起来离目标最近”不是一个模糊感觉，而是一个具体函数算出来的数值，这个数值就是启发式函数h(n)。整个搜索过程中，它唯一关心的就是h(n)的大小。

为什么说它“贪心”？因为它每一步都只做局部最优的选择，完全不考虑从起点走到当前节点已经花了多少代价。从理论算法的视角看，这叫“只考虑启发信息、不考虑代价信息”。为什么又说它“最佳优先”？因为在每一步，它都会优先处理当前评估值最好的节点。不同于深度优先那样一根筋钻到底，也不像广度优先那样机械地按层级推进，它永远在最“有希望”的节点上持续深入。

这个思路最大的优势是快。路径规划问题里，分支因子通常不小，盲目搜索经常把无关节点的状态空间全部摊开。而GBFS在启发式函数足够好的时候，会像一支穿云箭一样直插目标方向。等你理解到A*算法只比它多了一个g(n)代价项，就能明白这一项之差，结果天差地别。

在搜索算法家族里，几乎所有成员都可以放到同一个评估函数框架下对照理解。深度优先的评估依据是“深度越深越优先”，广度优先是“深度越浅越优先”，Dijkstra算法是“累计代价g(n)越小越优先”，A*是“g(n)+h(n)越小越优先”，而GBFS是“h(n)越小越优先”。记住这一条，你再遇到任何搜索算法都不会迷路。

1.2 同台对比：DFS、BFS和GBFS的搜索哲学差异

很多教程喜欢把GBFS和DFS、BFS放在一起比，但我不建议只去看它们“都是图遍历”这个表面共同点，更值得关注的是它们各自的搜索哲学。

DFS的哲学是“一条道走到黑”。它会顺着一条路径不停地往下走，直到走不通了再退回上一个岔路口换一条路。这种策略的优点是内存占用极小，因为只需要保存当前路径上的节点；缺点是容易走进错误分支浪费大量时间，而且不保证找到最优解，甚至在无限图中可能永远找不到解。

BFS的哲学是“逐层推进”。它先把起点所有的邻居都看一遍，再去看邻居的邻居，像水面涟漪一样一圈圈扩散。这种策略保证在无权图中找到步数最少的路径，代价是空间占用爆炸——每一层都要保留大量节点，复杂度随层数指数增长。

GBFS的哲学则是“跟着直觉冲”。它不像DFS那样无脑深入，也不像BFS那样无差别扩散，而是基于启发式函数对每个节点打分，每次都冲向分数最好的节点。如果启发式函数写得好，它能跳过大量无用的区域，直接逼近目标；但如果启发式函数有偏差，它就会像没头苍蝇一样被误导到局部区域里打转。

我在实际对比中感受最深的一点是：DFS和BFS的行为是“可预测”的，不管地图长什么样，它们的扩展模式基本固定；而GBFS的行为完全由启发式函数决定，换一个h(n)，它的搜索路径可能完全不同。这既是它的灵活之处，也是它的危险之处。

2. 算法原理与代码实现

2.1 启发式函数：GBFS的“指南针”怎么造

启发式函数h(n)的核心含义是：从节点n到目标节点的估计代价。它不需要精确，只需要给出一个方向性的判断。在几何场景中，常用的距离函数有三种，选谁取决于你的移动模型。

曼哈顿距离适合四方向网格（只能上下左右移动），它计算的是两个点之间横向纵向差之和。欧几里得距离适合可以任意角度移动的开放空间，是直线距离。切比雪夫距离适合八方向网格（可以斜向移动），取横向和纵向差的较大值。我用一个网格地图来举例：如果角色只能上下左右走，用欧几里得距离就会频繁出现“看着近、实际要绕远路”的误导，因为斜线跨过障碍后无法直接斜穿。

import math def manhattan_distance(pos, goal): return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1]) def euclidean_distance(pos, goal): return math.sqrt((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) def chebyshev_distance(pos, goal): return max(abs(pos[0] - goal[0]), abs(pos[1] - goal[1]))

这里有一个概念叫“可采纳性”。如果h(n)永远不大于从n到目标的真实最小代价，我们就说这个启发式函数是可采纳的。A*算法必须依赖可采纳性来保证最优解，而GBFS没有这个硬性要求，它甚至用高估的启发式也能跑。但我要提醒一句：GBFS不要求可采纳，不代表启发式函数可以乱写。h(n)越接近真实代价，GBFS的行为就越理性；h(n)越离谱，它就越容易在错误的区域里反复徘徊。

我在调试时常用一个“指南针”类比：h(n)就像手里的指南针，它能告诉你目标大致在哪个方向，但不能告诉你路怎么走。指南针没坏，你就不会跑到完全相反的方向去；指南针偏差大，你就可能朝着错误的方向走出很远才发现问题。

2.2 一份可直接抄的Python实现

我给出一个通用性比较强的GBFS实现，它接收三个东西：起始终止节点、一个获取邻居的函数、一个启发式函数。这种写法让算法本身和具体业务解耦，后面换地图、换启发式都很方便。

import heapq def greedy_best_first_search(start, goal, get_neighbors, heuristic): """ get_neighbors: (node) -> list[neighbor] heuristic: (node_a, node_b) -> float """ open_heap = [] # 小顶堆，元素为 (h值, 计数器, 节点) counter = 0 heapq.heappush(open_heap, (heuristic(start, goal), counter, start)) came_from = {start: None} # 记录前驱，用于回溯路径 visited = set() # 已经扩展过的节点，防止回头路 best_h = {start: heuristic(start, goal)} # 记录每个节点目前的最小h值 while open_heap: _, _, current = heapq.heappop(open_heap) if current in visited: continue visited.add(current) if current == goal: # 回溯出完整路径 path = [] node = goal while node is not None: path.append(node) node = came_from[node] path.reverse() return path for next_node in get_neighbors(current): if next_node in visited: continue h_next = heuristic(next_node, goal) # 只有当前算出的h值比历史记录更小，才重新入堆 if h_next < best_h.get(next_node, float('inf')): best_h[next_node] = h_next heapq.heappush(open_heap, (h_next, counter, next_node)) came_from[next_node] = current counter += 1 return None

这一段代码有几个关键细节值得展开。

第一，为什么用(h值, 计数器, 节点)这个三元组入堆？因为优先队列在比较元素时会依次比较元组里的字段。如果只存(h值, 节点)，遇到两个h值完全相等的情况，它就会继续比较节点对象本身，而如果节点对象不支持大小比较，代码就会直接崩。加一个单调递增的计数器，可以保证在h值相同时按入堆顺序处理，彻底避开比较问题。

第二，为什么需要best_h字典？因为同一个节点可能从不同邻居被多次发现，每次算出的h值可能不同。如果没有这个字典，一个节点可能会在上百个不同时刻被重复入堆，造成严重的重复计算和内存浪费。维护“每个节点当前最小的h值”这个映射，是工程上对GBFS的标准优化。

第三，visited集合和best_h是两回事。visited防止已经扩展过的节点被再次扩展，best_h防止同一个节点被重复入堆。前者管的是“别回头”，后者管的是“别重复排队”。这两个都加上，代码才算完整。

2.3 “贪心”的付出：只少了一个g(n)，结果天差地别

GBFS和A之间其实只差一个g(n)，也就是从起点到当前节点的累计代价。A的评估函数是f(n) = g(n) + h(n)，GBFS则是f(n) = h(n)。这个差别看起来只是一个加法项，但在实际运行中会产生非常不同的行为。

我做一个很直观的网格地图反例。假设起点在左下角，目标在右上角，中间有一堵L形墙，唯一的开口在墙的最右侧。使用欧几里得距离作为h(n)。GBFS从起点出发，会大步流星地朝着目标直线方向冲，因为它觉得这条路“离目标最近”。冲进墙的封闭区域后，它才发现没有路，只能沿着墙面一个个节点试探。最终它也能找到出口，但走过的路径明显绕路，而且扩展的节点集中在一个错误的局部区域内。

A就好很多。因为它在每一步都要加上已经走过的步数，一个绕路的节点即使h(n)很小，如果g(n)已经很大，总分也会被拉高，就不会那么容易被诱惑。换句话说，A的g(n)像一根拴在GBFS身后的保险绳，让它保持方向感的同时，不会被眼前的直线距离冲昏头脑。

更糟糕的情况是死循环。考虑两个相邻节点A和B，A的h值是3，B的h值是2。GBFS从A走到B，发现B的邻居中A又回来了。如果没有visited集合，它会从B跳回A，又从A跳到B，永远震荡下去。这就是“纯贪心不看代价”的结构性缺陷。

在实际工程里，这种图结构比你想象中更常见。紧凑的室内地图、带回廊的迷宫、多层的立体停车库，都可能出现“局部低值区”。所以我在第一次写GBFS时就养成了一个习惯：任何用到GBFS的代码，第一件事就是把visited和best_h写上，不要觉得图简单就能省。

3. 典型应用场景与案例拆解

3.1 八数码问题：错位数与曼哈顿距离的实战对比

八数码问题是一个经典搜索测试场：3x3棋盘上摆着8个数字块和一个空位，通过移动空位附近的数字块，把棋盘调整到目标排列。搜索算法的目标是从乱序初始状态找到一条到达目标状态的路径。

我搭了个小实验，随机生成了20个可解状态，分别用两个不同的启发式函数去跑。第一组用“错位数”，也就是统计有多少个数字不在目标位置上；第二组用“曼哈顿距离之和”，也就是每个数字到自己目标位置的曼哈顿距离总和。两个h(n)都简单，但信息量差很多。

实测下来的结果，典型的单个案例是这样：错位数启发式下，GBFS平均扩展到上千个节点，找到解的路径大约30步；换成曼哈顿距离后，扩展节点数掉到两三百，找到解的路径也缩短到25步左右。如果对照组用A*加曼哈顿距离，扩展节点只有几十个，解路径接近最短。

这个对比非常有代表性。错位数虽然计算最简单，但区分度很差——很多差别巨大的状态错位数完全相同，GBFS几乎没法靠它区分“更有希望”的方向。曼哈顿距离提供了更细粒度的信息，搜索效率立刻上了一个台阶。我拿这个案例给其他人讲启发式函数的重要性时，基本不需要再多解释。

需要说明的是，这些数字只是我本地测试里的相对参考。八数码的初始状态分布很广，不同初始状态的难度差异极大，有时候同一个启发式函数下，简单状态扩展几十个节点，复杂状态扩展几万个节点都正常。

3.2 地图路径规划：直线距离也会骗人

把GBFS搬到地图路径规划上，第一个要理解的问题是：地图上的“直线距离最近”和“实际路径最短”是两回事。

我做过一个园区导航的简化模拟。园区东门是起点，西门是目标，两者之间有一片人工水域，水面不能通行，桥在南北两个方向。GBFS用欧几里得距离做启发式，一开始就朝水域中心方向冲。从搜索日志上看，扩展节点密密麻麻集中在起点到水域之间的区域，直到这半边全部碰壁，才开始被迫沿着水岸向南北扩散找桥。最后找到的路线要绕一大圈，而A*在同样条件下能更早地发现绕行代价，找到明显更合理的路径。

如果你的业务不要求最优路线，只要求“能在几百毫秒内给出一个不会撞墙的路线”，GBFS在很多场景下是能用的，但必须在工程上做些保护。比如给搜索深度加一个上限，超过一定步数就切换算法；或者在地图预处理阶段做连通性分析，把目标节点所在的可达区域提前算好，如果起点和目标根本不在同一个连通区域，直接返回不可达，根本不用跑搜索。

这个“连通分量预处理”的方法我强烈建议你在做地图寻路时加上。它成本很低，一次预处理，后面每次查询都是常数时间，但能规避掉GBFS在不可达状态下做大量无效搜索的尴尬。

3.3 游戏AI里的“脑残”但够用的寻路

游戏AI是GBFS真正大量出没的地方，但通常不是以纯算法形式出现。我见过好些个即时策略游戏原型，里面敌方单位追玩家单位时，如果要每次都用全图A*，成本不低。于是开发者会把GBFS当成“方向生成器”：先让一个单位用GBFS算出大方向，然后在几步范围内做局部避障。这种思路能跑，是因为游戏AI不需要最优路径，它只需要“看起来没有在发呆或者在撞墙”。

还有一个常见用法是“混合决策”。大型多人在线地图里，NPC会在几个关键目标点之间移动，每个目标点之间用预计算的路径，而动态障碍物出现时，才临时用启发式搜索做一个局部绕行。这种情况下，GBFS跑得快的特性被放大，而它容易绕路的缺点被限制在局部修正的范围内，影响被控制住了。

在这个场景下选型，我的经验是：先明确“最优路径”是不是硬性需求。如果只是让人看起来合理地移动，GBFS甚至加权A都比纯A划算；如果游戏里还有计分、竞速、寻宝这类对路径有质量要求的机制，那就老老实实上A*，别拿玩家的体感开玩笑。

4. 性能对比与工程调优

4.1 同一张地图上GBFS、A*、Dijkstra的三种表现

我专门做过一个对照实验。地图是一张100x100的网格，随机撒20%的障碍物，起点在左上角，目标在右下角。三套算法用同一个邻接关系，跑完记录三个指标：扩展节点数、耗时、路径长度。这里边权都设为1，所以Dijkstra其实退化成BFS，但比较结果依然有参考意义。

这组数据很能说明问题。GBFS确实最快，扩展的区域也最小，但它找到的路径比最优解长了约10%。A*多花了两倍多一点的时间，但给出了最优路径。Dijkstra在这个无权图上完全处于劣势，扩展了几乎整个可达区域。

如果你的项目对“搜索结果必须是最优”没有硬性要求，这10%的路径长度差距有时是完全可以接受的。比如园区导览、仓库AGV的粗规划、游戏NPC的漫游，路径长一点无伤大雅，但响应速度直接决定体验。反过来，如果是地图导航、无人机航线、成本敏感的物流路径，这10%可能就是不能接受的损耗。

4.2 时间与空间复杂度：快在哪里，贵在哪里

从大O复杂度上说，GBFS的最坏情况和DFS、BFS一样是O(b^m)，其中b是分支因子，m是搜索深度。最坏情况下，启发式函数可能完全失效，搜索会退化成类似DFS的行为，甚至更糟。但在实际场景中，启发式信息会显著减小有效搜索深度，这正是它“平均很快”的来源。

空间复杂度是GBFS的短板。它需要维护一个优先队列，队列里可能保存大量节点，最坏情况也是O(b^m)。这一点在非常大的状态空间里会成为瓶颈，因为DFS只需要O(m)的空间，BFS和GBFS则需要远大于它的内存。

我在工程选型时的判断标准是：如果状态空间大且内存紧张，优先考虑DFS系算法或者迭代加深；如果状态空间可控，但搜索深度深、目标明确，优先考虑GBFS或A*；如果最优解是硬需求，直接排除GBFS。空间这一点常被初学者忽略，以为GBFS跑得快就万事大吉，实际上一张几十万节点的图，堆内存会迅速膨胀。

4.3 从GBFS到加权A*：工程中更常用的折中方案

有一类算法很多人没单独学过，但在工程里非常常用，就是加权A*。它的评估函数是f(n) = g(n) + w * h(n)，其中w是大于1的权重。当w=1时它就是标准A*，当w趋向无穷大时它趋近于GBFS。工程上取w=2到5，可以换来比A*快数倍的搜索速度，同时路径质量只下降几个百分点。

我在那个园区导航模拟里做了一个改动：把纯GBFS换成加权A*，w取3，结果扩展节点数比A*少了约30%，路径只比最优解长3%。这个性价比在很多业务场景下非常划算，特别是地图规模大的时候。

def weighted_astar_heuristic(node, goal, w=3): return manhattan_distance(node, goal) * w

加权A*的代码只需要在GBFS的框架上把f改成g + w * h就行，几乎没有额外成本。这算是我在实际项目中最常推荐的GBFS替代方案：想要速度，又不想让路径质量太难看，用它准没错。

5. 常见问题与避坑实录

5.1 陷入死循环：为什么必须给GBFS拉上“缰绳”

我在小范围测试里第一次让GBFS跑迷宫时，就遇上了死循环。原因是早期版本只在came_from里记录前驱，没有维护visited集合。两个相邻节点互相在对方的邻居列表里，h值又一大一小，搜索就在这两个节点之间来回跳，程序一直跑不完，CPU一下子就跑满了。

后来我总结出三条硬性规则：

• 每个扩展过的节点，一定要进visited集合，并且扩展前先检查。
• 每个节点的最小h值要用best_h记录，只有更小才允许入堆。
• 不要试图用“节点是否已经在堆里”来判断重复，因为优先队列不支持高效的查询，用字典维护是标准做法。

只要这三条写全，GBFS就不会因为环形结构而陷入无限循环。

5.2 找到的解不一定能用：路径质量差和“看着近实际绕”怎么缓解

GBFS最容易被吐槽的问题，就是它产出的路径有时候怎么看怎么别扭，明明目的地就在视线可及的地方，路线却绕了半个地图。这个问题的根源在于它完全不看g(n)，所以没有机制去压制那些“只在h上优秀”的绕路节点。

缓解办法有三个层次。第一层，换加权A*，给g(n)一个存在感，这是成本最低的改动。第二层，在搜索完成之后做路径平滑处理，把路径里明显的直角拐弯、重复绕行段用几何方法拉直，很多观感问题在这一步就能解决。第三层，在生成地图时就把障碍区域做膨胀或者使用导航网格，让搜索算法的天然劣势被地图表示抵消掉一部分。

我自己的实践经验是：先试着把纯GBFS的路径结果画出来看一眼，如果只有少量局部绕行，后处理平滑就够了；如果整体路线都是偏的，说明启发式函数本身和地图的几何结构不匹配，应该优先调整启发式或者换算法，而不是在后处理上打补丁。

5.3 启发式函数的3个坑与选择建议

第一个坑是h(n)严重高估。这在A*里是致命错误，因为会破坏最优性，在GBFS里同样危险。h(n)高估会让算法过分自信，直接冲向一个“虚假的近路”，实际走进了死胡同。GBFS没有g(n)兜底，这个偏向会被放大。

第二个坑是h(n)区分度太低。错位数就是一个典型，极端情况下很多完全不同的状态算出同一个h值，优先队列里所有节点分数一样，GBFS直接退化成某种近似BFS，既没有DFS的省内存，也没有BFS的最优性，非常尴尬。

第三个坑是移动模型和距离函数不匹配。四方向网格用欧几里得距离、八方向网格用曼哈顿距离，都会让h(n)产生系统性的偏差。选启发式函数时，先回答一个问题：角色实际是怎么移动的？

最后给一个选择速查：

这些建议来自我踩过不少坑之后的总结。如果你只是拿来学习或做原型验证，GBFS加一个简单启发式足够；一旦要上生产环境，我建议优先看加权A*，它保留了GBFS的速度直觉，又给路径质量上了一道保险。按照我给出的代码框架，从GBFS改到加权A*不过是几行代码的事，这也是它最值得先写一版的原因。