| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Classical vs Practical TSP |
| Difficulty | Moderate -0.8 This is a straightforward application of standard Decision Maths algorithms (nearest neighbour for upper bounds, vertex deletion for lower bounds) with no novel problem-solving required. The question guides students through each step explicitly, requiring only routine execution of memorized procedures and basic comparison of bounds. Significantly easier than average A-level maths questions which typically require more independent reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | - | 77 | 34 | 56 | 67 | 21 |
| B | 77 | - | 58 | 58 | 36 | 74 |
| C | 34 | 58 | - | 73 | 70 | 42 |
| D | 56 | 58 | 73 | - | 68 | 38 |
| E | 67 | 36 | 70 | 68 | - | 71 |
| F | 21 | 74 | 42 | 38 | 71 | - |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | In the classical problem each vertex must be visited only once. In the practical problem each vertex must be visited at least once. | B2, 1, 0 (2) |
| (b) | \(A \xrightarrow{21} F \xrightarrow{38} D \xrightarrow{58} B \xrightarrow{36} E \xrightarrow{70} C \xrightarrow{34} A\) with \(\{1 \, 4 \, 6 \, 3 \, 5 \, 2\}\) and \(21 + 38 + 58 + 36 + 70 + 34 = 257\) | M1 A1 A1 (3) |
| (c) | 257 is the better upper bound, it is lower. | B1ft (1) |
| (d) | R.M.S.T. with \(C \xrightarrow{34} A \xrightarrow{21} F \xrightarrow{38} D\) and \(E\) hanging from \(A\) with edge weight 67 | M1A1 (4) |
| Lower bound is \(160 + 36 + 58 = 254\) | ||
| (e) | Better lower bound is 254, it is higher | B1ft (1) |
| (f) | \(254 < \text{optimal} \leq 257\) | B1 (2) |
(a) | In the classical problem each vertex must be visited only once. In the practical problem each vertex must be visited **at least once**. | B2, 1, 0 (2) | |
(b) | $A \xrightarrow{21} F \xrightarrow{38} D \xrightarrow{58} B \xrightarrow{36} E \xrightarrow{70} C \xrightarrow{34} A$ with $\{1 \, 4 \, 6 \, 3 \, 5 \, 2\}$ and $21 + 38 + 58 + 36 + 70 + 34 = 257$ | M1 A1 A1 (3) | |
(c) | 257 is the better upper bound, it is lower. | B1ft (1) | ft their lowest |
(d) | R.M.S.T. with $C \xrightarrow{34} A \xrightarrow{21} F \xrightarrow{38} D$ and $E$ hanging from $A$ with edge weight 67 | M1A1 (4) | Finding correct RMST (maybe implicit) 160 sufficient; cao tree or 160. |
| Lower bound is $160 + 36 + 58 = 254$ | | |
(e) | Better lower bound is 254, it is higher | B1ft (1) | ft their highest |
(f) | $254 < \text{optimal} \leq 257$ | B1 (2) | cao |
**Total [12]**
---2. (a) Explain the difference between the classical and the practical travelling salesperson problems.
The table below shows the distances, in km, between six data collection points, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$, and F .
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 77 & 34 & 56 & 67 & 21 \\
\hline
B & 77 & - & 58 & 58 & 36 & 74 \\
\hline
C & 34 & 58 & - & 73 & 70 & 42 \\
\hline
D & 56 & 58 & 73 & - & 68 & 38 \\
\hline
E & 67 & 36 & 70 & 68 & - & 71 \\
\hline
F & 21 & 74 & 42 & 38 & 71 & - \\
\hline
\end{tabular}
\end{center}
Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.\\
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear.
Starting at B, a second upper bound of 293 km was found.\\
(c) State the better upper bound of these two, giving a reason for your answer.
By deleting A, a lower bound was found to be 245 km .\\
(d) By deleting B, find a second lower bound. Make your method clear.\\
(e) State the better lower bound of these two, giving a reason for your answer.\\
(f) Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel's optimal route.\\
\hfill \mbox{\textit{Edexcel D2 2009 Q2 [12]}}