| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a standard textbook dynamic programming question requiring mechanical application of the backward recursion algorithm to find shortest paths. The tabulation method is prescribed, the network is small and straightforward, and no problem-solving insight is needed—just systematic calculation following the standard D2 algorithm. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| Stage | State | Action |
| 1 | 0 | 0 |
| 1 | 0 | 4 |
| 2 | 0 | 0 |
| 1 | \(4+4 = 8\) | 8 |
| 1 | 0 | \(6+3 = 9\) |
| 1 | \(7+4 = 11\) | |
| 3 | 0 | 0 |
| 1 | \(3+9 = 12\) | 12 |
| Shortest route: \((3; 0) – (2; 1) – (1; 0) – (0; 0)\); Length of shortest route \(= 12\) km | B1 | For this route (not in reverse) |
| B1 | For 12 |
| Stage | State | Action | Cost | Minimum |
|-------|-------|--------|------|---------|
| 1 | 0 | 0 | 3 | 3 |
| | 1 | 0 | 4 | 4 |
| 2 | 0 | 0 | $0+3 = 9$ | M1 | For completing cost column for stage 2
| | | 1 | $4+4 = 8$ | 8 | A1 | For completing cost column for stage 3
| | 1 | 0 | $6+3 = 9$ | 9 | M1 | For completing minimum column for stage 2
| | | 1 | $7+4 = 11$ | | A1 | For completing minimum column for stage 3
| 3 | 0 | 0 | $5+8 = 13$ | |
| | | 1 | $3+9 = 12$ | 12 |
Shortest route: $(3; 0) – (2; 1) – (1; 0) – (0; 0)$; Length of shortest route $= 12$ km | B1 | For this route (not in reverse)
| B1 | For 12
---2 Answer this question on the insert provided.
The diagram shows a directed network of paths with vertices labelled with (stage; state) labels. The weights on the arcs represent distances in km . The shortest route from $( 3 ; 0 )$ to $( 0 ; 0 )$ is required.
Complete the dynamic programming tabulation on the insert, working backwards from stage 1 , to find the shortest route through the network. Give the length of this shortest route.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-2_501_1018_1741_575}
\captionsetup{labelformat=empty}
\caption{Stage 3 Stage 2 Stage 1}
\end{center}
\end{figure}
\hfill \mbox{\textit{OCR D2 2006 Q2 [6]}}