5 A card game between two players consists of several rounds. In each round the players both choose a card from those in their hand; they then show these cards to each other and exchange tokens. The number of tokens that the second player gives to the first player depends on the colour of the first player's card and the design on the second player's card. The table shows the number of tokens that the first player receives for each combination of colour and design. A negative entry means that the first player gives tokens to the second, zero means that no tokens are exchanged. 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.

1. 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.
2. 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.
3. 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.
4. 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)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4