[Routing] A-Star meet-in-the-middle
Jon Bright
jon at siliconcircus.com
Wed Nov 21 07:38:42 GMT 2007
Hi Marcus,
Marcus Wolschon wrote:
>
> you are using the heuristic to find a total ordering. Why should
> a linear factor make any difference here? As far as I can see
> the ordering resulting would be completely identical.
You're using the heuristic *and the distance travelled* to do the
ordering. Nic's suggesting applying a linear factor only to the
heuristic. A* works with an optimistic heuristic, giving the minimum
cost from the current node to the destination node. The factor makes it
slightly less optimistic, leading to routes towards the target being
preferred over potentially shorter routes which initially move away from
the target. An example:
/-----------------------------------------\
| |
| |
\-----S-\ C/-----\ /---\ /-----T
A | | | | | |
| | | | | |
| | | | | |
B\_______/ \____/ \____/
Starting at S, the algorithm proceeds to A and B. Assume the distance
travelled between S and A and between S and B is 10. Assume the
distance between B and C is 35. Assume the distance over the "top loop"
between A and T is 110. Assume the straight-line distance between A and
T is 100, the straight-line distance between B and T is 90 and the
straight-line distance between C and T is 80.
After travelling to A and B, the algorithm has:
route_a = 10+100 = 110
route_b = 10+90 = 100
It therefore explores route_b first and reaches C. It then has:
route_a = 10+100 = 110
route_b = (10+35)+80 = 125
It therefore explores route_a. Assuming there are no more fork nodes
between A and T, it reaches T and has
route_a = (10+110)+0 = 120
route_b = (10+35)+80 = 125
At this point, the algorithm terminates, having found the shortest
route. The distance that route_b has already travelled plus the
*shorted possible distance* that it would have to travel in order to
reach T is longer than the distance of route_a.
Nic's modification recognises that in real road networks, there's rarely
an exact straight line between two points. His hope was that adding 10%
to the straight-line distance still represents the minimum distance but
leads to routes away from the target being rejected more quickly.
> Would it break anything to even use sqr(dx)+sqr(dy) instead of
> sqrt(sqr(dx)+sqr(dy)) ?
Yes. The heuristic would no longer give the minimum distance. If you
don't see the problem, imagine the example above rotated by 45 degrees.
The straight-line distance between A and T is still 100.
dx=dy~=70.71. Instead of getting 100 back from the heuristic, though,
you get 10000 - and the algorithm will continue exploring route_b.
Summary:
- The heuristic must always be shorter than or equal to the shortest
actual path to the target for A* to find an optimal route.
- The closer the heuristic is to reality, the quicker A* will be.
- If the heuristic isn't shorter, the quality of the routes produced
will progressively degrade.
--
Jon
More information about the Routing
mailing list