如何用A star算法查找带有序必经点约束的源到目标路径

针对必须按顺序经过指定节点的最短简单路径问题，直接用常规A*无法满足约束，最直接有效的解决思路是分段计算+节点禁忌，具体操作如下：

• 拆分路径任务：把原路径需求拆分为多个连续的子任务。比如给定源点A、目标点B，必经点顺序为C→D→E，就拆成 A→C、C→D、D→E、E→B 四个独立的子路径计算任务。
• 逐段用A计算最短简单路径：每计算一段子路径时，要把之前所有已经走过的节点（包括前序子路径的起点、终点以及路径上的所有中间节点）加入禁忌列表，在A的寻路过程中禁止访问这些节点，确保当前子路径不会和已走路径形成环路，同时保证每一段都是无环的简单路径。
• 拼接子路径：把所有计算得到的子路径按顺序首尾拼接，最终得到的就是满足「按顺序经过所有必经点+无环路」的最短路径。

注意事项 #

• 如果某一段子任务无法找到可达路径（比如A到C没有连通路径），则整个寻路任务直接判定为无解。
• 提前校验必经点的合理性：比如必经点存在重复、必经点不在源点到目标点的连通区域内等情况，要提前过滤，避免无效计算。

内容的提问来源于stack exchange，提问作者Hee