- (a) Explain the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.
| A | B | C | D | E | F | G |
| A | - | 31 | 15 | 12 | 24 | 17 | 22 |
| B | 31 | - | 20 | 25 | 14 | 25 | 50 |
| C | 15 | 20 | - | 16 | 24 | 19 | 21 |
| D | 12 | 25 | 16 | - | 21 | 32 | 17 |
| E | 24 | 14 | 24 | 21 | - | 28 | 41 |
| F | 17 | 25 | 19 | 32 | 28 | - | 25 |
| G | 22 | 50 | 21 | 17 | 41 | 25 | - |
The table above shows the least direct distances, in miles, between seven towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G. Yiyi needs to visit each town, starting and finishing at A, and wishes to minimise the total distance she will travel.
(b) Show that there are two nearest neighbour routes that start from A. State these routes and their lengths.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the length of Yiyi's route.
(d) Use your results to write down the smallest interval which you can be confident contains the optimal length of Yiyi's route.