| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.3 This is a standard minimax route problem using dynamic programming with a clear network diagram and systematic table-filling approach. While it requires understanding the minimax criterion (minimizing the maximum edge) rather than shortest path, this is a routine D2 topic with straightforward application of the algorithm. The two-part structure and need to adapt when a tunnel is blocked adds minor complexity but remains procedural. |
| Spec | 7.05a Critical path analysis: activity on arc networks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage 1: \(JY=98^*\), \(KY=94^*\), \(LY=86^*\) | B1 | |
| Stage 2: \(GJ: \max(79,98)=98^*\); \(GK: \max(98,94)=98^*\); \(HK: \max(95,94)=95\); \(HL: \max(72,86)=86^*\); \(IL: \max(56,86)=86^*\) | A1A1 | |
| Stage 3: \(CG: \max(50,98)=98^*\); \(DG: \max(92,98)=98\); \(DH: \max(81,86)=86^*\); \(EH: \max(89,86)=89^*\); \(FH: \max(84,86)=86^*\); \(FI: \max(72,86)=86^*\) | M1, A1A1ft | |
| Stage 4: \(AC: \max(95,98)=98\); \(AD: \max(86,86)=86^*\); \(AE: \max(63,89)=89\); \(BE: \max(88,89)=89\); \(BF: \max(87,86)=87^*\) | M1, A1ft | |
| Stage 5: \(XA: \max(55,86)=86^*\); \(XB: \max(85,87)=87\) | A1ft | |
| Route: \(X\ A\ D\ H\ L\ Y\) (minimax \(= 86\)) | M1A1ft | 12 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(X\ B\ F \underset{I}{\overset{H}{\gtrless}} L\ Y\) (minimax \(= 87\)) | M1A1 | one, 2 |
# Question 7:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage 1: $JY=98^*$, $KY=94^*$, $LY=86^*$ | B1 | |
| Stage 2: $GJ: \max(79,98)=98^*$; $GK: \max(98,94)=98^*$; $HK: \max(95,94)=95$; $HL: \max(72,86)=86^*$; $IL: \max(56,86)=86^*$ | A1A1 | |
| Stage 3: $CG: \max(50,98)=98^*$; $DG: \max(92,98)=98$; $DH: \max(81,86)=86^*$; $EH: \max(89,86)=89^*$; $FH: \max(84,86)=86^*$; $FI: \max(72,86)=86^*$ | M1, A1A1ft | |
| Stage 4: $AC: \max(95,98)=98$; $AD: \max(86,86)=86^*$; $AE: \max(63,89)=89$; $BE: \max(88,89)=89$; $BF: \max(87,86)=87^*$ | M1, A1ft | |
| Stage 5: $XA: \max(55,86)=86^*$; $XB: \max(85,87)=87$ | A1ft | |
| Route: $X\ A\ D\ H\ L\ Y$ (minimax $= 86$) | M1A1ft | 12 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $X\ B\ F \underset{I}{\overset{H}{\gtrless}} L\ Y$ (minimax $= 87$) | M1A1 | one, 2 |
---7.\\
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121}
Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, $A , B , C , D , E , F , G , H , I , J , K$ and $L$, at which there are air pockets where he can take a breath.
The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next.
Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.
\begin{enumerate}[label=(\alph*)]
\item Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie.
Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
\item Find an optimal route for Agent Goodie avoiding tunnel XA.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q7 [14]}}