| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Improve Upper Bound with Shortcuts |
| Difficulty | Moderate -0.3 This is a standard D2 algorithm application question requiring Prim's algorithm for MST, then using it to find TSP bounds via the tour method and shortcuts, plus deletion method for lower bound. All techniques are routine textbook procedures with no novel problem-solving required, though the multi-part structure and careful bookkeeping across 14 marks makes it slightly more substantial than a minimal recall question. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | \(-\) | 85 | 110 | 175 | 108 | 100 |
| B | 85 | \(-\) | 38 | 175 | 160 | 93 |
| C | 110 | 38 | \(-\) | 148 | 156 | 73 |
| D | 175 | 175 | 148 | \(-\) | 110 | 84 |
| E | 108 | 160 | 156 | 110 | \(-\) | 92 |
| F | 100 | 93 | 73 | 84 | 92 | \(-\) |
The table below shows the distances, in km, between six towns $A$, $B$, $C$, $D$, $E$ and $F$.
\begin{tabular}{c|cccccc}
& A & B & C & D & E & F \\
\hline
A & $-$ & 85 & 110 & 175 & 108 & 100 \\
B & 85 & $-$ & 38 & 175 & 160 & 93 \\
C & 110 & 38 & $-$ & 148 & 156 & 73 \\
D & 175 & 175 & 148 & $-$ & 110 & 84 \\
E & 108 & 160 & 156 & 110 & $-$ & 92 \\
F & 100 & 93 & 73 & 84 & 92 & $-$
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Starting from $A$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected. [4]
\item \begin{enumerate}[label=(\roman*)]
\item Using your answer to part (a) obtain an initial upper bound for the solution of the travelling salesman problem. [2]
\item Use a short cut to reduce the upper bound to a value less than 680. [4]
\end{enumerate}
\item Starting by deleting $F$, find a lower bound for the solution of the travelling salesman problem. [4]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q6 [14]}}