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 排序依据DijkstragGBFShA*gh这张表其实就是三种算法的性格。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.mfunction [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的gh就会发现它为什么成为最经典的折中方案。