5 [Figure 3, printed on the insert, is provided for use in this question.]
- James is solving a travelling salesperson problem.
- He finds the following upper bounds: \(43,40,43,41,55,43,43\).
Write down the best upper bound.
- James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 .
Write down the best lower bound.
- Karen is solving a different travelling salesperson problem and finds an upper bound of 55 and a lower bound of 45 . Write down an interpretation of these results.
- The diagram below shows roads connecting 4 towns, \(A , B , C\) and \(D\). The numbers on the edges represent the lengths of the roads, in kilometres, between adjacent towns.
\includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-05_451_1034_1160_504}
Xiong lives at town \(A\) and is to visit each of the other three towns before returning to town \(A\). She wishes to find a route that will minimise her travelling distance.
- Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
- Use the nearest neighbour algorithm on Figure 3 to find an upper bound for the minimum length of a tour of this network that starts and finishes at \(A\).
- Hence find the actual route that Xiong would take in order to achieve a tour of the same length as that found in part (c)(ii).