5 [Figure 2, printed on the insert, is provided for use in this question.]
- Gill is solving a travelling salesperson problem.
- She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5.
Write down the best upper bound.
- She finds the following lower bounds: \(6.5,7,6.5,5,7\).
Write down the best lower bound.
- George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\).
The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available.
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
- Complete Figure 2 to show the minimum times to travel between all pairs of cities.
- Find an upper bound for the minimum total flying time by using the route FTPOMF.
- Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
- By deleting \(F\), find a lower bound for the minimum total flying time.