6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.
| Stage | State | Action | Working | Suboptimal maximum |
| \multirow[t]{2}{*}{3} | 0 | 0 | 1 | 1 |
| 1 | 0 | 2 | 2 |
| \multirow[t]{4}{*}{2} | \multirow[t]{2}{*}{0} | 0 | \(1 + 1 = 2\) | \multirow[b]{2}{*}{3} |
| | 1 | \(1 + 2 = 3\) | |
| \multirow[t]{2}{*}{1} | 0 | \(3 + 1 = 4\) | \multirow[t]{2}{*}{4} |
| | 1 | \(1 + 2 = 3\) | |
| \multirow[t]{4}{*}{1} | \multirow[t]{2}{*}{0} | 0 | \(1 + =\) | \multirow{4}{*}{} |
| | 1 | \(0 + =\) | |
| \multirow[t]{2}{*}{1} | 0 | \(0 + =\) | |
| | 1 | \(1 + =\) | |
| \multirow[t]{2}{*}{0} | \multirow[t]{2}{*}{0} | 0 | \(2 + =\) | \multirow{2}{*}{} |
| | 1 | \(2 + =\) | |
- 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 |
- 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.)
- 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.
- Use a dynamic programming tabulation to find the minimax route for the absolute differences.