[Routing] A-Star meet-in-the-middle
nroets at gmail.com
Tue Nov 20 21:13:11 GMT 2007
My 2c worth for faster routing :
* Rewrite in C and use hash tables.
* Change the A* heuristic from sqrt(sqr(dx)+sqr(dy)) to 1.1*sqrt(...)
or larger. This acknowledges that roads the shortest route between two
points is usually 10% longer than a straight route. And if you're
wrong the route may be slightly suboptimal, who cares.
(Why aren't we discussing the important issues, like adding a penalty
to right turns at intersections... ?)
More information about the Routing