| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2020 |
| Session | January |
| 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 D1 algorithms (nearest neighbour and lower bound via deletion) with clearly defined steps. The table lookup and arithmetic are routine, requiring only careful execution of memorized procedures rather than problem-solving or insight. |
| 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 | - | 35 | 42 | 55 | 48 | 50 |
| B | 35 | - | 40 | 49 | 52 | 31 |
| C | 42 | 40 | - | 47 | 53 | 49 |
| D | 55 | 49 | 47 | - | 39 | 44 |
| E | 48 | 52 | 53 | 39 | - | 52 |
| F | 50 | 31 | 49 | 44 | 52 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Nearest neighbour: A – B – F – D – E – C – A with total length 35 + 31 + 44 + 39 + 53 + 42 = 244 (km) | M1 A1 | (2) |
| MST with B removed: AC, CD, DF, DE gives a RMST weight of 172 (km). 172 + 31 + 35 = 238 (km) | B1 M1 A1 | (3) |
| Nearest neighbour: A – B – F – D – E – C – A with total length 35 + 31 + 44 + 39 + 53 + 42 = 244 (km) | M1 A1 | (2) |
|---|---|---|
| MST with B removed: AC, CD, DF, DE gives a RMST weight of 172 (km). 172 + 31 + 35 = 238 (km) | B1 M1 A1 | (3) |
**Notes for Question 1:**
- **a1M1:** Nearest neighbour A – B – F – D – E – C (condone lack of return to start) or correct route length of 244. Accept AB, BF, FD, DE, EC but do not accept weights only. Accept 1 2 6 4 5 3 across the top of the table
- **a1A1:** CAO both route (either in terms of vertices (ABFDECA) or arcs (AB, BF, FD, DE, EC, CA)) but not weights) and length correct (244) do not ISW if this value is then doubled to 488
- **b1B1:** CAO for RMST weight (either 172 or 42 + 47 + 44 + 39) – maybe implied by later working
- **b1M1:** Adding 31 + 35 (the two least weighted arcs) to their RMST length – this mark may be implied by the correct value for the lower bound – note that their RMST must contain only four arcs
- **b1A1:** CAO - if 238 seen without working then award B0M1A1
---\begin{enumerate}
\item 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 .
\end{enumerate}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 35 & 42 & 55 & 48 & 50 \\
\hline
B & 35 & - & 40 & 49 & 52 & 31 \\
\hline
C & 42 & 40 & - & 47 & 53 & 49 \\
\hline
D & 55 & 49 & 47 & - & 39 & 44 \\
\hline
E & 48 & 52 & 53 & 39 & - & 52 \\
\hline
F & 50 & 31 & 49 & 44 & 52 & - \\
\hline
\end{tabular}
\end{center}
Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.\\
(a) Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.\\
(2)\\
(b) Starting by deleting B , and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.\\
(3)\\
\hfill \mbox{\textit{Edexcel D1 2020 Q1 [5]}}