| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Session | Specimen |
| 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 application of the maximin algorithm to a network, requiring systematic table completion following a well-defined procedure. While it involves multiple steps, the method is algorithmic with no conceptual difficulty or novel problem-solving required, making it slightly easier than average for A-level. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| Stage 1: \(H \to HK = 18^*\); \(I \to IK = 19^*\); \(J \to JK = 21^*\) | M1 A1 | |
| Stage 2, State \(F\): \(FH = \min(16,18)=16\); \(FI = \min(23,19)=19^*\); \(FJ = \min(17,21)=17\) | M1 A1 A1 | |
| Stage 2, State \(G\): \(GH = \min(20,18)=18\); \(GI = \min(15,19)=15\); \(GJ = \min(28,21)=21^*\) | A1 | |
| Stage 3, State \(B\): \(BG = \min(18,21)=18^*\); State \(C\): \(CF = \min(25,19)=19^*\); \(CG = \min(16,21)=16\) | M1 A1 ft | |
| State \(D\): \(DF = \min(22,19)=19^*\); \(DG = \min(19,21)=19^*\); State \(E\): \(EF = \min(14,19)=14^*\) | ||
| Stage 4, State \(A\): \(AB = \min(24,18)=18\); \(AC = \min(25,19)=19^*\); \(AD = \min(27,19)=19^*\); \(AE = \min(23,14)=14\) | A1 ft | |
| Routes \(ACFIK\), or \(ADFIK\), or \(ADGJK\) | A1 ft |
# Question 6:
| Answer/Working | Marks | Notes |
|---|---|---|
| Stage 1: $H \to HK = 18^*$; $I \to IK = 19^*$; $J \to JK = 21^*$ | M1 A1 | |
| Stage 2, State $F$: $FH = \min(16,18)=16$; $FI = \min(23,19)=19^*$; $FJ = \min(17,21)=17$ | M1 A1 A1 | |
| Stage 2, State $G$: $GH = \min(20,18)=18$; $GI = \min(15,19)=15$; $GJ = \min(28,21)=21^*$ | A1 | |
| Stage 3, State $B$: $BG = \min(18,21)=18^*$; State $C$: $CF = \min(25,19)=19^*$; $CG = \min(16,21)=16$ | M1 A1 ft | |
| State $D$: $DF = \min(22,19)=19^*$; $DG = \min(19,21)=19^*$; State $E$: $EF = \min(14,19)=14^*$ | | |
| Stage 4, State $A$: $AB = \min(24,18)=18$; $AC = \min(25,19)=19^*$; $AD = \min(27,19)=19^*$; $AE = \min(23,14)=14$ | A1 ft | |
| Routes $ACFIK$, or $ADFIK$, or $ADGJK$ | A1 ft | |
**Total: 9 marks**
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{899a26d1-7599-4051-b1cf-596542624997-6_705_1424_1034_338}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
A maximin route is to be found through the network shown in Figure 3.\\
Complete the table in the answer book, and hence find a maximin route.\\
\hfill \mbox{\textit{Edexcel D2 Q6 [9]}}