Dynamic programming maximin route

4 A haulage company, based in town \(A\), is to deliver a tall statue to town \(K\). The statue is being delivered on the back of a lorry. The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road. The company wants to ensure that the height of the lowest bridge along the route from \(A\) to \(K\) is maximised. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221} Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution. Optimal route is

4. (a) Explain what is meant by a maximin route in dynamic programming, and give an example of a situation that would require a maximin solution.
(3) \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-2_700_1392_1069_338} A maximin route is to be found through the network shown in the diagram.
(b) Complete the table in the answer book, and hence find a maximin route.
(9)
(c) List all other maximin routes through the network.
(Total 14 marks)

4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.
(2) \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376} A maximin route from L to R is to be found through the staged network shown above.
(b) Use dynamic programming to complete a table below and hence find a maximin route.
(10) (Total 12 marks)

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, \(\mathrm { S } , \mathrm { A }\), B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.

1. Write down the type of dynamic programming problem that Janet needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence find the maximum weight of the truck Janet can use.
4. Write down the route that Janet should take. Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.
5. 1. Determine which of the three roads she should choose and its new minimum weight limit.
   2. Write down the maximum weight of the truck she would be able to use and the new route she would take.

6. \begin{figure}[h] \end{figure} A maximin route is to be found through the network shown in Figure 3.
Complete the table in the answer book, and hence find a maximin route.

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.

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}

6 The table below shows an incomplete dynamic programming tabulation to solve a maximin problem. Do not write your answer on this copy of the table.

1. Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
2. Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
3. Draw the network that is represented in the table. The network represents a system of pipes and the arc weights show the capacities of the pipes, in litres per second.
4. What does the answer to part (ii) represent in this network? The weights of the arcs in the maximin route are each reduced by the maximin value and then a maximin is found for the resulting network. This is done until the maximin value is 0 . At this point the network is as shown below. \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-8_552_1474_438_274}
5. (a) Describe how this solves the maximum flow problem on the original network.
   (b) Draw this maximum flow and draw a cut with value equal to the value of the flow. \section*{END OF QUESTION PAPER} \section*{\(\mathrm { OCR } ^ { \text {勾 } }\)}

3 [Answer this question on the insert provided.]
A flying doctor travels between islands using small planes. Each flight has a weight limit that restricts how much he can carry. A plague has broken out on Farr Island and the doctor needs to take several crates of medical supplies to the island. The crates must be carried on the same planes as the doctor. The diagram shows a network with (stage; state) variables at the vertices representing the islands, arcs representing flight routes that can be used, and weights on the arcs representing the number of crates that the doctor can carry on each flight. \begin{figure}[h] \end{figure} Stage 1 Stage 2

1. It is required to find the route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) for which the minimum number of crates that can be carried on any stage is a maximum (the maximin route). The insert gives a dynamic programming tabulation showing stages, states and actions, together with columns for working out the route minimum at each stage and for indicating the current maximin. Complete the table on the insert sheet and hence find the maximin route and the maximum number of crates that can be carried.
2. It is later found that the number of crates that can be carried on the route from ( \(2 ; 0\) ) to ( \(3 ; 0\) ) has been recorded incorrectly and should be 15 instead of 5 . What is the maximin route now, and how many crates can be carried?

6 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

1 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

5 A three-day journey is to be made from \(S\) to \(T\), with overnight stops at the end of the first day at either \(A\) or \(B\) and at the end of the second day at one of the locations \(C , D\) or \(E\). The network shows the number of hours of sunshine forecast for each day of the journey. \includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-05_753_1284_479_386} The optimal route, known as the maximin route, is that for which the least number of hours of sunshine during a day's journey is as large as possible.

1. Explain why the three-day route \(S A E T\) is better than \(S A C T\).
2. Use dynamic programming to find the optimal (maximin) three-day route from \(S\) to \(T\). (8 marks)

5 [Figure 3, printed on the insert, is provided for use in this question.]
A truck has to transport stones from a quarry, \(Q\), to a builders yard, \(Y\). The network shows the possible roads from \(Q\) to \(Y\). Along each road there are bridges with weight restrictions. The value on each edge indicates the maximum load in tonnes that can be carried by the truck along that particular road. \includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-6_723_1280_589_372} The truck is able to carry a load of up to 20 tonnes. The optimal route, known as the maximin route, is that for which the possible load that the truck can carry is as large as possible.

1. Explain why the route \(Q A C Y\) is better than the route \(Q B E Y\).
2. By completing the table on Figure 3, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { Y }\), to find the optimal (maximin) route from \(Q\) to \(Y\). Write down the maximin route and state the maximum possible load that the truck can carry from \(Q\) to \(Y\).

2 A delivery company needs to transport heavy loads from its warehouse to a ferry port. Each of the roads that it can use has a bridge with a maximum weight limit. The directed network below represents the roads that can be used to get from the warehouse to the ferry port. Road junctions are labelled with (stage; state) labels. The weights on the arcs represent weight limits in tonnes. \includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-03_896_1561_468_292}

1. Explain what a maximin route is.
2. Set up a dynamic programming tabulation, working backwards from stage 1, to find the two maximin routes through the network. What is the maximum load that can be transported in one journey from the warehouse to the ferry port?
3. A new road is opened connecting ( \(2 ; 0\) ) and ( \(2 ; 1\) ). There is no bridge on this road so it does not restrict the weight of the load that can be carried. Using the new road, what is the maximum load that can be transported in one journey from the warehouse to the ferry port? State the route that the delivery company should use. (Do not attempt to apply dynamic programming in this part.)

This question should be answered on the sheet provided. A rally consisting of four stages is being planned. The first stage will begin at A and the last stage will end at L. Various routes are being considered, with the end of one stage being the start of the next. The organisers want the shortest stage to be as long as possible. The table below shows the length, in miles, of each of the possible stages.

			Finishing point
		C	D	E	F	G	H	I
\multirow{3}{*}{Starting point}	A	1	4.5	13	10	8	11	4
	B					5	10.5
	C					9	6
	D					12	7	15
	E
	F							5
	G							8
	H							10
	I
	J
	K

Finishing point
J	K	L
		2
9	2	3
2	9
		5
		6
		10

Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route. [10 marks]