Power Programming

Dynamic Programming

Volume 5, Issue 4
Fall 1995

This is the first in a series of columns on advanced programming techniques and algorithms. This issue's column discusses dynamic programming, a powerful algorithmic scheme for solving discrete optimization problems. We illustrate the concepts with the generation of Fibonacci numbers, and then present two nontrivial examples, optimal matrix-chain multiplication and multiple-class mean value analysis of queueing networks. This last example applies the technique to a queueing-theory problem that was solved in a very different way by A.O. Allen and G. Hynes in volume 1, issue 3 of this journal.
 

View this article as a PDF