| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2022 |
| 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 the nearest neighbour algorithm with clear instructions and a simple distance table. Students need only follow the mechanical procedure of repeatedly selecting the shortest available edge from the current vertex, requiring minimal problem-solving or insight beyond algorithm execution. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| Aber | Bangor | Conwy | Deganwy | E'bach | |
| Aber | - | 9.1 | 10.0 | 12.3 | 17.1 |
| Bangor | 9.1 | - | 15.5 | 17.8 | 22.7 |
| Conwy | 10.0 | 15.5 | - | 2.4 | 7.6 |
| Deganwy | 12.3 | 17.8 | 2.4 | - | 8.0 |
| E'bach | 17.1 | 22.7 | 7.6 | 8.0 | - |
| Answer | Marks |
|---|---|
| Nearest neighbour from Deganwy: \(\text{Deganwy} \to \text{Conwy} \to \text{E'bach} \to \text{Aber} \to \text{Bangor} \to \text{Deganwy}\), finding first two arcs PI by \(2.4 + 7.6\) | M1 |
| \(2.4 + 7.6 + 17.1 + 9.1 + 17.8 = 54.0\), upper bound \(= 54\) | A1 |
| Answer | Marks |
|---|---|
| Translates problem to finding at least 2 arcs of the MST | M1 |
| Finds MST for \(B, C, D, E\): weight \(= 15.5 + 2.4 + 7.6 = 25.5\) | A1 |
| Two shortest arcs from Aber are \(9.1\) and \(10.0\); Lower bound \(= 25.5 + 19.1 = 44.6\) | B1F |
## Question 4(a):
Nearest neighbour from Deganwy: $\text{Deganwy} \to \text{Conwy} \to \text{E'bach} \to \text{Aber} \to \text{Bangor} \to \text{Deganwy}$, finding first two arcs PI by $2.4 + 7.6$ | M1 |
$2.4 + 7.6 + 17.1 + 9.1 + 17.8 = 54.0$, upper bound $= 54$ | A1 |
---
## Question 4(b):
Translates problem to finding at least 2 arcs of the MST | M1 |
Finds MST for $B, C, D, E$: weight $= 15.5 + 2.4 + 7.6 = 25.5$ | A1 |
Two shortest arcs from Aber are $9.1$ and $10.0$; Lower bound $= 25.5 + 19.1 = 44.6$ | B1F |
---4 Alun, a baker, delivers bread to community shops located in Aber, Bangor, Conwy, and E'bach.
Alun starts and finishes his journey at the bakery, which is located in Deganwy.\\
The distances, in miles, between the five locations are given in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Aber & Bangor & Conwy & Deganwy & E'bach \\
\hline
Aber & - & 9.1 & 10.0 & 12.3 & 17.1 \\
\hline
Bangor & 9.1 & - & 15.5 & 17.8 & 22.7 \\
\hline
Conwy & 10.0 & 15.5 & - & 2.4 & 7.6 \\
\hline
Deganwy & 12.3 & 17.8 & 2.4 & - & 8.0 \\
\hline
E'bach & 17.1 & 22.7 & 7.6 & 8.0 & - \\
\hline
\end{tabular}
\end{center}
The minimum total distance that Alun can travel in order to make all four deliveries, starting and finishing at the bakery in Deganwy is $x$ miles.
4 (a) Using the nearest neighbour algorithm starting from Deganwy, find an upper bound for $x$\\
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2022 Q4 [5]}}