| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Easy -1.2 This is a straightforward application of the dynamic programming algorithm to a small network with clearly defined stages (4 days) and states (towns). The method is mechanical: work backwards from the destination, calculating minimum values at each node. It requires only systematic application of a standard algorithm with no problem-solving insight or novel reasoning. |
| Spec | 7.03c Working with algorithms: trace, interpret, adapt |
1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-1_762_1475_205_239}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
A salesman is planning a four-day trip beginning at his home and ending at town $I$. He will spend the first night in town $A , B$ or $C$, the second night in town $D , E$ or $F$ and the third night in town $G$ or $H$. The network in Figure 1 shows the distances, in tens of miles, that he will drive each day according to the route he chooses.
Use dynamic programming to find the shortest route the salesman can take and state the distance he will drive in total using this route.\\
\hfill \mbox{\textit{OCR D2 Q1 [8]}}