Dynamic programming

Dynamic programming Flashcards

Spec 4.1 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

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⁡(max⁡(arc,next value))\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⁡(min⁡(arc,next value))\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.

Flashcards