2 marksExplain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.
3 marksWrite your answer in the Answer Booklet.
| A | B | C | D | E | F | G |
A | – | 17 | 24 | 16 | 21 | 18 | 41 |
B | 17 | – | 35 | 25 | 30 | 31 |
|
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 |
| 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 
km, where > 25
Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
Starting by deleting B and all of its arcs, find a lower bound for Preety’s route.
4 marksWrite your answer in the Answer Booklet.
Pretty found the nearest neighbour routes from each of A and C. Given that the sum of the lengths of these routes is 331 km,
find , making your method clear.
2 marksWrite down the smallest interval that you can be confident contains the optimal length of Preety’s route. Give your answer as an inequality.
Did this page help you?