[Routing] A-Star meet-in-the-middle

[Robert (Jamie) Munro]

-----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-----