Hi Jon,
you are right in this point - sorry , I did not check this good
enough...
...but two points still remain IMHO:
- IMHO it is necessary to use the ends of road-segments as the end-
points of a route instead of the usually uses nodes - otherwise it is
quite cumbersome to take into account the turn restrictions in a node...
- I would not store the entire routes, but write only the cost (in my
case to the destination) to the ends of road segments - otherwise I
may end in a memory overflow because of the redundancy of information
by storing entire routes. It is quite easy to get a route in a second
step then by a "forward" calculation.
Regards
Andreas
Am 20.11.2007 um 22:09 schrieb Jon Bright:
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
Andreas Leupin
Kretzgasse 2
CH-5416-Kirchdorf
Tel. P [+41](0)56 282 07 40
G [+41](0)56 310 39 32
[EMAIL PROTECTED]
_______________________________________________
Routing mailing list
[email protected]
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
