[A* bad snipped] > The approach I described seems to be a common base to compute the > shortest path. Then you can hack arround as much as you want.
Yes, it is common. But I have several reasons not to use it at all. One of these reason is that hacking does not yield any algorithmic advantages. > The performances of A* strongly depends on the heuristic. ACK. But the method itself is limited. > If you have THE perfect heuristic that knows exactly the smallest > *distance* to the destination, then the A* will iterate only the nodes > of the shortest path. As anyway you will have to list those nodes at > some point (to render the path for example), it's impossible to have a > better algorithm. If you have the shortest path stored somewhere, then > improvement would be better only by a constant factor. I am not sure what you try to say with that. My point is that that there are completely different methods from A* that perform _very_ well and that are faster by the order of magnitudes. For example, consider the method called "Transit Node Routing". It is possible to compute a shortest path in two or three microseconds, IIRC. > That approch tries to get an almost perfect estimation of the distance > to the destination and it's quite hard to trick. There is paper that reports on speedup techniques and various combinations: https://algo2.iti.uni-karlsruhe.de/1328.php. Page 19 lists preprocessing and query times for various methods. --Dennis _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
