你玩游戏的时候有没有想过?NPC 怎么总能精准找到绕开障碍物的路,既不绕远也不撞墙?或者用地图 APP 查路线,它怎么知道哪条路最快?其实背后很可能用到了 A * 算法 —— 这是 AI 搜索领域里最经典、最实用的路径规划算法,很多新手觉得它 “听起来难”,其实搞懂核心逻辑特别好上手。

先别被 “AI 搜索算法” 这个名字唬住,小索奇认为,A * 算法的本质就是 “找路时既看已走的路,也预判未走的路,用最小代价找到最优路径”。它比传统的 Dijkstra 算法快,就是因为多了 “预判” 这一步;比贪心算法靠谱,是因为没只盯着 “眼前最近”,还考虑了 “已经付出的成本”。

要理解 A*,先记牢它的核心公式:f (n) = g (n) + h (n)。小索奇给你拆成大白话:

  • f (n):某个节点(比如地图上的 A 点、B 点)的 “总代价”,算法每次都会优先选 f 值最小的节点探索;
  • g (n):“实际成本”—— 从起点走到这个节点,已经花了多少代价(比如走了 5 步、10 米,或者绕了 2 个红绿灯);
  • h (n):“预估成本”—— 从这个节点到终点,大概还需要多少代价(这就是 A * 的 “预判” 关键,也叫启发函数)。

举个具体例子:假设你要从小区门口(起点 S)到公司(终点 T),中间有两条路可选:一条是穿公园的近路(但要绕 2 个弯),一条是走主干道的直路(但红绿灯多)。g (n) 就是你从 S 走到公园入口(节点 A)的距离(比如 300 米),h (n) 就是从 A 到 T 的预估距离(比如 500 米),f (n) 就是 800 米;而走到主干道路口(节点 B)的 g (n) 是 400 米,h (n) 是 450 米,f (n) 是 850 米 —— 这时候算法会优先探索节点 A,因为它的 f 值更小,看起来 “总代价更低”。

很多新手学 A * 会踩的第一个坑,就是把 h (n)(启发函数)选得不对。比如在方格地图里(像贪吃蛇、迷宫游戏的方格):

  • 要是只能上下左右走(不能斜着穿格子),h (n) 得用 “曼哈顿距离” 计算:|x1 - x2| + |y1 - y2|(x、y 是节点的横纵坐标),比如从 (1,2) 到 (4,5),曼哈顿距离就是 (4-1)+(5-2)=6,正好是 “右走 3 步 + 上走 3 步” 的总步数;
  • 要是允许斜着走(比如游戏里的角色能斜向移动),才用 “欧几里得距离”(两点之间直线距离):√[(x1-x2)² + (y1-y2)²]。

小索奇见过有人在方格地图里用错启发函数,比如明明不能斜走,却用了欧几里得距离当 h (n),结果算法要么绕远路(因为预估距离比实际近),要么搜索变慢(因为预判不准,走了很多冤枉路)。所以选对 h (n),A * 就成功了一半。

再说说 A * 的运行逻辑,其实就是维护两个 “列表”,流程特别清晰:

  1. 初始化:把起点 S 放进 “待探索列表”(Open List),这个列表里存的都是 “可能走的节点”;再建一个 “已探索列表”(Close List),存 “已经确认不用再看的节点”;
  1. 循环:从 Open List 里挑 f 值最小的节点(比如节点 A),把它移到 Close List;
  1. 查邻居:看节点 A 周围的所有邻居节点(比如上下左右四个格子),排除掉已经在 Close List 里的(说明已经探索过,没必要再看)、或者是障碍物的(不能走的路);
  1. 算代价:对每个有效邻居,算它的 g (n)(A 的 g 值 + A 到邻居的距离)、h (n)(到终点的预估距离)、f (n);
  1. 更新列表:如果邻居不在 Open List 里,就把它加进去,顺便记上 “它的前一个节点是 A”(方便最后回溯路径);如果邻居已经在 Open List 里,就对比 “现在算的 g 值” 和 “之前存的 g 值”—— 要是现在的 g 值更小(比如之前走了远路,现在发现近路),就更新它的 g 值和 f 值,同时把 “前一个节点” 改成 A;
  1. 终止:直到把终点 T 放进 Close List,就可以通过 “前一个节点” 回溯出完整路径(从 T 倒推回 S)。

你可以试试用这个逻辑画个简单的迷宫:在纸上画 10x10 的方格,标上起点、终点和几个障碍物,按上面的步骤选节点、算 f 值,很快就能画出最优路径 —— 亲测这样动手画一遍,比看十遍理论还管用。

A算法的应用场景特别广,不只是游戏和地图:比如快递机器人在仓库里找货位,要避开货架和行人,背后是 A;比如无人机巡检时规划航线,避开电线杆和建筑物,也可能用到 A*;甚至你在 Excel 里做物流路线优化,把 “城市” 当节点、“运费” 当代价,也能套用 A * 的逻辑。

小索奇要提醒一句:A不是 “万能算法”,比如在节点特别多的地图(像全国路网)里,直接用 A会有点慢,这时候会用 “分层 A*”(先粗定位大区域,再细搜小范围)优化;但对大多数中小型项目,比如做个小迷宫游戏、写个简单的路径规划工具,基础版 A * 完全够用。

你平时有没有遇到过需要 “找最优路径” 的场景?比如做小项目时想让程序自动绕开障碍物,或者玩游戏时想自己写个寻路功能?其实用 A算法就能实现。你学 A时遇到过什么疑问?是搞不懂两个列表的逻辑,还是选不准启发函数?可以在评论区跟小索奇聊聊,咱们一起把这个实用算法吃透~

我是【即兴小索奇】,点击关注,后台回复 领取,获取更多相关资源

Logo

聚焦RDK与具身智能,汇集机器人开发教程、开源案例和技术交流

更多推荐