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

[keirf.livejournal.com]

The most efficient way if you want to minimise the number of calories you burn is to put your bike in the back of a taxi and get the driver to take you to them all by whatever route he chooses.

[wechsler.livejournal.com]

Bonus points for a general solution to the Traveling Salesman problem.

[mobbsy.livejournal.com]

[vatine]

"Take N! salesmen, N-1! starting from each site, all taking different routes through the network, in parallel, at the same speed; have them record the route taken and consider the route taken by the first to arrive as the best route through the network".

It's O(1) in space, O(e^N) in salesmen and, I guess O(N)-ish in time (actually, I could probably argue for O(e^N) in space, as each salesman will require dedicated storage).

[juggzy.livejournal.com]

You need to define efficiency.

[martling.livejournal.com]

I don't know but I bet you end up at LMH.

[katstevens.livejournal.com]

Make it into a weighted graph and I can apply an adaptation of Dijkstra's algorithm for you?

[lnr]

Zooming out a bit it looks like St Stephen's House and Wolfson would be the obvious end points actually, and that LMH and Catz are going to both be a bit of a nuisance.

[martling.livejournal.com]

Ah. I didn't know about Wolfson hiding out there.

Do the halls count?

[hsenag.livejournal.com]

Luckily Templeton is no more.

[j4.livejournal.com]

This may be quibbling over technicalities but I don't think that satisfies the "mode of transport = bicycle" condition, really. :-}

Also, I wouldn't trust someone who was being paid by time/distance to take me on the shortest/quickest route!

[j4.livejournal.com]

I wondered afterwards if anybody would pick up on that. It wasn't meant to be a trick question, I was just trying to pre-empt everybody saying "don't go by bike, then" if I asked for "quickest" route.

So, er, quickest, probably, but I'm open to other interpretations. :-}

[j4.livejournal.com]

Sorry, yes: colleges and PPHs.

[j4.livejournal.com]

Ditto Greyfriars, so this problem is two whole colleges easier than it would have been a year ago! :)

[j4.livejournal.com]

Er, um. Can you explain how to make it into a weighted graph?

NB imagine you're explaining it to somebody who didn't do any maths beyond GCSE, because that's precisely what you'll be doing. :-}

[vatine]

That'd give you a spanning tree, not necessarily the "the shortest route touching all points", but a minimum-cost traversal of the spanning tree would probably not be TOO far off an optimal route for whatever cost metric chosen).

[htfb.livejournal.com]

But not Ripon College, Cuddesdon.

[caramel-betty.livejournal.com]

A graph is something like this:

http://en.wikipedia.org/wiki/File:6n-graf.svg

So there's a road (edge) from college 6 to college 4, and a road from college 4 to college 5. There's no direct road between 3 and 5, but you can get there going indirectly. A weighted graph is that, with the distance between each college provided as a weight.

So what you're being asked for is basically: "Can you draw me a map with all the allowable cycle routes on, and the distance of each bit?"

[htfb.livejournal.com]

I did too much maths at Oxford, and therefore I am qualified to talk about this---because I once missed the deadline for getting the marks from my intercollegiate classes into pigeon-post...

It wasn't every college I had to go to but it does take Too Long. I think that after Catz I took a rough anticlockwise circuit of the city walls, before heading towards St Hilda's.

[liv]

You could try asking mathematicians, who will probably start whirling their eyes and explaining highly technical stuff about why this is a really hard problem. Or you could try asking members of student am dram societies who frequently have to go on flyering runs for their performances, and you're likely to get a more practically useful answer. My advice: ask OULES or GandS.

[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!

[katstevens.livejournal.com]

Well, er, yes. My 'adaptation' would involve looking at said spanning tree and going 'which of these routes has a good pub at the end?'

[katstevens.livejournal.com]

Beaten to it! That'll teach me to directly reply via email :)

[geekette8.livejournal.com]

Haha, this was more or less the answer I gave for this in the Complexity bit of my Part 2 exam. In fact I think you had to ensure that the only person who came out at the other end of the network would have traversed the quickest route, or something like that, so I I did make a comment along the lines of "as soon as one person exits, blow the rest up Lemmings-style. This would require an awful lot of suicidal volunteers".

[jiggery-pokery.livejournal.com]

Congratulations! You have just invented Oxienteering.

What you do now is give the participants a GPS each and get them to walk their chosen route, collecting stamps from the porters of each college they visit. Once they have all the stamps, they use the GPS to find out how far they've walked. At the end, take the route of the person who claims the shortest distance, walk it again and check they haven't cheated. It's not proven to be correct, but it's a good first estimate.

This acceptance of rough and ready answers may make me a physicist.

[imc.livejournal.com]

I was about to mention that this problem sounds a lot like the TSP (http://en.wikipedia.org/wiki/Travelling_salesman_problem). It is of course NP complete.

To get from the Oxford Colleges problem to the TSP, one merely needs to draw a map of Oxford annotated with cycling times for each section of road/path and apply the all-pairs shortest path algorithm (http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm) (which is comparatively trivial).

[sea-bright.livejournal.com]

I can't speak for OULES, but as far as I'm aware, G&S never did flyering runs this way: in any G&S sized cast, you've got people at a fair proportion of the colleges, so you just ask people to cover their own and maybe a couple that are nearby. Though that was back in the days when that sort of flyering was still allowed, of course.

I was thinking that it might be worth asking someone from the university messenger service, as presumably they have to do something along these lines. Or do they split the job between several people, too?

[j4.livejournal.com]

Were it still part of ox.ac.uk I'd consider including it just to make a point, but probably not in a lunch-hour...

[j4.livejournal.com]

Faster than a speeding pigeon! :-)

So how long did it take -- or rather how long do you reckon it would take an average cyclist -- to get round all/most of them?

[j4.livejournal.com]

We really should actually do this, you know. :-) Though possibly with two categories for entry, one pedestrian and one quite exciting cycling.

[jiggery-pokery.livejournal.com]

The thing I like about it is that the winner isn't the person who's the quickest, but the one who travels least far. (Yes, sorry for ignoring your cycling stipulation, but it does work both ways.)

Probably the easiest way to do it would be to propose it as a challenge in a letter to the OxStu and the Cherwell offering a very small prize and let the geekocracy puzzle it out; it could rattle on for weeks in the lettercol and percolate through to the newsgroups...

[htfb.livejournal.com]

Is it not? I'd say "Things have changed around Oxford since my day" were it not a conceptual impossibility and a waste of a perfectly good trope.

[scat0324.livejournal.com]

http://oxford.openguides.org/wiki/?Visit_Every_College_In_A_Single_Day might be a start. I'll see if any of the OSM routing guys would like a challenge.

[sparrowsion]

Complication to all the nice graph-traversal ideas: if the condition for bagging a college is merely to pass in front of the lodge then then doubling back (or otherwise changing direction) is going to incur a (potentially significant) time penalty compared to cycling straight on. Note that this doesn't apply to approaching it as a shortest-distance problem (or a walking problem, except where you've got a third option of "cross road and go up side street") which means that there are quite likely two "correct" solutions.

[damerell.livejournal.com]

Naked?