Moderate -0.3 This is a standard D2 TSP question requiring recall of definitions, application of Kruskal's algorithm (routine procedure), and using the MST method to find upper bounds. While multi-part with several steps, each component is a textbook exercise with no novel problem-solving required. The tour improvement in (d) is guided and algorithmic. Slightly easier than average due to being purely procedural.
2. (a) Explain the difference between the classical and practical travelling salesman problems.
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-1_691_1297_1014_383}
The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
(b) Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
(c) Use your answer to part (b) to determine an initial upper bound for the length of the route.
(d) Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.
e.g. when CD is part of the tree use GH (saving 26) and BD (saving 19) giving new u.b. of 125 km. Tour ABDEHGFDCA (or e.g. when BE is part of the tree use CG (saving 40) giving new upper bound of 130 km; Tour ABEHEDFGCA)
M1
(c) | Initial upper bound = $2 \times 85 = 170$ km | M1 A1 | 2 |
(d) | e.g. when CD is part of the tree use GH (saving 26) and BD (saving 19) giving new u.b. of 125 km. Tour ABDEHGFDCA (or e.g. when BE is part of the tree use CG (saving 40) giving new upper bound of 130 km; Tour ABEHEDFGCA) | M1 | 3 |
2. (a) Explain the difference between the classical and practical travelling salesman problems.\\
\includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-1_691_1297_1014_383}
The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at $A$, visit each restaurant at least once and cover a minimum distance.\\
(b) Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.\\
(c) Use your answer to part (b) to determine an initial upper bound for the length of the route.\\
(d) Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.\\
\hfill \mbox{\textit{Edexcel D2 2003 Q2 [10]}}