| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2015 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST with Parameter Constraint |
| Difficulty | Standard +0.8 This is a multi-part TSP question requiring Prim's algorithm, nearest neighbour heuristic, and lower bound calculation with a parameter constraint. While the individual algorithms are standard D2 content, part (e) requires students to work backwards from a given lower bound to find x, which demands understanding of how deletion lower bounds work and involves algebraic reasoning beyond routine application. The question has 6 parts with substantial working required, making it moderately challenging for Further Maths D2 level. |
| 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 | G | |
| A | - | \(x\) | 41 | 43 | 38 | 21 | 30 |
| B | \(x\) | - | 27 | 38 | 19 | 29 | 51 |
| C | 41 | 27 | - | 24 | 37 | 35 | 40 |
| D | 43 | 38 | 24 | - | 44 | 52 | 25 |
| E | 38 | 19 | 37 | 44 | - | 20 | 28 |
| F | 21 | 29 | 35 | 52 | 20 | - | 49 |
| G | 30 | 51 | 40 | 25 | 28 | 49 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Prim's: AF, EF, BE, BC, CD, DG | M1, A1 | Must use Prim's not NNA; if any arc creates a cycle then M0; order of arc selection clear |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(2 \times 136 = 272\) (km) | B1 | CAO (272) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| A – F – E – B – C – D – G – A: \(21+20+19+27+24+25+30 = 166\) (km) | B1, B1 | Must be in terms of nodes or arcs (not weights); CAO (166) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Starting at F, route length is \(153 + x\) | B1 | Either \(153+x\) or states a value in interval \(174 < \text{value} < 180\) |
| With \(x > 21\), \(153 + x\) is greater than 166 so the better upper bound is the one starting at A | DB1 | Correct argument that A gives better upper bound; dependent on previous B mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Length of RMST \(= 115\) | B1 | CAO – must be either explicitly stated or seen in working |
| \(115 + 21 + x = 159 \therefore x = 23\) (km) | M1, A1 | Adding the correct two least values (21 and \(x\)) to their RMST length and equating to 159; CAO (\(x=23\) clearly identified) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(159 \leq \text{optimal} \leq 166\) [accept \(159 < \text{optimal} \leq 166\)] | B2, 1, 0 | Any indication of interval containing 159 (lower bound) and their better upper bound from (d); CAO |
# Question 3:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Prim's: AF, EF, BE, BC, CD, DG | M1, A1 | Must use Prim's not NNA; if any arc creates a cycle then M0; order of arc selection clear |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $2 \times 136 = 272$ (km) | B1 | CAO (272) |
## Part (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| A – F – E – B – C – D – G – A: $21+20+19+27+24+25+30 = 166$ (km) | B1, B1 | Must be in terms of nodes or arcs (not weights); CAO (166) |
## Part (d)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Starting at F, route length is $153 + x$ | B1 | Either $153+x$ **or** states a value in interval $174 < \text{value} < 180$ |
| With $x > 21$, $153 + x$ is greater than 166 so the better upper bound is the one starting at A | DB1 | Correct argument that A gives better upper bound; dependent on previous B mark |
## Part (e)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Length of RMST $= 115$ | B1 | CAO – must be either explicitly stated or seen in working |
| $115 + 21 + x = 159 \therefore x = 23$ (km) | M1, A1 | Adding the **correct** two least values (21 and $x$) to their RMST length and equating to 159; CAO ($x=23$ clearly identified) |
## Part (f)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $159 \leq \text{optimal} \leq 166$ [accept $159 < \text{optimal} \leq 166$] | B2, 1, 0 | Any indication of interval containing 159 (lower bound) and their better upper bound from (d); CAO |
---3.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & $x$ & 41 & 43 & 38 & 21 & 30 \\
\hline
B & $x$ & - & 27 & 38 & 19 & 29 & 51 \\
\hline
C & 41 & 27 & - & 24 & 37 & 35 & 40 \\
\hline
D & 43 & 38 & 24 & - & 44 & 52 & 25 \\
\hline
E & 38 & 19 & 37 & 44 & - & 20 & 28 \\
\hline
F & 21 & 29 & 35 & 52 & 20 & - & 49 \\
\hline
G & 30 & 51 & 40 & 25 & 28 & 49 & - \\
\hline
\end{tabular}
\end{center}
The network represented by the table shows the least distances, in km, between seven theatres, A, $\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G .
Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is $x \mathrm {~km}$, where $21 < x < 27$
\begin{enumerate}[label=(\alph*)]
\item Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You should list the arcs in the order in which you consider them.
\item Use your answer to (a) to determine an initial upper bound for the length of Jasmine's route.
\item Use the nearest neighbour algorithm, starting at A , to find a second upper bound for the length of the route.
The nearest neighbour algorithm starting at F gives a route of $\mathrm { F } - \mathrm { E } - \mathrm { B } - \mathrm { A } - \mathrm { G } - \mathrm { D } - \mathrm { C } - \mathrm { F }$.
\item State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer.
Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.
\item Find $x$, making your method clear.
\item Write down the smallest interval that you can be confident contains the optimal length of Jasmine's route. Give your answer as an inequality.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2015 Q3 [12]}}