2. (a) Explain the difference between the classical and the practical travelling salesperson problem.
| A | B | C | D | E | F |
| A | - | 65 | 48 | 15 | 30 | 40 |
| B | 65 | - | 50 | 51 | 35 | 26 |
| C | 48 | 50 | - | 37 | 20 | 34 |
| D | 15 | 51 | 37 | - | 17 | 25 |
| E | 30 | 35 | 20 | 17 | - | 14 |
| F | 40 | 26 | 34 | 25 | 14 | - |
The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A , and wishes to minimise the total distance he will travel.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the route length.
(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route.