?

Log in

No account? Create an account
entries friends calendar profile Previous Previous Next Next
Oxbridges of Konigsberg - shadows of echoes of memories of songs — LiveJournal
j4
j4
Oxbridges of Konigsberg
Read 35 | Write
Comments
imc From: imc Date: February 11th, 2009 10:50 pm (UTC) (Link)
I was about to mention that this problem sounds a lot like the TSP. 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 (which is comparatively trivial).
Read 35 | Write