最快路径算法 [英] Fastest-path algorithm

问题描述

我目前正在实施的导航系统通过欧洲路由。到目前为止，我有最短路径来实现（Dijkstra算法和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.

我知道它可以只通过分配值到公路质量（例如1道，2主路......），然后用路线成本这个值乘和finaly使用Dijkstra算法或A *进行，但它并不复杂够了。

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.

有没有什么好的算法吗？或者至少对A *的好修改？

Are there any good algorithms for this? Or at least a good modification of A*?

推荐答案

在你实现最短路径的选择了距离作为权重的优势。

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 *（虽然并不总是最佳的，因为它依赖于一个启发式功能）可能是这种类型的应用的最佳选择。如果你的A *不够准确，我建议你要么去Dijkstras或花一些时间调整和改善你的启发式功能。

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屋！