Log in

No account? Create an account
entries friends calendar profile Previous Previous Next Next
shadows of echoes of memories of songs
Oxbridges of Konigsberg
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.


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...

Tags: , , ,

Read 35 | Write
keirf From: keirf Date: February 11th, 2009 04:47 pm (UTC) (Link)
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.
j4 From: j4 Date: February 11th, 2009 07:08 pm (UTC) (Link)
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!
wechsler From: wechsler Date: February 11th, 2009 05:01 pm (UTC) (Link)
Bonus points for a general solution to the Traveling Salesman problem.
From: vatine Date: February 11th, 2009 05:09 pm (UTC) (Link)
"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).
mobbsy From: mobbsy Date: February 11th, 2009 05:07 pm (UTC) (Link)
juggzy From: juggzy Date: February 11th, 2009 05:17 pm (UTC) (Link)
You need to define efficiency.
j4 From: j4 Date: February 11th, 2009 07:10 pm (UTC) (Link)
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. :-}
martling From: martling Date: February 11th, 2009 05:37 pm (UTC) (Link)
I don't know but I bet you end up at LMH.
lnr From: lnr Date: February 11th, 2009 06:15 pm (UTC) (Link)
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.
katstevens From: katstevens Date: February 11th, 2009 05:38 pm (UTC) (Link)
Make it into a weighted graph and I can apply an adaptation of Dijkstra's algorithm for you?
j4 From: j4 Date: February 11th, 2009 07:12 pm (UTC) (Link)
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. :-}
htfb From: htfb Date: February 11th, 2009 07:30 pm (UTC) (Link)
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.
j4 From: j4 Date: February 11th, 2009 11:01 pm (UTC) (Link)
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?
livredor From: livredor Date: February 11th, 2009 07:36 pm (UTC) (Link)
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.
sea_bright From: sea_bright Date: February 11th, 2009 10:55 pm (UTC) (Link)
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?
jiggery_pokery From: jiggery_pokery Date: February 11th, 2009 10:34 pm (UTC) (Link)
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.
j4 From: j4 Date: February 11th, 2009 11:04 pm (UTC) (Link)
We really should actually do this, you know. :-) Though possibly with two categories for entry, one pedestrian and one quite exciting cycling.
From: scat0324 Date: February 12th, 2009 09:47 am (UTC) (Link)
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.
sion_a From: sion_a Date: February 12th, 2009 10:40 am (UTC) (Link)
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.
(Deleted comment)
Read 35 | Write