In which order are the stages worked?

Backwards: start with the stage nearest the sink and work to the source.

What is the state variable?

What is known at the start of a stage, such as the vertex or the number of units left.

The decision made at a state, such as the next vertex or the number of units used.

What columns does a dynamic programming table have?

Stage, state, action and value.

Value at a state in a minimum route problem?

Minimum over actions of (arc length + value of next state).

Value at a state in a maximum route problem?

Maximum over actions of (arc length + value of next state).

What is a minimax route?

The largest arc used is as small as possible.

Value at a state in a minimax problem?

\min\big(\max(arc,next value)\big).

What is a maximin route?

The smallest arc used is as large as possible.

Value at a state in a maximin problem?

\max\big(\min(arc,next value)\big).

Why does choosing the shortest next arc at each step not work?

The shortest next arc may lead to a long remaining route; dynamic programming checks every action.

Dynamic programmingEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is Bellman's principle of optimality?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What is Bellman's principle of optimality?: Any part of an optimal route is itself an optimal route between its end points.
In which order are the stages worked?: Backwards: start with the stage nearest the sink and work to the source.
What is the state variable?: What is known at the start of a stage, such as the vertex or the number of units left.
What is the action?: The decision made at a state, such as the next vertex or the number of units used.
What columns does a dynamic programming table have?: Stage, state, action and value.
Value at a state in a minimum route problem?: Minimum over actions of (arc length + value of next state).
Value at a state in a maximum route problem?: Maximum over actions of (arc length + value of next state).
What is a minimax route?: The largest arc used is as small as possible.
Value at a state in a minimax problem?: $\min\big(\max(\text{arc},\text{next value})\big)$ .
What is a maximin route?: The smallest arc used is as large as possible.
Value at a state in a maximin problem?: $\max\big(\min(\text{arc},\text{next value})\big)$ .
Why does choosing the shortest next arc at each step not work?: The shortest next arc may lead to a long remaining route; dynamic programming checks every action.

Exam questions on Dynamic programming

A network of roads joins S to T through junctions A, B, C and D. The roads and their lengths, in km, are: SA 5, SB 3, AC 4, AD 7, BC 6, BD 2, CT 5 and DT 6. Dynamic programming is used to find the shortest route from S to T, working backwards from T. Stage 1 is the final step into T (from C or D), stage 2 is the step from A or B, and stage 3 is the step from S. The state is the vertex and the action is the next vertex.
Given that the shortest distance from A to T is $9$ km, complete the dynamic programming to find the shortest route from S to T and its length.2 marks
Messages are sent from S to T through routers A, B, C and D. The speed of a link is its capacity in Mbps, and the speed of a route is the speed of its slowest link. The links and capacities are: SA 8, SB 6, AC 4, AD 7, BC 9, BD 4, CT 6 and DT 5. The manager wants a route whose speed is as large as possible and uses dynamic programming, working backwards from T.
Given that the best speed from A to T is $5$ Mbps, complete the dynamic programming to find the best route from S to T and its speed.2 marks
A firm has 5 engineers to share between three projects, and all five must be used. The profit, in £ thousand, when a project is given 0, 1, 2, 3, 4 or 5 engineers is: Project 1: 0, 7, 9, 10, 11, 17. Project 2: 0, 6, 9, 13, 15, 16. Project 3: 0, 1, 7, 14, 18, 25. The firm uses dynamic programming to maximise the total profit. Stage 1 is Project 3, stage 2 is Projects 2 and 3 together, and stage 3 is all three projects. The state is the number of engineers available at that stage and the action is the number given to the project being considered.
Find the value of the best allocation of 4 engineers to Projects 2 and 3 together, and say how many go to Project 2, showing the options you compare.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).