最快路径算法

Question

我目前正在实施一个导航系统，用于欧洲的路线选择。到目前为止，我已经实现了最短路径(Dijkstra和A*)。这是最简单的部分，现在我需要一些最快路径的算法。它必须是快速可靠的。

我知道这可以通过为道路质量赋值(例如1条高速公路，2条主干道...)，然后将这些值与路线成本相乘，最后使用Dijkstra或A*来完成，但它还不够复杂。

我在寻找更精确的算法。地图本身包含各种数据，如道路质量、限速、红绿灯位置等，我想使用它。

有没有好的算法来解决这个问题呢？或者至少是A*的一个好的修改。

Answer 1

在最短路径的实现中，您选择了距离作为边的权重。

现在，如果你想找到最快的路径，你只需选取预期的旅行时间作为边的权重，而不是。类似地，如果你想要最可靠的路径，你可以选择一些“可靠性”的度量作为边缘的权重。

A* (尽管并不总是最优的，因为它依赖于启发式函数)可能是这类应用程序的最佳选择。如果你的A*不够准确，我建议你要么去Dijkstras，要么花一些时间调整和改进你的启发式函数。

Answer 2

这取决于你所谓的“最快”路径是什么意思。如果你知道在每一段道路上行驶的平均速度，那么你可以简单地转换你的图表，这样边就包含了“旅行时间”而不是“距离”。然后，您可以在新图上执行最短路径算法。

但你似乎提到了这还不够好。我认为问题在于你必须定义“最快”是什么意思。道路质量如何影响速度？那红绿灯呢？这些都是你必须找到一种方法来解决的变量。如果你作为一个人类不知道你将使用的度量标准，那么就很难让计算机来做这件事。