| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2021 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.8 This is a minimax dynamic programming problem requiring systematic tabulation through a 4-stage network. While the algorithm is standard for Further Maths D2, it requires careful bookkeeping across multiple stages, understanding of the minimax objective (minimizing the maximum daily distance rather than total distance), and working backwards through the network. The execution is methodical but time-consuming with multiple nodes per stage, making it moderately challenging within the Further Maths context. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimax | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| HT: 47*, IT: 48*, JT: 49* | B1 | Stage 1 correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Stage 2 completed with 4 states, at least 9 rows | M1 | Bod if something in each cell |
| D: \(\max(49,47)=49^*\), \(\max(50,48)=50\); E: \(\max(51,47)=51\), \(\max(46,49)=49^*\); F: \(\max(51,47)=51\), \(\max(52,48)=52\), \(\max(50,49)=50^*\); G: \(\max(53,48)=53\), \(\max(51,49)=51^*\) | A1 | Any two states in Stage 2 correct |
| All four states correct (no extra rows) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Stage 3 completed with 3 states, at least 8 rows | M1 | Bod if something in each cell |
| A: \(\max(53,49)=53\), \(\max(52,49)=52^*\), \(\max(53,50)=53\); B: \(\max(51,49)=51\), \(\max(50,50)=50^*\), \(\max(46,51)=51\); C: \(\max(50,49)=50^*\), \(\max(47,51)=51\) | A1ft | cao any 2 states correct in Stage 3 on follow through |
| All 3 states correct (no extra rows) | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Stage 4 completed with 1 state, at least 3 rows | M1 | Bod if something in each cell |
| S: \(\max(52,52)=52\), \(\max(48,50)=50^*\), \(\max(50,50)=50^*\) | A1ft | cao for Stage 4 following through their * values (no extra rows) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Route 1: \(S-B-F-J-T\) | B1ft | One correct route following through least values at each stage |
| Route 2: \(S-C-E-J-T\) | B1 | Both routes correct |
# Question 6:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimax | B1 | cao |
## Part (b):
**Stage 1:**
| Answer | Mark | Guidance |
|--------|------|----------|
| HT: 47*, IT: 48*, JT: 49* | B1 | Stage 1 correct |
**Stage 2:**
| Answer | Mark | Guidance |
|--------|------|----------|
| Stage 2 completed with 4 states, at least 9 rows | M1 | Bod if something in each cell |
| D: $\max(49,47)=49^*$, $\max(50,48)=50$; E: $\max(51,47)=51$, $\max(46,49)=49^*$; F: $\max(51,47)=51$, $\max(52,48)=52$, $\max(50,49)=50^*$; G: $\max(53,48)=53$, $\max(51,49)=51^*$ | A1 | Any two states in Stage 2 correct |
| All four states correct (no extra rows) | A1 | cao |
**Stage 3:**
| Answer | Mark | Guidance |
|--------|------|----------|
| Stage 3 completed with 3 states, at least 8 rows | M1 | Bod if something in each cell |
| A: $\max(53,49)=53$, $\max(52,49)=52^*$, $\max(53,50)=53$; B: $\max(51,49)=51$, $\max(50,50)=50^*$, $\max(46,51)=51$; C: $\max(50,49)=50^*$, $\max(47,51)=51$ | A1ft | cao any 2 states correct in Stage 3 on follow through |
| All 3 states correct (no extra rows) | A1 | cao |
**Stage 4:**
| Answer | Mark | Guidance |
|--------|------|----------|
| Stage 4 completed with 1 state, at least 3 rows | M1 | Bod if something in each cell |
| S: $\max(52,52)=52$, $\max(48,50)=50^*$, $\max(50,50)=50^*$ | A1ft | cao for Stage 4 following through their * values (no extra rows) |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Route 1: $S-B-F-J-T$ | B1ft | One correct route following through least values at each stage |
| Route 2: $S-C-E-J-T$ | B1 | Both routes correct |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{262aa0e6-479f-447a-94db-aeb901b3c6fe-7_782_1426_219_322}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, $S , A , B , C , D , E , F , G , H , I , J$ and $T$. The number on each arc shows the distance between these towns, in miles.
Bradley is planning a four-day cycle ride from $S$ to $T$.\\
He plans to leave his home at $S$. On the first night he will stay at $A , B$ or $C$, on the second night he will stay at $D , E , F$ or $G$, on the third night he will stay at $H , I$ or $J$, and he will arrive at his friend's house at $T$ on the fourth day.
Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.
\begin{enumerate}[label=(\alph*)]
\item Write down the type of dynamic programming problem that Bradley needs to solve.
\item Use dynamic programming to complete the table in the answer book.
\item Hence write down the possible routes that Bradley could take.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2021 Q6 [12]}}