Bellman's Principle (Leaving Cert Applied Maths): Flashcards
📚Flashcards
Practise the cards
15 cards from this deck
ShowHide
Practise the cards
15 cards from this deck
Bellman's Principle of Optimality
Bellman's Principle of Optimality
If optimal path is A→C through B, then B→C is also optimal (optimal paths contain optimal sub-paths)
Multi-stage network
Multi-stage network
Graph with nodes organised into distinct stages or levels
Purpose of multi-stage networks
Purpose of multi-stage networks
Solving sequential decision problems
Source node (S)
Source node (S)
Starting point of the journey
Sink node (T)
Sink node (T)
Final destination
Why stages numbered in reverse order
Why stages numbered in reverse order
To use backward induction from destination to source
Backward induction
Backward induction
Start calculations from destination and work backwards
Four columns in dynamic programming table
Four columns in dynamic programming table
Stage, State, Action, Value
Stage column in DP table
Stage column in DP table
Stage number (reverse from destination to source)
State column in DP table
State column in DP table
Current node or position
Action column in DP table
Action column in DP table
Possible moves or edges from this state
Value column in DP table
Value column in DP table
Optimal value from this state to destination
Direction to solve multi-stage network problems
Direction to solve multi-stage network problems
Work backwards from destination
Calculate value at intermediate stage
Calculate value at intermediate stage
Edge weight optimal value from destination node
Value calculation at terminal stage
Value calculation at terminal stage
Weight of edge connecting to T