PDF《第5章    动态规划 》

1? ? ? ? ? ? 第5章? ? 动态规划? ? ? 2? ? 第5章的主要内容? ?多阶段决策和最优化原理? ?离散变量的动态规划? ?阶段数固定(定期)的动态规划? ?阶段数不固定(不定期)的动态规划? ?连续变量的动态规划? ? ? 3? ? ? ? ? ? 5.

1/5.2? 多阶段决策和最优化原理? ? 4? ? 动态规划研究的问题? ?动态规划起源于

1950 年代,创始人为 R.?Bellman.? ?动态规划所研究的对象是多阶段决策问题.? ?这样的问题可以转化为一系列相互联系的单阶段优 化问题.? 在每个阶段都需要作出决策.? ?每个阶段的决策确定以后,就得到一个决策序列, 称为策略.? ?多阶段决策问题就是求一个策略,使各阶段的总体 5? ? 目标达到最优(如最小化费用,或最大化收益) .? ?相对于线性规划一次性地对一个问题求出整体最优解, 多阶段决策问题的这种解决办法(一个阶段一个阶段 地,而不是一次性地)称为动态规划(Dynamic? Programming) .而原来的线性规划方法被称为静态规 划.? 问题举例一:最短路问题? 如图,求从 a 到g的最短路.? ? 由于这 问题是 这是一个 是一个多 个多阶段图 阶段决策 6? 图(分层 策(优化 层图) ,该化)问题. 图上的最 ? ? 最短路 7? ? 如何求解?? ?由于这是一个多阶段图,从a到g的任何一条路径的 边数都是 6.? ?从a到g,必然要经过 a 的下一个阶段中的顶点 b1 或b2.因此,从a到g的最短路就是从 a 到b1,然后再 从b1 走到 g,以及从 a 到b2,再从 b2 走到 g,两种走 法中最短的一个.? ?于是,定义 fk(u,?g)为从当前顶点 u 开始经过 k 条边到 8? ? 达g的最短路长度.则有:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1 , ,

2 , , , min ,

1 k g u d k g v f v u l g u f k u N v k .? ?原问题即是求 fn(a,?g)(n?=?6) .? ?上述过程实际上是动态规划中"后向优化"的方法.? ? 逆 逆向求解 解递推方 方程(标号 9? 号法)? ? 10? ? 动态规划表格? ?行标 i: 从目标顶点 g 开始, 倒数第 i 层 (即, 计算 fi(u)) .? ?p1,?p2,?p3,?p4:倒数第 i 层的自上而下的各个顶点(最多4个) .? p1 p2 p3 p4 p1 p2 p3 p4

1 4

3 ? ?

1 1

1 ? ?

2 7

5 9 ?

2 1

2 2 ?

3 7

6 8 ?

3 2

2 2 ?

4 13

10 9

12 4

1 1

2 3 11? ?

5 13

16 ? ?

5 2

3 ? ?

6 18 ? ? ?

6 1 ? ? ? ?最短路为:a???b1???c2???d1???e2???f2???g.? 递归如何?循环如何?? 递归程序? ? f(i,?u,?g)? 1? ? if?i?=?1?then?return?d(u,?g),? 2? ? else?return?min?v???N(u)?{d(u,?v)?+?f(i???1,?v,?g)}.? 12? ? 循环程序? f(u,?g)? ? 1? ? p???(a,?b1,?c1,?d1,?e1,?d1,?f1,?g).? ? 2? ? for?b???b1? 到? b2?do? ? ? 3?for?c???c1? 到? c4?do? ? 4?for?d???d1? 到? d3?do? ? ? 5?for?e???e1? 到? e3?do? 6?for?f???f1? 到? f2?do? ? ? 7?q???(a,?b,?c,?d,?e,?f,?g).? 13? ? ? 8?if?q 的长度? ?v?then?v???t.? ? 5? ? endfor? ? ? 6? ? return?v.? 每计算一个单元格的? fk(x), 都需要计算一个 max?0???y? ??x?{…}函数.因此,尽管使用表格暂存了计算结果, 为计算出最后的? fn(x)? 仍需要大量的计算.? 小技巧:不用每行都从? 0? 计算到? 1000.每年无论 22? ? 如何投放,回收的机床最多是? 0.8x? 台(max{a,?b}?=? 0.8) .例如表格第? 5? 行表示最后一个阶段,其前面 有? 4? 个阶段.因此对于第

5 行,只需要从? 0? 计算 到? 0.84 ???1000???4096.? 但动态规划法已经比直接用递归的方法解递推方程 减少了大量的计算.? 23? ? 计算结果? ? 24? ? 递归的方法? f(k,?x)? ? 1? ? v???0.? ? 2? ? if?k?=?1?then? ? 3?for?y???0? 到? x?do? ? 4?t???g(y)?+?h(x???y).? ? 5?if?t?>?v?then?v???t.? ? 6?endfor? ? 25? ? ? 7? ? else? ? 8?for?y???0? 到? x?do? ? 9?t???g(y)?+?h(x???y)?+?f(k???1,?ay?+?b(x???y)).? 10?if?t?>?v?then?v???t.? 11?endfor? ? 12? ? endif? ? 13? ? return?v.? 26? ? 多阶段决策问题? 有一个系统,可以分成若干个阶段.? 任意一个阶段? k,系统的状态可以用? xk? 表示(可 以是数量、向量、集合等) .? 每一状态? xk? 都有一个决策集合? Qk(xk),在? Qk(xk)? 中选定一个决策? qk???Qk(xk), 状态? xk? 就转移到新的 状态 x?k?+?1?=?Tk(xk,?qk),并且得到效益(或费用)Rk(xk,? qk).? 27? ? 系统的目标就是在每一个阶段都在它的决策集合中 选择一个决策,使所有阶段的总效益达到最大(或 总费用达到最小) .? 这样的多阶段决策问题通常使用动态规划方法来求 解.? 动态规划的最优子结构性质? 动态规划的最优化原理:需要问题的最优解具有如下所 述的最优子结构性质:? 28? ? 一个多阶段决策问题,假设其最优策略的第一阶段 的决策为? q1,系统转移到的新状态为? x2.则该最优 策略以后诸决策对以? x2? 为初始状态的子问题而言, 必须构成其最优策略.? 该子问题与原问题是同一类问题,只是问题规模下 降了.? 当观察到问题解的最优子结构性质时,就意味着问 题可能用动态规划法求解.? 29? ? 动态规划的子问题重叠性质? 从算法角度而言, (离散变量的)动态规划所依赖的 另一个要素是子问题重叠性质:一个问题的求解可 以划分成若干子问题的求解,而处理这些子问题的 计算是部分重叠的.? 动态规划法利用问题的子问题重叠性质设计算法, 能够节省大量的计算.对一些看起来不太可能快速 求解的问题,往往能设计出多项式时间算法.? ? 30? ? 在算法理论中,多项式时间算法通常被认为是"有 效的算法" (efficient?algorithm) .? 前向优化? 写动态规划递推方程时,一般有两种写法:前向优 化和后向优化.假设问题有 n 个阶段.? 定义 fk()? 为问题的前 k 个阶段(从第