Compare Multiple Upper Bounds

7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools. \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.

1. Complete Table 1.
2. 1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
   2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
   3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
3. 1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
   2. Hence find a lower bound for the length of Sam's minimum tour.
   3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
4. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
   (2 marks) \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 2}

   	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { F }\)	G
   A	-	2	6	4	16	27
   \(\boldsymbol { B }\)	2	-	8	3	15	26
   \(\boldsymbol { C }\)	6	8	-	10	22	32
   \(\boldsymbol { D }\)	4	3	10	-	12	23
   \(\boldsymbol { F }\)	16	15	22	12	-	20
   G	27	26	32	23	20	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}

4.

1. Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G.

   	A	B	C	D	E	F	G
   A	-	25	31	28	35	30	32
   B	25	-	34	24	27	32	39
   C	31	34	-	40	35	27	29
   D	28	24	40	-	37	35	36
   E	35	27	35	37	-	28	31
   F	30	32	27	35	28	-	33
   G	32	39	29	36	31	33	-

   Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.
2. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran's route. Make your method clear. Starting at D, a second upper bound of 203 km was found.
3. State whether this is a better upper bound than the answer to (b), giving a reason for your answer. A reduced network is formed by deleting \(G\) and all the arcs that are directly joined to \(G\).
4. 1. Use Prim's algorithm, starting at A, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.
   2. Hence calculate a lower bound for the length of Fran's route. By deleting A, a second lower bound was found to be 188 km .
5. State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.
6. Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran's optimal route.