Dynamic programming

Dynamic programming

Spec 4.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Dynamic programming splits a problem into stages and works backwards from the last.
  • The state says where you are; the action is the decision made there.
  • Bellman's principle: any part of an optimal route is itself optimal.
  • For a minimum route, value =min⁡(arc+next value)=\min(\text{arc}+\text{next value}). Minimax and maximin use the larger or smaller of arc and next value.
  • Complete each stage's table before the next, then read the route forwards.

Stages, states and Bellman

Split the problem into stages, solve the last first and work backwards. Bellman's principle lets you store one best value per state.

Dynamic programming solves a problem by splitting it into stages, solving the last stage first and working backwards.

At each stage the state variable describes where you are (the vertex, or the number of units left), and the action is the decision (the next vertex, or how many units to use).

So the best way onward from a state does not depend on how you reached it, and one best value is stored for each state.

SABCDT
A staged network: each vertex is a state, each arrow an action. Solve the last stage (right) first, then work back to the start.
  • Bellman's principleany part of an optimal route is itself optimal

What does Bellman's principle let us do?

A minimum route

Work backwards from the sink. Each state's value is the minimum over actions of arc length plus next value.

Work backwards from the sink. For each state the value is the minimum over the actions of (arc length ++ value of the next state).

Record each stage in a table with columns stage, state, action, value, then read the route forwards from the start.

State which way you number the stages, work back one stage at a time, and only then read the route forwards.

SA 6SB 5AC 3AD 8BC 5BD 4CT 7DT 3SABCDT
The shortest route S, B, D, T is drawn solid.

Worked example

Arcs: SASA 6, SBSB 5, ACAC 3, ADAD 8, BCBC 5, BDBD 4, CTCT 7, DTDT 3. Find the shortest route from SS to TT.

A state has an arc of length 4 to a state of value 9, and an arc of 6 to a state of value 5. What is its minimum value?

Maximum, minimax and maximin

Maximum uses max of arc plus next. Minimax uses the larger of arc and next, then the minimum. Maximin uses the smaller, then the maximum.

The same method works with other ways of combining arcs.

  • Maximum route (longest, or greatest profit): value =max⁡(arc+next value)=\max(\text{arc}+\text{next value}).
  • Minimax route: the largest arc used is as small as possible.
  • Maximin route: the smallest arc used is as large as possible.

In minimax and maximin problems do not add the arc and the next value: take the larger (minimax) or the smaller (maximin) of the two.

w = 3w = 6w = 5w = 2SABT
Arc weights as shown. Maximum: S-A-T (3+6 = 9). Minimax: S-B-T (largest arc 5, against 6). Maximin: S-A-T (smallest arc 3, against 2).

Maximum

Aim:
Greatest total
Value:
max⁡(arc+next)\max(\text{arc}+\text{next})

Minimax

Aim:
Largest arc as small as possible
Value:
min⁡(max⁡(arc,next))\min(\max(\text{arc},\text{next}))

Maximin

Aim:
Smallest arc as large as possible
Value:
max⁡(min⁡(arc,next))\max(\min(\text{arc},\text{next}))

Worked example

Use the same network. Find the route whose largest arc is as small as possible.

In a maximin problem, an arc of 6 leads to a state of value 4. What is the value through that arc?

Allocation problems

Take the activities one at a time: stage is activities considered, state is units available, action is units given to the current activity.

Dynamic programming is not only for networks. To share NN units between several activities, take the activities one at a time.

Stage 1 is the last activity, which takes all the units left. For later stages the value of a state ss is max⁡k(profit(k)+value of the previous stage with s−k units)\max_k\big(\text{profit}(k)+\text{value of the previous stage with }s-k\text{ units}\big).

Keep the columns in the order stage, state, action, value so that each line can be checked from the previous stage.

  1. 1

    Stage 1: the last activity

    takes all the units left in each state

  2. 2

    Stage 2: add the next activity

    try every action k and add its profit to the stage 1 value for s − k units

  3. 3

    Record the best value for each state

    and the action that gave it

  4. 4

    Work back to the full N units

    read off the best total, then trace the actions

Allocating N units: take the activities one at a time.

Stage

  • Activities considered so far

State

  • Units available

Action

  • Units given to the current activity

Value

  • Best total profit from here onwards

Worked example

Three projects and 4 engineers. Project 3 gives 18 for 4 engineers and 14 for 3. Project 2 gives 6 for 1 engineer. What is the value of giving 1 engineer to Project 2 when 4 are available?

With 5 units available, you give 2 to the current activity. How many units does the previous stage have?

Setting out a solution

Define the stages, complete each table before the next, show every action, then trace the route forwards.

A clear layout earns the method marks.

Work backwards from the sink or last activity: complete each stage's table before the next. List each action and its total so a marker sees the minimum, maximum, minimax or maximin chosen.

At the first stage read off the best value, then trace the actions forwards. Quote the final answer in the units of the question.

  1. 1

    Define

    state the stages and what state and action mean

  2. 2

    Work backwards

    complete each stage's table before the next

  3. 3

    Show every action

    list each action and its total

  4. 4

    Read the answer

    at the first stage, then trace the actions forwards

  5. 5

    Conclude

    quote the final answer in the units of the question

Setting out a dynamic programming solution

In which order do you complete the stages?

Try an exam question

A network has arcs SASA 4, SBSB 7, ACAC 6, ADAD 2, BCBC 3, BDBD 5, CTCT 5 and DTDT 8. Use dynamic programming to find the shortest route from SS to TT and its length.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Working backwards from T, what is the shortest distance from A to T?

1 mark, marked against the mark scheme

Revision notes