| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a straightforward application of the standard dynamic programming algorithm for shortest path problems, which is a core D2 topic. The network structure is clearly defined with four stages, requiring systematic backward/forward pass calculations but no problem-solving insight or tricky decision-making—purely algorithmic execution of a well-practiced technique. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03b Algorithm awareness: uses and practical limitations7.03c Working with algorithms: trace, interpret, adapt |
| \multirow{2}{*}{} | Finishing point | |||||||||||
| B | C | D | E | \(F\) | G | \(H\) | \(I\) | \(J\) | \(K\) | \(L\) | ||
| \multirow{11}{*}{Starting point} | A | 5 | 4.5 | 13 | 10 | |||||||
| B | 8 | 11 | 4 | |||||||||
| C | 5 | 10.5 | ||||||||||
| D | 9 | 6 | ||||||||||
| E | 12 | 7 | 15 | |||||||||
| \(F\) | 5 | 2 | 2 | |||||||||
| G | 8 | 9 | 3 | |||||||||
| \(H\) | 10 | 2 | 9 | |||||||||
| I | 5 | |||||||||||
| J | 6 | |||||||||||
| K | 10 | |||||||||||
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Stage 1: \(IL\to L=5^*\), \(JL\to L=6^*\), \(KL\to L=10^*\) | M1 | |
| Stage 2: \(FI\to I=5+5=10\), \(FJ\to J=2+6=8^*\), \(FK\to K=2+10=12\); \(GI=8+5=13^*\), \(GJ=9+6=15\), \(GK=3+10=13^*\); \(HI=10+5=15\), \(HJ=2+6=8^*\), \(HK=9+10=19\) | M1 A2 | |
| Stage 3: \(BF=8+8=16\), \(BG=11+13=24\), \(BH=4+8=12^*\); \(CF=5+8=13^*\), \(CH=10.5+8=18.5\); \(DF=9+8=17\), \(DH=6+8=14^*\); \(EF=12+8=20^*\), \(EG=7+13=20^*\), \(EH=15+8=23\) | M1 A2 | |
| Stage 4: \(AB=5+12=17^*\), \(AC=4.5+13=17.5\), \(AD=13+14=27\), \(AE=10+20=30\) | M1 A1 | |
| Giving route \(ABHJL\) | A1 | (10) |
# Question 4:
| Answer/Working | Mark | Guidance |
|---|---|---|
| Stage 1: $IL\to L=5^*$, $JL\to L=6^*$, $KL\to L=10^*$ | M1 | |
| Stage 2: $FI\to I=5+5=10$, $FJ\to J=2+6=8^*$, $FK\to K=2+10=12$; $GI=8+5=13^*$, $GJ=9+6=15$, $GK=3+10=13^*$; $HI=10+5=15$, $HJ=2+6=8^*$, $HK=9+10=19$ | M1 A2 | |
| Stage 3: $BF=8+8=16$, $BG=11+13=24$, $BH=4+8=12^*$; $CF=5+8=13^*$, $CH=10.5+8=18.5$; $DF=9+8=17$, $DH=6+8=14^*$; $EF=12+8=20^*$, $EG=7+13=20^*$, $EH=15+8=23$ | M1 A2 | |
| Stage 4: $AB=5+12=17^*$, $AC=4.5+13=17.5$, $AD=13+14=27$, $AE=10+20=30$ | M1 A1 | |
| Giving route $ABHJL$ | A1 | **(10)** |
---4. 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 total length of the route chosen to be as small as possible. The table below shows the length, in miles, of each of the possible stages.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{11}{|c|}{Finishing point} \\
\hline
& & B & C & D & E & $F$ & G & $H$ & $I$ & $J$ & $K$ & $L$ \\
\hline
\multirow{11}{*}{Starting point} & A & 5 & 4.5 & 13 & 10 & & & & & & & \\
\hline
& B & & & & & 8 & 11 & 4 & & & & \\
\hline
& C & & & & & 5 & & 10.5 & & & & \\
\hline
& D & & & & & 9 & & 6 & & & & \\
\hline
& E & & & & & 12 & 7 & 15 & & & & \\
\hline
& $F$ & & & & & & & & 5 & 2 & 2 & \\
\hline
& G & & & & & & & & 8 & 9 & 3 & \\
\hline
& $H$ & & & & & & & & 10 & 2 & 9 & \\
\hline
& I & & & & & & & & & & & 5 \\
\hline
& J & & & & & & & & & & & 6 \\
\hline
& K & & & & & & & & & & & 10 \\
\hline
\end{tabular}
\end{center}
Use dynamic programming to find the route which satisfies the wish of the organisers.
\hfill \mbox{\textit{OCR D2 Q4 [10]}}