Question 6 - A-Level Maths

OCR D2 2011 January — Question 6 13 marks

Exam Board	OCR
Module	D2 (Decision Mathematics 2)
Year	2011
Session	January
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Dynamic Programming
Type	Dynamic programming order sequencing
Difficulty	Moderate -0.5 Part (i) is straightforward arithmetic from a table (10+3+2+2+17=34 minutes). Part (ii) requires recognizing that the route visits bird 1 (Kite) twice, violating the constraint. This is a standard D2 dynamic programming question testing understanding of state formulation in TSP-type problems, but requires minimal problem-solving beyond reading comprehension and basic calculation.
Spec	7.04c Travelling salesman upper bound: nearest neighbour method 7.04d Travelling salesman lower bound: using minimum spanning tree 7.05a Critical path analysis: activity on arc networks 7.05b Forward and backward pass: earliest/latest times, critical activities

6 Answer this question on the insert provided. Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation.

	Entrance/exit	Kite	Lark	Moorhen	Nightjar
Entrance/exit	-	10	14	12	17
Kite	10	-	3	2	6
Lark	14	3	-	2	4
Moorhen	12	2	2	-	3
Nightjar	17	6	4	3	-

Let the stages be $0,1,2,3,4,5$. Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be $0,1,2,3,4$ representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.
Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.

Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

Stage

State

Action

Working

Suboptimal minimum

\multirow{4}{*}{4}

1(234)

2(134)

3(124)

4(123)

\multirow{12}{*}{3}

1(23)

4(123)

$17 + 6 = 23$

1(24)

3(124)

$12 + 2 = 14$

1(34)

2(134)

$14 + 3 = 17$

2(13)

4(123)

$17 + 4 = 21$

2(14)

3(124)

$12 + 2 = 14$

2(34)

1(234)

$10 + 3 = 13$

3(12)

4(123)

$17 + 3 = 20$

3(14)

2(134)

$14 + 2 = 16$

3(24)

1(234)

$10 + 2 = 12$

4(12)

3(124)

$12 + 3 = 15$

4(13)

2(134)

$14 + 4 = 18$

4(23)

1(234)

$10 + 6 = 16$

\multirow{12}{*}{2}

1(2)

3(12) 4(12)

$20 + 2 = 22$

1(3)

2(13) 4(13)

$21 + 3 = 24 18 + 6 = 24$

1(4)

2(1)

2(3)

2(4)

3(1)

3(2)

3(4)

4(1)

4(2)

4(3)

\multirow{4}{*}{1}

Show mark scheme Show mark scheme source

Question 6(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
$10+3+2+3+17 = 35$	B1	$35$

Question 6(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
Visits the kite twice; Does not visit the nightjar at all	B1	Does not visit every bird (in context)

Question 6(iii):

Answer	Marks	Guidance
Answer	Mark	Guidance
$18$ is the suboptimal min from stage 3, state $4(13)$; $6$ is the time taken to travel from bird 1 to bird 4 (kite to nightjar)	B1 B1	Identifying the 18 with coming from state $4(13)$; Identifying the 6 with kite – nightjar in table, with 1 to 4 or $1(3)$ to $4(13)$; Note: 18 and 6 are given in question

Question 6(iv):

Answer	Marks	Guidance
Answer	Mark	Guidance
Action column correct for stage 2 (at least 14 of the 20 correct)	M1
All suboptimal min values transferred correctly from stage 3	A1
All times transferred correctly from table for stage 2	M1
All suboptimal min column correct for stage 2	A1
Suboptimal min values transferred correctly from stage 2	M1	Follow through their suboptimal min values from stage 2 for the method marks
Suboptimal min column correct for stage 1 from their stage 2 values	M1
Totally correct table (cao)	A1
Kite – lark – nightjar – moorhen (or moorhen – nightjar – lark – kite); Minimum journey time $= 32$ minutes	B1 B1	cao (names must be used, allow letters but not numbers); $32$ cao

# Question 6(i):

| Answer | Mark | Guidance |
|--------|------|----------|
| $10+3+2+3+17 = 35$ | B1 | $35$ |

# Question 6(ii):

| Answer | Mark | Guidance |
|--------|------|----------|
| Visits the kite twice; Does not visit the nightjar at all | B1 | Does not visit every bird (in context) |

# Question 6(iii):

| Answer | Mark | Guidance |
|--------|------|----------|
| $18$ is the suboptimal min from stage 3, state $4(13)$; $6$ is the time taken to travel from bird 1 to bird 4 (kite to nightjar) | B1 B1 | Identifying the 18 with coming from state $4(13)$; Identifying the 6 with kite – nightjar in table, with 1 to 4 or $1(3)$ to $4(13)$; Note: 18 and 6 are given in question |

# Question 6(iv):

| Answer | Mark | Guidance |
|--------|------|----------|
| Action column correct for stage 2 (at least 14 of the 20 correct) | M1 | |
| All suboptimal min values transferred correctly from stage 3 | A1 | |
| All times transferred correctly from table for stage 2 | M1 | |
| All suboptimal min column correct for stage 2 | A1 | |
| Suboptimal min values transferred correctly from stage 2 | M1 | Follow through their suboptimal min values from stage 2 for the method marks |
| Suboptimal min column correct for stage 1 from their stage 2 values | M1 | |
| Totally correct table (cao) | A1 | |
| Kite – lark – nightjar – moorhen (or moorhen – nightjar – lark – kite); Minimum journey time $= 32$ minutes | B1 B1 | cao (names must be used, allow letters but not numbers); $32$ cao |

Show LaTeX source

6 Answer this question on the insert provided.
Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
 & Entrance/exit & Kite & Lark & Moorhen & Nightjar \\
\hline
Entrance/exit & - & 10 & 14 & 12 & 17 \\
\hline
Kite & 10 & - & 3 & 2 & 6 \\
\hline
Lark & 14 & 3 & - & 2 & 4 \\
\hline
Moorhen & 12 & 2 & 2 & - & 3 \\
\hline
Nightjar & 17 & 6 & 4 & 3 & - \\
\hline
\end{tabular}
\end{center}

Let the stages be $0,1,2,3,4,5$. Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be $0,1,2,3,4$ representing the entrance/exit, kite, lark, moorhen and nightjar respectively.\\
(i) Calculate how many minutes it takes to travel the route

$$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$

The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.\\
(ii) Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem.

Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.\\
(iii) For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.\\
(iv) Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Working & Suboptimal minimum \\
\hline
\multirow{4}{*}{4} & 1(234) & 0 & 10 & 10 \\
\hline
 & 2(134) & 0 & 14 & 14 \\
\hline
 & 3(124) & 0 & 12 & 12 \\
\hline
 & 4(123) & 0 & 17 & 17 \\
\hline
\multirow{12}{*}{3} & 1(23) & 4(123) & $17 + 6 = 23$ & 23 \\
\hline
 & 1(24) & 3(124) & $12 + 2 = 14$ & 14 \\
\hline
 & 1(34) & 2(134) & $14 + 3 = 17$ & 17 \\
\hline
 & 2(13) & 4(123) & $17 + 4 = 21$ & 21 \\
\hline
 & 2(14) & 3(124) & $12 + 2 = 14$ & 14 \\
\hline
 & 2(34) & 1(234) & $10 + 3 = 13$ & 13 \\
\hline
 & 3(12) & 4(123) & $17 + 3 = 20$ & 20 \\
\hline
 & 3(14) & 2(134) & $14 + 2 = 16$ & 16 \\
\hline
 & 3(24) & 1(234) & $10 + 2 = 12$ & 12 \\
\hline
 & 4(12) & 3(124) & $12 + 3 = 15$ & 15 \\
\hline
 & 4(13) & 2(134) & $14 + 4 = 18$ & 18 \\
\hline
 & 4(23) & 1(234) & $10 + 6 = 16$ & 16 \\
\hline
\multirow{12}{*}{2} & 1(2) & 3(12) 4(12) & \(20 + 2 = 22\) & 21 \\
\hline
 & 1(3) & 2(13) 4(13) & $21 + 3 = 24 18 + 6 = 24$ & 24 \\
\hline
 & 1(4) &  &  &  \\
\hline
 & 2(1) &  &  &  \\
\hline
 & 2(3) &  &  &  \\
\hline
 & 2(4) &  &  &  \\
\hline
 & 3(1) &  &  &  \\
\hline
 & 3(2) &  &  &  \\
\hline
 & 3(4) &  &  &  \\
\hline
 & 4(1) &  &  &  \\
\hline
 & 4(2) &  &  &  \\
\hline
 & 4(3) &  &  &  \\
\hline
\multirow{4}{*}{1} & 1 &  &  &  \\
\hline
 & 2 &  &  &  \\
\hline
 & 3 &  &  &  \\
\hline
 & 4 &  &  &  \\
\hline
0 & 0 & \begin{tabular}{l}
1 \\
2 \\
3 \\
4 \\
\end{tabular} &  &  \\
\hline
\end{tabular}
\end{center}

\hfill \mbox{\textit{OCR D2 2011 Q6 [13]}}

This paper (6 questions)

View full paper

Q1 4 Q2 7 Q3 12 Q4 18 Q5 18 Q6 13