3. (a) Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.
| A | B | C | D | E | F | G |
| A | - | 17 | 24 | 16 | 21 | 18 | 41 |
| B | 17 | - | 35 | 25 | 30 | 31 | \(x\) |
| C | 24 | 35 | - | 28 | 20 | 35 | 32 |
| D | 16 | 25 | 28 | - | 29 | 19 | 45 |
| E | 21 | 30 | 20 | 29 | - | 22 | 35 |
| F | 18 | 31 | 35 | 19 | 22 | - | 37 |
| G | 41 | \(x\) | 32 | 45 | 35 | 37 | - |
The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is \(x \mathrm {~km}\), where \(x > 25\)
Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
(b) Starting by deleting B and all of its arcs, find a lower bound for Preety's route.
Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,
(c) find \(x\), making your method clear.
(d) Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.