Oxbridges of Konigsberg

[j4]

A challenge for the cartographically minded among my readers:

What's the most efficient route for visiting all Oxford's colleges?

Method of transport: bicycle. No other restrictions except that you must pass the lodge of each college. Doubling back on yourself is allowed (despite the title of the post!).

A reminder of the location of all the Colleges can be seen on this hopefully accurate map from the University website.

ETA:

I do realise this is a hard problem (Owen says it may even be an NP-hard problem) but thought it might've been the sort of thing that you clever people had already done... like the "visit all the underground stations in a day" challenge, kind of thing...

Comments

[katstevens.livejournal.com]

Hurray one of the bits of maths that's relatively easy to explain :)

First, make all of the colleges into dots (or nodes).

Second, draw lines between all the dots (or edges) - these represent the possible paths you'd go on your bike between the colleges so if there is more than one way to get between two colleges, you can draw two lines.

Third, put a number (the weight) onto each edge - this number represents the time in minutes (or seconds, whatever) it takes to travel each edge. Obv if you have two edges between the same two nodes, the one with the lowest figure is going to be the one you want if you're trying to do a shortest route thing, and you can get rid of the lengthy ones.

Once you've converted Oxford into this sort of abstract map, you can do lots of horrendous calculations on it! Or better yet, get your computer to do them for you!