| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | March |
| Marks | 12 |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Standard +0.3 This is a standard travelling salesman problem (TSP) question using textbook algorithms (nearest neighbour, lower bound via MST). Part (i) is trivial path-reading, parts (ii)-(iv) apply routine algorithms with minimal problem-solving, and part (v) involves straightforward arithmetic to find an unknown edge length. While it requires multiple steps, all techniques are standard Further Maths Discrete content with no novel insight required. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| D | A | B | F | G | |
| D | - | ||||
| A | - | 70 | |||
| B | - | 84 | |||
| F | 84 | - | |||
| G | 70 | - |
| Answer | Marks | Guidance |
|---|---|---|
| ADEG | B1 | AD, DE, EG |
| Answer | Marks | Guidance |
|---|---|---|
| Distance table with D, A, B, F, G rows/columns completed with values 42, 40, 44, 28 in row A; 42, 32, 56, 70 in row B; 40, 32, 34, 50 in row F; 44, 56, 34, 40 in row G | M1, A1 | Any four of 42, 40, 44, 28, 32, 56, 50, 40 correctly placed, at least once; All sixteen cells completed correctly |
| Answer | Marks | Guidance |
|---|---|---|
| DGFABD. 196 (km) | M1, A1 | Nearest neighbor at least to DGFA; 196 |
| Answer | Marks | Guidance |
|---|---|---|
| AB, BG, GF = 122; DG, DB = 68. 190 (km) | M1, A1 | Tree on \(\{A, B, F, G\}\); 2 arcs from D; 190 |
| Answer | Marks | Guidance |
|---|---|---|
| \(190 \leq \text{distance} \leq 196\) | B1 ft | Lower bound their 190 from (iii), upper bound their 196 from (ii), with their 190 no greater than their 196. |
| Answer | Marks | Guidance |
|---|---|---|
| DFGBAD. DF = 8 (km) | M1, A1 | DF + 122 + 42 or implied; 8 |
| Answer | Marks | Guidance |
|---|---|---|
| DFDGBAD. 2DF = 172 - 152 = 20. DF = 10 km | M1, A1 | 2DF + 28 + 82 + 42 or implied; 10 |
## (i)
| ADEG | B1 | AD, DE, EG |
## (ii)(a)
| Distance table with D, A, B, F, G rows/columns completed with values 42, 40, 44, 28 in row A; 42, 32, 56, 70 in row B; 40, 32, 34, 50 in row F; 44, 56, 34, 40 in row G | M1, A1 | Any four of 42, 40, 44, 28, 32, 56, 50, 40 correctly placed, at least once; All sixteen cells completed correctly |
## (ii)(b)
| DGFABD. 196 (km) | M1, A1 | Nearest neighbor at least to DGFA; 196 |
## (iii)
| AB, BG, GF = 122; DG, DB = 68. 190 (km) | M1, A1 | Tree on $\{A, B, F, G\}$; 2 arcs from D; 190 |
## (iv)
| $190 \leq \text{distance} \leq 196$ | B1 ft | Lower bound their 190 from (iii), upper bound their 196 from (ii), with their 190 no greater than their 196. |
## (v)(a)
| DFGBAD. DF = 8 (km) | M1, A1 | DF + 122 + 42 or implied; 8 |
## (v)(b)
| DFDGBAD. 2DF = 172 - 152 = 20. DF = 10 km | M1, A1 | 2DF + 28 + 82 + 42 or implied; 10 |
---The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them.
\includegraphics{figure_3}
A delivery driver needs to start from his depot at D, make deliveries at each of A, B, F and G, and finish at D.
\begin{enumerate}[label=(\roman*)]
\item Write down a route from A to G of length 70 km. [1]
\end{enumerate}
The table shows the length of the shortest path between some pairs of places.
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& D & A & B & F & G \\
\hline
D & - & & & & \\
\hline
A & & - & & & 70 \\
\hline
B & & & - & 84 & \\
\hline
F & & & 84 & - & \\
\hline
G & & 70 & & & - \\
\hline
\end{tabular}
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item \begin{enumerate}[label=(\alph*)]
\item Complete the table.
\item Use the nearest neighbour method on the table, starting at D, to find the length of a cycle through D, A, B, F and G, ignoring possibly repeating E and C. [4]
\end{enumerate}
\item By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel. [2]
\item What can you conclude from your previous answers about the distance that the driver must travel? [1]
\end{enumerate}
A new road is constructed between D and F. Using this road the driver starts from D, makes the deliveries and returns to D having travelled just 172 km.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{4}
\item Find the length of the new road if
\begin{enumerate}[label=(\alph*)]
\item the driver does not return to D until all the deliveries have been made,
\item the driver uses the new road twice in making the deliveries. [4]
\end{enumerate}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q5 [12]}}