下载  >  课程资源  >  讲义  > 105.Dynamic Programming

105.Dynamic Programming 评分:

a good textbook for dynamic programming and describe a lot of useful method
PURE AND APPLIED MATHEMATICS A Program of MonographS, TextbookS, and Lecture Notes Eⅹ ECUTIVE EDITORS Earl J. Taft Zuhair mashed Rutgers University University of Central florida Piscataway, New Jersey 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 Universitat Siegen 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 Macias, 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 Zolesio, 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 Washed, 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) eodore 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 Orders(2008) Fritz Schwarz, Algorithmic Lie Theory for Solving Ordinary Differential Equations(2008) Jane Cronin, Ordinary Differential Equations: Introduction and Qualitative Theory, Third Edition(2008 Su Gao, Invariant Descriptive Set Theory(2009) Christopher Apelian and Steve Surace, Real and Complex Analysis(2010) Norman L. Johnson, Combinatorics of Spreads and Parallelisms (2010 Lawrence Narici and Edward Beckenstein, Topological Vector Spaces, Second Edition(2010) Moshe Sniedovich, Dynamic Programming: Foundations and Principles, Second Edition (2010) Dynamic Programming Foundations and principles Second edition Moshe sniedovich University of Melbourne Melbourne, austra CRC) CRC Press Taylor Francis group Boca Raton London New york RC Press is an imprint of the Taylor Francis Group, an informa business A ChaPMaN hall book CRC Press Taylor Francis Group 6000 Broken Sound Parkway nw, suite 300 Boca raton, Fl 33487-2742 o 2011 by Taylor and Francis Group, LLC CRC Press is an imprint of Taylor Francis group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10987654 International Standard Book Number-13: 978-1-4200-1463-1(Ebook-PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,trans mitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers Forpermissiontophotocopyorusematerialelectronicallyfromthisworkpleaseaccesswww.copyright. com(http://www.copyright.com/)orcontacttheCopyrightcLearanceCenter,Inc.(ccc),222Rosewood Drive, Danvers, MAO1923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe Visit the taylor Francis Web site at http://www.taylorandfrancis.com and the crc press web site at http://www.crcpress.com P reface(first edition) I started entertaining the idca of writing a book on dynamic programming when I first realized that in contrast to, say, linear programming, there seems to be a gentlemen's disagreement as to what exactly dynamic programming is. Obviously, T envisioned a text that would offer a conclusive and incon- testable formulation of dynamic programming. But I soon discovered that dynamic programming actually invites a certain amount of disagreement with respect to its definition because, by its very nature, it can be approached from a variety of angles depending on one's approach to modeling analysis and problem solving. We thus find the intuitionist at one end, the formalist at the other. and the rest somewhere in between. So in this book i examine the question what is dymamic programming? knowing full well that whatever answer one formulates, by necessity it will be subjective in nature This book does not ain to portray dynamic programining as a practical tool. It does not examine how dynamic programming solves real-world prob- lems in inventory, scheduling, sport and recreation, expert systems etc. The book aims to give a portrait of dynamic programming as a methodology to identify its constituent components, explain how it looks at problems and describe how it proposes to tackle them. It should therefore appeal to readers in academia as well as to practitioners who have an interest in this facet of dynamic programming It should be of particular interest lo readers who leach dynarnic prO- gramming, as in my view, this book offers a refreshing supplement to texts which present dynamic programming from the conventional standpoint of Learn,Teach Dynanic Pyoyr'aTrerning by Esarmple. These readers are advised that, although the book is not designed to serve as a course-text, because it is sclf-containcd it can bc uscd as ancillary reading for graduatc and advanccd undergraduate courses in dynamic programming As for my method of probing the topic; although I fully recognize that certain aspects of dynamic programming are probably best suited for a non- formal treatment, my exposition throughout this book is strictly formal Still, the mathematical knowledge required for following the presentation minimal- calculus, set theory and some optimization theory, all at the elementary level. The book does demand, however, mathematical maturity which comes into play more in modelling and formulation than in analysis I would like to thank my colleagues and graduate students for their helpful cOllinents and constructive crilicisIn on various drafts ol the manuscript.I am particularly grateful to Alleli Domingo, Emmanuel Macalalag and Steven 11 Ostrover for their comments on the final draft. I thank Ruth Dawe and Henry Bochm from Marcel Dckkor Inc. for their encouragement, patience and support. And finally, special Chanks are due to my wile, Shoshana, for her major contribution to this bool Substantial work on this book was done when i was with the nation Research Institute for Mathematical Sciences of the CSiR, Pretoria, South Afri oshe snegov Melbourn e June 1991 P reface(second edition) In the intervening years since the publication of the first edition of this book in 1992, I continued working on various aspects of dynamic programming and the results of this research appeared in a number of publications. So when i was approached by the publisher with the suggestion to consider a second edition of this book, I decided to take up the oller realizing Chat a second edition should provide me with an opportunity to enhance certain chapters in the first edition with the material (ideas, examples, etc. ) that I had developed in more recent years. I was particularly keen to revisit a topic that I consider crucial for a good understanding of dynamic programming, namely Modeling And so, I expanded Che discussions on sequential decision nodels and che dynamic programming modcls,ng, ar role of the state variable in modeling, and I added a new chapter on forward I also added a new chapter where i discuss the Pash method -also known as Reaching- and I give a dynamic programming perspective on Dijkstras algorithm for the shortest path problem. My main objective in including this discussion on Dijkstra's algorithm is to make it abundantly clear that in spite of the impression given by the computer science literature--thi gorithm is in fact a dynamic programming algorithm par excellence Thus, apart from slight modifications in the contents of existing chapters the major revisions are as follows igIn Chapter 10: R.cfincmcnts Chapter ll: The State w chap Chapter 14: FC er 15: Push ew append Appendix e: The C As for the book's ncw titlo With hindsight, it seems to me that this should have been the book's title in ils lirst edition! The new title, I subinil, captures Inore faithfully the goal that I had set out to accomplish in writing this book, which as I indicated

2018-11-02 上传 大小:2.97MB
举报 收藏