用地标改进 A star 寻路的启发函数
内容提要
本文介绍如何改进A*寻路算法的启发函数。传统欧氏距离无法感知墙壁，导致效率低下。作者提出用地标预计算路径，通过三角形不等式判断何时采用地标方向，从而O(1)提升性能，并支持多地标及动态生成。
延伸解读
启发函数为何要保证可采纳性
A*算法依赖启发函数估计剩余代价，若估计值始终不大于真实代价，则保证找到最优路径。传统欧氏距离满足这一性质，但在地图有墙时估计过于乐观，导致算法探索大量无效节点。改进启发函数时，仍需保持可采纳性，否则可能牺牲最优性。本文用地标距离构造下界，既保持可采纳性，又更贴近真实路径，从而在保证最优性的前提下提升效率。
地标法的核心思想与适用条件
地标法通过预计算到地标的最短路径，利用三角形不等式判断当前点到目标点的直线距离是否可能小于实际路径。若直线距离过短，则改用朝向地标的预设方向。该方法适用于地图静态且地标可达的场景，尤其适合起点与目标点相距较远、中间有障碍物的情况。若地图动态变化或地标不可达，则需重新计算或退化为传统启发函数。
多地标与动态生成地标的扩展
文章提出可预计算多个地标，并在估价时选择使SL-EL较小的地标，以更紧的下界提升引导效果。地标也可动态生成：当到达新目的地时，将其记录为地标，供后续寻路使用。这种策略类似人类利用已知地标导航，逐步积累经验，但需注意地标数量增加会带来存储和查询开销，实际应用中需权衡。
Q&A
A*寻路算法中，传统欧氏距离启发函数的主要缺点是什么？
传统欧氏距离启发函数无法感知墙壁等障碍物，导致算法在复杂地图中可能先向错误方向扩展大量节点，效率低下。例如，起点在房间内而目标在东边、门在西边时，算法会先尝试东侧所有路径，直到最后才从西门出去。
用地标改进A*启发函数的基本思路是什么？
预先用Dijkstra算法计算从地图上每个点到某个地标的最短路径（流图），在启发函数中利用三角形不等式判断：当当前位置到目标的直线距离小于当前位置到地标的已知距离减去地标到目标的已知距离时，说明直线方向不可靠，应改用朝向地标的预设路径方向作为启发值，否则仍用直线方向。这样可以在O(1)时间内获得更准确的启发值。
在A*启发函数中，如何利用三角形不等式判断是否采用地标方向？
设当前位置为S，目标为E，地标为L。根据三角形不等式，SE + EL >= SL，即SE >= SL - EL。如果SE小于SL - EL，说明直线距离太短，直线方向可能被墙阻挡，此时应采用朝向地标的预设路径方向；否则直线方向可能更有效。
用地标改进启发函数后，时间复杂度有何变化？
改进后的启发函数仍然是O(1)的，因为地标流图是预先计算好的，每次查询只需查表并做简单比较，不会增加时间复杂度，但能显著提升寻路效率。
如何利用地标判断目标是否可达？
如果当前位置能到达地标，而地标到目标不可达，则目标不可达；反之，如果地标到目标可达，而当前位置无法到达地标，目标也不可达。只有当前位置和目的地都能到达地标时，路径一定存在。
如何选择多个地标以及动态生成地标？
可以预先计算多个地标，在启发函数中比较哪个地标更有效，选择SL - EL值较小的地标来采用其预设路径。地标也可以动态生成：例如，如果没去过广州，可以先用离广州较近的深圳作为地标，一旦抵达广州，就把广州记录为新地标，方便后续寻路。
