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
Read 35 | Write
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).
geekette8 From: geekette8 Date: February 11th, 2009 10:18 pm (UTC) (Link)
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".
Read 35 | Write