[talk-au] How to map out streets the most efficently

[Andy Owen]

On Wed, 2009-06-17 at 19:27 +1000, Liz wrote:
> On Wed, 17 Jun 2009, James Livingston wrote:
> > There's a nice mathematical algorithm for figuring out that.
> It's a problem given to all computer science students to solve: 
> "the travelling salesman".
> The more points to cover, the more processing power it uses 
> which makes the way the human brain can solve those problems really cool.
> 

(sorry, I didn't get my comp sci degree for nothing :))

Actually, this is the Chinese Postman Problem, which is closer to the
problem of finding a Eulerian path, which is actually very possible -
even without knowing the map before hand (with a few assumptions). The
travelling salesman problem tries to find a short path between lots of
places, but it doesn't make any attempt to cover every street, so it
will miss out on lots of roads.

Exciting computer science ahead. Read on if bored (you've been warned):

A Eulerian path is a path that goes down every road exactly once, which
is exactly what you want. Unfortunately, it is only possible to do when
there are 0 or 2 intersections with an odd number of roads leading into
them (a dead end counts as an intersection too). And, if there is a pair
of intersections with an odd number of roads, then we need to start on
one of them (and we'll finish at the other). 

And yes, you also need to have full knowledge of the map when you are
planning, there also can't be one-way streets or turning restrictions.
If you ignore the restriction from the previous paragraph for now then:

1) Keep driving until you hit an intersection.
2) Go down a road you haven't been down. If there are multiple roads
which you haven't driven down, then pick any of the roads to follow,
unless choosing one would split the set of undriven roads in two. 

Now to fix the dead end and T intersection problem, before you start:
1) Find an intersection with an odd number of roads going to it.
2) Find the shortest path from it to any other intersection with an odd
number of roads going to it.
3) Add a fake road along that path, so you are then allowed to travel
down it more than one time.

For example, if you have a T intersection leading to a dead end, then
the dead end road would get a fake road placed over the top of it.

(but like most maths, this would probably end up making things worse if
you actually tried it - as it is much quicker to go straight than to be
constantly making right hand turns everywhere, and this algorithm
doesn't care)

(oh, and someone suggested that if the roads were all in a grid, you
could do smart things to take into account the redundancy, and just
zig-zag through, knowing you can extrapolate later... I don't know of
any algorithms that will find the best path in these cases - you would
need to add a fair bit of extra magic to existing graph theory to solve
it)

Andy
> 
> _______________________________________________
> Talk-au mailing list
> Talk-au at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-au