| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2019 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | State Best Bounds Interval |
| Difficulty | Moderate -0.3 This is a standard textbook application of nearest neighbour algorithm and minimum spanning tree deletion method for TSP bounds. The procedures are algorithmic and well-practiced, requiring careful arithmetic but no problem-solving insight. Slightly easier than average due to the small graph size (6 vertices) and routine nature of the question. |
| 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 | - | 73 | 56 | 27 | 38 | 48 |
| B | 73 | - | 58 | 59 | 43 | 34 |
| C | 56 | 58 | - | 46 | 38 | 42 |
| D | 27 | 59 | 46 | - | 25 | 32 |
| E | 38 | 43 | 38 | 25 | - | 21 |
| F | 48 | 34 | 42 | 32 | 21 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| NNA: A – D – E – F – B – C – A, \(27+25+21+34+58+56 = 221\) (km) | M1 A1 A1 | a1M1: Nearest neighbour A – D – E – F – B or accept 15 6 2 3 4 across the top of the table. a1A1: Route correctly stated, must return to A, accept link back to A. a2A1: Length correctly stated. Do not ISW if candidates then go on to double the route length |
| RMST weight = 118 (km), \(118 + 27 + 38 = 183\) (km) | M1 A1 A1 | b1B1: CAO for RMST weight (either 118 or \(34 + 21 + 25 + 38\)) – maybe implied by later working. b1M1: Adding \(27 + 38\) (the two least weighted arcs) to their RMST length – this mark maybe implied by the correct value for the lower bound – note that their RMST must contain only four arcs. b1A1: CAO - if 183 seen without working then award all 3 marks in (b) |
| \(183 \leq \text{length} \leq 221\) | M1 A1 A1 | c1M1: Their answers from (a) and (b) correctly used, accept any inequalities or any indication of an interval from their 183 to their 221 (so \(183 - 221\) can score this mark). Please note that UB > LB for this mark. c1A1: CAO (no follow through on their values) including correct inequalities or equivalent set notation (but condone \(183 < \text{length} \leq 221\)) |
| Total: 8 marks |
| Answer | Marks | Guidance |
|--------|-------|----------|
| NNA: A – D – E – F – B – C – A, $27+25+21+34+58+56 = 221$ (km) | M1 A1 A1 | a1M1: Nearest neighbour A – D – E – F – B or accept 15 6 2 3 4 across the top of the table. a1A1: Route correctly stated, must return to A, accept link back to A. a2A1: Length correctly stated. Do not ISW if candidates then go on to double the route length |
| RMST weight = 118 (km), $118 + 27 + 38 = 183$ (km) | M1 A1 A1 | b1B1: CAO for RMST weight (either 118 or $34 + 21 + 25 + 38$) – maybe implied by later working. b1M1: Adding $27 + 38$ (the two least weighted arcs) to their RMST length – this mark maybe implied by the correct value for the lower bound – note that their RMST must contain only four arcs. b1A1: CAO - if 183 seen without working then award all 3 marks in (b) |
| $183 \leq \text{length} \leq 221$ | M1 A1 A1 | c1M1: Their answers from (a) and (b) correctly used, accept any inequalities or any indication of an interval from their 183 to their 221 (so $183 - 221$ can score this mark). Please note that UB > LB for this mark. c1A1: CAO (no follow through on their values) including correct inequalities or equivalent set notation (but condone $183 < \text{length} \leq 221$) |
| **Total: 8 marks** | | |
---1.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 73 & 56 & 27 & 38 & 48 \\
\hline
B & 73 & - & 58 & 59 & 43 & 34 \\
\hline
C & 56 & 58 & - & 46 & 38 & 42 \\
\hline
D & 27 & 59 & 46 & - & 25 & 32 \\
\hline
E & 38 & 43 & 38 & 25 & - & 21 \\
\hline
F & 48 & 34 & 42 & 32 & 21 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.
\begin{enumerate}[label=(\alph*)]
\item Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
\item Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
\item Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2019 Q1 [8]}}