Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

12
  • 29
    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?
    – A. Rex
    Commented Jan 11, 2009 at 18:33
  • 10
    We didn't do any preprocessing of that nature, but it certainly seems like an interesting optimisation.
    – Nick Johnson
    Commented Jan 13, 2009 at 10:17
  • 29
    "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.
    – a1kmm
    Commented Nov 3, 2009 at 1:02
  • 6
    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.
    – Nick Johnson
    Commented Nov 3, 2009 at 23:18
  • 12
    A*, in the worst case (a heuristic that says all paths are equivalent), is exactly equal to Djikstra's.
    – Tordek
    Commented Oct 26, 2010 at 22:32