| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Multiple Nearest Neighbour Routes |
| Difficulty | Moderate -0.3 This is a standard algorithmic question from D2 requiring application of well-defined procedures (Prim's algorithm, nearest neighbour heuristic, lower bound calculation). While it involves multiple parts and careful bookkeeping with a 6-city table, each step follows a mechanical algorithm with no novel problem-solving or proof required. Slightly easier than average A-level due to its procedural nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| A | B | C | D | E | F | |
| A | - | 36 | 18 | 28 | 24 | 22 |
| B | 36 | - | 54 | 22 | 20 | 27 |
| C | 18 | 54 | - | 42 | 27 | 24 |
| D | 28 | 22 | 42 | - | 20 | 30 |
| E | 24 | 20 | 27 | 20 | - | 13 |
| F | 22 | 27 | 24 | 30 | 13 | - |
| Answer | Marks |
|---|---|
| Spanning tree found. Allow \(1 \times 2 \times 43\) across top of table or 93 | M1 |
| CAO must see tree or list of arcs | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| 186 | B1ft | ft \(93 \times 2\) |
| Answer | Marks |
|---|---|
| One Nearest Neighbour, each vertex visited at least once (condone lack of return to start) | M1 |
| One correct route and length CAO – must return to start | A1 |
| Second correct route and length CAO – must return to start | A1 |
| Answer | Marks |
|---|---|
| ft but only on three different values | B1ft |
| Answer | Marks |
|---|---|
| Finding correct RMST (maybe implicit) 77 sufficient, or correct numbers, 4 arcs | M1 |
| CAO tree or 77 | A1 |
| Adding 2 least arcs to A, 18 and 22 or 40 only | M1 |
| CAO 117 | A1 |
# Question 1:
## Part (a)
Spanning tree found. Allow $1 \times 2 \times 43$ across top of table or 93 | M1 |
CAO must see tree or list of arcs | A1 |
## Part (b)
186 | B1ft | ft $93 \times 2$
## Part (c)
One Nearest Neighbour, each vertex visited at least once (condone lack of return to start) | M1 |
One correct route and length CAO – must return to start | A1 |
Second correct route and length CAO – must return to start | A1 |
## Part (d)
ft but only on three different values | B1ft |
## Part (e)
Finding correct RMST (maybe implicit) 77 sufficient, or correct numbers, 4 arcs | M1 |
CAO tree or 77 | A1 |
Adding 2 least arcs to A, 18 and 22 or 40 only | M1 |
CAO 117 | A1 |
---\begin{enumerate}
\item The table below shows the least costs, in pounds, of travelling between six cities, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F .
\end{enumerate}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F \\
\hline
A & - & 36 & 18 & 28 & 24 & 22 \\
\hline
B & 36 & - & 54 & 22 & 20 & 27 \\
\hline
C & 18 & 54 & - & 42 & 27 & 24 \\
\hline
D & 28 & 22 & 42 & - & 20 & 30 \\
\hline
E & 24 & 20 & 27 & 20 & - & 13 \\
\hline
F & 22 & 27 & 24 & 30 & 13 & - \\
\hline
\end{tabular}
\end{center}
Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.\\
(a) Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.\\
(2)\\
(b) Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.\\
(1)\\
(c) Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.\\
(d) State the best upper bound from your answers to (b) and (c).\\
(e) Starting by deleting A , and all of its arcs, find a lower bound for the route length.\\
\hfill \mbox{\textit{Edexcel D2 2010 Q1 [11]}}