下载文档原格式
第三章：动态规划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子策略。
动态规划（生产和存储问题）一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。
1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。
动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。
例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。
二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素：1．阶段阶段（stage）是对整个过程的自然划分。
通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。
阶段变量一般用k=1.2….n.表示。
1.状态状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。
它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。
通常还要求状态是可以直接或者是间接可以观测的。
描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。
变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。
用X(k)表示第k阶段的允许状态集合。
n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。
《高级算法与数据结构》课程思政元素第三章动态规划3.1 动态规划算法的基本原理一、授课内容1.1 动态规划算法的基本思想在现实生活中，有一类问题被定义为最优决策问题，这类问题可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的那个解，即最优解。
20世纪40年代，Richard Bellman首次使用了动态规划这个术语，用来描述最优决策问题的求解过程。
其核心思想是将最优决策问题按照时间或空间特征分解成若干相互关联的阶段，以便按次序去求每个阶段的解。
各阶段开始时具有客观条件（称之为状态），当各阶段的状态确定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
“动态”是指在一定条件下，根据上一阶段的状态和决策来导出本阶段的状态，“规划”是指建立状态转移方程。
最优决策问题的难点在于，各个阶段决策的选取不能任意确定，它既依赖于当前面临的状态，又影响着以后的发展。
1.2 动态规划算法与分治法的区别和联系动态规划算法与（第二章）分治法类似，都是将待求解问题分解为若干个子问题，先求解子问题，再结合这些子问题的解得到原问题的解。
与分治法不同之处在于：（1）适合用动态规划求解的问题经分解得到的子问题往往不是相互独立的（即重叠子问题），在递归模型上采用分治法自顶向下求解时，有些子问题被反复计算。
动态规划算法正是利用重叠子问题的性质，将各阶段子问题的最优值保存在一个表格中，在需要时以常数时间查看结果，这样可以避免大量的重复计算。
对于一些在递归模型上具有指数下界的算法来说，当不同子问题的个数随问题的大小呈多项式增长时，用动态规划的表格式方法来存储重叠子问题的解，可以将指数时间减少为多项式时间，从而有效降低了时间复杂度。
（2）每个阶段的子问题可能会有许多可行解，当问题的最优解包含了其子问题的最优解时（即最优子结构），表格里只存储子问题的最优解就可以了。
利用最优子结构性质，动态规划可以自底向上的从子问题的最优解逐步构造出原问题的最优解，从而有效控制了空间复杂度。
