[Routing] A-Star meet-in-the-middle
Andreas Leupin
a.leupin at hispeed.ch
Tue Nov 20 20:53:31 GMT 2007
However, I think that the A*-algorithm is not ideal because it is
absolutely symmetrical around the start/destination - this means that
routes leading away from the destination are equal than those leading
into the direction of the destination. On www.leupinfo.ch/OpenGPScout
I tried to describe an algorithm, which is very similar to A* but
prefers the routes to the direction of the destination...
Furthermore I prefer to calculate the route from destination to
start, because the start-point is constantly changing during the
drive, whereas the destination is stable - therefore, I can use the
calculations already done, when I leave the precalculated route
during my drive...
Regards
Andreas
Am 20.11.2007 um 17:24 schrieb Robert (Jamie) Munro:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> 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.
>
> Robert (Jamie) Munro
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (Darwin)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFHQwpAz+aYVHdncI0RAvhqAJ9WQlNWFO47CTiOc61MgwgXrgoDuQCgn9+Y
> 1MLVeZXctjbxXefe+p1cp7k=
> =BS9q
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
Andreas Leupin
Kretzgasse 2
CH-5416-Kirchdorf
Tel. P [+41](0)56 282 07 40
G [+41](0)56 310 39 32
a.leupin at hispeed.ch
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071120/55042d34/attachment.html>
More information about the Routing
mailing list