[pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation
Stephen V. Mather
svm at clevelandmetroparks.com
Fri Apr 12 18:07:55 PDT 2013
I'm curious about efficiency of A* vs Dijkstra in large networks. If A* tends to follow the straight line nodes until/unless it finds an obstacle, for really large networks, under what conditions is A* a better choice than Dijkstra?
Also, regarding A* implementation, is it strict, or is there any way to relax the admissibility criterion as currently implemented?
Finally, in using pgRouting for turn by turn, we have pre-chopped our network into short segments to ensure the nearest search node is close to the point we are searching so the directions start from a nearby point, not the nearest network intersection.
For datasets as large as the one we are working with, this seems to result in a pretty high random IO tax. I wondered if anyone has some boilerplate modifying the returned route, slicing the nearest ways to the beginning and end points with ST_ClosestPoint or similar?
[http://sig.cmparks.net/cmp-ms-90x122.png] Stephen V. Mather
(216) 635-3243 (Work)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Pgrouting-users