Introduction to Dynamic Programming
Dynamic programming is similar to linear programming. Both seek to solve the problem of optimising some quantity – often profit must be maximised. It involves identifying stages and all possible stages and actions within a project. Decisions are made at each stage that optimise the desired quantity, with calculations being carried out that follow from the optimal value from the previous stage.
Calculations out carried out backwards, from the end of the project to the beginning.
Stages, states, actions (along the the arcs) and values on the arcs may be presented in a table. Notice we are working from the right.
Stage | State | Action | Value |
1 | F | FH | 1 |
G | GH | 5 | |
2 | D | DF | 7 |
D | DG | 3 | |
E | EF | 2 | |
EG | 1 | ||
3 | B | BD | 2 |
BE | 1 | ||
C | CD | 2 | |
CE | 5 | ||
4 | A | AB | 5 |
AC | 3 |