Moderate -0.3 This is a straightforward application of dynamic programming to find the shortest path through a staged network with three intermediate stages. The problem is well-structured with clear stages (B/C/D, E/F/G/H, I/J/K) and requires only systematic backward induction—a standard algorithmic procedure taught in D2. While it requires careful bookkeeping across 8 marks, it involves no conceptual difficulty or novel insight, making it slightly easier than average.
Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times -- at \(B\), \(C\) or \(D\), at \(E\), \(F\), \(G\) or \(H\) and at \(I\), \(J\) or \(K\).
\includegraphics{figure_2}
Fig. 2
Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the total waiting time is as small as possible.
Use dynamic programming to find the route that Arthur should use. [8 marks]
Arthur is planning a bus journey from town $A$ to town $L$. There are various routes he can take but he will have to change buses three times -- at $B$, $C$ or $D$, at $E$, $F$, $G$ or $H$ and at $I$, $J$ or $K$.
\includegraphics{figure_2}
Fig. 2
Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the total waiting time is as small as possible.
Use dynamic programming to find the route that Arthur should use. [8 marks]
\hfill \mbox{\textit{OCR D2 Q3 [8]}}