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

Robert (Jamie) Munro rjmunro at arjam.net
Tue Nov 20 17:39:44 GMT 2007


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Stefan de Konink wrote:
> Robert (Jamie) Munro schreef:
>> Is there a reason you can't route by doing 2 A-stars simultaneously, one
>> from the start and one from the destination, and stop when the 2 meet?
> 
>> AFAICS, this is likely to be quicker than a normal A-star because the
>> recursion will be less broad. I'm not 100% sure though.
> 
> A* is best first, so why would you think the recursion starts?

Recursion probably isn't the right word.

The A* search broadens out as the time taken gets longer than the
heuristic says it could take. So, if your max speed is 70mph, and you've
been following roads that are 30mph towards your destination, the
heuristic will be faster for routes nearer your starting point. This is
how A* finds, say, a motorway route that is longer but faster than the
through the middle of town route.

> Next to this, if you start on the end of the route, you need to walk
> as-if you are walking the inverse direction. This could get pretty
> critical :)

That isn't /that/ hard to do. In fact Gosmore already does all routing
backwards.

Robert (Jamie) Munro
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHQxvRz+aYVHdncI0RAqgmAJ92flWWcUSczsWVvzsJyGxaPE/xqQCeMc2y
d9g9CFLhsP5YKa0CFm18LSk=
=BD61
-----END PGP SIGNATURE-----




More information about the Routing mailing list