| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a standard algorithmic question requiring systematic application of the nearest neighbour algorithm and minimum spanning tree deletion method. While multi-part with several marks, it involves routine procedural steps (reading from a table, following prescribed algorithms) with minimal problem-solving or conceptual insight beyond understanding what upper/lower bounds mean. Typical D1 examination question that's easier than average A-level maths. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { P }\) | \(T\) | \(V\) | |
| \(\boldsymbol { B }\) | - | 43 | 57 | 52 | 18 |
| \(\boldsymbol { C }\) | 43 | - | 18 | 13 | 56 |
| \(P\) | 57 | 18 | - | 8 | 48 |
| \(T\) | 52 | 13 | 8 | - | 51 |
| \(V\) | 18 | 56 | 48 | 51 | - |
| Answer | Marks | Guidance |
|---|---|---|
| 130 | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(T\) | 8 | \(P\) |
| M1 | Visits all vertices starting from \(T\) | |
| A1 | Correct order | |
| B1 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| A possible solution, eg tour. May be improved on | E1 | |
| E1 | 2 | Allow 'can' in this case as (i) < (ii) OE |
| Answer | Marks | Guidance |
|---|---|---|
| Spanning tree with 3 edges | M1 | |
| A1 | Correct | |
| \(PT\), \(CT\), \(PV\) | ||
| \(C\) | ||
| + 2 shortest from \(B\): 43 and 18 | ||
| m1 | 2 edges from \(B\) | |
| A1 | Correct | |
| (Lower bound) = 130 | A1 | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| May not exist. Cannot be lowered | E1 | |
| E1 | 2 | OE |
| Answer | Marks | Guidance |
|---|---|---|
| Tour or optimum or same as (a)(i) | B1 | |
| E1 | 2 | Lower bound = Upper bound |
| Total | 16 |
## 4(a)(i)
| 130 | B1 | 1 |
## 4(a)(ii)
| $T$ | 8 | $P$ | 48 | $C$ | 18 | $B$ | 43 | $V$ | 18 | $T$ | 51 | = 138 | M1 | Tour (vertices or edges) starting from $T$ (Letters not numbers) |
| | | | | | | | | | | | | | M1 | Visits all vertices starting from $T$ |
| | | | | | | | | | | | | | A1 | Correct order |
| | | | | | | | | | | | | | B1 | 4 |
## 4(a)(iii)
| A possible solution, eg tour. May be improved on | E1 | | OE |
| | E1 | 2 | Allow 'can' in this case as (i) < (ii) OE |
## 4(b)(i)
| Spanning tree with 3 edges | M1 | |
| | A1 | Correct |
| $PT$, $CT$, $PV$ | | |
| $C$ | | |
| + 2 shortest from $B$: 43 and 18 | | |
| | m1 | 2 edges from $B$ |
| | A1 | Correct |
| (Lower bound) = 130 | A1 | 5 | CSO |
## 4(b)(ii)
| May not exist. Cannot be lowered | E1 | | OE |
| | E1 | 2 | OE |
## 4(c)
| Tour or optimum or same as (a)(i) | B1 | |
| | E1 | 2 | Lower bound = Upper bound |
| Total | | 16 |4 David, a tourist, wishes to visit five places in Rome: Basilica ( $B$ ), Coliseum ( $C$ ), Pantheon ( $P$ ), Trevi Fountain ( $T$ ) and Vatican ( $V$ ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place.
The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { P }$ & $T$ & $V$ \\
\hline
$\boldsymbol { B }$ & - & 43 & 57 & 52 & 18 \\
\hline
$\boldsymbol { C }$ & 43 & - & 18 & 13 & 56 \\
\hline
$P$ & 57 & 18 & - & 8 & 48 \\
\hline
$T$ & 52 & 13 & 8 & - & 51 \\
\hline
$V$ & 18 & 56 & 48 & 51 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the total travelling time for the tour TPVBCT.
\item Find the total travelling time for David's tour using the nearest neighbour algorithm starting from $T$.
\item Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item By deleting $B$, find a lower bound for the total travelling time for the minimum tour.
\item Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
\end{enumerate}\item Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q4 [16]}}