中科院陈玉福算法讲义ch5.pdfVIP

106 第五章 动态规划算法 第五章 动态规划算法 §1.动态规划算法的基本思想 动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际 生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为 依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这 类问题的解决是多阶段的决策过程。20世纪50年代，贝尔曼（Richard Bellman） 等人提出了解决这类问题的“最优化原则”，从而创建了求解最优化问题的一种 新的算法――动态规划算法。最优化原则指出，多阶段过程的最优决策序列具有 性质： 无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始 决策所产生的状态构成一个最优决策序列。 这要求原问题计算模型的最优解需包含其（相干）子问题的一个最优解（称为最 优子结构性质 ）。 动态规划算法采用最优化原则来建立递归关系式（关于求最优值的），在求 解问题时有必要验证该递归关系式是否保持最优化原则。若不保持，则动态规划 算法不适合求解该计算模型。在得到最优值的递归式之后，需要执行回溯以构造 最优解。在使用动态规划算法自顶向下（Top-Down）求解时，每次产生的子问题 并不总是新问题，有些子问题反复计算多次，动态规划算法正是利用了这种子问 题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中，当再次要 解此子问题时，只是简单地调用（用常数时间）一下已有的结果。 通常，不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规 划算法通常只需要多项式时间，从而获得较高的解题效率。最优子结构性质和子 问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 例 5.1.1．多段图问题 设G=(V,E)是一个赋权有向图，其顶点集V被划分成k2个不相交的子集V : i 1≤i≤k，其中，V 和 V 分别只有一个顶点 s(称为源)和一个顶点 t(称为汇)，图 1 k 5-1-1中所有的边(u,v)的始点和终点都在相邻的两个子集V 和V 中，而且 i i＋1 u∈V ，v∈V 。多阶段图问题是：求由s到t 的最小成本路径（也叫最短路径）。 i i＋1 对于每一条由s到t 的路径，可以把它看成在k-2个阶段做出的某个决策序 列的相应结果：第i步决策就是确定V 中哪个顶点在这条路径上。假设 i+1 s, v , v , … , v , t 2 3 k-1 是一条由s到t 的最短路径，再假定从源点s(初始状态)开始，已经作出了到顶 点 v 的决策(初始决策)，则 v 就是初始决策产生的状态。若将 v 看成是原问题 2 2 2 第五章 动态规划算法 107 的子问题的初始状态，这个子问题就是找一条由 v 到 t 的最短路径。事实上， 2 路径v , v , … , v , t一定是v 到t的一条最短路径。不然，设 2 3 k-1 2