| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.3 This is a standard textbook application of dynamic programming with a minimax objective. The question provides a clear network diagram and explicitly tells students to use dynamic programming. The algorithm is straightforward: work backwards from L, recording the minimum of the maximum waiting times for each path. While it requires systematic working through multiple stages, it involves no novel insight—just careful application of a taught algorithm with about 3-4 stages of computation. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage 4 (\(I,J,K \to L\)): \(I\): 19, \(J\): 18, \(K\): 26 | B1 | |
| Stage 3 (\(E,F,G,H\)): minimax calculations from each node | M1 | |
| \(E\): \(\min(21+19, 29+18, 35+26)=\min(40,47,61)\)... correct values | A1 | |
| Stage 2 (\(B,C,D\)): correct minimax values | M1A1 | |
| Stage 1 (\(A\)): correct minimax values | M1A1 | |
| Optimal route identified with maximum waiting time stated | A1 | cao |
# Question 3:
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage 4 ($I,J,K \to L$): $I$: 19, $J$: 18, $K$: 26 | B1 | |
| Stage 3 ($E,F,G,H$): minimax calculations from each node | M1 | |
| $E$: $\min(21+19, 29+18, 35+26)=\min(40,47,61)$... correct values | A1 | |
| Stage 2 ($B,C,D$): correct minimax values | M1A1 | |
| Stage 1 ($A$): correct minimax values | M1A1 | |
| Optimal route identified with maximum waiting time stated | A1 | cao |
---3. This question should be answered on the sheet provided.
Arthur is planning a bus journey from town $A$ to town $L$. There are various routes he can take but he will have to change buses three times - at $B , C$ or $D$, at $E , F , G$ or $H$ and at $I , J$ or $K$.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e892e87c-1c2d-4f97-ac23-41e38663d0f0-03_764_1410_477_315}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the maximum waiting time at any one stop is as small as possible.
Use dynamic programming to find the route that Arthur should use.\\
(9 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q3 [9]}}