Further Maths Dynamic programming Practice Questions

Free Further Maths Dynamic programming practice questions with full step-by-step worked solutions. Covers dynamic-programming, bellman, stage-state-action, minimisation. Practise exam-style problems and check your method.

dynamic-programmingbellmanstage-state-actionminimisationmaximisationmaximin-minimax
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
A route must be chosen through a staged network so as to keep the total cost as low as possible. The states are arranged in stages as follows: stage 00 contains AA; stage 11 contains BB, CC, DD; stage 22 contains EE, FF; stage 33 contains GG. Each arc joins a state to a state in the next stage, and the arc values are AB=7AB=7, AC=33AC=33, AD=3AD=3, BE=46BE=46, BF=27BF=27, CE=37CE=37, CF=24CF=24, DE=41DE=41, DF=26DF=26, EG=18EG=18, FG=16FG=16. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from AA to GG.
Show worked solution

Worked solution

  1. Identify the stages, states and arcs of the network

    stages 0 to 3,  source A,  sink G\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G

    Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.

  2. Work backwards from the final stage, giving each state its optimal value

    g(A)=45,  g(B)=43,  g(C)=40,  g(D)=42,  g(E)=18,  g(F)=16g(A)=45,\;g(B)=43,\;g(C)=40,\;g(D)=42,\;g(E)=18,\;g(F)=16

    Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.

  3. Trace the optimal route forwards from the source

    A→D→F→G(3+26+16=45)A\to D\to F\to G\quad\left(3+26+16=45\right)

    Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.

  4. State the minimum total cost

    minimum total cost=45\text{minimum total cost}=45

    The least possible total cost of a route from AA to GG is 4545.

Answer
4545
Question 2
2 markseasy
The states are arranged in stages as follows: stage 00 contains AA; stage 11 contains BB, CC, DD; stage 22 contains EE, FF; stage 33 contains GG. Each arc joins a state to a state in the next stage, and the arc values are AB=10AB=10, AC=17AC=17, AD=36AD=36, BE=7BE=7, BF=15BF=15, CE=37CE=37, CF=23CF=23, DE=6DE=6, DF=38DF=38, EG=46EG=46, FG=8FG=8. Using Bellman's principle of optimality, determine the route of greatest total value from AA to GG. Which of the following is that route?
Show worked solution

Worked solution

  1. Identify the stages, states and arcs of the network

    stages 0 to 3,  source A,  sink G\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G

    Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.

  2. Work backwards from the final stage, giving each state its optimal value

    g(A)=100,  g(B)=53,  g(C)=83,  g(D)=52,  g(E)=46,  g(F)=8g(A)=100,\;g(B)=53,\;g(C)=83,\;g(D)=52,\;g(E)=46,\;g(F)=8

    Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.

  3. Trace the optimal route forwards from the source

    A→C→E→G(17+37+46=100)A\to C\to E\to G\quad\left(17+37+46=100\right)

    Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.

  4. Select the route of greatest total value

    optimal route:  A→C→E→G\text{optimal route}:\;A\to C\to E\to G

    This route attains the maximum total value of 100100 and no other route matches it.

Answer
A→C→E→GA\to C\to E\to G
Question 3
4 marksintermediate
The states are arranged in stages as follows: stage 00 contains AA; stage 11 contains BB, CC, DD; stage 22 contains EE, FF, GG; stage 33 contains HH. Each arc joins a state to a state in the next stage, and the arc values are AB=22AB=22, AC=31AC=31, AD=42AD=42, BE=41BE=41, BF=9BF=9, BG=13BG=13, CE=43CE=43, CF=20CF=20, CG=47CG=47, DE=29DE=29, DF=40DF=40, DG=25DG=25, EH=7EH=7, FH=8FH=8, GH=49GH=49. Using Bellman's principle of optimality, determine the route of greatest total value from AA to HH. Which of the following is that route?
Show worked solution

Worked solution

  1. Identify the stages, states and arcs of the network

    stages 0 to 3,  source A,  sink H\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }H

    Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.

  2. Give the sink its initial value

    g(H)=0g(H)=0

    The route ends at HH, so from HH there is no further value to add.

  3. Stage 2: optimise the states EE, FF, GG

    g(E)=max⁡{7+0}=7,g(F)=max⁡{8+0}=8,g(G)=max⁡{49+0}=49g(E)=\max\{7+0\}=7,\quad g(F)=\max\{8+0\}=8,\quad g(G)=\max\{49+0\}=49

    Each of these states is given its best value using the values already fixed at the next stage.

  4. Stage 1: optimise the states BB, CC, DD

    g(B)=max⁡{41+7, 9+8, 13+49}=62,g(C)=max⁡{43+7, 20+8, 47+49}=96,g(D)=max⁡{29+7, 40+8, 25+49}=74g(B)=\max\{41+7,\,9+8,\,13+49\}=62,\quad g(C)=\max\{43+7,\,20+8,\,47+49\}=96,\quad g(D)=\max\{29+7,\,40+8,\,25+49\}=74

    Each of these states is given its best value using the values already fixed at the next stage.

  5. Stage 0: optimise the states AA

    g(A)=max⁡{22+62, 31+96, 42+74}=127g(A)=\max\{22+62,\,31+96,\,42+74\}=127

    Each of these states is given its best value using the values already fixed at the next stage.

  6. Trace the optimal route forwards from the source

    A→C→G→H(31+47+49=127)A\to C\to G\to H\quad\left(31+47+49=127\right)

    Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.

  7. Select the route of greatest total value

    optimal route:  A→C→G→H\text{optimal route}:\;A\to C\to G\to H

    This route attains the maximum total value of 127127 and no other route matches it.

Answer
A→C→G→HA\to C\to G\to H
Question 4
6 markshard
The states are arranged in stages as follows: stage 00 contains AA; stage 11 contains BB, CC; stage 22 contains DD, EE, FF; stage 33 contains GG, HH; stage 44 contains II. Each arc joins a state to a state in the next stage, and the arc values are AB=23AB=23, AC=40AC=40, BD=39BD=39, BE=47BE=47, BF=42BF=42, CD=18CD=18, CE=45CE=45, CF=8CF=8, DG=36DG=36, DH=34DH=34, EG=6EG=6, EH=4EH=4, FG=17FG=17, FH=37FH=37, GI=7GI=7, HI=20HI=20. Using Bellman's principle of optimality, determine the route of greatest total value from AA to II. Which of the following is that route?
Show worked solution

Worked solution

  1. Identify the stages, states and arcs of the network

    stages 0 to 4,  source A,  sink I\text{stages }0\text{ to }4,\;\text{source }A,\;\text{sink }I

    Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.

  2. Give the sink its initial value

    g(I)=0g(I)=0

    The route ends at II, so from II there is no further value to add.

  3. Stage 3: optimise state GG

    g(G)=max⁡{7+0}=7g(G)=\max\{7+0\}=7

    The optimal value at state GG combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  4. Stage 3: optimise state HH

    g(H)=max⁡{20+0}=20g(H)=\max\{20+0\}=20

    The optimal value at state HH combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  5. Stage 2: optimise state DD

    g(D)=max⁡{36+7, 34+20}=54g(D)=\max\{36+7,\,34+20\}=54

    The optimal value at state DD combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  6. Stage 2: optimise state EE

    g(E)=max⁡{6+7, 4+20}=24g(E)=\max\{6+7,\,4+20\}=24

    The optimal value at state EE combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  7. Stage 2: optimise state FF

    g(F)=max⁡{17+7, 37+20}=57g(F)=\max\{17+7,\,37+20\}=57

    The optimal value at state FF combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  8. Stage 1: optimise state BB

    g(B)=max⁡{39+54, 47+24, 42+57}=99g(B)=\max\{39+54,\,47+24,\,42+57\}=99

    The optimal value at state BB combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  9. Stage 1: optimise state CC

    g(C)=max⁡{18+54, 45+24, 8+57}=72g(C)=\max\{18+54,\,45+24,\,8+57\}=72

    The optimal value at state CC combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  10. Stage 0: optimise state AA

    g(A)=max⁡{23+99, 40+72}=122g(A)=\max\{23+99,\,40+72\}=122

    The optimal value at state AA combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  11. Trace the optimal route forwards from the source

    A→B→F→H→I(23+42+37+20=122)A\to B\to F\to H\to I\quad\left(23+42+37+20=122\right)

    Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.

  12. Select the route of greatest total value

    optimal route:  A→B→F→H→I\text{optimal route}:\;A\to B\to F\to H\to I

    This route attains the maximum total value of 122122 and no other route matches it.

Answer
A→B→F→H→IA\to B\to F\to H\to I
Question 5
9 markschallenging
The states are arranged in stages as follows: stage 00 contains AA; stage 11 contains BB, CC, DD; stage 22 contains EE, FF, GG; stage 33 contains HH, II; stage 44 contains JJ. Each arc joins a state to a state in the next stage, and the arc values are AB=9AB=9, AC=45AC=45, AD=34AD=34, BE=23BE=23, BF=33BF=33, BG=3BG=3, CE=25CE=25, CF=44CF=44, CG=31CG=31, DE=46DE=46, DF=42DF=42, DG=18DG=18, EH=21EH=21, EI=2EI=2, FH=22FH=22, FI=24FI=24, GH=26GH=26, GI=6GI=6, HJ=41HJ=41, IJ=13IJ=13. Using Bellman's principle of optimality, determine the route of greatest total value from AA to JJ. Which of the following is that route?
Show worked solution

Worked solution

  1. Identify the stages, states and arcs of the network

    stages 0 to 4,  source A,  sink J\text{stages }0\text{ to }4,\;\text{source }A,\;\text{sink }J

    Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.

  2. Give the sink its initial value

    g(J)=0g(J)=0

    The route ends at JJ, so from JJ there is no further value to add.

  3. Stage 3: optimise state HH

    g(H)=max⁡{41+0}=41g(H)=\max\{41+0\}=41

    The optimal value at state HH combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  4. Stage 3: optimise state II

    g(I)=max⁡{13+0}=13g(I)=\max\{13+0\}=13

    The optimal value at state II combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  5. Stage 2: optimise state EE

    g(E)=max⁡{21+41, 2+13}=62g(E)=\max\{21+41,\,2+13\}=62

    The optimal value at state EE combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  6. Stage 2: optimise state FF

    g(F)=max⁡{22+41, 24+13}=63g(F)=\max\{22+41,\,24+13\}=63

    The optimal value at state FF combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  7. Stage 2: optimise state GG

    g(G)=max⁡{26+41, 6+13}=67g(G)=\max\{26+41,\,6+13\}=67

    The optimal value at state GG combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  8. Stage 1: optimise state BB

    g(B)=max⁡{23+62, 33+63, 3+67}=96g(B)=\max\{23+62,\,33+63,\,3+67\}=96

    The optimal value at state BB combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  9. Stage 1: optimise state CC

    g(C)=max⁡{25+62, 44+63, 31+67}=107g(C)=\max\{25+62,\,44+63,\,31+67\}=107

    The optimal value at state CC combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  10. Stage 1: optimise state DD

    g(D)=max⁡{46+62, 42+63, 18+67}=108g(D)=\max\{46+62,\,42+63,\,18+67\}=108

    The optimal value at state DD combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  11. Stage 0: optimise state AA

    g(A)=max⁡{9+96, 45+107, 34+108}=152g(A)=\max\{9+96,\,45+107,\,34+108\}=152

    The optimal value at state AA combines each outgoing arc with the value already fixed at the state it leads to, and keeps the largest total.

  12. Trace the optimal route forwards from the source

    A→C→F→H→J(45+44+22+41=152)A\to C\to F\to H\to J\quad\left(45+44+22+41=152\right)

    Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.

  13. State Bellman's principle of optimality

    optimal policy  ⇒  optimal sub-policy\text{optimal policy}\;\Rightarrow\;\text{optimal sub-policy}

    Any part of an optimal route is itself optimal for the sub-problem that starts where that part begins, so each state need only be optimised once.

  14. Record the optimal value at every state

    g(A)=152,  g(B)=96,  g(C)=107,  g(D)=108,  g(E)=62,  g(F)=63,  g(G)=67,  g(H)=41,  g(I)=13g(A)=152,\;g(B)=96,\;g(C)=107,\;g(D)=108,\;g(E)=62,\;g(F)=63,\;g(G)=67,\;g(H)=41,\;g(I)=13

    Each label is the best value obtainable on a route from that state to the sink.

  15. Select the route of greatest total value

    optimal route:  A→C→F→H→J\text{optimal route}:\;A\to C\to F\to H\to J

    This route attains the maximum total value of 152152 and no other route matches it.

Answer
A→C→F→H→JA\to C\to F\to H\to J

Unlock 65 more Dynamic programming questions

Create a free account to work through every Further Maths Dynamic programming question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Dynamic programming practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisFlows in networksGame theory