[Routing] A-Star meet-in-the-middle
Jon Bright
jon at siliconcircus.com
Tue Nov 20 21:09:55 GMT 2007
Hi Andreas,
Andreas Leupin wrote:
> 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.
I skimmed over the PDF at
http://www.leupinfo.ch/pdf/OpenGPScout_YP.pdf
As far as I can make out, the routing algorithm you're describing /is/
in fact A* (from the destination to the start). The straight-line
distance you describe is (one possible) heuristic as used by A*. To
quote from
http://en.wikipedia.org/wiki/A*_search_algorithm
"The priority assigned to a path x is determined by the function f(x) =
g(x) + h(x)."
g(x) here is the distance travelled, while h(x) is a heuristic for the
distance still to travel - in your case the straight-line distance.
Have I misunderstood?
--
Jon
Andreas Leupin wrote:
> 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
> <http://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 <mailto: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 <mailto:a.leupin at hispeed.ch>
>
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
More information about the Routing
mailing list