带时间约束的最小通行费路径：A*算法启发式函数如何设计

你的问题属于带时间约束的最小费用路径问题，A的启发式需要满足可采纳性*（不会高估当前节点到终点的最小费用，保证能找到最优解），同时要把时间约束纳入逻辑过滤无效路径，具体设计步骤如下：

第一步：提前预处理两个距离矩阵 #

N≤50的规模下，只需要做一次O(N³)的Floyd算法，就能得到两个全源最短路结果：

• 任意城市u到终点N-1的最小通行时间，记为min_time[u]：以通行时间为边权计算，这个值是u到终点的时间下界，任何路径的耗时都不可能低于它
• 任意城市u到终点N-1的最小通行费，记为min_cost[u]：以通行费为边权计算，这个值是u到终点的费用下界，任何路径的总费用都不可能低于它

第二步：设计带约束的启发式函数 #

注意A的搜索状态不能仅存当前城市u，还要存到达u时已经消耗的总时间used_t，避免同一城市不同时间消耗的状态互相干扰。
启发式函数h(u, used_t)的逻辑：

先做可行性剪枝：如果used_t + min_time[u] > t，说明哪怕走最快的路径也会超过时间阈值，这个状态直接丢弃，不用进入优先队列
可行状态的启发值直接取min_cost[u]即可

设计合理性说明 #

• 满足可采纳性：min_cost[u]是u到终点的最小费用，绝对不会高估实际需要的费用，保证A*找到的第一个到达终点的可行路径，就是时间合规前提下总费用最低的最优解
• 时间约束已经通过min_time[u]提前过滤无效状态，大幅降低搜索队列的规模，提升搜索效率

可选优化项 #

如果想进一步加快收敛，优先队列的排序键可以设置为(已消耗费用 + h(u, used_t), used_t + min_time[u])，同等费用优先级下先搜时间余量更充足的路径，能更快找到可行解。

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