A*算法处理目标点位于已知图外的最短路径寻路问题咨询

• 替换原有的固定时间/固定节点终止逻辑，改用A最优性剪枝终止：额外维护两个变量，分别记录当前已探索所有节点中「路径累计成本 + 到目标点3D欧氏距离」的最小值，以及对应的节点。由于A的优先队列是按f值（累计成本+启发值）升序弹出的，当队列中下一个待弹出节点的f值大于你记录的全局最小值时，即可终止算法，此时你记录的对应节点就是符合要求的最优终点。该逻辑不会强制算法必须探索到某个预设节点，且能保证返回的结果是当前已知图下的最优解，不会出现随机路径的问题。
• 引入权衡系数适配场景需求：如果你对「路径成本低」和「离目标近」的需求有侧重，可以在计算全局最优值的时候给两个项加可配置的权重，比如全局评价值 = α * 路径累计成本 + β * 节点到目标的欧氏距离，α越大越优先选成本低的路径，β越大越优先选靠近目标的路径，你可以根据自己的图更新频率调整系数，比如图更新频率高的时候可以提高β的权重，让路径尽量往目标方向靠，方便后续更新后重跑时更快扩展到目标点。
• 增量式A*适配动态图更新：无需每次图更新后都从零开始运行算法，你可以缓存上一次运行得到的路径成本字典、父节点字典以及未处理完的优先队列，当图结构更新时，仅需要把受更新影响的节点的成本重新计算后重新插入优先队列，在原有探索结果的基础上继续运行即可，能大幅降低重跑的计算开销。
• 边界节点预筛选加速计算：你可以提前对已知图做预处理，标记所有处于拓扑边界的节点（即存在至少一个方向没有邻接节点的节点），在算法运行过程中只要探索到边界节点就直接纳入全局最优值的统计范围，无需等该节点从优先队列弹出再计算，能进一步加快终止判断的效率。

内容的提问来源于stack exchange，提问作者Deniz da King