| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Basic Chinese Postman (closed route) |
| Difficulty | Easy -1.3 This is a straightforward application of basic algorithms from Decision Mathematics. Parts (a) and (d) require simple table lookups and addition, part (b) is a standard nearest neighbour algorithm execution, and part (c) is trivial comparison. No problem-solving insight or complex reasoning is needed—just methodical application of a well-practiced procedure with clear instructions. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| \backslashbox{From}{To} | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(D\) | E |
| A | - | 1.7 | 1.9 | 1.8 | 2.1 |
| B | 3.1 | - | 2.5 | 1.8 | 3.7 |
| \(\boldsymbol { C }\) | 3.1 | 2.9 | - | 2.7 | 4.2 |
| \(\boldsymbol { D }\) | 2.0 | 2.8 | 2.1 | - | 2.3 |
| E | 2.2 | 3.6 | 1.9 | 1.7 | - |
| Answer | Marks | Guidance |
|---|---|---|
| \(B\ E\ C\ D\ A\ B\), \(12(.0)\) | B1 | 1 mark |
| Answer | Marks | Guidance |
|---|---|---|
| Tour starts/finishes at \(B\); visits \(B\) twice and all other vertices once | M1, m1 | If solution only on a matrix, order of selection of vertices must be clearly shown |
| Correct order | A1 | |
| \(= 13.5\) | B1 | Total: 4 |
| Answer | Marks | Guidance |
|---|---|---|
| \(12(.0)\) | B1F | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(B\ A\ D\ E\ C\ B\) | M1 | Tour starts/finishes at \(B\); if solution only on a matrix, order of selection of vertices must be clearly shown |
| Visits \(B\) twice and all other vertices once | m1 | |
| Correct order | A1 | |
| \(= 12.1\) | B1 | Total: 4 |
## Question 5:
### Part (a)
| $B\ E\ C\ D\ A\ B$, $12(.0)$ | B1 | 1 mark |
### Part (b)
| Tour starts/finishes at $B$; visits $B$ twice and all other vertices once | M1, m1 | If solution only on a matrix, order of selection of vertices must be clearly shown |
| Correct order | A1 | |
| $= 13.5$ | B1 | **Total: 4** |
### Part (c)
| $12(.0)$ | B1F | 1 | Their min, condone writing 'part (a)' ft |
### Part (d)
| $B\ A\ D\ E\ C\ B$ | M1 | Tour starts/finishes at $B$; if solution only on a matrix, order of selection of vertices must be clearly shown |
| Visits $B$ twice and all other vertices once | m1 | |
| Correct order | A1 | |
| $= 12.1$ | B1 | **Total: 4** |
---5 There is a one-way system in Manchester. Mia is parked at her base, $B$, in Manchester and intends to visit four other places, $A , C , D$ and $E$, before returning to her base. The following table shows the distances, in kilometres, for Mia to drive between the five places $A , B , C , D$ and $E$. Mia wants to keep the total distance that she drives to a minimum.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\backslashbox{From}{To} & $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $D$ & E \\
\hline
A & - & 1.7 & 1.9 & 1.8 & 2.1 \\
\hline
B & 3.1 & - & 2.5 & 1.8 & 3.7 \\
\hline
$\boldsymbol { C }$ & 3.1 & 2.9 & - & 2.7 & 4.2 \\
\hline
$\boldsymbol { D }$ & 2.0 & 2.8 & 2.1 & - & 2.3 \\
\hline
E & 2.2 & 3.6 & 1.9 & 1.7 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Find the length of the tour $B E C D A B$.
\item Find the length of the tour obtained by using the nearest neighbour algorithm starting from $B$.
\item Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
\item On a particular day, the council decides to reverse the one-way system. For this day, find the length of the tour obtained by using the nearest neighbour algorithm starting from $B$.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q5 [10]}}