| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Easy -1.2 This is a standard textbook application of two algorithmic procedures (nearest neighbour and deletion method for bounds) with straightforward table lookups and arithmetic. The question requires careful execution but no problem-solving insight or novel thinking—purely mechanical application of learned algorithms. |
| 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 | - | 16 | 25 | 21 | 12 | 15 |
| B | 16 | - | 24 | 22 | 21 | 12 |
| C | 25 | 24 | - | 18 | 30 | 27 |
| D | 21 | 22 | 18 | - | 15 | 12 |
| E | 12 | 21 | 30 | 15 | - | 18 |
| F | 15 | 12 | 27 | 12 | 18 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| (a) Distance from A to C: \(\frac{12 + 15 + 12 + 12 + 24 + 25}{100} = 100\) km | 1M1 1A1 2A1 | 1M1: NN. Each vertex visited at least once, accept 156324 across top of table (condone lack of return to start). 1A1: Route CAO must return to A. 2A1: Length CAO 100. Do not ISW if candidates then go on to double the route length. |
| (b) Delete A. RMST weight = \(12 + 12 + 15 + 18 = 57\) (km) | 1M1 | Finding correct RMST (maybe implicit) 57 sufficient; or 12, 12, 15 and 18. Must have 4 arcs. |
| Lower bound = \(57 + 12 + 15 = 84\) (km) | 2M1 2A1 4 Total 7 | b1M1: CAO; tree or list of arcs or 57 or 12 + 12 + 15 + 18 seen. b2M1: Adding 2 least arcs from A to 'tree'; 12 and 15 or AF and AE or 27 only. Must add these arcs distinctly. b2A1: CAO 84 |
| Answer/Working | Marks | Guidance |
|---|---|---|
| **(a)** Distance from A to C: $\frac{12 + 15 + 12 + 12 + 24 + 25}{100} = 100$ km | 1M1 1A1 2A1 | 1M1: NN. Each vertex visited at least once, accept 156324 across top of table (condone lack of return to start). 1A1: Route CAO must return to A. 2A1: Length CAO 100. Do not ISW if candidates then go on to double the route length. |
| **(b)** Delete A. RMST weight = $12 + 12 + 15 + 18 = 57$ (km) | 1M1 | Finding correct RMST (maybe implicit) 57 sufficient; or 12, 12, 15 and 18. Must have 4 arcs. |
| Lower bound = $57 + 12 + 15 = 84$ (km) | 2M1 2A1 4 **Total 7** | b1M1: CAO; tree or list of arcs or 57 or 12 + 12 + 15 + 18 seen. b2M1: Adding 2 least arcs from A to 'tree'; 12 and 15 or AF and AE or 27 only. Must add these arcs distinctly. b2A1: CAO 84 |
---2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 16 & 25 & 21 & 12 & 15 \\
\hline
B & 16 & - & 24 & 22 & 21 & 12 \\
\hline
C & 25 & 24 & - & 18 & 30 & 27 \\
\hline
D & 21 & 22 & 18 & - & 15 & 12 \\
\hline
E & 12 & 21 & 30 & 15 & - & 18 \\
\hline
F & 15 & 12 & 27 & 12 & 18 & - \\
\hline
\end{tabular}
\end{center}
Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.
\begin{enumerate}[label=(\alph*)]
\item Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
\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 2012 Q2 [7]}}