3 动态规划..ppt

13 3动态规划动态规划 2 动态规划(dynamic programming) 是求解决策过程(decision process) 最优化的数学方法。 20 世纪 50 年代初美国数学家 等人在研究多阶段决策过程( multistep decision process) 的优化问题时,提出了著名的最优化原理(principle of optimality) , 把多阶段过程转化为一系列单阶段问题,逐个求解, 创立了解决这类过程优化问题的新方法——动态规划。 1957 年出版了他的名著 Dynamic Programming ,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。 3 学习要点: ?多阶段决策过程的最优化问题?动态规划算法的基本要素?(1)最优子结构性质?(2)重叠子问题性质?设计动态规划算法的步骤: ?(1)找出最优解的性质,并刻划其结构特征。?(2)递归地定义最优值。?(3)以自底向上的方式计算出最优值。?(4)根据计算最优值时得到的信息,构造最优解。 4 ?应用范例?(1)最短路径?(2)矩阵连乘问题; ?(3)流动推销员?(4)流水作业调度; ?(5)背包问题; ?(6)最优二叉搜索树。 5多阶段决策过程特点: 状态 x 1阶段 1T 1决策 u 1状态 x 2决策 u 2阶段 2T 2状态 x 3... 状态 x k决策 u k阶段 kT k状态 x k +1... 状态 x n决策 u n阶段 nTn 状态 x n +1 多阶段决策问题多阶段决策问题把所给问题恰当地划分为若干个相互联系又有区别的子问题, 称之为阶段。阶段是按决策进行的时间或空间上先后顺序划分的。 6 动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。多阶段决策问题多阶段决策问题 7 ?基本思想: 将待求解问题分解成若干个子问题算法总体思想算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 8 ?经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。算法总体思想算法总体思想 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 9 ?如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。算法总体思想算法总体思想 n= n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) 10 在每种情况下, 列出各种可能的局部解, 然后按某些条件, 从局部解(或中间解)中挑选出可能产生最佳解的结果,而扬弃其余。算法总体思想算法总体思想