E-Book Overview
Incorporating a number of the author’s recent ideas and examples, Dynamic Programming: Foundations and Principles, Second Edition presents a comprehensive and rigorous treatment of dynamic programming. The author emphasizes the crucial role that modeling plays in understanding this area. He also shows how Dijkstra’s algorithm is an excellent example of a dynamic programming algorithm, despite the impression given by the computer science literature. New to the Second Edition Expanded discussions of sequential decision models and the role of the state variable in modeling A new chapter on forward dynamic programming models A new chapter on the Push method that gives a dynamic programming perspective on Dijkstra’s algorithm for the shortest path problem A new appendix on the Corridor method Taking into account recent developments in dynamic programming, this edition continues to provide a systematic, formal outline of Bellman’s approach to dynamic programming. It looks at dynamic programming as a problem-solving methodology, identifying its constituent components and explaining its theoretical basis for tackling problems.
E-Book Content
Dynamic Programming Foundations and Principles Second Edition
DK2356_FM.indd 1
8/2/10 3:17:00 PM
PURE AND APPLIED MATHEMATICS A Program of Monographs, Textbooks, and Lecture Notes
EXECUTIVE EDITORS Earl J. Taft Rutgers University Piscataway, New Jersey
Zuhair Nashed University of Central Florida Orlando, Florida
EDITORIAL BOARD M. S. Baouendi Anil Nerode University of California, Cornell University San Diego Freddy van Oystaeyen Jane Cronin University of Antwerp, Rutgers University Belgium Jack K. Hale Donald Passman Georgia Institute of Technology University of Wisconsin, S. Kobayashi Madison University of California, Fred S. Roberts Berkeley Rutgers University Marvin Marcus David L. Russell University of California, Virginia Polytechnic Institute Santa Barbara and State University W. S. Massey Walter Schempp Yale University Universität Siegen
DK2356_FM.indd 2
8/2/10 3:17:00 PM
MONOGRAPHS AND TEXTBOOKS IN PURE AND APPLIED MATHEMATICS Recent Titles A. B. Kharazishvili, Strange Functions in Real Analysis, Second Edition (2006) Vincenzo Ancona and Bernard Gaveau, Differential Forms on Singular Varieties: De Rham and Hodge Theory Simplified (2005) Santiago Alves Tavares, Generation of Multivariate Hermite Interpolating Polynomials (2005) Sergio Macías, Topics on Continua (2005) Mircea Sofonea, Weimin Han, and Meir Shillor, Analysis and Approximation of Contact Problems with Adhesion or Damage (2006) Marwan Moubachir and Jean-Paul Zolésio, Moving Shape Analysis and Control: Applications to Fluid Structure Interactions (2006) Alfred Geroldinger and Franz Halter-Koch, Non-Unique Factorizations: Algebraic, Combinatorial and Analytic Theory (2006) Kevin J. Hastings, Introduction to the Mathematics of Operations Research with Mathematica®, Second Edition (2006) Robert Carlson, A Concrete Introduction to Real Analysis (2006) John Dauns and Yiqiang Zhou, Classes of Modules (2006) N. K. Govil, H. N. Mhaskar, Ram N. Mohapatra, Zuhair Nashed, and J. Szabados, Frontiers in Interpolation and Approximation (2006) Luca Lorenzi and Marcello Bertoldi, Analytical Methods for Markov Semigroups (2006) M. A. Al-Gwaiz and S. A. Elsanousi, Elements of Real Analysis (2006) Theodore G. Faticoni, Direct Sum Decompositions of Torsion-Free Finite Rank Groups (2007) R. Sivaramakrishnan, Certain Number-Theoretic Episodes in Algebra (2006) Aderemi Kuku, Representation Theory and Higher Algebraic K-Theory (2006) Robert Piziak and P. L. Odell, Matrix Theory: From Generalized Inverses to Jordan Form (2007) Norman L. Johnson, Vikram Jha, and Mauro Biliotti, Handbook of Finite Translation Planes (2007) Lieven Le Bruyn, Noncommutative Geometry and Cayley-smooth