Timeline for What algorithms compute directions from point A to point B on a map?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2009 at 20:28 | comment | added | Konrad Rudolph | Well, the point is that A* uses a heuristic (as opposed to being one) to determine the next step. This one decision can indeed be suboptimal. But it only affects runtime, not the result, since it only determines how much better than Dijstra it guesses. | |
| Jan 10, 2009 at 15:52 | comment | added | A. Rex | Yes, of course. After I wrote my original post, I thought about the word "heuristic" that I used. It's a bit inaccurate here, because it does find an optimal solution. | |
| Jan 10, 2009 at 10:43 | comment | added | Konrad Rudolph | Yes, it is. What I wanted to get at is that A* can be used instead and that it always finds an optimal solution (even though it uses a heuristic)! | |
| Jan 10, 2009 at 1:04 | comment | added | A. Rex | Suppose you are trying to find directions from point A to B, the optimal distance for which is d. Dijkstra's algorithm will, at the very least, examine all points at distance at most d from A. If A is San Francisco and B is Boston, this means it examines most of the US. N'est-ce pas? | |
| Jan 10, 2009 at 0:47 | history | answered | Konrad Rudolph | CC BY-SA 2.5 |