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

[Stephen Woodbridge]

On 4/12/2013 9:07 PM, Stephen V. Mather wrote:
> 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?

In general, A* is much more efficient because it does not have to solve 
the whole network as Dijkstra has to. Take the simple case of the start 
node in a center of a square region with a uniform distribution of nodes 
and edges over the square. If you route from the center to one of the 
corners, A* only needs to look at enough edges to get to the destination 
node and it can stop. While Dijkstra will solve the whole network.

But for large networks, the overwhelming cost might to be build the 
graph in the first place. I don't have hard numbers handy about I think 
that fetching the edges and building the graph cost more than solving it.

> Also, regarding A* implementation, is it strict, or is there any way to
> relax the admissibility criterion as currently implemented?

There are not any controls that I am aware of.

> 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.

You might want to look at TRSP. This is going to replace shooting star 
which is seriously broken and noone know how it is supposed to work. 
TRSP allow you to select an edge and an offset along that edge as the 
start and end point. This is critical is you want your start or end 
point to be on a segment that is a one way street. For ample it is 
possible to have both the start and the end on the same segment like:

     ---o-->--E--->--------S----o----

In this case to get from S to E you have to exit right and find a route 
back around to the E coming from the left. TRSP (Turn restricted 
shortest path) is a little slower (not much) than dijkstra. You don't 
have to give it turn restriction but if you have them they can be 
supplied. There is a trivial test(s) in the sew-devel-2_0 branch for 
trsp. It was developed under contract by a UK client and has been used 
with restrictions and Navteq data. The test use the same graph with and 
with out turn restriction. There is an image of the graph in 
doc/static/images/

Let me know if your need more information.

> 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?

I have done this, it is not that hard.

-Steve


> 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>
>
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>