上一篇讲了A算法的原理和最优性证明。A的性能好不好80%取决于启发式函数选得对不对。今天专门讲启发式函数的设计——不同场景该用哪种距离度量以及背后的原理和原因。这个问题面试出现频率很高。面试官通常会问你的A用的什么启发式为什么这么选回答不好这个问题说明你对A的理解还停留在会调库的层面没有真正理解算法的工作原理。一、启发式函数的核心原则设计启发式函数只有一个硬性要求可采纳性——h(n)不能高估真实代价。这是保证A*找到最优解的前提条件。在这个前提下h(n)越大越好越接近真实代价搜索越快。所以理想情况是在保证不高估的前提下让h(n)尽可能大。# 可采纳的启发式h(n) h_true(n) # 好的启发式h(n) 接近 h_true(n) # 差的启发式h(n) 远小于 h_true(n) # 不可采纳的启发式h(n) h_true(n)某些地方二、曼哈顿距离曼哈顿距离只能沿坐标轴方向移动时的最短距离。名字来源于曼哈顿的街道布局——横平竖直不能穿楼而过。def manhattan(a, b): return abs(a[0]-b[0]) abs(a[1]-b[1])适用场景4连接的2D网格只能上下左右走。为什么因为4连接网格中从A到B至少要走过|x差||y差|步。曼哈顿距离正好等于这个最小步数所以是可采纳的——而且是最紧的可采纳估计恰好等于真实代价的下界。举个例子从(1,1)到(4,5)曼哈顿距离 |4-1| |5-1| 3 4 7。在4连接网格中从(1,1)到(4,5)确实至少需要7步。注意如果用在8连接网格上曼哈顿距离会高估真实代价因为8连接可以走对角线实际距离更短变成不可采纳的。所以一定要根据连接方式选启发式。三、欧几里得距离欧几里得距离两点之间的直线距离。def euclidean(a, b): return ((a[0]-b[0])**2 (a[1]-b[1])**2) ** 0.5适用场景连续空间中的运动规划。机器人可以在任意方向移动直线距离是最短可能距离。欧几里得距离永远 任何实际路径长度因为直线最短所以是可采纳的。在网格地图中也可以用但效果不如曼哈顿/切比雪夫——因为它没有考虑网格的离散结构提供的信息量较少。说白了就是低估太多A*还是会搜索很多不必要的节点。四、对角线距离切比雪夫/八方向距离切比雪夫距离def chebyshev(a, b): return max(abs(a[0]-b[0]), abs(a[1]-b[1]))适用场景8连接网格对角线代价和直线代价相同都是1。这种场景在实际中比较少见但在某些理论分析中会用到。八方向距离octile distancedef octile(a, b): dx abs(a[0]-b[0]) dy abs(a[1]-b[1]) return (dx dy) (1.414 - 2) * min(dx, dy)适用场景8连接网格对角线代价是sqrt(2)≈1.414直线代价是1。这是8连接网格最常用的启发式也是最紧的可采纳估计。octile距离的物理意义min(dx,dy)步走对角线每步sqrt(2)剩下的|dx-dy|步走直线每步1。总代价 min(dx,dy)*sqrt(2) |dx-dy|*1。化简后就是上面的公式。举个例子从(0,0)到(3,4)dx3, dy4。min3, |dx-dy|1。octile 31.414 11 5.242。而曼哈顿距离 34 7。octile比曼哈顿更接近真实代价所以A*用octile会更快。五、怎么选一张表搞定地图类型连接方式推荐启发式2D网格4连接曼哈顿距离2D网格8连接对角线代价sqrt(2)octile距离2D网格8连接对角线代价1切比雪夫距离连续空间任意方向欧几里得距离3D网格6连接3D曼哈顿距离3D网格26连接3D octile距离六、高级技巧1. 加权启发式如果不需要最优解可以把h(n)乘以一个权重w 1f(n) g(n) w * h(n) # w 1这会让搜索更快但找到的路径可能不是最优的。w越大越快但路径质量越差。工程上w通常取1.5-3.0。Weighted A*在实时性要求高的场景中很常见。比如移动机器人导航、无人机路径规划路径不需要绝对最优——差不多好就行但必须算得快。2. 动态加权离起点远的时候权重小保证大方向正确离终点近的时候权重大精确搜索。这种策略在起点和终点距离很远时特别有效。3. 考虑地形代价如果地图有不同的地形草地、泥地、水面启发式可以用地形加权def terrain_aware_heuristic(a, b, cost_map): # 用最小地形代价估计保证可采纳 min_cost cost_map.min() return euclidean(a, b) * min_cost关键是取最小代价——这样才不会高估真实代价保证可采纳性。4. 预计算距离场从终点做一次Dijkstra/BFS得到每个格子到终点的真实最短距离。这个距离场作为启发式是完美的——h(n) h_true(n)。但需要预计算而且终点变了就要重算。适合终点固定的场景。七、面试实战Q为什么4连接网格用曼哈顿距离而不是欧几里得距离A因为欧几里得距离 曼哈顿距离。在4连接网格中从A到B的最短路径长度等于曼哈顿距离。用欧几里得距离虽然也可采纳但低估了真实代价提供的信息量少搜索更慢。Q如果h(n)不可采纳会怎样AA可能找不到最优解。但工程上经常故意用不可采纳的启发式比如加权A用路径质量换速度。关键是知道自己在做什么——如果任务要求最优路径h必须可采纳。Q启发式函数能考虑障碍物吗A标准启发式不考虑障碍物只算直线距离。但你可以预计算一个考虑障碍物的距离场作为启发式——比如从终点做BFS得到每个格子到终点的最短距离。这个启发式更精确但需要预计算。工程上如果地图变化不频繁预计算距离场是很好的优化手段。Q3D空间用什么启发式A3D空间如果是连续空间用3D欧几里得距离。如果是6连接的3D网格上下左右前后用3D曼哈顿距离|dx||dy||dz|。如果是26连接的3D网格用3D octile距离。原理和2D一样——根据连接方式选最紧的可采纳估计。Q实际项目中你怎么选启发式A之前做仓储AGV导航时地图是2D网格8连接。用的octile距离作为基础启发式。然后加了一个距离场——从每个目标站点预计算的Dijkstra距离场。两者取最大值作为最终启发式两个可采纳启发式的最大值仍可采纳。效果比单独用octile快了大约5倍。小结启发式函数的选择取决于地图的连接方式4连接用曼哈顿8连接用octile连续空间用欧几里得。核心原则是可采纳性——不高估真实代价。好的启发式让A*快几倍甚至几十倍。工程上还可以用加权启发式、地形感知启发式、预计算距离场等高级技巧。记住一个原则在可采纳的前提下h(n)越大越好。下一篇讲A的几个重要变体——Weighted A/ARA*/D*它们在工程中的应用非常广泛。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第209篇 A算法详解——启发式搜索的原理和最优性证明下一篇预告第211篇 A算法变体——Weighted A*/ARA*/D*的工程应用有任何问题欢迎评论区留言我会尽量回复。