| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Challenging +1.8 This is a non-standard dynamic programming problem requiring students to maximize the minimum stage length across a 4-stage route, which is conceptually more challenging than typical shortest/longest path problems. The table interpretation, state space design, and minimax optimization criterion make this substantially harder than routine D2 questions, though the computational steps remain manageable. |
| Spec | 7.05a Critical path analysis: activity on arc networks |
| Finishing point | ||||||||
| C | D | E | F | G | H | I | ||
| \multirow{3}{*}{Starting point} | A | 1 | 4.5 | 13 | 10 | 8 | 11 | 4 |
| B | 5 | 10.5 | ||||||
| C | 9 | 6 | ||||||
| D | 12 | 7 | 15 | |||||
| E | ||||||||
| F | 5 | |||||||
| G | 8 | |||||||
| H | 10 | |||||||
| I | ||||||||
| J | ||||||||
| K |
| Finishing point | |||||
| J | K | L | |||
| 2 | |||||
| 9 | 2 | 3 | |||
| 2 | 9 | ||||
| 5 | |||||
| 6 | |||||
| 10 |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | A | AB |
Question 4:
4 | A | AB
AC
AD
AEThis question should be answered on the sheet provided.
A rally consisting of four stages is being planned. The first stage will begin at A and the last stage will end at L. Various routes are being considered, with the end of one stage being the start of the next. The organisers want the shortest stage to be as long as possible. The table below shows the length, in miles, of each of the possible stages.
\begin{tabular}{c|cccc|cccc}
& & & Finishing point & & & & & \\
& & C & D & E & F & G & H & I \\
\hline
\multirow{3}{*}{Starting point} & A & 1 & 4.5 & 13 & 10 & 8 & 11 & 4 \\
& B & & & & & 5 & 10.5 & \\
& C & & & & & 9 & 6 & \\
& D & & & & & 12 & 7 & 15 \\
& E & & & & & & & \\
& F & & & & & & & 5 \\
& G & & & & & & & 8 \\
& H & & & & & & & 10 \\
& I & & & & & & & \\
& J & & & & & & & \\
& K & & & & & & & \\
\end{tabular}
\begin{tabular}{c|ccccc}
Finishing point & & & & & \\
J & K & L & & & \\
\hline
& & & & & \\
& & 2 & & & \\
9 & 2 & 3 & & & \\
2 & 9 & & & & \\
& & 5 & & & \\
& & 6 & & & \\
& & 10 & & & \\
\end{tabular}
Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route. [10 marks]
\hfill \mbox{\textit{Edexcel D2 Q4 [10]}}