Dynamic Programming.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：4.07M 资料格式：pdf 举报版权申诉

leokan1991-610869-4744302543333667895.pdf-第1页.png

第1页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第2页.png

第2页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第3页.png

第3页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第4页.png

第4页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第5页.png

第5页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第6页.png

第6页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第7页.png

第7页 / 共376页

leokan1991-610869-4744302543333667895.pdf-第8页.png

第8页 / 共376页

文本预览

Art Lew Holger Mauch Dynamic Programming A Computational Tool With 55 Figures and 5 Tables 123

Computer Sciences and Prof. Art Lew Department of Information University of Hawaii at Manoa 1680 East-West Road Honolulu, HI 96822 USA E-mail: artlew@hawaii.edu Dr. Holger Mauch Department of Computer Science Natural Sciences Collegium Eckerd College 4200, 54th Ave. S. Saint Petersburg, FL USA E-mail: mauchh@eckerd.edu 33711 Library of Congress Control Number: 2006930743 ISSN print edition: 1860-949X ISSN electronic edition: 1860-9503 ISBN-10 3-540-37013-7 Springer Berlin Heidelberg New York ISBN-13 978-3-540-37013-0 Springer Berlin Heidelberg New York j j g g p p py g py g y y This work is subject to copyright. All rights are reserved, whether the whole or part of the mate- rial is concerned, specifically the rights of tran slation, reprinting, reuse of illustrations, recita- y y tion, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication ly under the provisions of the y p p German Copyright Law of Septem ber 9, 1965, in its current version, and permission for use p must always be obtained from Springer-Verlag. Violations are liable to prosecution under the German Copyright Law. or parts thereof is permitted on py g py g g g pp pp p p p p g g g g yy p p y gg pp Springer is a part of Springer Science+Business Media springer.com Springer-Verlag Berlin Heidelberg 2007 p gg gg The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. g g p y p y g g p p p p pp g Cover design: deblik, Berlin Typesetting by the authors and SPi Printed dd on acid-ffree paper SPIN: 11550860 d 89/SPi 5 4 3 2 1 0 © ©

To the Bellman Continuum, in memory of Richard Bellman. A.L. To my family. H.M.

Preface Dynamic programming has long been applied to numerous areas in mathe- matics, science, engineering, business, medicine, information systems, bio- mathematics, artiﬁcial intelligence, among others. Applications of dynamic programming have increased as recent advances have been made in areas such as neural networks, data mining, soft computing, and other areas of compu- tational intelligence. The value of dynamic programming formulations and means to obtain their computational solutions has never been greater. This book describes the use of dynamic programming as a computational tool to solve discrete optimization problems. (1) We ﬁrst formulate large classes of discrete optimization problems in dynamic programming terms, speciﬁcally by deriving the dynamic program- ming functional equations (DPFEs) that solve these problems. A text-based language, gDPS, for expressing these DPFEs is introduced. gDPS may be regarded as a high-level speciﬁcation language, not a conventional procedural computer programming language, but which can be used to obtain numerical solutions. (2) We then deﬁne and examine properties of Bellman nets, a class of Petri nets that serves both as a formal theoretical model of dynamic programming problems, and as an internal computer data structure representation of the DPFEs that solve these problems. (3) We also describe the design, implementation, and use of a software tool, called DP2PN2Solver, for solving DPFEs. DP2PN2Solver may be regarded as a program generator, whose input is a DPFE, expressed in the input speciﬁ- cation language gDPS and internally represented as a Bellman net, and whose output is its numerical solution that is produced indirectly by the generation of “solver” code, which when executed yields the desired solution. This book should be of value to diﬀerent classes of readers: students, in- structors, practitioners, and researchers. We ﬁrst provide a tutorial intro- duction to dynamic programming and to Petri nets. For those interested in dynamic programming, we provide a useful software tool that allows them to obtain numerical solutions. For researchers having an interest in the ﬁelds of

VIII Preface dynamic programming and Petri nets, unlike most past work which applies dynamic programming to solve Petri net problems, we suggest ways to apply Petri nets to solve dynamic programming problems. For students and instructors of courses in which dynamic programming is taught, usually as one of many other problem-solving methods, this book provides a wealth of examples that show how discrete optimization problems can be formulated in dynamic programming terms. Dynamic programming has been and continues to be taught as an “art”, where how to use it must be learned by example, there being no mechanical way to apply knowledge of the general principles (e.g., the principle of optimality) to new unfamiliar problems. Experience has shown that the greater the number and variety of problems presented, the easier it is for students to apply general concepts. Thus, one objective of this book is to include many and more diverse examples. A further distinguishing feature of this book is that, for all of these examples, we not only formulate the DP equations but also show their computational solutions, exhibiting computer programs (in our speciﬁcation language) as well as providing as output numerical answers (as produced by the automatically generated solver code). In addition, we provide students and instructors with a software tool (DP2PN2Solver) that enables them to obtain numerical solutions of dynamic programming problems without requiring them to have much computer pro- gramming knowledge and experience. This software tool can be downloaded from either of the following websites: http://natsci.eckerd.edu/∼mauchh/Research/DP2PN2Solver http://www2.hawaii.edu/∼icl/DP2PN2Solver Further information is given in Appendix B. Having such software support allows them to focus on dynamic programming rather than on computer pro- gramming. Since many problems can be solved by diﬀerent dynamic program- ming formulations, the availability of such a computational tool, that makes it easier for readers to experiment with their own formulations, is a useful aid to learning. The DP2PN2Solver tool also enables practitioners to obtain numerical solutions of dynamic programming problems of interest to them without requiring them to write conventional computer programs. Their time, of course, is better spent on problem formulation and analysis than on program design and debugging. This tool allows them to verify that their formulations are correct, and to revise them as may be necessary in their problem solving eﬀorts. The main limitation of this (and any) dynamic programming tool for many practical problems is the size of the state space. Even in this event, the tool may prove useful in the formulation stage to initially test ideas on simpliﬁed scaled-down problems. As a program generator, DP2PN2Solver is ﬂexible, permitting alternate front-ends and back-ends. Inputs other than in the gDPS language are possi- ble. Alternative DPFE speciﬁcations can be translated into gDPS or directly

Preface IX into Bellman nets. Output solver code (i.e., the program that numerically solves a given DPFE) may be in alternative languages. The solver code emphasized in this book is Java code, largely because it is universally and freely available on practically every platform. We also discuss solver codes for spreadsheet systems and Petri net simulators. By default, the automatically generated solver code is hidden from the average user, but it can be inspected and modiﬁed directly by users if they wish. Furthermore, this book describes research into connections between dynamic programming and Petri nets. It was our early research into such connections that ultimately lead to the concept of Bellman nets, upon which the development of our DP2PN2Solver tool is based. We explain here the underlying ideas associated with Bellman nets. Researchers interested in dy- namic programming or Petri nets will ﬁnd many open questions related to this work that suggest avenues of future research. For example, additional research might very likely result in improvements in the DP2PN2Solver tool, such as to address the state-space size issue or to increase its diagnostic capabilities. Every other aspect of this work may beneﬁt from additional research. Thus, we expect the DP2PN2Solver tool described in this book to un- dergo revisions from time to time. In fact, the tool was designed modularly to make it relatively easy to modify. As one example, changes to the gDPS speciﬁcation language syntax can be made by simply revising its BNF deﬁ- nition since we use a compiler-compiler rather than a compiler to process it. Furthermore, alternate input languages (other than gDPS) and solver codes (other than Java) can be added as optional modules, without changing the existing modules. We welcome suggestions from readers on how the tool (or its description) can be improved. We may be contacted at artlew@hawaii.edu or mauchh@eckerd.edu. Updates to the software and to this book, including errata, will be placed on the aforementioned websites. Acknowledgements. The authors wish to thank Janusz Kacprzyk for including this monograph in his ﬁne series of books. His encouragement has been very much appreciated. Honolulu, June 2006, St. Petersburg, June 2006, Art Lew Holger Mauch

Contents Part I Dynamic Programming 1 3 Introduction to Dynamic Programming . . . . . . . . . . . . . . . . . . . . 5 Principles of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . 1.1 6 1.1.1 Sequential Decision Processes . . . . . . . . . . . . . . . . . . . . . 9 1.1.2 Dynamic Programming Functional Equations . . . . . . . . The Elements of Dynamic Programming . . . . . . . . . . . . 11 1.1.3 Application: Linear Search . . . . . . . . . . . . . . . . . . . . . . . . 12 1.1.4 Problem Formulation and Solution . . . . . . . . . . . . . . . . . 14 1.1.5 State Transition Graph Model . . . . . . . . . . . . . . . . . . . . . 17 1.1.6 Staged Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.1.7 Path-States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.1.8 1.1.9 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.1.10 Shortest Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.1.11 All-Pairs Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.1.12 State Space Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.1.13 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.1.14 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.1.15 Probabilistic DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.1.16 Nonoptimization Problems . . . . . . . . . . . . . . . . . . . . . . . . 33 1.1.17 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Computational Solution of DPFEs . . . . . . . . . . . . . . . . . . . . . . . . 34 Solution by Conventional Programming . . . . . . . . . . . . . 35 1.2.1 The State-Decision-Reward-Transformation Table . . . . 36 1.2.2 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.2.3 1.2.4 Spreadsheet Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Example: SPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.2.5 1.2.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.3 Overview of Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.2

XII Contents 2 Applications of Dynamic Programming . . . . . . . . . . . . . . . . . . . . 45 2.1 Optimal Allotment Problem (ALLOT) . . . . . . . . . . . . . . . . . . . . 49 2.2 All-Pairs Shortest Paths Problem (APSP) . . . . . . . . . . . . . . . . . . 50 2.3 Optimal Alphabetic Radix-Code Tree Problem (ARC) . . . . . . . 51 2.4 Assembly Line Balancing (ASMBAL) . . . . . . . . . . . . . . . . . . . . . 52 2.5 Optimal Assignment Problem (ASSIGN) . . . . . . . . . . . . . . . . . . . 54 2.6 Optimal Binary Search Tree Problem (BST) . . . . . . . . . . . . . . . 55 2.7 Optimal Covering Problem (COV) . . . . . . . . . . . . . . . . . . . . . . . 57 2.8 Deadline Scheduling Problem (DEADLINE) . . . . . . . . . . . . . . . . 57 2.9 Discounted Proﬁts Problem (DPP) . . . . . . . . . . . . . . . . . . . . . . . . 58 2.10 Edit Distance Problem (EDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.11 Fibonacci Recurrence Relation (FIB) . . . . . . . . . . . . . . . . . . . . . . 60 2.12 Flowshop Problem (FLOWSHOP) . . . . . . . . . . . . . . . . . . . . . . . . 61 2.13 Tower of Hanoi Problem (HANOI) . . . . . . . . . . . . . . . . . . . . . . . . 62 Integer Linear Programming (ILP) . . . . . . . . . . . . . . . . . . . . . . . . 63 2.14 2.15 Integer Knapsack as ILP Problem (ILPKNAP) . . . . . . . . . . . . . 64 Interval Scheduling Problem (INTVL) . . . . . . . . . . . . . . . . . . . . . 64 2.16 2.17 Inventory Problem (INVENT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.18 Optimal Investment Problem (INVEST) . . . . . . . . . . . . . . . . . . . 67 2.19 Investment: Winning in Las Vegas Problem (INVESTWLV) . . 68 2.20 0/1 Knapsack Problem (KS01) . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.21 COV as KSINT Problem (KSCOV) . . . . . . . . . . . . . . . . . . . . . . . 70 2.22 Integer Knapsack Problem (KSINT) . . . . . . . . . . . . . . . . . . . . . . . 70 2.23 Longest Common Subsequence (LCS) . . . . . . . . . . . . . . . . . . . . . 71 2.24 Optimal Linear Search Problem (LINSRC) . . . . . . . . . . . . . . . . . 73 2.25 Lot Size Problem (LOT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.26 Longest Simple Path Problem (LSP) . . . . . . . . . . . . . . . . . . . . . . 74 2.27 Matrix Chain Multiplication Problem (MCM) . . . . . . . . . . . . . . 75 2.28 Minimum Maximum Problem (MINMAX) . . . . . . . . . . . . . . . . . 75 2.29 Minimum Weight Spanning Tree Problem (MWST) . . . . . . . . . 77 2.30 The Game of NIM (NIM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.31 Optimal Distribution Problem (ODP) . . . . . . . . . . . . . . . . . . . . . 80 2.32 Optimal Permutation Problem (PERM) . . . . . . . . . . . . . . . . . . . 81 2.33 Jug-Pouring Problem (POUR) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.34 Optimal Production Problem (PROD) . . . . . . . . . . . . . . . . . . . . . 83 2.35 Production: Reject Allowances Problem (PRODRAP) . . . . . . . 84 2.36 Reliability Design Problem (RDP) . . . . . . . . . . . . . . . . . . . . . . . . 84 2.37 Replacement Problem (REPLACE) . . . . . . . . . . . . . . . . . . . . . . . 85 2.38 Stagecoach Problem (SCP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 2.39 Seek Disk Scheduling Problem (SEEK) . . . . . . . . . . . . . . . . . . . . 87 2.40 Segmented Curve Fitting Problem (SEGLINE) . . . . . . . . . . . . . 88 2.41 Program Segmentation Problem (SEGPAGE) . . . . . . . . . . . . . . 91 2.42 Optimal Selection Problem (SELECT) . . . . . . . . . . . . . . . . . . . . 94 2.43 Shortest Path in an Acyclic Graph (SPA) . . . . . . . . . . . . . . . . . . 95 2.44 Shortest Path in an Cyclic Graph (SPC) . . . . . . . . . . . . . . . . . . . 95

分享到：

赞收藏

资料库

Dynamic Programming.pdf

相关推荐

课程资源

热门标签

最新资料