| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a standard textbook application of the nearest neighbour algorithm and lower bound calculation using minimum spanning tree. The question provides a clear network diagram and asks for routine algorithmic procedures with no novel problem-solving required. While it involves multiple steps, each step follows a well-practiced algorithm taught directly in D2 courses. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(AB = 19\) (via \(C\): \(11+8\)) | B1 | |
| \(AD = 23\), \(AF = 40\) (via \(E\): \(22+17+...\), check routes) | B1 | |
| Remaining correct entries in table | B1 | All correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A \to C\) (nearest unvisited, distance 11) | M1 | Correct application of algorithm |
| \(C \to B\) (8), \(B \to E\) (via...), continuing to visit all nodes | A1 | Correct route followed through |
| Route: \(A\)–\(C\)–\(B\)–\(E\)–\(F\)–\(D\)–\(A\), total = \(11+8+20+17+31+23 = 110\) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Residual network without \(A\) and its arcs | M1 | Correct deletion |
| Find minimum spanning tree of remaining nodes \(B, C, D, E, F\) | M1 | Correct method (e.g. Kruskal/Prim) |
| MST: \(BC=8\), \(CE=9\), \(EF=17\), \(DE=27\)... selecting minimum edges | A1 | Correct MST |
| Add two shortest arcs at \(A\): \(AC=11\), \(AD=23\) | M1 | |
| Lower bound = MST total \(+ 11 + 23\) | A1 | cao |
# Question 1:
## Part (a) – Table of least distances
| Answer | Marks | Guidance |
|--------|-------|----------|
| $AB = 19$ (via $C$: $11+8$) | B1 | |
| $AD = 23$, $AF = 40$ (via $E$: $22+17+...$, check routes) | B1 | |
| Remaining correct entries in table | B1 | All correct |
**Key distances:**
- $AB = 19$ ($A$–$C$–$B$)
- $AC = 11$
- $AD = 23$
- $AE = 22$
- $AF = 39$ ($A$–$E$–$F$: $22+17$)
- $BC = 8$, $BD = 32$ (via $E$: $8+9+...$), $BF = 32+17$...
- Complete table required
## Part (b) – Nearest Neighbour from A
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A \to C$ (nearest unvisited, distance 11) | M1 | Correct application of algorithm |
| $C \to B$ (8), $B \to E$ (via...), continuing to visit all nodes | A1 | Correct route followed through |
| Route: $A$–$C$–$B$–$E$–$F$–$D$–$A$, total = $11+8+20+17+31+23 = 110$ | A1 | cao |
## Part (c) – Lower bound (delete A)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Residual network without $A$ and its arcs | M1 | Correct deletion |
| Find minimum spanning tree of remaining nodes $B, C, D, E, F$ | M1 | Correct method (e.g. Kruskal/Prim) |
| MST: $BC=8$, $CE=9$, $EF=17$, $DE=27$... selecting minimum edges | A1 | Correct MST |
| Add two shortest arcs at $A$: $AC=11$, $AD=23$ | M1 | |
| Lower bound = MST total $+ 11 + 23$ | A1 | cao |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d28d78c1-052d-4350-a7e3-284380e3bbab-2_703_958_351_552}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.
\begin{enumerate}[label=(\alph*)]
\item By inspection, complete the two copies of the table of least distances in your answer book.
\item Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou's route. Write down the route which gives this upper bound.
\item Starting by deleting A, and all of its arcs, find a lower bound for the route length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2011 Q1 [10]}}