Definition:Dynamic Programming
Definition
Dynamic programming is a method of solving problems of optimization in operations research where a step-wise approach to decision making is appropriate.
 | This article is complete as far as it goes, but it could do with expansion. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Expand}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Examples
Arbitrary Example
The following diagram represents the problem of minimizing the fare for a $3$-stage bus journey from $A$ to $D$:
$B_1$, $B_2$ and $B_3$ are the possible end points of the first stage of the journey.
$C_1$ and $C_2$ are the possible end points of the second stage of the journey.
The number on each line represents the bus fare for that route.
The problem is to find the route from $A$ to $D$ which has the lowest fare.
The dynamic programming approach first finds the optimum one-stage strategy for the final (third) stage, from either $C_1$ or $C_2$ to $D$.
This is trivially found to be $C_2$, as there is only one route from each.
The next step is to find the optimum two-stage strategy from $B_1$, $B_2$ and $B_3$ to $D$.
Here it can be found by inspection that:
- from $B_1$ to $D$, $C_1$ is the optimal route, which costs $7$, as opposed to $10$ via $C_2$
- from $B_2$ to $D$, $C_1$ is the optimal route, which costs $11$, as opposed to $12$ via $C_2$
- from $B_3$ to $D$, $C_2$ is the optimal route, which costs $13$, as opposed to $19$ via $C_1$.
Now we note that no matter how many additional earlier stages we add, the above routes are always optimal once we have arrived at one of $B_1$, $B_2$ and $B_3$.
Hence we see that from $A$, the three-stage total fare is:
- via $B_1$: $10 + 7 = 17$
- via $B_2$: $5 + 11 = 16$
- via $B_3$: $5 + 13 = 18$.
Hence the optimum route is via $B_2$ and $C_1$.
Also see
- Results about dynamic programming can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): dynamic programming
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): dynamic programming