具体描述
Focusing on the modeling and solution of deterministic multistage decision problems, this book looks at dynamic programming as a problem-solving optimization method. With over 400 useful references, this edition discusses the dynamic programming analysis of a problem, illustrates the rationale behind this analysis, and clarifies the theoretical grounds that justify the rationale. It also explains the meaning and role of the concept of state in dynamic programming, examines the purpose and function of the principle of optimality, and outlines solution strategies for problems defiant of conventional treatment.
《算法艺术：动态规划的优雅之道》 在纷繁复杂的计算世界里，总有一些问题，其优雅的解决方案潜藏在层层递进的推理之中。本书《算法艺术：动态规划的优雅之道》正是探索这类问题的指南，它带领读者深入理解一种强大而精妙的算法范式——动态规划。 动态规划并非一项孤立的技能，而是一种思维方式，一种将宏大挑战分解为一系列更小、可管理子问题，并通过巧妙地存储和重用子问题解决方案来高效求解最终问题的艺术。本书将从最基础的概念入手，逐步揭示动态规划的内在逻辑和核心思想。我们将深入剖析“最优子结构”和“重叠子问题”这两个动态规划的基石，理解它们如何赋予算法以无与伦比的效率。 本书的结构设计旨在循序渐进，确保读者能够扎实地掌握每一个概念。我们不会直接抛出复杂的例子，而是从简单易懂的问题出发，例如经典的斐波那契数列计算、硬币找零问题，一步步引导读者领略动态规划的魅力。通过这些基础案例，读者将学会如何识别问题中的子结构，如何定义状态转移方程，以及如何选择合适的存储方式（如表格或数组）来保存中间结果。 随着理解的加深，我们将进阶到更具挑战性的问题。本书将涵盖一系列在计算机科学、运筹学、生物信息学等领域中具有广泛应用的动态规划典型问题，例如： 背包问题系列： 从0/1背包到多重背包，再到完全背包，我们将逐一解析它们的特点，并展示如何运用动态规划来解决资源分配和最优选择的难题。 最长公共子序列 (LCS) 与编辑距离： 这两个问题在文本比对、生物序列分析等领域至关重要。我们将详细讲解如何利用动态规划高效地找出字符串之间的相似性。 矩阵链乘法： 优化计算顺序，避免不必要的乘法开销，这不仅是一个理论问题，在实际的编译器设计和高性能计算中也有着重要的应用。 图论中的动态规划应用： 如最短路径问题（Bellman-Ford算法的动态规划思想）、最小生成树的某些变种等，展现动态规划在图算法中的强大威力。 组合优化问题： 许多NP-hard问题虽然无法在多项式时间内得到精确解，但动态规划的某些思想仍能为近似算法或特定规模问题提供有效的解决方案。 本书的讲解风格强调“理解”而非“记忆”。每一个动态规划的解法都将被细致地剖析，包括： 1. 问题定义与分析： 清晰地阐述问题的背景和目标。 2. 识别最优子结构： 如何从整体最优推导出局部最优。 3. 定义状态： 确定用什么变量来表示子问题的解。 4. 建立状态转移方程： 找出不同子问题解之间的递推关系。 5. 确定边界条件： 给出最简单的子问题的直接解。 6. 实现方法： 分别讲解自顶向下（带备忘录的递归）和自底向上（迭代）两种实现方式，并讨论它们的优劣。 7. 复杂度分析： 严格分析算法的时间复杂度和空间复杂度。 此外，本书还将提供丰富的练习题，涵盖从入门到精通的各个难度级别。这些练习题的设计旨在巩固所学知识，并鼓励读者将动态规划的思想应用于解决新的、未曾谋面的问题。我们相信，通过动手实践，读者将能够真正内化动态规划的精髓。 《算法艺术：动态规划的优雅之道》不仅是一本技术手册，更是一次思维的旅程。它旨在培养读者分析复杂问题、设计高效算法的能力。无论您是计算机科学专业的学生，还是希望提升算法能力的软件工程师，亦或是对解决实际问题充满热情的算法爱好者，本书都将是您不可或缺的伙伴，助您掌握这门强大的算法艺术。通过本书的学习，您将能够以一种全新的视角审视计算世界，并发现隐藏在问题背后的优雅解决方案。
作者简介
目录信息
Contents
1 Introduction 1
1.1 Welcome to Dynamic Programming! . . . . . . . . . . . . . 2
1.2 How to Read This Book . . . . . . . . . . . . . . . . . . . . 6
I Science 9
2 Fundamentals 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Meta-Recipe Revisited . . . . . . . . . . . . . . . . . . . . . 13
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Decomposition of the Solution Set . . . . . . . . . . . . . . . 16
2.5 Principle of Conditional Optimization . . . . . . . . . . . . 17
2.6 Conditional Problems . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 19
2.8 Solution Procedure . . . . . . . . . . . . . . . . . . . . . . . 19
2.9 Time Out: Direct Enumeration! . . . . . . . . . . . . . . . . 21
2.10 Equivalent Conditional Problems . . . . . . . . . . . . . . . 22
2.11 Modified Problems . . . . . . . . . . . . . . . . . . . . . . . 24
2.12 The Role of a Decomposition Scheme . . . . . . . . . . . . . 26
2.13 Dynamic Programming Problem — Revisited . . . . . . . . 30
2.14 Trivial Decomposition Scheme . . . . . . . . . . . . . . . . . 32
2.15 Summary and a Look Ahead . . . . . . . . . . . . . . . . . . 33
3 Multistage Decision Model 35
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 A Prototype Multistage Decision Model . . . . . . . . . . . 37
3.3 Problem vs Problem Formulation . . . . . . . . . . . . . . . 41
3.4 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Markovian Policies . . . . . . . . . . . . . . . . . . . . . . . 52
3.6 Remarks on the Notation . . . . . . . . . . . . . . . . . . . 54
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 56
4 Dynamic Programming — An Outline 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Markovian Decomposition Scheme . . . . . . . . . . . . . . 64
4.4 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Dynamic Programming Problems . . . . . . . . . . . . . . . 70
4.6 The Final State Model . . . . . . . . . . . . . . . . . . . . . 75
4.7 Principle of Optimality . . . . . . . . . . . . . . . . . . . . . 81
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Solution Methods 85
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2 Additive Functional Equations . . . . . . . . . . . . . . . . . 87
5.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 88
5.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 101
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6 Successive Approximation Methods 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4 Functional Equations of Type One . . . . . . . . . . . . . . 121
6.5 Functional Equations of Type Two . . . . . . . . . . . . . . 125
6.6 Truncation Method . . . . . . . . . . . . . . . . . . . . . . . 131
6.7 Stationary Models . . . . . . . . . . . . . . . . . . . . . . . 135
6.8 Truncation and Successive Approximation . . . . . . . . . . 139
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 144
7 Optimal Policies 145
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 146
7.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 150
7.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 156
7.5 Successive Approximation in the Policy Space . . . . . . . . 165
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 168
8 The Curse of Dimensionality 169
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.3 Discrete Problems . . . . . . . . . . . . . . . . . . . . . . . . 173
8.4 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.5 Complete Enumeration . . . . . . . . . . . . . . . . . . . . . 179
8.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9 The Rest Is Mathematics and Experience 183
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.2 Choice of Model . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.3 Dynamic Programming Models . . . . . . . . . . . . . . . . 185
9.4 Forward Decomposition Models . . . . . . . . . . . . . . . . 188
9.5 Practice What You Preach! . . . . . . . . . . . . . . . . . . 189
9.6 Computational Schemes . . . . . . . . . . . . . . . . . . . . 190
9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.8 Dynamic Programming Software . . . . . . . . . . . . . . . 193
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
II Art 195
10 Refinements 197
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
10.2 Weak-Markovian Condition . . . . . . . . . . . . . . . . . . 198
10.3 Markovian Formulations . . . . . . . . . . . . . . . . . . . . 204
10.4 Decomposition Schemes . . . . . . . . . . . . . . . . . . . . 206
10.5 Sequential Decision Models . . . . . . . . . . . . . . . . . . 218
10.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.7 Shortest Path Model . . . . . . . . . . . . . . . . . . . . . . 247
10.8 The Art of Dynamic Programming Modeling . . . . . . . . . 257
10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 259
11 The State 261
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 262
11.3 Mathematically Speaking . . . . . . . . . . . . . . . . . . . . 271
11.4 Decomposition Revisited . . . . . . . . . . . . . . . . . . . . 285
11.5 Infeasible States and Decisions . . . . . . . . . . . . . . . . . 291
11.6 State Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 294
11.7 Nodes as States . . . . . . . . . . . . . . . . . . . . . . . . . 304
11.8 Multistage vs Sequential Models . . . . . . . . . . . . . . . . 311
11.9 Models vs Functional Equations . . . . . . . . . . . . . . . . 313
11.10 Easy Problems . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.11 Modeling Tips . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.12 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 330
11.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
12 Parametric Schemes 333
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
12.2 Background and Motivation . . . . . . . . . . . . . . . . . . 334
12.3 Fractional Programming Scheme . . . . . . . . . . . . . . . 339
12.4 C-programming Scheme . . . . . . . . . . . . . . . . . . . . 344
12.5 Lagrange Multiplier Scheme . . . . . . . . . . . . . . . . . . 352
12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 356
13 The Principle of Optimality 357
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
13.2 Bellman’s Principle of Optimality . . . . . . . . . . . . . . . 362
13.3 Prevailing Interpretation . . . . . . . . . . . . . . . . . . . . 364
13.4 Variations on a Theme . . . . . . . . . . . . . . . . . . . . . 366
13.5 Criticism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.6 So What Is Amiss? . . . . . . . . . . . . . . . . . . . . . . . 370
13.7 The Final State Model Revisited . . . . . . . . . . . . . . . 370
13.8 Bellman’s Treatment of Dynamic Programming . . . . . . . 372
13.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
13.10 Post Script: Pontryagin’s Maximum Principle . . . . . . . . 377
14 Forward Decomposition 381
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
14.2 Function Decomposition . . . . . . . . . . . . . . . . . . . . 384
14.3 Initial Problem . . . . . . . . . . . . . . . . . . . . . . . . . 398
14.4 Separable Objective Functions Revisited . . . . . . . . . . . 398
14.5 Modified Problems Revisited . . . . . . . . . . . . . . . . . . 400
14.6 Backward Conditional Problems Revisited . . . . . . . . . . 403
14.7 Markovian Condition Revisited . . . . . . . . . . . . . . . . 404
14.8 Forward Functional Equation . . . . . . . . . . . . . . . . . 405
14.9 Impact on the State Space . . . . . . . . . . . . . . . . . . . 405
14.10 Anomaly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
14.11 Pathologic Cases . . . . . . . . . . . . . . . . . . . . . . . . 414
14.12 Summary and Conclusions . . . . . . . . . . . . . . . . . . . 416
14.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 417
15 Push! 419
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
15.2 The Pull Method . . . . . . . . . . . . . . . . . . . . . . . . 422
15.3 The Push Method . . . . . . . . . . . . . . . . . . . . . . . . 427
15.4 Monotone Accumulated Return Processes . . . . . . . . . . 434
15.5 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 441
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
15.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 449
III Epilogue 451
16 What Then Is Dynamic Programming? 453
16.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
16.2 Non-Optimization Problems . . . . . . . . . . . . . . . . . . 457
16.3 An Abstract Dynamic Programming Model . . . . . . . . . 459
16.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
16.5 The Towers of Hanoi Problem . . . . . . . . . . . . . . . . . 476
16.6 Optimization-Free Dynamic Programming . . . . . . . . . . 482
16.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 484
IV Appendices 487
A Contraction Mapping 489
A.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.2 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.3 Contraction in the Functional Space . . . . . . . . . . . . . 492
A.4 Contraction in the Domain Space . . . . . . . . . . . . . . . 494
A.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 502
B Fractional Programming 503
B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
B.2 Dinkelbach’s Algorithm . . . . . . . . . . . . . . . . . . . . . 504
B.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 509
C Composite Concave Programming 511
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
C.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 513
C.3 Pseudolinear Problems . . . . . . . . . . . . . . . . . . . . . 516
C.4 Convex Problems . . . . . . . . . . . . . . . . . . . . . . . . 519
C.5 One-Dimensional Convex Additive Problems . . . . . . . . . 525
D The Principle of Optimality in Stochastic Processes 529
D.1 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 529
D.2 Common Interpretation of the Principle . . . . . . . . . . . 531
D.3 Principle of Optimality (stochastic models) . . . . . . . . . 533
D.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
D.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 534
E The Corridor Method 535
E.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
E.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 536
E.3 Example: TSP . . . . . . . . . . . . . . . . . . . . . . . . . . 537
E.4 Generating Corridors . . . . . . . . . . . . . . . . . . . . . . 540
E.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 547
Bibliography 549
Index 595
· · · · · · (收起)
1 Introduction 1
1.1 Welcome to Dynamic Programming! . . . . . . . . . . . . . 2
1.2 How to Read This Book . . . . . . . . . . . . . . . . . . . . 6
I Science 9
2 Fundamentals 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Meta-Recipe Revisited . . . . . . . . . . . . . . . . . . . . . 13
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Decomposition of the Solution Set . . . . . . . . . . . . . . . 16
2.5 Principle of Conditional Optimization . . . . . . . . . . . . 17
2.6 Conditional Problems . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 19
2.8 Solution Procedure . . . . . . . . . . . . . . . . . . . . . . . 19
2.9 Time Out: Direct Enumeration! . . . . . . . . . . . . . . . . 21
2.10 Equivalent Conditional Problems . . . . . . . . . . . . . . . 22
2.11 Modified Problems . . . . . . . . . . . . . . . . . . . . . . . 24
2.12 The Role of a Decomposition Scheme . . . . . . . . . . . . . 26
2.13 Dynamic Programming Problem — Revisited . . . . . . . . 30
2.14 Trivial Decomposition Scheme . . . . . . . . . . . . . . . . . 32
2.15 Summary and a Look Ahead . . . . . . . . . . . . . . . . . . 33
3 Multistage Decision Model 35
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 A Prototype Multistage Decision Model . . . . . . . . . . . 37
3.3 Problem vs Problem Formulation . . . . . . . . . . . . . . . 41
3.4 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Markovian Policies . . . . . . . . . . . . . . . . . . . . . . . 52
3.6 Remarks on the Notation . . . . . . . . . . . . . . . . . . . 54
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 56
4 Dynamic Programming — An Outline 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Markovian Decomposition Scheme . . . . . . . . . . . . . . 64
4.4 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Dynamic Programming Problems . . . . . . . . . . . . . . . 70
4.6 The Final State Model . . . . . . . . . . . . . . . . . . . . . 75
4.7 Principle of Optimality . . . . . . . . . . . . . . . . . . . . . 81
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Solution Methods 85
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2 Additive Functional Equations . . . . . . . . . . . . . . . . . 87
5.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 88
5.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 101
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6 Successive Approximation Methods 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4 Functional Equations of Type One . . . . . . . . . . . . . . 121
6.5 Functional Equations of Type Two . . . . . . . . . . . . . . 125
6.6 Truncation Method . . . . . . . . . . . . . . . . . . . . . . . 131
6.7 Stationary Models . . . . . . . . . . . . . . . . . . . . . . . 135
6.8 Truncation and Successive Approximation . . . . . . . . . . 139
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 144
7 Optimal Policies 145
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 146
7.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 150
7.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 156
7.5 Successive Approximation in the Policy Space . . . . . . . . 165
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 168
8 The Curse of Dimensionality 169
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.3 Discrete Problems . . . . . . . . . . . . . . . . . . . . . . . . 173
8.4 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.5 Complete Enumeration . . . . . . . . . . . . . . . . . . . . . 179
8.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9 The Rest Is Mathematics and Experience 183
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.2 Choice of Model . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.3 Dynamic Programming Models . . . . . . . . . . . . . . . . 185
9.4 Forward Decomposition Models . . . . . . . . . . . . . . . . 188
9.5 Practice What You Preach! . . . . . . . . . . . . . . . . . . 189
9.6 Computational Schemes . . . . . . . . . . . . . . . . . . . . 190
9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.8 Dynamic Programming Software . . . . . . . . . . . . . . . 193
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
II Art 195
10 Refinements 197
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
10.2 Weak-Markovian Condition . . . . . . . . . . . . . . . . . . 198
10.3 Markovian Formulations . . . . . . . . . . . . . . . . . . . . 204
10.4 Decomposition Schemes . . . . . . . . . . . . . . . . . . . . 206
10.5 Sequential Decision Models . . . . . . . . . . . . . . . . . . 218
10.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.7 Shortest Path Model . . . . . . . . . . . . . . . . . . . . . . 247
10.8 The Art of Dynamic Programming Modeling . . . . . . . . . 257
10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 259
11 The State 261
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 262
11.3 Mathematically Speaking . . . . . . . . . . . . . . . . . . . . 271
11.4 Decomposition Revisited . . . . . . . . . . . . . . . . . . . . 285
11.5 Infeasible States and Decisions . . . . . . . . . . . . . . . . . 291
11.6 State Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 294
11.7 Nodes as States . . . . . . . . . . . . . . . . . . . . . . . . . 304
11.8 Multistage vs Sequential Models . . . . . . . . . . . . . . . . 311
11.9 Models vs Functional Equations . . . . . . . . . . . . . . . . 313
11.10 Easy Problems . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.11 Modeling Tips . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.12 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 330
11.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
12 Parametric Schemes 333
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
12.2 Background and Motivation . . . . . . . . . . . . . . . . . . 334
12.3 Fractional Programming Scheme . . . . . . . . . . . . . . . 339
12.4 C-programming Scheme . . . . . . . . . . . . . . . . . . . . 344
12.5 Lagrange Multiplier Scheme . . . . . . . . . . . . . . . . . . 352
12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 356
13 The Principle of Optimality 357
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
13.2 Bellman’s Principle of Optimality . . . . . . . . . . . . . . . 362
13.3 Prevailing Interpretation . . . . . . . . . . . . . . . . . . . . 364
13.4 Variations on a Theme . . . . . . . . . . . . . . . . . . . . . 366
13.5 Criticism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.6 So What Is Amiss? . . . . . . . . . . . . . . . . . . . . . . . 370
13.7 The Final State Model Revisited . . . . . . . . . . . . . . . 370
13.8 Bellman’s Treatment of Dynamic Programming . . . . . . . 372
13.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
13.10 Post Script: Pontryagin’s Maximum Principle . . . . . . . . 377
14 Forward Decomposition 381
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
14.2 Function Decomposition . . . . . . . . . . . . . . . . . . . . 384
14.3 Initial Problem . . . . . . . . . . . . . . . . . . . . . . . . . 398
14.4 Separable Objective Functions Revisited . . . . . . . . . . . 398
14.5 Modified Problems Revisited . . . . . . . . . . . . . . . . . . 400
14.6 Backward Conditional Problems Revisited . . . . . . . . . . 403
14.7 Markovian Condition Revisited . . . . . . . . . . . . . . . . 404
14.8 Forward Functional Equation . . . . . . . . . . . . . . . . . 405
14.9 Impact on the State Space . . . . . . . . . . . . . . . . . . . 405
14.10 Anomaly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
14.11 Pathologic Cases . . . . . . . . . . . . . . . . . . . . . . . . 414
14.12 Summary and Conclusions . . . . . . . . . . . . . . . . . . . 416
14.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 417
15 Push! 419
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
15.2 The Pull Method . . . . . . . . . . . . . . . . . . . . . . . . 422
15.3 The Push Method . . . . . . . . . . . . . . . . . . . . . . . . 427
15.4 Monotone Accumulated Return Processes . . . . . . . . . . 434
15.5 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 441
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
15.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 449
III Epilogue 451
16 What Then Is Dynamic Programming? 453
16.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
16.2 Non-Optimization Problems . . . . . . . . . . . . . . . . . . 457
16.3 An Abstract Dynamic Programming Model . . . . . . . . . 459
16.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
16.5 The Towers of Hanoi Problem . . . . . . . . . . . . . . . . . 476
16.6 Optimization-Free Dynamic Programming . . . . . . . . . . 482
16.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 484
IV Appendices 487
A Contraction Mapping 489
A.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.2 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.3 Contraction in the Functional Space . . . . . . . . . . . . . 492
A.4 Contraction in the Domain Space . . . . . . . . . . . . . . . 494
A.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 502
B Fractional Programming 503
B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
B.2 Dinkelbach’s Algorithm . . . . . . . . . . . . . . . . . . . . . 504
B.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 509
C Composite Concave Programming 511
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
C.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 513
C.3 Pseudolinear Problems . . . . . . . . . . . . . . . . . . . . . 516
C.4 Convex Problems . . . . . . . . . . . . . . . . . . . . . . . . 519
C.5 One-Dimensional Convex Additive Problems . . . . . . . . . 525
D The Principle of Optimality in Stochastic Processes 529
D.1 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 529
D.2 Common Interpretation of the Principle . . . . . . . . . . . 531
D.3 Principle of Optimality (stochastic models) . . . . . . . . . 533
D.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
D.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 534
E The Corridor Method 535
E.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
E.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 536
E.3 Example: TSP . . . . . . . . . . . . . . . . . . . . . . . . . . 537
E.4 Generating Corridors . . . . . . . . . . . . . . . . . . . . . . 540
E.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 547
Bibliography 549
Index 595
· · · · · · (收起)
读后感
用户评价
坦白说，初次接触《信息熵与编码理论》这本书时，我有些犹豫，因为我对信息论的理解一直停留在皮毛阶段。然而，这本书彻底颠覆了我的刻板印象。它没有急于抛出香农公式，而是从物理学中热力学第二定律的熵概念引入，构建了一个极其优雅的桥梁，将宏观世界的无序性与微观世界的信息不确定性联系起来。这种跨学科的宏大叙事视角，极大地拓宽了我的视野。书中关于信源编码和信道编码的论述，逻辑链条清晰得令人赞叹，尤其是对线性分组码和卷积码的讲解，图文并茂，配合着精心挑选的例题，使得原本复杂冗余的代数结构变得可以触摸、可以理解。这本书的阅读体验是沉浸式的，它要求读者不仅要“看懂”，更要“感受”信息在传输过程中所经历的转化与损耗，它让我开始以一种全新的、更具哲学意味的眼光看待数据和通信的本质。
这本书的排版和案例设计，简直是为实战派程序员量身定做的“操作手册”。我通常在阅读技术书籍时，最怕的就是理论和实践脱节，但《计算的艺术》这本书完美地规避了这一点。它不是那种堆砌晦涩公式的学术著作，而是充满了鲜活的、可以立即在实际项目中应用的技巧。比如，书中关于内存层次结构优化那一部分，它不是空谈理论上的缓存一致性，而是直接给出了不同数据结构在L1、L2缓存中访问效率的对比图表，并附带了数个C++代码片段，清晰展示了如何通过调整数据布局来榨取机器性能的每一分潜力。我按照书中的建议重构了一个我工作中一个耗时的批处理模块，结果性能提升了惊人的40%，这让我对这本书的实用价值深信不疑。作者的叙述风格非常接地气，充满了工程师特有的幽默感，读起来毫无压力，仿佛身边就坐着一位经验丰富的前辈在手把手地教你如何“驯服”硬件。
我向来对那些只谈宏观、不深入细节的书籍持保留态度，但《并行计算与GPU加速》这本书恰恰相反，它以一种近乎偏执的细节深度，带领读者潜入了现代高性能计算的核心。书中的重点放在了CUDA编程模型上，作者对于线程块（Block）、线程（Thread）以及网格（Grid）的层次化组织，描述得细致入微，几乎可以作为官方文档的补充阅读材料。最让我受益匪浅的是关于内存访问模式的优化章节，书中详细分析了不同数据类型在共享内存（Shared Memory）和全局内存（Global Memory）之间的传输瓶颈，并提供了大量的实践建议，比如如何通过“数据重排”来最大化内存合并访问（Coalesced Access）。这本书的语言风格极为直接和技术化，几乎没有冗余的修饰词，每一句话都直指核心，非常适合那些已经掌握了基础C++，并希望快速掌握GPU并行编程精髓的工程师。它就像一本“反汇编”手册，教你如何与现代处理器进行最底层的对话。
《离散数学的思维之道》这本书，与其说是一本技术指南，不如说是一本关于如何进行严谨逻辑推理的“心法要诀”。它的侧重点并非在于教会读者某一个具体的算法，而是培养一种自上而下的、结构化的思维方式。书中的章节编排充满了匠心，从集合论的基础构建，到命题逻辑的演绎推理，再到谓词逻辑的表达能力，作者步步为营，构建了一个坚不可摧的逻辑城堡。我尤其欣赏它在讲解证明技巧时所采用的启发式教学方法，它不像传统的教材那样只是给出证明过程，而是先提出一个“为什么我们不知道如何证明”，然后再引导我们探索不同的证明路径，这种“解构问题”的过程，比直接给出答案更有教育意义。阅读这本书，我感觉自己仿佛在进行一场智力体操，它强迫我的大脑去适应一种更高维度的抽象思考模式，这对于任何从事复杂系统设计或理论研究的人来说，都是一次不可多得的思维洗礼。
翻开这本《算法之巅》，我立刻被它深邃而严谨的数学基础所吸引。作者似乎有一种魔力，能将那些看似晦涩难懂的离散数学概念，用一种近乎诗意的语言娓娓道来。书中对图论的讲解，尤其令人拍案叫绝，它不仅仅罗列了各种算法的步骤，更深入剖析了每一步背后的逻辑推导，仿佛在引导读者亲手构建起整个知识体系的骨架。我记得有一次，为了理解某个特定的最短路径变种，我反复琢磨了书中一个几何直觉的类比，它瞬间打通了我的思维壁垒，那种豁然开朗的感觉，至今记忆犹新。这本书的深度远超出了教科书的范畴，它更像是一本武林秘籍，需要读者沉下心来，耐心地去品味其中的每一招一式。对于那些渴望从“会用”算法进阶到“精通”算法的读者来说，这本书无疑是殿堂级的存在，它挑战了我的认知极限，让我对计算复杂性有了全新的认识，特别是关于NP完全性那几章的论述，逻辑之严密，论证之有力，让人不得不折服于作者深厚的功底。
