[Routing] Getting A* to prefer Motorways

[Frederik Ramm]

Hi,

>    even for the shortest route the heuristic isn't correct in every
>    case. For example, if you are on a peninsula with the target on
>    the other side of a bay it may be better to move first away from
>    the target instead of searching directly a way in the direction
>    of the target.

It is not the job of the heuristic to be "correct" in your case; A* is
perfectly capable of finding the correct way even in cases like yours.

The job of the heuristic (in A*) is to give you the theoretical
optimum for a route between two points so that the algorithm knows
when to stop searching.

For example, I have a known route from my startpoint A to my
destination B with a length (or time or whatever I'm optimising for)
of 100. I also have a route of length 80 to another point, C. If the
heuristic h(B,C) is, for example, 18, then I know it might make sense
to search for a route from B to C with less than 20 units. If the
heuristic is 21, then I can disregard the whole "C" business.

Bye
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00.09' E008°23.33'