| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Classical vs Practical TSP |
| Difficulty | Moderate -0.3 This is a standard D2 TSP question requiring routine application of nearest neighbour algorithm and minimum spanning tree deletion method. Part (a) is bookwork recall, parts (b-d) follow algorithmic procedures with no novel problem-solving required. The calculations are straightforward with a small 6-vertex network, making this slightly easier than average A-level maths. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | - | 65 | 48 | 15 | 30 | 40 |
| B | 65 | - | 50 | 51 | 35 | 26 |
| C | 48 | 50 | - | 37 | 20 | 34 |
| D | 15 | 51 | 37 | - | 17 | 25 |
| E | 30 | 35 | 20 | 17 | - | 14 |
| F | 40 | 26 | 34 | 25 | 14 | - |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | \(B2, 1, 0\) | (2) |
| (b) | \(M1 A1\) | (3) |
| \(A1\) | — | Route correctly stated, must return to A, accept link back to A |
| (c) | \(M1 A1\) | (3) |
| \(A1\) | — | RMST correct or list of arcs or \(77\) or \(26 + 14 + 17 + 20\) seen |
| (d) | \(B2, 1, 0\) | (2) |
| 10 marks |
**(a)** | $B2, 1, 0$ | (2) | Understands the difference is connected to number of times each vertex may be visited |
**(b)** | $M1 A1$ | (3) | Nearest neighbour A–D–E–F–B–C–A or accept 145623 across top of table (condone lack of return to start) |
| $A1$ | — | Route correctly stated, must return to A, accept link back to A |
**(c)** | $M1 A1$ | (3) | Finding RST (maybe implicitly) using correct two least lengths. Their RST must have only four arcs of which none are incident to A |
| $A1$ | — | RMST correct or list of arcs or $77$ or $26 + 14 + 17 + 20$ seen |
**(d)** | $B2, 1, 0$ | (2) | Their correct numbers correctly used (upper bound must be a cycle, lower bound must have scored M1 in (c)), accept any inequalities or any indication of interval from their 122 to their 170 |
| | 10 marks | |
---2. (a) Explain the difference between the classical and the practical travelling salesperson problem.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F \\
\hline
A & - & 65 & 48 & 15 & 30 & 40 \\
\hline
B & 65 & - & 50 & 51 & 35 & 26 \\
\hline
C & 48 & 50 & - & 37 & 20 & 34 \\
\hline
D & 15 & 51 & 37 & - & 17 & 25 \\
\hline
E & 30 & 35 & 20 & 17 & - & 14 \\
\hline
F & 40 & 26 & 34 & 25 & 14 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A , and wishes to minimise the total distance he will travel.\\
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length.\\
(c) Starting by deleting A, and all of its arcs, find a lower bound for the route length.\\
(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route.\\
\hfill \mbox{\textit{Edexcel D2 2014 Q2 [10]}}