Timeline for What algorithms compute directions from point A to point B on a map?
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 27, 2016 at 6:22 | comment | added | Nick Johnson | @ivan_petrushenko The area of two circles with radius r/2 is half the area of once circle with radius r. | |
| Jul 26, 2016 at 10:31 | comment | added | user6611771 | I don't understood your first idea about eliminates half the work. Can you expand your answer (provide more details), please? | |
| Oct 26, 2010 at 22:32 | comment | added | Tordek | A*, in the worst case (a heuristic that says all paths are equivalent), is exactly equal to Djikstra's. | |
| Oct 26, 2010 at 17:59 | comment | added | jcampbell1 | A simple A* heuristic uses the geometric distance to the destination divided by the maximum possible travel speed. Thus, A* will proceed by searching paths that are headed in the right direction. Dijkstra's is terrible because it stupidly searches in all directions. | |
| May 9, 2010 at 0:15 | history | edited | Michal Sznajder | CC BY-SA 2.5 |
link to wikipedia added
|
| Nov 3, 2009 at 23:18 | comment | added | Nick Johnson | Actually, on further consideration, you're entirely right. You could enhance an existing algorithm to make use of this by simply adding the Great Circle Distance between the target node and the destination to the cost of the edge being evaluated. I'm actually not sure if our algorithm did that - but it's a very sensible optimization. | |
| Nov 3, 2009 at 16:29 | comment | added | Nick Johnson | I don't see how A* with an estimator like that can be more efficient than dijkstra's, then. If it finds a path of cost n, in order to be certain there are no cheaper paths, it must have explored all paths of cost <n, which is exactly what Dijkstra's does. | |
| Nov 3, 2009 at 1:02 | comment | added | a1kmm | "it's only guaranteed to produce a solution, not necessarily the most efficient one" This is untrue; as long as the heuristic used is admissible, the A* algorithm produces the least-cost path. Admissible means that the cost is never over-estimated, but it may be underestimated (but poor estimates will slow the algorithm). Using data from pre-processing is likely to aid in making a better admissible heuristic, and therefore making A* work faster. | |
| Nov 2, 2009 at 18:50 | comment | added | Nick Johnson | A* is likely to be more efficient, but it's only guaranteed to produce a solution, not necessarily the most efficient one. That can be a problem for users, where an inefficient solution translates into lost time or money, or the user concluding your software sucks. Still, you could probably build in some heuristic about when to abandon A* for Dijkstra's. | |
| Nov 2, 2009 at 17:31 | comment | added | John Kemeny | Did you ever try A* instead of bidirectional Djikstra? Did you have coordinates for the vertices? If so, it sounds like you could do quite better with some heuristics. | |
| Feb 26, 2009 at 17:00 | vote | accept | CommunityBot | ||
| Feb 26, 2009 at 17:00 | history | bounty ended | A. Rex | ||
| Feb 20, 2009 at 23:32 | comment | added | A. Rex | Yeah, it seems Google does it. See the comments on Will Dean's answer. | |
| Jan 13, 2009 at 10:17 | comment | added | Nick Johnson | We didn't do any preprocessing of that nature, but it certainly seems like an interesting optimisation. | |
| Jan 11, 2009 at 18:33 | comment | added | A. Rex | Someone who worked on this in the real world, awesome! Do you have any idea how much it's possible to precompute, as in the article about Google mentioned in another comment? | |
| Jan 11, 2009 at 12:41 | history | answered | Nick Johnson | CC BY-SA 2.5 |