[OSM-dev] Feature request for OSMApplet for London Mapping event

Robert (Jamie) Munro rjmunro at arjam.net
Tue Jan 9 19:04:36 GMT 2007


Kristian Thy wrote:
> On Tue, Jan 09, Robert (Jamie) Munro wrote:
>> What would be nice would be for JOSM to solve the travelling salesman
>> problem and issue navigation instructions to visit all the untagged
>> segments in an area with the least possible driving.
> 
> That would be great! Then we could use the million dollar prize for new
> hardware >:)
> 
> http://www.claymath.org/millennium/

:-)

I didn't quite mean solve it, just make a good enough approximation that
means you don't end up driving the same roads over and over and miss out
some others. You can solve small cases with brute force, of course, but
all the untagged ways and segments in London is probably too much.

Of course, it's never going to work in practise because 50% of the one
way roads will be in the other direction than the computer wants you to
drive them. As soon as you find this out (or just take a wrong turn), it
could try and calculate a new route, but the route you will end up
taking will probably be far from the theoretical optimal one which you
could calculate once you have finished, given a large supercomputer and
lots of time.

Robert (Jamie) Munro

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20070109/76838925/attachment.pgp>


More information about the dev mailing list