Re: [Navit-users] A* search - debugging

[Helge H. <hel...@ai...>]

Alexander Atanasov wrote:
> Hi, Helge,
>
> It would be good to have A*!
>   
It is faster for normal maps, because it basically directs the
Dijkstra search in the direction of the target point.
Plain Dijkstra expands at the same rate in all directions.

My A* patch now works, in the sense that creates correct
routes.  Unfortunately, it is 3 times slower, I guess
some error cause it to expand the search in wrong directions first.

Do anybody know if "transform_distance" is the correct
function for finding the distance between a graph node
and the endpoint?  I need the distance measured with the same
units as used for road lengths.
> There is an interesting problem: reading only the necessery graphs
> when calculating the route, we have blocks of data with roads.
> Is it possible to teach A* to read kind of next block when it reaches
> the end of current graph, i've read that A* calculates the possible direction?
>   
I don't know enough about navit to make such changes. Adding
A* to the existing Dijkstra isn't that hard, so that's what I do
now.  Both A* and Dijkstra will only visit parts of the graph, the
parts necessary to complete the search for the shortest path.

A bug-free A* will visit fewer unnecessary graph nodes than Dijkstra,
that is why it is faster.  It is mostly the same algorithm.

A* _can_ be slower if most of the shortest path is _not_ between
the start and the destination, and there also is a lot of
irrelevant roads inbetween.  But that is highly unusual for a street map.

Helge Hafting