动态规划（一）

背景 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决。 动态规划算法通常用来解决最优化问题。这些问题可能存在多个解，每个解具有一个值。我们希望找到一个具有最优（最大或最小）值的解。在动态规划算法中，主要关心的是找到一个最优解和求出最优解的值，而不是找出所有的最优解。

背景 动态规划算法可分解成从先到后的4个步骤： 1. 描述一个最优解的结构； 2. 递归地定义最优解的值； 3. 以“自底向上”的方式计算最优解的值； 4. 从已计算的信息中构建出最优解的路径。 其中步骤1~3是动态规划求解问题的基础。如果题目只要求最优解的值，则步骤4可以省略。

从一个例子谈起 问题: 求城市间最短通路. 设有如图所示的N座城市, 相邻城市之间有若干条通路, 线上的数字表示通路的距离. 试求出从A到D的最短距离. A B1 B2 C2 C1 C3 D 5 2 3 7 4 图1

最短通路问题的解结构 分析: 我们可以用搜索，枚举图中的每条路径。但当图的规模大起来时，搜索的效率显然是非常低的。让我们试着用动态规划的思路来分析这道题： 动态规划策略的第一步是描述一个最优解的结构。对最短通路问题解的结构，我们这样来分析： 从图中可以看到，从A点要到D点必然要经过B1和B2中的一个。到底选择B1还是B2，不能只比较A到B1和A到B2这两段的长度。本问题的性质表明：局部最优并不能保证全局最优。例如，按照局部最优的策略选择的路径是：A-B2-C3-D，路径长度为11。而实际上A-B1-C2-D才是最优解，其路径长度为10。所以“贪心法”在本题中不可用。 A B1 B2 C2 C1 C3 D 5 2 3 7 4

最短通路问题的解结构 因此，我们既要考查选择B1的解又要考查选择B2的解。然后再比较两个解，看哪个最优。 首先，我们假定选择B1的解是最优的，也就是说A-B1…D是最短通路。那么一个关键的观察是：B1 …D也必须是最短的。为什么？ 证明如下： 假设从B1到D还有更短的路径，那么替换掉组成A -B1…D的路径，必然就得到一个更短的A-D的通路，这与题目假设A -B1…D是最短通路相矛盾。因此，B1 …D是最短通路。 同理，我们假定选择B2的解是最优的，即A-B2 …D是最短通路。那么B2 …D也必须是最短通路。 A B1 B2 C2 C1 C3 D 5 2 3 7 4

最短通路问题的解结构 更一般地说，对最短通路问题，问题的一个最优解（找到从A到D的最短通路）中包含着子问题（找到从B1到D的最短通路或从B2到D的最短通路）的一个最优解。 我们把这一性质称为最优子结构。最优子结构是可以应用动态规划解题的标志性特点之一。 A B1 B2 C2 C1 C3 D 5 2 3 7 4

最短通路问题的解结构 最优子结构性质表明我们可以利用子问题的最优解来构造问题的最优解。 对最短通路问题，子问题的最优解这样来构造问题的最优解： 问题的最优解 = MIN(B1~D的最优解+A~B1的长度，B2~D的最优解+A~B2的长度) 因此，为了解决A~D的最短通路问题，我们必须首先解决B1~D的最短通路问题和B2~D的最短通路问题。这显然是一个递归的过程。 A B1 B2 C2 C1 C3 D 5 2 3 7 4

递归地定义最优解的值 动态规划策略的第二步是根据子问题的最优解递归地定义问题的最优解的值。我们用 MD(v)表示点v到点D的最短通路的长度，用w(v,u)表示点v到点u的线段长度, d(v)是与v相邻的节点的集合。那么根据前面的分析就有： A B1 B2 C2 C1 C3 D 5 2 3 7 4

递归地定义最优解的值 根据这个这个公式，我们可以推导出： MD(A) = min{w(A,B1)+MD(B1), w(A, B2)+MD(B2)} MD(B1)= min{w(B1,C1) + MD(C1), w(B1, C2)+MD(C2)} MD(B2)= min{w(B2,C2) + MD(C2), w(B2,C3)+MD(C3)} MD(C1)= min{w(C1,D)+MD(D)} MD(C2)= min{w(C2,D)+MD(D)} MD(C3)= min{w(C3,D)+MD(D)} MD(D) = 0 递归边界条件 MD(C1) = 4 MD(C2) = 3 MD(C3) = 5 MD(B1) = 5 MD(B2) = 9 MD(A) = 10 上述手工方式推导出本题的解是为了让大家熟悉递归法求解问题的过程。根据上述递归式写出相应的递归程序应当是不难的事情。留给大家做课后练习。 A B1 B2 C2 C1 C3 D 5 2 3 7 4

自底向上计算最优解的值 如果我们满足于用递归式计算出问题的解，则没有达到动态规划的目的。通过分析前面递归计算过程，我们发现MD(C2)在计算MD(B1)和MD(B2)时均要用到，而在计算完MD(B1)后, 并没有保存MD(C2)的值, 所以在计算MD(B2)时还要重新计算MD(C2). 而MD(D)则被重复计算了3次. 在本题中的图是经过简化的, 所以重复计算量看上去并不多(共4次), 但考虑到总的计算量只有7次(7个结点的MD), 所以重复计算的比例还是相当高的. 如果图的宽度和深度更大一些, 则重复计算量还要大!

自底向上计算最优解的值 我们注意到: 越是接近底层的子问题被重复计算的次数也就越多. 我们能不能将上述递归法的求解过程进行优化, 避免重复计算, 使所有的子问题都只计算一次! 要实现这一点, 必须做到二件事: 1. 自底向上计算子问题最优解. 越是靠近底层的子问题, 越是先计算出来. 2. 用表格存储计算出的子问题的最优解的值, 以便在计算它的“上层”子问题时能够直接引用, 而不是去重新计算.

自底向上计算最优解的值 为简化问题, 图1的顶点用数字编号, 依次是: A : 1 B1: 2 B2: 3 C1: 4 C2: 5 C3: 6 D: 7 这样, 图1用邻接矩阵作为存储结构, 即为: Const M : array[1..7, 1..7] of integer = ( (0, 5, 2, 0, 0, 0, 0), (0, 0, 0, 3, 2, 0, 0), (0, 0, 0, 0, 7, 4, 0), (0, 0, 0, 0, 0, 0, 4), (0 ,0, 0, 0, 0, 0, 3), (0, 0, 0, 0, 0, 0, 5), (0, 0, 0, 0, 0, 0, 0)); Var S : array[1..7] of integer; {用来存储各个结点的最短通路的数组}

完整的动态规划求解的程序 Program DP1_R; {动态规划讲义例题1，动态规划解法} const MaxV = 7; MaxLen = MaxInt; M : array[1..MaxV, 1..MaxV] of integer = ( (0, 5, 2, 0, 0, 0, 0), (0, 0, 0, 3, 2, 0, 0), (0, 0, 0, 0, 7, 4, 0), (0, 0, 0, 0, 0, 0, 4), (0 ,0, 0, 0, 0, 0, 3), (0, 0, 0, 0, 0, 0, 5), (0, 0, 0, 0, 0, 0, 0) ); var S: array[1..MaxV] of integer; {用来存储各个结点的最短通路的数组, 全局变量} {计算点K到点D的最短通路长度。图以邻接矩阵存储，点D是图的终点，出度为0。} procedure MD; i, j, t: integer; begin S[MaxV] := 0; {最底层的D点的MD值为0}

完整的动态规划求解的程序 for i := 6 downto 1 do begin {自底向上计算各个结点的MD值} S[i] := MaxLen; {当前结点的MD初值为无穷大} for j := i + 1 to MaxV do {遍历结点i的“底层”结点} if M[i,j] <> 0 then begin {如果j是i的下层结点，则计算经过j的MD值} t := M[i,j] + S[j]; if t < S[i] then {如果计算出的MD值小于当前保存的S[i]，则更新S[i]} S[i] := t; end; end; {MD} begin MD; {调用求最短通路的过程} writeln(S[1]); {输出问题的最优解S[1]} end. 在自底向上的动态规划算法求解最优解的过程中, 问题的最优解是最后得到的.

构建最优解的路径 本题已经得到一个最优解, 但没有获得这个最优解是“怎样”得到的, 也就是说我们除了知道10从A到D的最短通路长度外, 无法知道是怎样从A走到D才是最短的通路. 而往往这才是更有价值的问题. 要得到最优解的路径(最优解的形成过程), 需要在计算的过程中记录额外的过程信息. 在最短通路问题中，在计算结点I的最短路径时，每当我们找到一个比当前路径长度更小的值时，只是记录了这个更小的值，而没有记录这个值是由哪个结点产生的。利用一个数组来记录这一信息。 Var w: array[1..MaxV] of integer; {存储结点的最短通路的下一跳结点编号} 由于D是最后一个结点，没有后续结点了，所以w[D](在程序中是w[7])的值规定为0.

构建最优解的路径 然后在计算S[i]时, 程序修改如下: for i := 6 downto 1 do begin {自底向上计算各个结点的MD值} S[i] := MaxLen; {当前结点的MD初值为无穷大} w[i] := 0; {“ 下一跳初值设为0”} for j := i + 1 to MaxV do {遍历结点i的“底层”结点} if M[i,j] <> 0 then begin {如果j是i的下层结点，则计算经过j的MD值} t := M[i,j] + S[j]; if t < S[i] then begin {如果计算出的MD值小于当前保存的S[i]，则更新S[i]} S[i] := t; w[i] := j; {新的MD值是由点j产生的, 因此“下一跳”是点j} end;

构建最优解的路径 输出最优解的路径. 我们定义了一个过程Print来输出最优解的路径. 注意到从起始点A开始, 数组w记录了每个结点的下一跳的编号, 数组下标就是当前结点的编号. 而终点D的下一跳编号为0, 作为循环终止的条件. 而w是全局数组, 在程序的所有地方都可以访问. Procedure Print; var i: integer; begin i := 1; repeat write(i:3); i := w[i]; until i = 0; writeln; end; 通常,可以把输出最优解的路径的过程处理为递归过程.

小结 动态规划是一种算法策略, 它采用了两个主要的设计方法: 表格化 - 利用数组存储中间计算环节 自底向上 - 从最底层子问题开始, 逐步上升计算, 最后得到问题的解 动态规划主要适用于一类所谓的“最优化”问题, 即求最大(或最小)值. 当分析问题的性质, 满足如下二点时, 就可采用动态规划策略求解: 最优子结构 - 问题的一个最优解中包含着子问题的一个最优解. 重叠子问题 – 求解问题的解时要反复计算若干个子问题. 同理, 求解各个子问题时又要反复计算若干子子问题, 这些子子问题可能是新产生的, 也可能是重复产生的.

练习 调试运行整个最短通路问题. 装配线调度问题: 汽车厂的总装车间有两条装配线. 每条装配线上都有n个装配点,编号分别为j=1,2,…,n. 我们标记第I条(I=1,2)装配线的第j个装配点为Si,j . 我们规定S1,j 和S2,j做的工作相同, 但由于效率, 技术等原因使S1,j和S2,j的工作时间却不同. 我们标记Ai,j为Si,j的工作时间. 汽车底盘进入两条装配线的进入时间分别标记为E1和E2. 汽车除了在一条装配线上流动外, 还可以转移到另一条装配线上去. 我们把在Si,j工作完后转移到另一条装配线的时间标记为Ti,j. 汽车可以在两条装配线上随意地调度. 请问: 在如图(见下页)所示的装配线中, 怎样安排汽车的装配点, 使得装配时间最短?

E1 E2 A1,1 A2,1 A1,2 A2,2 A1,3 A2,3 A1,4 A2,4 …… A1,n-1 A2,n-1 A1,n A2,n T1,1 T2,1 T1,2 T1,3 T1,n-1 T2,2 T2,3 T2,n-1

S1,1 S1,1 S1,2 S1,3 S1,4 S1,5 S1,6 2 4 7 8 9 5 3 6 A2,n-1 1 S2,1 S2,2 S2,3 S2,4 S2,5 S2,6