-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Marcus Wolschon wrote: > Nic Roets schrieb: >> * 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. > > Hello Nic, > > you are using the heuristic to find a total ordering. Why should > a linear factor make any difference here? As far as I can see > the ordering resulting would be completely identical.
No it wouldn't. You don't order by the heuristic's remaining estimate, you order by (heuristic's remaining estimate) + (distance you have already travelled to get node). It's important that both are in the same unit, weather that is time or distance. It is also best if the heuristic under-estimates the remaining time, because then the algorithm will find the optimal rout (routes that have only been calculated half way will seem to be faster than routes that have been completed because the algorithm will underestimate the costs of travelling the other half of the route). Multiplying the heuristics guess by 1.1 will bias the algorithm so that it is less likely to go back and try other routes, and will be more likely to just settle on the first route it finds. This will make it quicker, but potentially sub-optimal. Robert (Jamie) Munro -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHREFyz+aYVHdncI0RApF1AJ9+yts5DFAUmT9tA3/O8xrR0bUZsACfeyUz 2E/NfAz8otLlrHcC5CHOdYg= =nOPU -----END PGP SIGNATURE----- _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
