文档介绍：数据构造与算法动态规划
动态规划概述
动态规划概述
动态规划〔Dynamic Programming〕，在20 世纪50年代由美国数学家
Richard Bellman〔理查德 .贝尔曼〕提出，作为多阶段决策过程最优化
的一种通用算法设计法，不仅解决特定类型的最优化问题，也包括某些
非最优化问题。
多阶段决策过程最优化
诸多实际问题：有多个解，但要找到最优解。
穷举法通过找出全部解，再从中找出最优解。对于那些计算复杂度高的
如组合问题，找出其全部解所消耗的计算时间往往不可承受！
为降低求解难度，把求解过程分为一系列阶段，各个阶段按最优性原那么
计算，在最后阶段可得最优解。包括：分段、求解 两大步。
—— 不能段化的问题不能用动态规划法求解。
最优性原那么
阶段 1
阶段 2
......
阶段 n
求解算法
求解算法
求解算法
多阶段决策过程
动态：求解算法施加的状态是变化的。
当前状态只与直接前趋有关，对直接
前趋施加求解算法， 成为当前状态。
最优性原那么 ( Principle of Optimality ) :
问题的最优解，是由其子问题的最优解组成。
特定问题该原那么不一定满足〔罕见〕，因此，有必要检查该原那么的适用性。
某些多阶段决策问题本身没有最优化要求，如后面的中国象棋马从棋盘上一点移到另一点的全路径问题，又如计算裴波那契序列的动态规划算法，都属于非最优化问题的动态规划法。
动态规划法的特点：
1. 分阶段计算。对最优化问题，各阶段满足最优性原那么。
2. 一般用自顶向下分析〔规模减小〕，自底向上实现〔规模增加〕。
计算过程：一阶段一阶段地向前推进，直到最终状态。
数塔
数塔
有一个三角形数塔如图。求一条自塔顶到塔底的路径，该路径上节点值
之和最大。〔 注意动态规划法与穷举法、贪婪法的区别 〕
贪婪算法：从塔顶到塔底，13 + 12 + 16 + 15 + 24 = 80
问题分段：每一级台阶划分为一个阶段 —— 多阶段决策优化问题。
逐段计算：当前问题的最优解由各子问题的最优解组成。
如：max(12+6, 7+6) = 18，max(40+18, 40+27) = 67, ......
5 级
4 级
3 级
2 级
1级
18 27 39 32
67 46 55
78 67
91
13
11
12
7
40
14
16
15
8
24
6
7
13
12
11
数塔问题：动态规划法与穷举法效率比较
数塔：动态规划法与穷举法的时间效率比较
输入规模：为便于分析，选数塔层数 k , k > 0
根本操作：加法运算
效率类别：无最正确、最差〔均从塔顶到塔底〕
增长函数 T(k) ：
各层节点数：1, 2, 3, 4, 5, ......
节点的总数：1, 3, 6, 10, 15, ......
数塔层数 k ：1, 2, 3, 4, 5, ......
路径总数 t ： 0, 2, 4, 8, 16, ...... t = 2k-1, k > 0
1. 穷举法：T(k) = (k-1) 2k-1，k > 0 指数型
本例 k = 5，每条路径 5 个节点做 k-1 = 4 次加法，共 64 次。
2. 动态规划法：〔层节点数 = 层数〕
塔底向塔顶计算，第 k 层加法总数为第 k-1 层的节点数×2 ：
T(k) = 2×(k-1+...+3+2+1) = k(k-1), k > 0 平方型
本例 k = 5 ，加法总数 2×(4+3+2+1) = 20 次
最小代价子母树
最小代价子母树
有 n≥2 堆沙子，重量向量 W = ( w1,...wn ) ，将它们归并为 1 堆。
规那么：只能将相邻 2 堆归为 1 堆，经过 n-1 次归并后成为 1 堆。
要求：找到代价最小的归并方案。
代价：新产生沙堆的质量和。代价最小的归并树即最小代价子母树。
动态规划法求解：
问题分段：将每次归并划分为一个阶段，共 n-1 个阶段。
逐段计算：自底向上〔规模增大 n = 2, 3, ... , n-1〕
n = 2：1 种归并法即 2 合 1 .
n = 3：2 种归并法，第 1 种归并法如图，前 1 堆后 2 堆
c(i, j) ——