GBFS 路径规划：只盯着终点走，真的会更快吗？-酒店常州论坛

GBFS 路径规划：只盯着终点走，真的会更快吗？

关键词｜启发式搜索｜贪心策略｜Manhattan 距离

前言

如果说 Dijkstra 是一个非常稳重的人，那么 GBFS 就像一个目标感极强、甚至有些“莽”的人。它不在乎已经走了多远，只关心一件事：

当前位置看起来离终点还有多远？

这种做法当然很激进。好处是搜索方向非常明确，很多地图上它能迅速逼近终点；坏处是，一旦前方障碍复杂，它也很容易被“看起来更近”这件事带偏。GBFS 很适合拿来理解“启发式搜索”到底是什么意思。

原理讲解

1. 启发函数 h(n)

GBFS 的核心是启发函数：

它表示“从当前节点到终点还剩多少距离”的估计值。常见写法有：

Manhattan 距离

Euclidean 距离

Octile 距离

适合 8 邻域：

2. GBFS 的排序规则

GBFS 的评价函数非常干脆：

也就是说，它完全不考虑从起点已经走了多少。假设有两个候选节点：

A：已经绕了 20 格，但离终点只剩 2 格
B：目前只走了 8 格，但离终点还剩 5 格

GBFS 会优先选 A。因为它只看：

谁离终点更近

3. 为什么它不保证最短路

考虑一个 U 型障碍。终点就在 U 型结构的另一侧。离终点最近的点，往往就在障碍壁附近，但真正的正确路线可能要先向反方向走，绕到开口处再回来。GBFS 会天然抗拒“先离终点远一点”。所以它很适合：

障碍简单
目标方向明确
更关心搜索速度而不是最优性

但不适合作为严格最短路基准。

4. 算法流程

GBFS 和 Dijkstra 的整体结构几乎一样。唯一核心区别是：

算法	OPEN 排序依据
Dijkstra	`g`
GBFS	`h`
A*	`g+h`

这张表其实就是三种算法的性格。

5. 一个典型反例：终点就在墙后面

可以想象下面这种布局：

S → → → █ G █ █ █ ← ← ↓

从几何距离看，贴着墙向右走会让h快速减小，因此 GBFS 很喜欢这条方向。可真正的通道却在墙的下方。算法必须暂时“离终点更远”，才能绕过去。这正是 GBFS 的软肋：启发函数只告诉你目标在哪，并不告诉你障碍怎样分布。

6. 启发函数不是越大越好

有人会下意识觉得：

既然启发函数可以让搜索更有方向，那把它放大是不是会更快？

例如：

对于 GBFS 来说，统一倍乘并不会改变节点排序；但在 A* 或加权 A* 中，权重会改变g与h的平衡。这里真正应该关注的不是数值大不大，而是：

是否能反映当前运动模型；
是否会让搜索过度偏向目标；
是否会忽略必要的绕行。

7. GBFS 最适合扮演什么角色

在实际项目里，我更愿意把 GBFS 当成一种“速度基线”或“启发式对照组”。如果它和 A* 在某张地图上得到几乎相同的路径，但扩展节点明显更少，说明这张地图的障碍结构比较简单，启发方向非常有效。反过来，如果 GBFS 路径明显更绕，也正好说明g的存在为什么重要。

代码详解

1. 节点结构没有变化

仍然可以写成：

[x, y, g, h, px, py]

虽然g不参与扩展顺序，但仍然会记录下来，因为最后我们还要计算路径实际 cost。

2. 关键变化只有一行

[~, index] = min(OPEN(:, 4));

这里第四列就是h。换句话说，GBFS 的全部“贪心”都来自这行代码。它告诉算法：

别管之前花了多少，谁离 goal 最近，就先处理谁。

3. 启发函数计算

典型实现：

h_val = abs(node(1) - goal(1)) + ... abs(node(2) - goal(2));

这是 Manhattan 距离。如果地图允许 8 邻域斜走，严格从几何匹配上来说，Octile distance 会更自然。不过 GBFS 本来就不追求理论最优，因此这里主要影响的是搜索“偏向”程度。

4. g 为什么还要保留

代码里仍会写：

new_g = cur_g + step_cost;

原因不是排序，而是为了最终报告：

cost

所以可以把g理解成一本账。GBFS 不用这本账决定下一步，但最后还是要告诉你一共花了多少。

5. 一个很适合观察的现象

如果把expand全部画出来：

Dijkstra：像圆一样向外扩散
GBFS：像一束光一样直冲目标
A*：介于两者之间

这也是最推荐做公众号配图的对比之一。

8. 运行结果应该怎样观察

建议把障碍墙的缺口改到远离 goal 的一侧，再运行一次。你会发现 GBFS 一开始仍会非常坚定地朝 goal 方向扩展，直到障碍迫使它改变策略。这个实验比单纯看公式更能说明：h只提供方向感，并不包含完整环境结构。

完整 MATLAB 实现：`gbfs.m`

function [path, goal_reached, cost, EXPAND] = gbfs(map, start, goal) % 节点格式为 [x, y, g, h, px, py]。 % GBFS 的搜索顺序只由启发值 h 决定，g 主要用于记录最终路径代价。 OPEN = []; CLOSED = []; EXPAND = []; cost = 0; goal_reached = false; % 8 邻域移动：直移代价为 1，对角移动代价约为 sqrt(2) motion = [-1, -1, 1.414; ... 0, -1, 1; ... 1, -1, 1.414; ... -1, 0, 1; ... 1, 0, 1; ... -1, 1, 1.414; ... 0, 1, 1; ... 1, 1, 1.414]; motion_num = size(motion, 1); % 起点同时记录累计代价和到目标的启发距离 node_s = [start, 0, h(start, goal), start]; OPEN = [OPEN; node_s]; while ~isempty(OPEN) % 贪心最佳优先搜索只比较 h，优先展开最接近目标的候选点 [~, index] = min(OPEN(:, 4)); cur_node = OPEN(index, :); OPEN(index, :) = []; if loc_list(cur_node, CLOSED, [1, 2]) continue end % 保存展开轨迹，方便绘制搜索区域 if ~loc_list(cur_node, EXPAND, [1, 2]) EXPAND = [EXPAND; cur_node(1:2)]; end % 找到目标后返回当前累计路径代价 if cur_node(1) == goal(1) && cur_node(2) == goal(2) CLOSED = [cur_node; CLOSED]; goal_reached = true; cost = cur_node(3); break end for i = 1:motion_num node_n = [ cur_node(1) + motion(i, 1), ... cur_node(2) + motion(i, 2), ... cur_node(3) + motion(i, 3), ... 0, ... cur_node(1), cur_node(2)]; % 为新邻居计算 Manhattan 启发距离 node_n(4) = h(node_n(1:2), goal); if loc_list(node_n, CLOSED, [1, 2]) continue end if map(node_n(1), node_n(2)) == 2 continue end OPEN = [OPEN; node_n]; end CLOSED = [cur_node; CLOSED]; end path = extract_path(CLOSED, start); end %% function h_val = h(cur_node, goal) % 采用 Manhattan 距离衡量当前节点与目标之间的启发距离 h_val = abs(cur_node(1) - goal(1)) + abs(cur_node(2) - goal(2)); end function index = loc_list(node, list, range) % 在 list 指定字段中查找与 node 相同的记录 num = size(list); index = 0; if ~num(1) return else for i = 1:num(1) if isequal(node(range), list(i, range)) index = i; return end end end end function path = extract_path(close, start) % 依据父节点坐标从目标侧逐级回溯到起点 path = []; closeNum = size(close, 1); index = 1; while 1 path = [path; close(index, 1:2)]; if isequal(close(index, 1:2), start) break end for i = 1:closeNum if isequal(close(i, 1:2), close(index, 5:6)) index = i; break end end end end

总结与思考

GBFS 很像现实中的“只看眼前方向”。有时候这种策略特别有效，尤其是终点明显、障碍不复杂的时候；但一旦环境需要绕路，它就会暴露出明显短板。它最大的教学价值，是帮助我们真正理解启发式搜索：

启发函数并不是“答案”，而只是搜索方向上的一种估计。

如果把g和h放在一起，下一步自然就会走到 A。GBFS 也提醒我们一件事：搜索速度和路径质量往往存在取舍。一个更激进的启发策略，可能更快抵达终点，也可能更容易被障碍结构欺骗。理解了这个矛盾，再看 A的g+h，就会发现它为什么成为最经典的折中方案。

企业官网建设流程全解析