Dynamic programming minimax route

5 A three-day journey is to be made from \(P\) to \(V\), with overnight stops at the end of the first day at one of the locations \(Q\) or \(R\), and at the end of the second day at \(S , T\) or \(U\). The network shows the journey times, in hours, for each day of the journey. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-10_737_1280_447_388} The optimal route, known as the minimax route, is that in which the longest day's journey is as small as possible.

1. Explain why the route \(P Q S V\) is better than the route \(P Q T V\).
2. By completing the table opposite, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { V }\), to find the optimal (minimax) route from \(P\) to \(V\). You should indicate the calculations as well as the values at stages 2 and 3.
   (8 marks)

   \(\ldots . . .\).

   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-11_1000_114_1710_159}

3. \begin{figure}[h] \end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.

1. Complete the table in the answer booklet.
   (8)
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
   (2)

7. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121} Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath. The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next. Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.

1. Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie. Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
2. Find an optimal route for Agent Goodie avoiding tunnel XA.

4. \begin{figure}[h] \end{figure} Figure 1 represents the maintenance choices a council can make and their costs, in \(\pounds 1000\) s, over the next four years. The council wishes to minimise the greatest annual cost of maintenance.

1. Use dynamic programming to find a minimax route from S to T .
   (9)
2. State your route and the greatest annual cost incurred by the council.
   (2)
3. Calculate the average annual cost to the council.
   (2)

3

1. Stage	State	Action	Working	Minimax
   \multirow{3}{*}{1}	0	0	1
   	1	0	3
   	2	0	2
   \multirow{6}{*}{2}	\multirow{2}{*}{0}	0	(4,	\multirow{2}{*}{}
   		1	(2,
   	\multirow{2}{*}{1}	1	(3,	\multirow{2}{*}{}
   		2	(5,
   	\multirow{2}{*}{2}	0	(2,	\multirow{2}{*}{}
   		2	(4,
   \multirow{3}{*}{3}	\multirow{3}{*}{0}	0	(5,	\multirow{3}{*}{}
   		1	(3,
   		2	(1,

2. Minimax value = \(\_\_\_\_\) Minimax route = \(\_\_\_\_\)
3. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-10_958_1527_1539_351}

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?

3. This question should be answered on the sheet provided. Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times - at \(B , C\) or \(D\), at \(E , F , G\) or \(H\) and at \(I , J\) or \(K\). \begin{figure}[h] \end{figure} Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the maximum waiting time at any one stop is as small as possible. Use dynamic programming to find the route that Arthur should use.
(9 marks)

4. This question should be answered on the sheet provided. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h] \end{figure} Figure 2 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. As her plane does not have a large fuel tank, the owner wishes to choose a route that minimises the maximum distance of any one flight. Find the route that she should use and state the maximum distance of any one stage on this route.

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, \(S , A , B , C , D , E , F , G , H , I , J\) and \(T\). The number on each arc shows the distance between these towns, in miles. Bradley is planning a four-day cycle ride from \(S\) to \(T\).
He plans to leave his home at \(S\). On the first night he will stay at \(A , B\) or \(C\), on the second night he will stay at \(D , E , F\) or \(G\), on the third night he will stay at \(H , I\) or \(J\), and he will arrive at his friend's house at \(T\) on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.

1. Write down the type of dynamic programming problem that Bradley needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence write down the possible routes that Bradley could take.

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

1. On the insert, complete the last two columns of the table.
2. State the minimax value and write down the minimax route.
3. Complete the diagram on the insert to show the network that is represented by the table.

5 Tom is going on a driving holiday and wishes to drive from \(A\) to \(K\).
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level. Tom wants to ensure that the maximum altitude of any road along the route from \(A\) to \(K\) is minimised. \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}

1. 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.
2. Tom finds that the road \(C F\) is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.
   [0pt] [2 marks] \section*{Answer space for question 5}

   Stage	State	From	Value
   1	H	\(K\)
   	I	\(K\)
   	\(J\)	\(K\)
   2

   1. Optimal route is \(\_\_\_\_\)
   2. Tom's route is \(\_\_\_\_\) Maximum altitude is \(\_\_\_\_\) Figure 4 below shows a network of pipes.
      The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
      \end{figure}
   3. Find the value of the initial flow.
   4. 1. Use the initial flow and the labelling procedure on Figure 5 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
      2. State the value of the maximum flow and, on Figure 6, illustrate a possible flow along each edge corresponding to this maximum flow.
   5. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
   6. On a particular day, there is a restriction at vertex \(G\) which allows a maximum flow through \(G\) of 30 . Find, by inspection, the maximum flow through the network on this day.
   7. Initial flow \(=\) \(\_\_\_\_\)
   8. 1. Figure 5 \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296} \(7 \quad\) Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where \(x\) is a constant. The value of the game is 2.5 .

         Jose
         \cline { 2 - 4 }	Strategy	C	D
         \cline { 2 - 4 } Arsene	A	\(x + 3\)	1
         \cline { 2 - 4 }	B	\(x + 1\)	3
         \cline { 2 - 4 }
         \cline { 2 - 4 }

   9. Find the optimal mixed strategy for Arsene.
   10. Find the value of \(x\).
       \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
       \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}

3. \begin{figure}[h] \end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.

1. Complete the table in the answer booklet.
   (8)
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
   (2)

\includegraphics{figure_2} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the minimax route.

1. Complete the table in the answer booklet. [8]
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route. [2]

1. State Bellman's principle of optimality. [1]
2. Explain what is meant by a minimax route. [1]
3. Describe a practical problem that would require a minimax route as its solution. [2]

(Total 4 marks)