Dynamic Programming in a Generalized Decision Model

TitleDynamic Programming in a Generalized Decision Model
Publication TypeTechnical Report
Year of Publication1993
AuthorsHuckenbeck, U.
Other Numbers868

(Pages: 40) We present two dynamic programming strategies for a general class of decision processes. Each of these algorithms includes among others the following graph theoretic optimization algorithms as special cases:-the Ford-Bellman Strategy for optimal paths in acyclic digraphs,-the Greedy Method for optimal forests and spanning trees in undirected graphs.In our general decision model, we define several structural properties of cost measures in order to formulate sufficient conditions for the correctness of our algorithms.Our first algorithm works as fast as the original Ford-Bellman Strategy and the Greedy Method, respectively. Our second algorithm solves a larger class of optimization problems than our first search strategy.

Bibliographic Notes

ICSI Technical Report TR-93-080

Abbreviated Authors

U. Huckenbeck

ICSI Publication Type

Technical Report