文件名称：Dynamic Programming in a Generalized Decision Mode
文件大小：25.05MB
文件格式：PDF
更新时间：2022-02-19 15:14:12
算法 DP
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: ffl the Ford-Bellman Strategy for optimal paths in acyclic digraphs, ffl 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