What algorithms compute directions from point A to point B on a map?
How do map providers (such as Google or Yahoo! Maps) suggest directions?
I mean, they probably have real-world data in some form, certainly including distances but also perhaps things like driving speeds, presence of sidewalks, train schedules, etc. But suppose the data were in a simpler format, say a very large directed graph with edge weights reflecting distances. I want to be able to quickly compute directions from one arbitrary point to another. Sometimes these points will be close together (within one city) while sometimes they will be far apart (cross-country).
Graph algorithms like Dijkstra's algorithm will not work because the graph is enormous. Luckily, heuristic algorithms like A* will probably work. However, our data is very structured, and perhaps some kind of tiered approach might work? (For example, store precomputed directions between certain "key" points far apart, as well as some local directions. Then directions for two far-away points will involve local directions to a key points, global directions to another key point, and then local directions again.)
What algorithms are actually used in practice?
PS. This question was motivated by finding quirks in online mapping directions. Contrary to the triangle inequality, sometimes Google Maps thinks that XZ takes longer and is farther than using an intermediate point as in XYZ. But maybe their walking directions optimize for another parameter, too?
PPS. Here's another violation of the triangle inequality that suggests (to me) that they use some kind of tiered approach: XZ versus XYZ. The former seems to use prominent Boulevard de Sebastopol even though it's slightly out of the way.
Edit : Neither of these examples seem to work anymore, but both did at the time of the original post.
Speaking as someone who spent 18 months working at a mapping company, which included working on the routing algorithm... yes, Dijkstra's does work, with a couple of modifications:
With modifications along those lines, you can do even cross-country routing in a very reasonable timeframe.
This question has been an active area of research in the last years. The main idea is to do a preprocessing on the graph once , to speed up all following queries . With this additional information itineraries can be computed very fast. Still, Dijkstra's Algorithm is the basis for all optimisations.
Arachnid described the usage of bidirectional search and edge pruning based on hierarchical information. These speedup techniques work quite well, but the most recent algorithms outperform these techniques by all means. With current algorithms a shortest paths can be computed in considerable less time than one millisecond on a continental road network. A fast implementation of the unmodified algorithm of Dijkstra needs about 10 seconds .
The article Engineering Fast Route Planning Algorithms gives an overview of the progress of research in that field. See the references of that paper for further information.
The fastest known algorithms do not use information about the hierarchical status of the road in the data, ie if it is a highway or a local road. Instead, they compute in a preprocessing step an own hierarchy that optimised to speed up route planning. This precomputation can then be used to prune the search: Far away from start and destination slow roads need not be considered during Dijkstra's Algorithm. The benefits are very good performance and a correctness guarantee for the result.
The first optimised route planning algorithms dealt only with static road networks, that means an edge in the graph has a fixed cost value. This not true in practice, since we want to take dynamic information like traffic jams or vehicle dependent restrictrions into account. Latest algorithms can also deal with such issues, but there are still problems to solve and the research is going on.
If you need the shortest path distances to compute a solution for the TSP , then you are probably interested in matrices that contain all distances between your sources and destinations. For this you could consider Computing Many-to-Many Shortest Paths Using Highway Hierarchies. Note, that this has been improved by newer approaches in the last 2 years.
Just addressing the triangle inequality violations, hopefully the extra factor they're optimising for is common sense. You don't necessarily want the shortest or fastest route, as it can lead to chaos and destruction. If you want your directions to prefer the major routes that are truck-friendly and can cope with having every sat-nav-following driver sent down them, you quickly discard the triangle inequality[1].
If Y is a narrow residential street between X and Z, you probably do only want to use the shortcut via Y if the user explicitly asks for XYZ. If they ask for XZ, they should stick to major roads even if it's a bit further and takes a bit longer. It's similar to Braess's paradox - if everyone tries to take the shortest, fastest route, the resulting congestion means that it's not the fastest route for anyone any more. From here we stray from graph theory into game theory.
[1] In fact, any hope that the distances produced will be a distance function in the mathematical sense dies when you allow one-way roads and lose the symmetry requirement. Losing the triangle inequality too is just rubbing salt in the wound.
链接地址: http://www.djcxy.com/p/29210.html上一篇: 用于（简单）无向图的Python库/模块
下一篇: 什么算法在地图上计算从点A到点B的方向？