| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Standard +0.3 This is a standard textbook dynamic programming question with a straightforward maximin objective. Students follow a prescribed algorithmic procedure (working backwards, filling a table) with no novel problem-solving required. The maximin criterion is slightly less common than shortest path, but the mechanical application of the algorithm makes this easier than average. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities7.05c Total float: calculation and interpretation7.05d Latest start and earliest finish: independent and interfering float7.05e Cascade charts: scheduling and effect of delays |
| Stage | State | From | Value |
| 1 | H | \(K\) | |
| I | \(K\) | ||
| J | K | ||
| 2 | |||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Stage 1: \(H \to K = 18\), \(I \to K = 15\), \(J \to K = 12\) | B1 | All three values correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(E\): \(\min(11, 17) \to \max(\min(11,18), \min(17,15)) = \max(11,15) = 15\), from \(I\) | M1 | Correct method for maximising minimum |
| \(F\): \(\max(\min(13,18), \min(15,15), \min(14,15)) = \max(13,15,14) = 15\), from \(I\) | A1 | |
| \(G\): \(\max(\min(16,15), \min(14,15), \min(20,12)) = \max(15,14,12) = 15\), from \(F\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B\): \(\max(\min(11,15)) = 11\), from \(E\) | M1 | Correct method applied |
| \(C\): \(\max(\min(13,15), \min(12,15), \min(13,15)) = \max(13,12,13) = 13\), from \(B\) or \(F\) | A1 | |
| \(D\): \(\max(\min(15,15), \min(16,15)) = \max(15,15) = 15\), from \(F\) or \(G\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A\): \(\max(\min(12,11), \min(15,13), \min(13,15)) = \max(11,13,13) = 13\), from \(C\) or \(D\) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Optimal route: \(A \to C \to F \to I \to K\) or \(A \to D \to F \to I \to K\), value = 13 | B1 | Accept either valid route with correct value |
# Question 4:
## Stage 1 (working backwards from K)
| Answer | Mark | Guidance |
|--------|------|----------|
| Stage 1: $H \to K = 18$, $I \to K = 15$, $J \to K = 12$ | B1 | All three values correct |
## Stage 2
| Answer | Mark | Guidance |
|--------|------|----------|
| $E$: $\min(11, 17) \to \max(\min(11,18), \min(17,15)) = \max(11,15) = 15$, from $I$ | M1 | Correct method for maximising minimum |
| $F$: $\max(\min(13,18), \min(15,15), \min(14,15)) = \max(13,15,14) = 15$, from $I$ | A1 | |
| $G$: $\max(\min(16,15), \min(14,15), \min(20,12)) = \max(15,14,12) = 15$, from $F$ | A1 | |
## Stage 3
| Answer | Mark | Guidance |
|--------|------|----------|
| $B$: $\max(\min(11,15)) = 11$, from $E$ | M1 | Correct method applied |
| $C$: $\max(\min(13,15), \min(12,15), \min(13,15)) = \max(13,12,13) = 13$, from $B$ or $F$ | A1 | |
| $D$: $\max(\min(15,15), \min(16,15)) = \max(15,15) = 15$, from $F$ or $G$ | A1 | |
## Stage 4 (from A)
| Answer | Mark | Guidance |
|--------|------|----------|
| $A$: $\max(\min(12,11), \min(15,13), \min(13,15)) = \max(11,13,13) = 13$, from $C$ or $D$ | M1 A1 | |
## Optimal Route
| Answer | Mark | Guidance |
|--------|------|----------|
| Optimal route: $A \to C \to F \to I \to K$ or $A \to D \to F \to I \to K$, value = 13 | B1 | Accept either valid route with correct value |4 A haulage company, based in town $A$, is to deliver a tall statue to town $K$. The statue is being delivered on the back of a lorry.
The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road.
The company wants to ensure that the height of the lowest bridge along the route from $A$ to $K$ is maximised.\\
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221}
Working backwards from $\boldsymbol { K }$, use dynamic programming to find the optimal route when driving from $A$ to $K$.
You must complete the table opposite as your solution.
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Stage & State & From & Value \\
\hline
1 & H & $K$ & \\
\hline
& I & $K$ & \\
\hline
& J & K & \\
\hline
2 & & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
\end{tabular}
\end{center}
Optimal route is
\hfill \mbox{\textit{AQA D2 2013 Q4 [9]}}