最快路径算法

Question

我正在实现一个用于在欧洲进行路线规划的导航系统。目前，我已经实现了最短路径算法（Dijkstra和A*）。这是容易的部分，现在我需要一些最快路径算法。它必须快速且可靠。

我知道可以通过为道路质量（例如1号高速公路，2号主要道路等）分配值，然后将这些值与路线成本相乘，并最终使用Dijkstra或A*来实现，但这并不够复杂。

我正在寻找更精确的算法。地图本身包含各种数据，如道路质量、限速、交通信号灯位置等，我想利用它们。

是否有任何好的算法？或者至少有一个好的A*修改版吗？

- radek

---

一种“最短路径”的算法可以被改为“最快路径”，只需要将边的权重从距离改为旅行时间。A*仍然是你最好的选择，只需要根据现有数据设计一个很好的权重估计方法（并设计一个启发式算法）。 - Niki Yoshiuchi

为什么你不能在计算边缘成本时将所有因素都考虑进去（就像你建议考虑道路质量一样）？ - dave

我认为一定有更好的方法。但是如果每个人都建议修改后的A*算法是最佳解决方案，那么我会接受它。 - radek

A算法中并没有规定你应该选择什么作为边权重，因此从某种意义上说，它仍然不是A的修改版本。 - aioobe

Answer 1

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

如果您想要找到最快的路径，您可以选择预期旅行时间作为边的权重。同样地，如果您想要找到最可靠的路径，您可以选择一些“可靠性”度量作为边的权重。

A*（虽然并非总是最优，但它依赖于启发式函数）可能是此类型应用程序的最佳选项。如果您的A *不够准确，我建议您要么选择Dijkstra，要么花些时间调整和改进启发式函数。

- aioobe

---

只要A的启发式函数是可接受的，按照计算机科学对"最优"的定义，A总是最优的。 - Oren A

哦，我不确定“admissible”在这个上下文中的意思。但是，我怀疑对于带有任意边权重的图形而言，很难拥有这样的启发式函数。 - aioobe

当然可以 - 对于这些情况，可以很容易地找到可接受的函数（例如对于实际距离 - 你只需测量空中线路（这就是你称之为的吗？））。 - Oren A

谢谢回答。那么，将不同权重与欧几里得距离这样的简单启发式混合真的可以吗？我认为我至少需要调整启发式加权。 - radek

你的启发式函数应该尽可能准确地估计剩余的距离/旅行时间/等等。 - aioobe

几年前：可接受的启发式是被证明永远不会低估距离的启发式。正如@OrenA所提到的，直线距离启发式在寻找已知坐标的两点之间的最短路径时是可接受的。 - scozy

Answer 2

这取决于你对“最快”的路径是什么意思。如果你知道每个路段上的平均行驶速度，那么你可以将图形转换为包含“旅行时间”而不是“距离”的边缘。然后，您可以在新图形上执行最短路径算法。

但是，似乎您提到这还不够好。我认为问题在于您必须定义“最快”的含义。道路质量如何影响速度？交通信号灯呢？这些都是您必须找到一种解决方法来考虑的变量。如果您作为人类不知道要使用的指标，那么让计算机完成它将很难。

- Claudiu