|
From: KaZeR <ka...@al...> - 2007-12-26 10:40:46
|
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 > |