A* 路径规划：为什么它能兼顾“走得快”和“走得短”？

A* 路径规划为什么它能兼顾“走得快”和“走得短”关键词启发式搜索gh可采纳性Octile 距离前言在栅格路径规划里A* 几乎是绕不开的算法。它不像 Dijkstra 那样“稳稳地向四周铺开”也不像 GBFS 那样“只盯着终点猛冲”。A* 做的事情很像我们现实中的路线选择既要考虑已经走了多远也要估计还剩多远。这一篇我们不只看公式fgh而是把这三个量真正拆开并结合 MATLAB 代码看它们如何影响搜索过程。原理讲解1. 三个代价值A* 定义其中起点到当前节点的真实代价当前节点到终点的估计代价经过当前节点时对整条路径总代价的估计可以把它理解成 text 总预算 ≈ 已经花掉的钱 预计还要花的钱### 2. 为什么 A* 比 Dijkstra 更有方向感 Dijkstra $$ fg $$ 它不知道终点在哪。GBFS $$ fh $$ 它不关心已经走了多少。A* $$ fgh $$ 于是搜索既不会无脑向四周扩也不会完全被终点方向牵着走。 ### 3. 启发函数为什么重要 如果 $$ h(n)0 $$ 那么 A* 就退化成 Dijkstra。如果 h 很强A* 会更像 GBFS。理论上为了保证经典最优性通常希望启发函数满足 $$ h(n)\le h^*(n) $$ 其中 $h^*(n)$ 是从当前节点到终点的真实最短代价。这叫**可采纳性admissibility**。 ### 4. 8 邻域里 Manhattan 有一个容易忽略的问题 如果允许斜走 text (0,0) → (1,1)真实一步代价是但 Manhattan 距离是出现高估。因此在 8 邻域下更自然的是 Octile distance这类细节非常值得关注因为“代码能运行”不等于“理论条件完全满足”。5. 算法流程A* 的执行过程可以概括为六步首先令 计算起点启发值并加入 OPEN随后对所有候选节点计算 每轮取f最小的节点展开对其可行邻居更新g、h与父节点信息并将已经处理完成的节点加入 CLOSED当 goal 被取出后沿父节点链回溯得到最终路径。这个流程和 Dijkstra 的框架非常接近真正改变搜索方向的核心就是h被加入了优先级计算。6. 一次简单的 f 值比较假设 OPEN 中有两个候选节点节点ghfghA4610B729A 离起点更近但 B 离终点更近。Dijkstra 会选 A因为g(A)g(B)GBFS 会选 B因为h(B)h(A)A* 也会选 B因为这个例子很小却把三种算法的区别说得非常清楚。7. 可采纳性之外还有“一致性”如果启发函数满足就称它具有一致性consistency。直观理解就是从当前点对终点的估计不应该比“先走一步再从邻居估计”还夸张。一致启发函数会让标准 A* 的f值沿路径呈非递减趋势也能减少节点被重新打开的需求。对普通栅格教学来说不必一开始就陷入严格证明但知道这个概念有助于理解为什么某些启发函数“理论上更干净”。8. A* 真正的性能瓶颈在哪里A* 速度通常由三件事共同决定启发函数质量越接近真实剩余代价搜索越集中OPEN 数据结构线性扫描和最小堆差别很大地图分辨率分辨率越高节点数增长越快。因此同样叫 A*不同工程实现的运行时间可能差一个数量级。算法名只是起点数据结构和地图建模同样重要。代码详解1. 起点初始化node_s [start, 0, h(start, goal), start];含义非常直观[x, y, g0, h, px, py]起点的父节点可以先写成自己。2. A* 最核心的三行f OPEN(:, 3) OPEN(:, 4); [~, index] min(f); cur_node OPEN(index, :);没有比这更能代表 A* 的代码了。第三列是g第四列是h。3. 生成邻居node_n(3) cur_node(3) step_cost; node_n(4) h(node_n(1:2), goal);一部分代价来自“已经发生”另一部分来自“未来估计”。4. 为什么会有重复节点一些简洁 MATLAB 实现并不会专门维护 OPEN 中某个坐标的唯一最优版本而是允许重复候选加入 OPEN。之后if loc_list(cur_node, CLOSED, [1,2]) continue end再把已经正式处理过的重复节点跳掉。这种写法简单但大地图会产生更多冗余。5. 路径回溯每次生成邻居时都保存parent cur_node(1:2);因此 goal 找到后可以沿父节点一路回到 start。这也是为什么路径规划代码里经常会同时保存状态 代价 父指针9. 一个值得做的对比实验保持地图、start、goal 完全一致分别运行dijkstra(...) gbfs(...) a_star(...)记录costsize(expand,1)运行时间通常会看到Dijkstra扩展最多路径基准稳定 GBFS扩展较少但路径可能更绕 A*在二者之间取得平衡这比孤立地看 A* 一张图更有说服力。完整 MATLAB 实现a_star.mfunction [path, goal_reached, cost, EXPAND] a_star(map, start, goal) % OPEN/CLOSED 中每行使用 [x, y, g, h, px, py]。 % A* 通过 f g h 同时考虑已走代价与剩余距离估计。 OPEN []; CLOSED []; EXPAND []; cost 0; goal_reached false; % 8 邻域运动模型 motion [-1, -1, sqrt(2); ... 0, -1, 1; ... 1, -1, sqrt(2); ... -1, 0, 1; ... 1, 0, 1; ... -1, 1, sqrt(2); ... 0, 1, 1; ... 1, 1, sqrt(2)]; motion_num size(motion, 1); % 起点 g0并计算初始启发值 node_s [start, 0, h(start, goal), start]; OPEN [OPEN; node_s]; while ~isempty(OPEN) % 计算所有候选节点的 fgh并取最小项展开 f OPEN(:, 3) OPEN(:, 4); [~, index] min(f); 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 % 按 8 邻域生成候选节点 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)]; % 计算邻居到 goal 的 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(node, goal) % 启发函数Manhattan 距离 h_val abs(node(1) - goal(1)) abs(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) % 根据 CLOSED 中的父节点字段恢复完整路径 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总结与思考A* 最值得记住的不只是fgh。真正重要的是它提供了一种很通用的思想搜索不只看过去也利用对未来的估计。这套思想后来会反复出现JPS减少没有必要扩展的节点Theta*改变邻居连接方式D*复用旧搜索结果Informed RRT*缩小后续采样空间它们看起来不同但本质上都在减少“没有价值的搜索”。从 A* 开始路径规划真正进入了“有方向地搜索”这一阶段。工程上我更愿意把 A* 看成一个“框架”而不是某个固定版本。邻域模型、启发函数、OPEN 数据结构、代价地图、障碍膨胀方式都会改变最终表现。真正掌握 A*不是会写出fgh而是知道这些模块分别在控制什么。