7.01a Types of problem: existence, construction, enumeration, optimisation

4 The diagram represents a map of an army truck-driving course that includes several bridges. The start and a 'safe point' just after each bridge have been given (stage; state) labels. The number below each bridge shows its weight limit, in tonnes. \includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-4_698_1413_438_365} An army cadet needs to drive a truck through the course from start to finish, crossing exactly three bridges.

1. Draw a network, using the (stage; state) labels given, to represent the routes through the course. The weights on the arcs should show the weight limits for the bridges. The cadet wants to find out the weight of the heaviest truck she can use.
2. Which network problem does she need to solve?
3. Set up a dynamic programming tabulation to solve the cadet's problem. Write down the weight of the heaviest truck she can use and write down the (stage; state) labels for the route she should take.

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

5 Henry is doing a sponsored cycle ride for charity. He needs to finish at noon on Sunday. He can ride up to 50 miles each day, except Sunday when he can ride at most 20 miles if he is to finish on time. The total length of the ride is 95 miles so Henry has allowed 3 days for the ride. Henry will start his ride at \(A\) and travel through \(B , C , D\) and \(E\), in that order, and finish on Sunday at \(F\). He will stay overnight on Friday and Saturday at two of the places \(B , C , D\) and \(E\). The distances between the places along the route are: $$A - B = 30 \text { miles } , \quad B - C = 15 \text { miles } , \quad C - D = 35 \text { miles } , \quad D - E = 12 \text { miles } , \quad E - F = 3 \text { miles. }$$ To reach \(F\) on Sunday he must have reached at least \(D\) by Saturday night (since the distance from \(D\) to \(F\) is less than 20 miles but \(C\) to \(F\) is more than 20 miles.) Henry wants to use dynamic programming to minimise the maximum distance that he cycles on any day.
The stages will be the days. The places where Henry stays overnight will be the states. Henry starts on Friday morning at \(A\) which has the (stage; state) label ( \(0 ; 0\) ). On Friday night he can either stay at \(B ( 1 ; 0 )\) or at \(C ( 1 ; 1 )\). Depending on where he stays on Friday night, he can spend Saturday night at \(D ( 2 ; 0 )\) or \(E ( 2 ; 1 )\). On Sunday he arrives at \(F ( 3 ; 0 )\).
[0pt]

1. Use this information and the table below to draw a network, labelled with stages and states, to show the possible transitions between states. The arc weights should be the distances between the states. [2] Henry uses dynamic programming, working backwards from stage 3, to find where he should stay overnight to give the route for which the maximum on any day is a minimum. His tabulation is shown below.

   Stage	State	Action	Working	Suboptimal minimax
   \multirow[t]{2}{*}{2}	0	0	15	15
   	1	0	3	3
   \multirow{3}{*}{1}	0	0	\(\max ( 50,15 )\)	50
   	\multirow[t]{2}{*}{1}	0	\(\max ( 35,15 )\)	\multirow[t]{2}{*}{35}
   		1	\(\max ( 47,3 )\)
   \multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	\(\max ( 30,50 )\)	\multirow[b]{2}{*}{45}
   		1	max(45, 35)

2. (a) In the last row of the table, the action value is 1 . Explain what this tells you.
3. (b) In the last row of the table, the working column is \(\max ( 45,35 )\). Explain where each of the values 45 and 35 comes from and how they relate to the (stage; state) values for this row and for a row from the next stage.
4. Use the table to deduce where Henry should make his overnight stops to minimise the maximum distance that he cycles on any day. Explain how you obtained this solution from the table. Henry is so pleased with his ride that he decides to do a longer ride. Again he will cycle up to 50 miles each day, except the last day when he will cycle at most 20 miles. He wants to complete the ride in five days, and he wants to minimise the maximum distance that he rides on any one day. He will start at \(A\) and travel through \(B , C , D , E , F , G , H , I , J\) and \(K\), in that order, and finish at \(L\).
   He will stay overnight on Wednesday, Thursday, Friday and Saturday at four of \(B , C , D , E , F , G , H , I , J\) and \(K\). The distances between the places along the route are:

   \(A - B = 30\) miles,	\(B - C = 15\) miles,	\(C - D = 35\) miles,	\(D - E = 12\) miles,
   \(E - F = 3\) miles,	\(F - G = 30\) miles,	\(G - H = 10\) miles,	\(H - I = 25\) miles,
   \(I - J = 10\) miles,	\(J - K = 10\) miles,	\(K - L = 5\) miles.

5. (a) Which is the furthest place from \(L\) that Henry must reach by Saturday night if he is to finish on time?
   (b) Work backwards to deduce the furthest place from \(L\) that Henry must reach by Friday night, Thursday night and Wednesday night.
6. Find out where Henry could stay each night, and hence define appropriate states for each of stages 1, 2, 3 and 4 . (Note that not every place need correspond to a (stage; state) label.)
7. Set up a dynamic programming tabulation, working backwards from stage 5, to minimise the maximum distance that Henry must ride on any one day. Where should he make his overnight stops?

4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( \(5 ; 0\) ) and the exit as ( \(0 ; 0\) ). He then counted the numbers of plants along paths. These numbers are shown below.

1. Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
2. Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.

2

1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, F, I
   \(M\)	6	\(E , G , J\)
   \(N\)	8	\(H\), \(K\)

   Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
3. Compare the solutions to parts (i) and (ii).

6 Set up a dynamic programming tabulation to find the maximin route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}

3 Throughout this question all clock times are in Greenwich Mean Time (GMT).
An aeroplane needs to arrive at its destination at 3pm. The places it can pass through on its route are shown in the network, together with the flying times, in hours, between them. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-4_609_1523_486_255} Use a dynamic programming tabulation, working backwards from 3pm at the destination, to find the latest time that the aeroplane could set off. If the aeroplane takes off at its latest time, which places does it pass through, and at what time does it reach each of these places?

1 Alfie has a set of 15 cards numbered consecutively from 1 to 15.
He chooses two of the cards.

1. How many different sets of two cards are possible? Alfie places the two cards side by side to form a number with 2,3 or 4 digits.
2. Explain why there are fewer than \({ } ^ { 15 } \mathrm { P } _ { 2 } = 210\) possible numbers that can be made.
3. Explain why, with these cards, 1 is the lead digit more often than any other digit. Alfie makes the number 113, which is a 3-digit prime number. Alfie says that the problem of working out how many 3-digit prime numbers can be made using two of the cards is a construction problem, because he is trying to find all of them.
4. Explain why Alfie is wrong to say this is a construction problem.

1 Jane wants to travel from home to the local town. Jane can do this by train, by bus or by both train and bus.

1. Give an example of a problem that Jane could be answering that would give a construction problem. A website gives Jane all the possible buses and trains that she could use.
   Jane finds 7 possible ways to make the journey.

2 Jameela needs to store ten packages in boxes. She has a list showing the size of each package. The boxes are all the same size and Jameela can use up to six of these boxes to store all the packages.

1. Which of the following is a question that Jameela could ask which leads to a construction problem? Justify your choice.
   The total volume of the packages is \(1 \mathrm {~m} ^ { 3 }\). The volume of each of the six boxes is \(0.25 \mathrm {~m} ^ { 3 }\).
2. Explain why a solution to the problem of storing all the packages in six boxes may not exist. The volume of each package is given below.

   Package	A	B	C	D	E	F	G	H	I	J
   Volume \(\left( \mathrm { m } ^ { 3 } \right)\)	0.20	0.05	0.15	0.25	0.04	0.03	0.02	0.02	0.12	0.12

3. By considering the five largest packages (A, C, D, I and J) first, explain what happens if Jameela tries to pack the 10 packages using only four boxes. You may now assume that the packages will always fit in the boxes if there is enough volume.
4. Use first-fit to find a way of storing the packages in the boxes. Show the letters of the packages in each box, in the order that they are packed into that box. The order of the packages within a box does not matter and the order of the boxes does not matter. So, for example, having A and E in box 1 is the same as having E and A in box 2 , but different from having A in one box and E in a different box.
5. Suppose that packages A and B are not in the same box. In this case the following are true:
   Use the inclusion-exclusion principle to determine how many of the 8 ways include neither package F nor package G.

1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and arriving in Southampton by 4 pm . He wants to leave Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that leads to
(A) an existence problem,
(B) an optimisation problem.

3 A set of ten cards have the following values: \(\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}\) Kerenza wonders if there is a set of these cards with a total of exactly 50 .

1. Which type of problem (existence, construction, enumeration or optimisation) is this? The five cards \(4,8,8,10\) and 20 have a total of 50.
2. How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
3. How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
4. Show how quicksort works by using it to sort the original list of ten cards into increasing order.
   You should indicate the pivots used and which values are already known to be in their correct position.