Dynamic Programming in a Generalized Decision Model
| Title | Dynamic Programming in a Generalized Decision Model |
| Publication Type | Technical Report |
| Year of Publication | 1993 |
| Authors | Huckenbeck, U. |
| Other Numbers | 868 |
| Abstract | (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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-080.pdf |
| Bibliographic Notes | ICSI Technical Report TR-93-080 |
| Abbreviated Authors | U. Huckenbeck |
| ICSI Publication Type | Technical Report |