下载文档原格式
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
第3章动态规划动态规划是一种通过将问题分解为子问题，并且以自底向上的方式求解子问题从而求解整个问题的算法设计方法。
它在计算机科学中的应用非常广泛，特别是在优化问题和组合优化问题中。
动态规划的核心思想是将问题划分为多个重叠子问题，并且将计算结果储存起来以供后续使用。
通过这种方式，可以避免重复计算，提高算法效率。
动态规划通常适用于满足最优子结构的问题，即问题的最优解可以通过一系列子问题的最优解得到。
在动态规划中，需要定义一个状态转移方程，用于描述问题的最优解与其子问题的最优解之间的关系。
通过利用状态转移方程，可以从最底层的子问题开始，逐步求解出更大规模的问题的最优解。
最终，可以得到整个问题的最优解。
动态规划的基本步骤包括问题建模、确定状态、定义状态转移方程、确定边界条件和计算最优解。
首先，需要将原始问题转化为适合动态规划求解的形式，通常可以采用数学建模的方法。
然后，需要确定问题的状态，即将问题划分为多个子问题，并且定义子问题的状态。
接下来，需要定义状态转移方程，该方程记录了问题的最优解与子问题的最优解之间的关系。
然后，需要确定边界条件，即问题的最基本解。
最后，通过逐步计算子问题的最优解，得到整个问题的最优解。
动态规划在多个领域都有广泛的应用。
在计算机科学中，动态规划被广泛应用于图论算法、字符串处理算法、序列比对算法等。
此外，动态规划还被应用于经济学、运筹学和生物学等领域的优化问题。
通过应用动态规划，可以有效地解决这些领域中的复杂问题。
总结起来，动态规划是一种通过将问题划分为多个子问题，并且利用状态转移方程求解子问题从而求解整个问题的算法设计方法。
通过避免重复计算，动态规划可以提高计算效率，并且被广泛应用于计算机科学和其他领域的问题求解。
§12.4 动态规划[学习目标]1. 能建立动态规划问题的数学模型；2. 会表述动态规划问题的一般形式；3. 会求解简单的动态规划问题。
动态规划是解决多阶段决策过程最优化的一种方法。
这种方法把困难的多阶段决策问题变换成一系列互相联系比较容易的单阶段问题，解决了这一系列比较容易的单阶段问题，也就解决了这困难的多阶段决策问题。
多阶段决策问题，是指这样一类活动的过程，在它的每个阶段都需要做出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程决策的效果。
多阶段决策问题就是要在允许的各阶段的决策范围内，选择一个最优决策，使整个系统在预定的标准下达到最佳的效果。
有时阶段可以用时间表示，在各个时间段，采用不同决策，它随时间而变动，这就有“动态”的含意。
动态规划就是要在时间的推移过程中，在每个时间阶段选择适当的决策，以便整个系统达到最优。
用动态规划可以解决管理中的最短路问题、装载问题、库存问题、资源分配、生产过程最优化问题。
近几十年来，动态规划在理论、方法和应用等方面取得了突出的进展，并在工程技术、经济、工业生产与管理、军事工程等领域得到广泛的应用。
下面我们先看一个简单的例子。
一、引例：最短线路问题如图形5.5，从A 0地要铺设一条管道到A 6地，、中间必须经过五个中间站。
第一可以在A B 11,两地中任选取一个，类似地，第二、三、四、五站可供选择的地点分别是{}{}{}{}A B C D A B C A B C A B 222233344455,,,,,,,,,,,。
连接两点间的管道的距离用图3-7上的数字表示，两点间没有连线的相应两点间不能铺设管道，现要选择一条从A 0到A 6的铺管线路，使总距离最短。
解 最短线路问题有一个特性，如果最短线路在第k 站通过p k ，则这一线路在由p k 出发到达终点的所有可能选择的不同线路来说，必定也是距离最短的。
最短线路的这一特性，启发我们从最后一段开始，用从后向前逐渐递推的方法，示出各点到A 6的最短线路，最后球得从A 0到A 6的最短线路。
