1)The shortest route is London -> Cambridge -> Coventry -> Bath -> London with a distance of 296 miles.
2)If you look at an atlas, this route puts the cities in a sensible loop.
3)The only way to be certain this route is optimal is to consider all the other routes. However, it seems likely this is the best route, because it uses most of the smaller numbers from the table.
4)There are 3*2*1=6 routes in total. Starting from London:
5)The longest route is London -> Bath -> Cambridge -> Coventry -> London with a distance of 372 miles.
After adding in Oxford to the route:
The shortest route is now 314 miles:
London -> Cambridge -> Coventry -> Bath -> Oxford -> London
The longest route is now 413 miles:
London->Bath->Cambridge->Oxford->Coventry-> London
For the case, with 5 cities including London, we need to check 4*3*2*1=24 possible routes.
In general, for n cities, we need to check (n-1)! routes. (Can you explain why?). Here's a table showing how long this would take:
| Number of cities | (n-1)! | Time take to search all routes |
| 4 | 6 | 6*10^-6 s |
| 5 | 24 | 2.4*10^-5 s |
| 10 | 362880 | 0.36s |
| 15 | 1.31*10^12 | 1.31*10^6 s = 15.2 days |
| 20 | 2.43*10^18 | 2.43*10^12 s = 77100 years |
| 100 | 9.33*10^157 | 9.33*10^151 s = 1.08*10^147 years! |
N.B. The age of the universe is 433.6 x 1015s!
(We say this algorithm has order of n! time complexity.)
The greedy algorithm takes time proportional to n^2, where n is the number of cities in the route. Departing London, it needs to find the smallest of (n-1) numbers, which takes (n-2) comparisons. From this city, it needs to find the smallest of (n-2) numbers, which takes (n-3) comparisons. This continues, until the destination before London is fixed, as all the other cities have been visited.
In total, this takes (n-2)+(n-3)+... + 1 = (n-1)*(n-2)/2 = O(n^2) operations as claimed.
If n=100, this would take about 0.01s, assuming we can still do 10^6 operations a second.
The olympic route can be seen here. Was your guess correct?
Investigation from the end of the problem - new resource?
Suppose that you don't have the time for the brute force approach to complete. You could try a 'greedy algorithm' which starts at London and then simply travels to the next nearest remaining city and so on. How quickly would the greedy algorithm take the computer for 100 cities?
Investigation: Implement the greedy algorithm 'by eye' for the major population centres shown on the map below. What order would you place the cities in by using this method? Does it agree with your friends' routes? Did any questions or observations arise in you mind when you implemented the greedy algorithm? Now try to determine a better route using cunning or any other method at your disposal. You could check to find the actual length of the routes to see if you improved on the order provided by the greedy algorithm. You might wish to compare with the actual torch route when it is revealed to see if your ordering for these places matches the actual ordering used on the torch relay.