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 >> [email protected] <mailto:[email protected]> >> 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 > [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]> > > > > > ------------------------------------------------------------------------ > > _______________________________________________ > Routing mailing list > [email protected] > http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
