| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2019 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a straightforward application of two standard algorithms (nearest neighbour and lower bound via deletion) to a small 6-node problem. The table lookup and arithmetic are routine, requiring only careful execution of memorized procedures with no problem-solving insight or novel reasoning. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | A | B | C | D | E | F |
| A | - | 53 | 47 | 39 | 35 | 40 |
| B | 53 | - | 32 | 46 | 41 | 43 |
| C | 47 | 32 | - | 51 | 47 | 37 |
| D | 39 | 46 | 51 | - | 36 | 49 |
| E | 35 | 41 | 47 | 36 | - | 42 |
| F | 40 | 43 | 37 | 49 | 42 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| NNA: \(D - E - A - F - C - B - D\) | M1 | Nearest neighbour starting at D – must get to at least \(D - E - A - F - C\), or correct length stated |
| \(36 + 35 + 40 + 37 + 32 + 46 = 226\) (km) | A1 (2) | Both route and length correctly stated (route must return to D). If double 226, A0. Do not isw. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| RMST weight \(= 144\) (km) | B1 | CAO for RMST weight (either 144 or \(35 + 40 + 37 + 32\)) – maybe implied by later working |
| \(144 + 39 + 36 = 219\) (km) | M1 A1 (3) | Adding 39 and 36 (the two least weighted arcs) to their RMST length. CAO – if 219 seen without working then award all 3 marks in (b) |
# Question 1:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| NNA: $D - E - A - F - C - B - D$ | M1 | Nearest neighbour starting at D – must get to at least $D - E - A - F - C$, or correct length stated |
| $36 + 35 + 40 + 37 + 32 + 46 = 226$ (km) | A1 (2) | Both route and length correctly stated (route must return to D). If double 226, A0. Do not isw. |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| RMST weight $= 144$ (km) | B1 | CAO for RMST weight (either 144 or $35 + 40 + 37 + 32$) – maybe implied by later working |
| $144 + 39 + 36 = 219$ (km) | M1 A1 (3) | Adding 39 and 36 (the two least weighted arcs) to their RMST length. CAO – if 219 seen without working then award all 3 marks in (b) |
---1.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & A & B & C & D & E & F \\
\hline
A & - & 53 & 47 & 39 & 35 & 40 \\
\hline
B & 53 & - & 32 & 46 & 41 & 43 \\
\hline
C & 47 & 32 & - & 51 & 47 & 37 \\
\hline
D & 39 & 46 & 51 & - & 36 & 49 \\
\hline
E & 35 & 41 & 47 & 36 & - & 42 \\
\hline
F & 40 & 43 & 37 & 49 & 42 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.
\begin{enumerate}[label=(\alph*)]
\item Starting at D , use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length.
\item Starting by deleting D , and all of its arcs, find a lower bound for the route length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2019 Q1 [5]}}