5 [Figure 3, printed on the insert, is provided for use in this question.]
\begin{enumerate}[label=(\alph*)]
\item James is solving a travelling salesperson problem.
\begin{enumerate}[label=(\roman*)]
\item He finds the following upper bounds: $43,40,43,41,55,43,43$.

Write down the best upper bound.
\item James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 .

Write down the best lower bound.
\end{enumerate}\item 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.
\item 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.
\begin{enumerate}[label=(\roman*)]
\item Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
\item 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$.
\item 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).
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{AQA D1 2008 Q5 [10]}}