The problem nobody can solve quickly
Tonight's idea
A delivery van must visit every town on the map once and return to its start, driving as little as possible. This is the travelling salesman problem. A round trip that visits every town once is called a tour.
Being greedy built the cheapest network. The greedy idea here is nearest neighbour: from where you are, always drive to the closest town you have not visited. It is quick, and it can be wrong.
The safe method is to try every tour. With \(n\) towns, fix the start. The other towns can follow in \((n-1)!\) orders, where \(k!\) means \(k \times (k-1) \times \cdots \times 1\). Each tour appears twice, once in each direction.
The number of different tours of \(n\) towns is \(\dfrac{(n-1)!}{2}\).
For 5 towns that is 12. For 20 towns it is about \(6 \times 10^{16}\). Nobody has found a method that is always right and stays fast as the map grows. Nobody has proved that there is none, either.
Watch one: greedy against the best
Start at A. The nearest town is C (5). From C the nearest unvisited town is D (4). From D, B (10) beats E (11). Then E (4), and the only way home is the 12.
\(A \to C \to D \to B \to E \to A\): \(5 + 4 + 10 + 4 + 12 = 35\) km.
Checking all 12 tours finds a shorter one. \(A \to B \to E \to C \to D \to A\): \(9 + 4 + 8 + 4 + 6 = 31\) km. Greedy grabbed the 5 and the 4 first, and paid with the 10 and the 12.
Your turn
- How many different tours are there for (a) 4 towns, (b) 6 towns, (c) 10 towns?
- On the map, run nearest neighbour starting from (a) B, (b) D. Write down each tour and its length. Does the starting town matter?
- The two shortest roads are B–E and C–D. Exactly four of the 12 tours use both. List the four and find their lengths. Does using both cheapest roads guarantee the best tour?
- A computer checks a million tours every second. (a) How long does it need for 15 towns? (b) For 20 towns, in years? (c) By what factor does the work grow when a 21st town is added?
Stretch: a floor under every tour
Remove one road from any tour. What is left still connects every town. So every tour is longer than the cheapest network. Find the cheapest network on the map (being greedy works there) and its total length. How far above this floor is the best tour?
Answers
- (a) \(3!/2 = 3\). (b) \(5!/2 = 60\). (c) \(9!/2 = 181{,}440\).
- (a) \(B \to E \to C \to D \to A \to B\): \(4 + 8 + 4 + 6 + 9 = 31\) km, the best tour. (b) \(D \to C \to A \to B \to E \to D\): \(4 + 5 + 9 + 4 + 11 = 33\) km. Yes: the same rule gives 35, 31 or 33 depending on where it starts. From B it happens to be right, but nothing told you so.
- Treat B–E and C–D as two blocks to place around A; each block can face either way. A–B–E–C–D–A: 31. A–B–E–D–C–A: 33. A–E–B–C–D–A: \(12 + 4 + 7 + 4 + 6 = 33\). A–E–B–D–C–A: 35 (the greedy tour, backwards). No: three of the four are not the best.
- (a) \(14!/2 = 43{,}589{,}145{,}600\) tours, about 43,600 seconds: roughly 12 hours. (b) \(19!/2 \approx 6.08 \times 10^{16}\) tours, so \(6.08 \times 10^{10}\) seconds, about 1,900 years. (c) \(\dfrac{20!/2}{19!/2} = 20\). Each extra town multiplies the work by the number of towns already there. That is why "try them all" is hopeless, and why a fast method would matter.
Stretch. Take the cheapest roads that do not close a loop: C–D (4), B–E (4), A–C (5), then B–C (7), skipping A–D (6), which would close the loop A–C–D. Total 20 km. A tour with one road removed is a network joining all five towns, so it is at least 20 km, and the whole tour is more. The best tour, 31 km, is 11 km above the floor. A floor like this tells you how far from the best a tour can possibly be, without finding the best.