Re: [Navit-users] [PATCH] A* search for navit, nice speedup in many cases

[KaZeR <ka...@al...>]

Thank you helge. This looks promising. We'll have a deep look at it!


hel...@ai... a écrit :
> A patch that makes navit routing use the A* search algorithm. The patch is
> small because A* is nearly the same as the Dijkstra algorithm already
> implemented.
>
> My speed test:
> 1. Load a OSM map of Scandinavia
> 2. Have navit find a route from Trondheim to Copenhagen.
>    (Navit will search from Copenhagen to Trondheim.)
>
> The Dijkstra algorithm used 8s on my work laptop.
> The A* algorithm uses 2s. :-)  4x speedup for this case.
>
> Strangely enough, I am completely unable to reproduce the old test. All
> versions of navit (dijkstra, A*) now does this route in 2s.
>
> I am very irritated at the moment. There could still be a bug in my code
> that prevents A* from being faster than dijkstra. No problem with that.
> This does *not* explain why the old program used to use 8s and now
> suddenly use 2s though. Looks like the world is not behaving realistic
> today, which is nasty.
>
> I hope someone interested will test the patch and see if it makes any
> difference.
>
>   

> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> SF.Net email is sponsored by:
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services
> for just about anything Open Source.
> http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
> ------------------------------------------------------------------------
>
> _______________________________________________
> Navit-users mailing list
> Nav...@li...
> https://lists.sourceforge.net/lists/listinfo/navit-users
>