有时间约束的最短路径

Question

给出了几个城市(<=50)以及两个(N * N)矩阵，表示城市间的旅行时间和城市间的收费。现在给定时间t (<10000)，我们必须选择一条从城市0到达城市N-1的路径，使通行费最小，并在给定时间t内完成旅行。

我正在考虑用A星算法来解决上面的问题。我如何通过将它们组合成一个启发式函数来满足这两个要求?

Answer 1

我认为你可以使用一个简单的启发式距离得分计算,并使用人数和时间成本计算,如c0der述。

你的A*搜索应该动态比较所有当前路径。像往常一样删除所有循环，如果两条路径到达同一点的成本较低，则删除成本较高的路径。在每次迭代之后，路径列表根据它们的启发式分数重新排序，更好的路径将在该列表中出现。