Dynamic programming shortest/longest path

5 Each path from \(S\) to \(T\) in the network below represents a possible way of using the internet to buy a ticket for a particular event. The number on each edge represents a charge, in pounds, with a negative value representing a discount. For example, the path SAEIT represents a ticket costing \(23 + 5 - 4 - 7 = 17\) pounds. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-12_1023_1330_540_350}

1. By working backwards from \(\boldsymbol { T }\) and completing the table on Figure 4, use dynamic programming to find the minimum weight of all paths from \(S\) to \(T\).
2. State the minimum cost of a ticket for the event and the paths corresponding to this minimum cost.
   (3 marks)
   1. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4}

      Stage	State	From	Value
      1	I	\(T\)	-7
      	\(J\)	\(T\)	-6
      	\(K\)	\(T\)	-5
      2	\(E\)	\(I\)	\(- 7 - 4 = - 11\)
      	F	I
      		\(J\)
      	G	I
      		\(J\)
      		\(K\)
      	\(H\)	\(K\)
      3

      \end{table}

5 A firm is considering various strategies for development over the next few years. In the network, the number on each edge is the expected profit, in millions of pounds, moving from one year to the next. A negative number indicates a loss because of building costs or other expenses. Each path from \(S\) to \(T\) represents a complete strategy. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-12_748_1575_559_228}

1. By completing the table on the page opposite, or otherwise, use dynamic programming working backwards from \(\boldsymbol { T }\) to find the maximum weight of all paths from \(S\) to \(T\).
2. State the overall maximum profit and the paths from \(S\) to \(T\) corresponding to this maximum profit.

   1. Stage	State	From	Calculation	Value
      1	G	\(T\)
      	H	\(T\)
      	I	\(T\)
      2	D	G
      		\(H\)
      	E	G
      		\(H\)
      		I
      	\(F\)	\(H\)
      		I
      3

   2. Maximum profit is £ \(\_\_\_\_\) million Corresponding paths from \(S\) to \(T\) \(\_\_\_\_\)

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from \(A\) to \(I\). \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-20_867_1644_552_191}

1. Working backwards from \(\boldsymbol { I }\), use dynamic programming to find the maximum number of bags that can be collected when driving from \(A\) to \(I\). You must complete the table opposite as your solution.
2. State the route that the collector should take in order to collect the maximum number of bags.

   1. Stage	State	From	Value
      1	G	I
      	H	I
      2

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).

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?

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]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-3_595_1054_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).

4 Jeremy is planning a long weekend break during which he wants to photograph as many different churches as he can. He will start from his home, \(J\), on Friday morning and return to his home on Monday evening. Table 1, below, summarises the routes he can take each day and the number of churches that he will pass on each route. You may assume that the 28 churches in the table are all different. \begin{table}[h] \end{table}

1. Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above. Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. \(J\) will have (stage; state) variable ( \(0 ; 0\) ) at the start of the journey and ( \(4 ; 0\) ) at the end. Table 2 shows the (stage; state) variables for all the other places. \begin{table}[h]

   Place	\(K\)	\(L\)	\(M\)	\(N\)	\(P\)	\(R\)	\(S\)	\(T\)
   Stage variable	1	1	2	2	2	3	3	3
   State variable	0	1	0	1	2	0	1	2

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.

6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.

1. Complete the working and suboptimal maximum columns on the copy of the table in your Answer Book. Write down the weight of the maximum path and the corresponding route. Give your route using (stage; state) variables. Ken has entered a cake-making competition. The actions in the dynamic programming tabulation above represent the different types of cake that Ken could make. Each competitor must make one cake in each stage of the competition. The rules of the competition mean that, for each competitor, the actions representing their four cakes must form a route from \(( 0 ; 0 )\) to \(( 4 ; 0 )\). The weights in the tabulation are the number of points that Ken can expect to get by making each of the cakes. Each cake is also judged for how well it has been decorated. The number of points that Ken expects to get for decorating each cake is shown below. Ken is not very good at decorating the cakes. He expects to get 0 points for decorating for the cakes that are not listed below.

   Cake	(0; 0) to (1; 0)	(1; 0) to (2; 1)	(1; 1) to (2; 0)	(2; 0) to (3; 0)	(2; 0) to (3; 1)	(2; 1) to (3; 0)	(2; 1) to (3; 1)
   Decorating points	1	1	2	1	1	1	1

2. Calculate the number of decorating points that Ken can expect if he makes the cakes given in the solution to part (i). When Ken meets the other competitors he realises that he is not good enough to win the competition, so he decides instead to try to win the judges' special award. For each cake, the absolute difference between the score for cake-making and the score for decorating is calculated. The award is given to the person whose biggest absolute difference is least. (Note: to find the absolute difference, calculate larger number-smaller number, or 0 if they are the same.)
3. Draw the graph that the dynamic programming tabulation represents. Label the vertices using (stage; state) labels with \(( 0 ; 0 )\) at the left hand side and \(( 4 ; 0 )\) at the right hand side. Make the graph into a network by weighting the arcs with the absolute differences.
4. Use a dynamic programming tabulation to find the minimax route for the absolute differences.

3. This question should be answered on the sheet provided. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue. \begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.
(9 marks)

4. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses. Use dynamic programming to find the route which should maximise the salesman's net profit. State the expected profit from using this route.
(10 marks)

3. \begin{figure}[h] \end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)

1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
   (1) It is given that the minimum weight route from S to T passes through B .
2. Use dynamic programming to find
   1. the range of possible values of \(x\)
   2. the minimum weight route from S to T .
      (12)

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns. Elena plans to drive from S to T . She must arrive at T by 9 pm .

1. By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm .
2. Hence write down the route that Elena should take.

2 Answer this question on the insert provided. The diagram shows a directed network of paths with vertices labelled with (stage; state) labels. The weights on the arcs represent distances in km . The shortest route from \(( 3 ; 0 )\) to \(( 0 ; 0 )\) is required. Complete the dynamic programming tabulation on the insert, working backwards from stage 1 , to find the shortest route through the network. Give the length of this shortest route. \begin{figure}[h] \end{figure}

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from \(A\) to \(I\). \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-144_867_1644_552_191}

1. Working backwards from \(\boldsymbol { I }\), use dynamic programming to find the maximum number of bags that can be collected when driving from \(A\) to \(I\). You must complete the table opposite as your solution.
2. State the route that the collector should take in order to collect the maximum number of bags.

   1. Stage	State	From	Value
      1	G	I
      	H	I
      2

5 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows 11 vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown. \includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-05_824_1504_559_278}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to find the minimum cost of travelling from \(S\) to \(T\). You may wish to complete the table on Figure 3 as your solution.
2. State the minimum cost and the routes corresponding to this minimum cost.

3 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows eight vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown. \includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-03_595_1234_1866_386}

1. Use dynamic programming to find the minimum cost of travelling from \(A\) to \(H\). You may use Figure 3 for your working.
2. State the minimum cost and the possible routes corresponding to this minimum cost.

5 [Figure 2, printed on the insert, is provided for use in this question.]
A company has a number of stores. The following network shows the possible actions and profits over the next five years. The number on each edge is the expected profit, in millions of pounds. A negative number indicates a loss due to investment in new stores. \includegraphics[max width=\textwidth, alt={}, center]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-06_1006_1583_591_223}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to maximise the expected profits over the five years. You may wish to complete the table on Figure 2 as your solution.
2. State the maximum expected profit and the sequence of vertices from \(S\) to \(T\) in order to achieve this.
   (2 marks)

6 The network below has 11 vertices and 16 edges connecting some pairs of vertices. The numbers on the edges are their weights. The weight of the edge \(D G\) is given in terms of \(x\). There are three routes from \(A\) to \(K\) that have the same minimum total weight. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-16_863_1444_552_299} Working backwards from \(\boldsymbol { K }\), use dynamic programming, to find:

1. the minimum total weight from \(A\) to \(K\);
2. the value of \(x\);
3. the three routes corresponding to the minimum total weight. You must complete the table opposite as your solution.
   [0pt] [12 marks] \section*{Answer space for question 6}

   Stage	State	From	Calculation	Value
   1	I	K
   	\(J\)	K

3

1. Set up a dynamic programming tabulation to find the minimum weight route from ( \(0 ; 0\) ) to ( \(4 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-03_707_1342_1594_443} Give the route and its total weight.
2. Explain carefully how the route is obtained directly from the values in the table, without referring to the network.

1. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at his home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 1 shows the distances, in tens of miles, that he will drive each day according to the route he chooses. Use dynamic programming to find the shortest route the salesman can take and state the distance he will drive in total using this route.

2. 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 1 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. The owner of the plane wishes to choose a route that minimises the total distance that she flies. Use dynamic programming to find the route that she should use and state the total length of this route.

4. 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 total length of the route chosen to be as small as possible. The table below shows the length, in miles, of each of the possible stages. Use dynamic programming to find the route which satisfies the wish of the organisers.

1. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.

Victor owns some kiosks selling ice cream, hot dogs and soft drinks. The network below shows the choices of action and the profits, in thousands of pounds, they generate over the next four years. The negative numbers indicate losses due to the purchases of new kiosks. \includegraphics{figure_5} Use a suitable algorithm to determine the sequence of actions so that the profit over the four years is maximised and state this maximum profit. (Total 12 marks)