OCR D2 2007 June — Question 4

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2007
SessionJune
TopicDynamic Programming

4 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a minimax problem.
StageStateA ctionWorkingM inimax
\multirow{3}{*}{1}0044
1033
2022
\multirow{9}{*}{2}\multirow{3}{*}{0}0\(\max ( 6,4 ) = 6\)\multirow{3}{*}{3}
1\(\max ( 2,3 ) = 3\)
2\(\max ( 3,2 ) = 3\)
\multirow{3}{*}{1}0\(\max ( 2,4 ) =\)\multirow{3}{*}{}
1\(\max ( 4,3 ) =\)
2\(\max ( 5,2 ) =\)
\multirow{3}{*}{2}0max(2,\multirow{3}{*}{}
1max(3,
2max(4,
\multirow{3}{*}{3}\multirow{3}{*}{0}0max(5,\multirow{3}{*}{}
1max(5,
2max(2,
  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.