[Routing] A-Star meet-in-the-middle
jon at siliconcircus.com
Tue Nov 20 21:24:19 GMT 2007
Nic Roets wrote:
> * Rewrite in C and use hash tables.
While we're still at the stage of working out which algorithms to use
how, I much prefer using ruby/similar. Prototyping is far easier. When
it's clear what's best, a C implementation may be worthwhile.
> * Change the A* heuristic from sqrt(sqr(dx)+sqr(dy)) to 1.1*sqrt(...)
> or larger. This acknowledges that roads the shortest route between two
> points is usually 10% longer than a straight route. And if you're
> wrong the route may be slightly suboptimal, who cares.
Tried it. 1.1 is too high, you easily get suboptimal routes. I then
tried a similar approach:
distance > 100km -> distance*1.2
distance > 50km -> distance*1.1
distance > 10km -> distance*1.05
distance <= 10km -> distance
I tried this with varying factors/limits. Depending on the parameters,
the result was (in general terms) that it produced suboptimal routes or
that it didn't help too much with speed. I didn't find a happy medium
for my test routes.
> (Why aren't we discussing the important issues, like adding a penalty
> to right turns at intersections... ?)
Because we didn't yet work out which algorithm to use to get acceptable
speed on long routes. Once you've got this and solved the
less-knotty-but-still-not-trivial problem of whether you want to
penalise right (UK) or left (Europe, US) turns, actual implementation
should be simple.
More information about the Routing