[pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation

[Stephen V. Mather]

Hi All,

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?

Thanks,
Best,
Steve


[http://sig.cmparks.net/cmp-ms-90x122.png] Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com<http://www.clemetparks.com>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130413/0379733f/attachment.html>