GBFS贪婪最佳优先搜索算法深度解析

一、从一个问路的场景说起

假设你站在一个陌生城市的街头，想要去市中心的火车站。你手里没有地图，只有一个指南针和一张标注了火车站方向的简易示意图。

你会怎么走？

大多数人的选择是：朝着火车站的方向走，遇到岔路口就选那条看起来更靠近火车站的路。你不会绕到城市的另一头去试探，也不会把所有的路都走一遍。你只做一件事——每一步都选择看起来离目标最近的方向。

这种"跟着感觉走"的策略，在计算机科学中就叫做贪婪最佳优先搜索（Greedy Best-First Search，简称GBFS）。它是启发式搜索算法家族中最直观、最简单的一员，也是理解更复杂搜索算法（如A*）的基础。

二、GBFS的核心思想

2.1 什么是启发式搜索

在介绍GBFS之前，我们先来理解一个关键概念：启发函数（Heuristic Function）。

传统的搜索算法（如BFS、DFS）就像是蒙着眼睛找路——它们只知道自己走过了哪里，却不知道目标在哪里。而启发式搜索则像是睁开了眼睛，它通过一个"启发函数"来估算当前位置到目标的距离，从而引导搜索方向。

用一个简单的公式来表示：

1

f(n) = h(n)

其中：

• f(n) 是节点 n 的评估值
• h(n) 是启发函数，表示从节点 n 到目标节点的估算代价

GBFS的策略非常直接：每次选择评估值最小的节点进行扩展。换句话说，永远朝着看起来离目标最近的方向前进。

2.2 启发函数的设计

启发函数是GBFS的灵魂。一个好的启发函数能让算法快速找到目标，一个差的启发函数则可能让算法绕很多弯路。

常见的启发函数有：

对于网格地图中的路径搜索，曼哈顿距离是最常用的启发函数：

1
2

def manhattan_distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

这个函数的含义很直观：在只能走横竖的网格中，从A点到B点至少要走多少步。

三、GBFS算法详解

3.1 算法流程

GBFS的实现依赖于优先级队列（Priority Queue），也叫"开集合"（Open Set）。算法的基本流程如下：

1
2
3
4
5
6
7
8
9
10
11

1. 将起点加入优先级队列，评估值为启发函数值
2. 初始化"已访问集合"（Closed Set）为空
3. 当优先级队列不为空时：
   a. 取出评估值最小的节点（当前节点）
   b. 如果当前节点是目标节点，搜索成功，返回路径
   c. 将当前节点加入已访问集合
   d. 遍历当前节点的所有邻居：
      i. 如果邻居已在已访问集合中，跳过
      ii. 如果邻居不在优先级队列中，计算其启发函数值，加入队列
      iii. 如果邻居已在队列中且新的评估值更小，更新
4. 如果队列为空仍未找到目标，搜索失败

用流程图来表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

┌─────────────┐
│  加入起点    │
└──────┬──────┘
       ▼
┌─────────────┐
│ 队列是否为空？│──是──▶ 搜索失败
└──────┬──────┘
       │否
       ▼
┌─────────────┐
│ 取出最优节点 │
└──────┬──────┘
       ▼
┌─────────────┐
│ 是目标节点吗？│──是──▶ 搜索成功
└──────┬──────┘
       │否
       ▼
┌─────────────┐
│ 标记为已访问  │
└──────┬──────┘
       ▼
┌─────────────┐
│ 扩展邻居节点  │
└──────┬──────┘
       ▼
┌─────────────┐
│ 加入优先级队列│
└─────────────┘

3.2 Python实现

下面我们用Python实现一个基于网格地图的GBFS算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import heapq

def greedy_best_first_search(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    
    def heuristic(x, y):
        return abs(x - goal[0]) + abs(y - goal[1])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    open_set = []
    heapq.heappush(open_set, (heuristic(start[0], start[1]), start[0], start[1]))
    
    came_from = {}
    visited = set()
    
    while open_set:
        h, x, y = heapq.heappop(open_set)
        
        if (x, y) == goal:
            path = []
            while (x, y) in came_from:
                path.append((x, y))
                x, y = came_from[(x, y)]
            path.append(start)
            path.reverse()
            return path
        
        if (x, y) in visited:
            continue
        visited.add((x, y))
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                if (nx, ny) not in visited:
                    heapq.heappush(open_set, (heuristic(nx, ny), nx, ny))
                    if (nx, ny) not in came_from:
                        came_from[(nx, ny)] = (x, y)
    
    return None

我们来测试一下这个算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

grid = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]

start = (0, 0)
goal = (9, 9)

path = greedy_best_first_search(grid, start, goal)

if path:
    print(f"找到路径，长度为 {len(path)} 步")
    print("路径：", path)
else:
    print("未找到路径")

运行结果：

1
2

找到路径，长度为 19 步
路径： [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9)]

可以看到，GBFS找到了一条沿着地图右边缘向下走的路径。这符合贪心策略的特点——始终朝着目标（右下角）的方向前进。

四、GBFS的特性分析

4.1 最优性：不保证最短路径

GBFS最大的特点就是不保证找到最优路径。这是因为它只关心"离目标有多近"，而不关心"已经走了多远"。

我们来看一个经典的例子：

1
2
3
4
5

S ── 1 ── A ── 1 ── B ── 1 ── G
│                     │
5                     5
│                     │
C ──── 1 ──── D ──── 1 ┘

在这个图中：

• 起点是S，目标是G
• 上边的路径 S→A→B→G，总长度是3
• 下边的路径 S→C→D→G，总长度是11

如果我们用"到G的直线距离"作为启发函数，那么从S出发时：

• A离G的直线距离约为2，评估值=2
• C离G的直线距离约为5，评估值=5

GBFS会优先扩展A，然后是B，最后到达G。找到的路径长度是3，恰好是最优的。这是因为启发函数"恰好"引导了正确的方向。

但如果地图是这样的：

1
2
3
4
5

S ─────── 10 ─────── A
│                     │
1                     1
│                     │
B ─────── 10 ─────── G

启发函数（直线距离）告诉我们：

• 从S看，A离G更近（距离1），评估值=1
• 从S看，B离G更远（距离10），评估值=10

GBFS会优先选择走 S→A→G，总长度11。但实际上 S→B→G 同样是11，两条路径长度相同。这个例子中启发函数没有"骗"我们，但下面这个例子更能说明问题。

再看一个更直观的网格例子：

1
2
3
4
5

S . . . . . . . . .
# # # # # # # # # .
. . . . . . . . . .
. # # # # # # # # #
. . . . . . . . . G

在这个地图中：

• 起点S在左上角
• 目标G在右下角
• 中间有两条水平的墙

GBFS一开始会向右走，但走到第一条墙的尽头后，会绕远路。而最优路径可能是先向下走，避开墙壁。

这就是GBFS的问题：它可能被局部最优迷惑，为了"靠近目标"而绕了远路。

4.2 完备性：有限空间中完备

在有限的状态空间中，如果存在从起点到目标的路径，GBFS一定能找到它——只要我们正确维护了"已访问集合"，避免重复访问。

但在无限的状态空间中，GBFS可能永远找不到目标。比如在一个无限大的网格中，如果启发函数引导算法朝着错误的方向越走越远，它就永远不会回头。

4.3 时间和空间复杂度

GBFS的时间和空间复杂度取决于启发函数的质量：

其中：

• b 是分支因子（每个节点的平均邻居数）
• d 是最浅目标节点的深度
• m 是搜索空间的最大深度

在最好的情况下，启发函数完美地引导算法直达目标，搜索的节点数与路径长度成正比。在最坏的情况下，启发函数完全失效，算法退化为类似DFS的行为，可能遍历整个搜索空间。

五、GBFS与其他搜索算法的对比

5.1 四种经典搜索算法

为了更清楚地理解GBFS的位置，我们把它和另外三种经典搜索算法放在一起对比：

可以看到，这四种算法的区别就在于评估函数的设计：

• BFS只看"已经走了多远"（深度）
• DFS反着看深度，越深越优先
• GBFS只看"离目标还有多远"（启发函数）
• A*两者都看，是BFS和GBFS的结合

5.2 为什么A*比GBFS更优秀

A*算法的评估函数是：

1

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

其中 g(n) 是从起点到当前节点的实际代价，h(n) 是从当前节点到目标的估计代价。

为什么加上 g(n) 就保证了最优性？因为A综合考虑了"已经付出的代价"和"未来可能的代价"。当启发函数满足*可采纳性（即h(n)不高估实际代价）时，A*第一次找到目标时的路径一定是最优的。

打个比方：

• GBFS就像是一个只看终点方向的跑步者，哪里看起来离终点近就往哪跑，可能绕了远路自己还不知道
• A*就像是一个带着计步器的跑步者，既看终点方向，又记着自己跑了多少路，确保每一步都在"总路程最短"的轨道上

5.3 什么时候用GBFS

既然A*更优秀，那GBFS还有用武之地吗？答案是肯定的：

1. 只需要找到路径，不需要最优：在很多实际场景中，我们只需要找到一条可行的路径，而不要求它是最短的。比如游戏中的NPC寻路，只要能到达玩家位置就行，路径差几步没关系。

2. 启发函数非常可靠：如果启发函数设计得非常好，几乎能准确估计距离，那么GBFS的效果会非常接近A*，但实现更简单。

3. 实时性要求高：GBFS通常比A*更快找到第一条路径（虽然不一定最优）。在某些实时系统中，"快速找到一条路"比"找到最优路径"更重要。

4. 内存受限：GBFS的内存占用通常比A*小，因为它不需要维护g值。在内存紧张的环境中，GBFS可能是更好的选择。

六、GBFS的改进与变体

6.1 带回溯的GBFS

标准的GBFS一旦选择了一个方向，就很难回头——因为优先级队列中可能已经积累了大量"看起来更优"的节点。

一种改进方法是加入回溯机制：当发现当前路径走不通时，回退到上一个岔路口，选择次优的方向继续搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def gbfs_with_backtracking(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    
    def heuristic(x, y):
        return abs(x - goal[0]) + abs(y - goal[1])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    path = [start]
    visited = {start}
    
    while path:
        x, y = path[-1]
        
        if (x, y) == goal:
            return path
        
        neighbors = []
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0 and (nx, ny) not in visited:
                neighbors.append((heuristic(nx, ny), nx, ny))
        
        if neighbors:
            neighbors.sort()
            _, nx, ny = neighbors[0]
            visited.add((nx, ny))
            path.append((nx, ny))
        else:
            path.pop()
    
    return None

这种实现更像是"带启发的深度优先搜索"，内存占用更小，但可能更容易陷入局部最优。

6.2 加权GBFS

有时候，我们希望在"贪心程度"上做一些调整。比如，在搜索的早期多探索一些，在搜索的后期更贪心一些。

加权GBFS的评估函数是：

1

f(n) = w * h(n)

其中 w 是权重：

• w = 1：标准GBFS
• w > 1：更贪心，更快但可能更偏离最优
• w < 1：不那么贪心，可能更接近最优但更慢

1
2
3
4
5

def weighted_gbfs(grid, start, goal, weight=1.0):
    # ... 类似标准GBFS，只是启发函数值乘以weight
    def heuristic(x, y):
        return weight * (abs(x - goal[0]) + abs(y - goal[1]))
    # ...

6.3 双向GBFS

另一种改进思路是双向搜索：从起点和终点同时出发，相向而行，当两个搜索前沿相遇时，就找到了完整的路径。

双向GBFS可以显著减少搜索的节点数，尤其是在大规模地图中。

1

正向搜索：S → · → · → ◀── 相遇点 ──▶ · → · → G ：反向搜索

七、总结与思考

GBFS是一个简单而强大的算法，它教会我们一个朴素但深刻的道理：方向比努力更重要。

• BFS像是"全面撒网"，虽然能找到最优解，但代价是巨大的搜索量
• DFS像是"一条道走到黑"，可能很快找到解，也可能走很多冤枉路
• GBFS则是"朝着目标前进"，用启发函数指引方向，通常能更快地找到解

当然，GBFS也有它的局限性：

• 它不保证找到最优路径
• 它的效果高度依赖启发函数的质量
• 它可能被局部最优所迷惑

但这些局限性并不妨碍GBFS成为一个非常实用的算法。在很多实际问题中，我们并不需要最优解，只需要一个"足够好"的解，而且要快。这时候，GBFS就是最好的选择。

学习GBFS的真正价值，不在于记住算法的每一个步骤，而在于理解"启发式思维"——在信息不完全的情况下，如何利用已有知识做出最优的决策。这种思维方式，不仅适用于算法设计，也适用于我们生活中的方方面面。

下次当你面临选择、需要快速做出决策时，不妨想想GBFS：找到你的"启发函数"，然后朝着目标前进。