Dynamic programming 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?
- .
- What is a maximin route?
- The smallest arc used is as large as possible.
- Value at a state in a maximin problem?
- .
- 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.