Publication Details
Title: Dynamic Programming in a Generalized Decision Model
Author: U. Huckenbeck
Group: ICSI Technical Reports
Date: December 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-080.pdf
Overview:
(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 Information:
ICSI Technical Report TR-93-080
Bibliographic Reference:
U. Huckenbeck. Dynamic Programming in a Generalized Decision Model. ICSI Technical Report TR-93-080, December 1993
Author: U. Huckenbeck
Group: ICSI Technical Reports
Date: December 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-080.pdf
Overview:
(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 Information:
ICSI Technical Report TR-93-080
Bibliographic Reference:
U. Huckenbeck. Dynamic Programming in a Generalized Decision Model. ICSI Technical Report TR-93-080, December 1993