A New Theory of Dynamic Programming.
Paul Helman · Deep Blue (University of Michigan) · 1982
We develop a formal model of enumeration problems and define dynamic programming in its setting. Dynamic programming is then proved to be an optimally efficient class of algorithms. An enumeration problem is a problem whose solution is computed as the product of a finite set of objects, which we call structures. Paths through a graph and ordered binary trees are examples of structures. In most problems the size of the structure space makes a direct computation of the product infeasible. The model allows for the problem to be solved by alternate means. Subproblems are defined, and the concept of comparability is introduced. Solutions to subproblems of comparable structures may be combined, obtaining solutions to larger subproblems. Our notion of comparability generalizes Bellman's principle of optimality. Our model allows for a wide range of decomposition strategies. We identify one class of decomposition computations with dynamic programming; this definition is justified by viewing many classic dynamic programming solutions as members of this class. We then prove the class of dynamic programming computations to be optimally efficient among a large and natural class of computations. This class contains all computations which possess certain desirable properties. Previous models of dynamic programming are based on finite automata, and view problems as requiring the selection of an optimal policy (i.e., sequence of decisions). A major advantage of our model is that it can naturally include in its theory many important and diverse problems. Our model does not require problems to be viewed as sequential decision problems, nor need they be optimization problems. Further, since our model is based on simple algebraic operators, it should be an aid to problem solvers from many disciplines. To demonstrate the power of our model, we view six diverse problems as interpretations: the serial decision process; the traveling salesperson problem; the optimal alphabetic encoding problem; a discrete, decomposable optimization problem; the context free language recognition problem; and a probabilistic circuit problem.