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.
| Stage 5 | (5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants | | | |
| Stage 4 | (4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants | (4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants | | |
| Stage 3 | ( \(3 ; 0\) ) to ( \(2 ; 1\) ): 8 plants (3;0) to (2;3): 6 plants | (3;1) to (2;0): 7 plants \(( 3 ; 1 )\) to (2;2): 6 plants | (3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( \(3 ; 2\) ) to ( \(2 ; 3\) ): 8 plants | |
| Stage 2 | (2; 0) to (1; 0): 4 plants ( \(2 ; 0\) ) to ( \(1 ; 1\) ): 5 plants | (2; 1) to (1; 0): 6 plants | (2;2) to (1;1): 7 plants | (2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants |
| Stage 1 | (1;0) to (0;0): 4 plants | (1; 1) to (0;0): 4 plants | | |
- 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.
- 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.