最快路径算法
我目前正在实施一个用于穿越欧洲的导航系统。到目前为止，我已经实现了最短路径（Dijkstra 和 A*）。这是简单的部分，现在我需要一些最快路径的算法。它必须快速且可靠。
我知道只需为道路质量分配值（例如 1 条高速公路、2 条主要道路...），然后将这些值乘以路线成本，最后使用 Dijkstra 或 A* 即可完成，但它还不够复杂。
我正在寻找更准确的算法。地图本身包含各种数据，比如道路质量、限速、红绿灯位置等，我想使用它。
有什么好的算法吗？或者至少是对 A* 的良好修改？
I'm currently implementing a navigation system for routing through Europe. So far, I have shortest path implemented (Dijkstra and A*). It was the easy part, now I need some algorithm for fastest path. It has to be fast and reliable.
I know it can be done just by assigning values to a road quality (for example 1 highway, 2 main road ...), then multiply these values with route costs and finaly use Dijkstra or A*, but it's not sophisticated enough.
I'm searching for more accurate algorithm. The map itself contains all kinds of data, like road quality, speed limits, traffic lights positions etc., and I want to use it.
Are there any good algorithms for this? Or at least a good modification of A*?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在最短路径的实现中，您选择距离作为边的权重。
现在，如果您想找到最快的路径，您只需选择预期行进时间作为边缘的权重。同样，如果您想要最可靠的路径，您可以选择一些“可靠性”度量作为边缘的权重。
A*（尽管并不总是最佳的，因为它依赖于启发式函数）可能是此类应用程序的最佳选择。如果你的 A* 不够准确，我建议你要么选择 Dijkstras，要么花一些时间调整和改进你的启发式函数。
In your implementation for shortest path you chose distance as weight for an edge.
Now if you want to find the fastest path, you simply pick expected travel time as weight for the edges instead. Similarly, if you want the most reliable path, you pick some measurement of "reliability" as weight for the edges.
A* (although not always optimal, as it relies on a heuristics function) is probably your best option for this type of application. If your A* is not accurate enough, I suggest you either go for Dijkstras or spend some time on tweaking and improving your heuristics function.
这取决于您所说的“最快”路径是什么意思。如果您知道在道路的每个路段上可以行驶的平均速度，那么您可以转换图表，使边缘包含“行驶所需的时间”而不是“距离”。然后您可以对新图执行最短路径算法。
不过，您提到的似乎还不够好。我认为问题在于你必须定义“最快”的含义。道路质量如何影响速度？交通灯呢？这些都是你必须找到一种方法来解释的变量。如果你作为一个人不知道你将使用的指标，那么就很难让计算机来做这件事。
It depends what you mean by 'fastest' path. If you knew the average speed you could travel on on each segment of the road, then you could just convert your graph so the edges contain "time taken to travel" instead of "distance". Then you can do a shortest-path algorithm over the new graph.
It seems like you mentioned that's not good enough, though. I think the problem is that you have to define what 'fastest' means. How does road quality affect speed? What about traffic lights? These are all variables you have to find a way to account for. If you as a human don't know the metric you'll be using, it'll be hard to get the computer to do it.