第8章 动态规划

1、12 动态规划(Dynamic Programming)是应用数学是应用数学和计算机科学领域中一个非常重要的算法设计技和计算机科学领域中一个非常重要的算法设计技术术 美国数学家美国数学家Richard Bellman于于20世纪世纪50年代发年代发明，用于明，用于解决多阶段决策过程最优问题解决多阶段决策过程最优问题 这里的这里的Programming是计划和规划的意思是计划和规划的意思3 1.最优化原理（最优子结构性质）最优化原理（最优子结构性质） 一个最优化策略的子策略总是最优的。一个问题满一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质足最优化原理又称其具有

2、最优子结构性质 使我们可以使我们可以自底向上自底向上的方式从的方式从子问题的最优解子问题的最优解逐步逐步构造出整个问题的最优解。构造出整个问题的最优解。 最优化原理是动态规划的基础，任何问题，如果失最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法去了最优化原理的支持，就不可能用动态规划方法计算计算 若路线若路线I I和和J J是是A A到到C C的最优路径，则的最优路径，则根据最优化原理，路线根据最优化原理，路线J J必是从必是从B B到到C C的最优路线。的最优路线。4 2.无后向性无后向性 将各阶段按照一定的次序排列好之后，对于某个给将各阶段按照一定

3、的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。这就是无后向性，又称为无后效性。 5 3.子问题的重叠性子问题的重叠性(非必要条件非必要条件) 该条件为非必要条件，该条件为非必要条件，但是缺少此条件，则动态规划方法与别的方法相比毫无优势。但是缺少此条件，则动态规划方法与别的方法相比毫无优势。 每次产生的子问题并不是新的子问题，

4、有些子问题被重复计每次产生的子问题并不是新的子问题，有些子问题被重复计算。算。 在解某一问题中，相同的子问题反复出现，并且不同子问题在解某一问题中，相同的子问题反复出现，并且不同子问题的个数又相对较少时，用动态规划是有效的。的个数又相对较少时，用动态规划是有效的。 动态规划实质上是一种以空间换时间的技术，动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。所以它的空间复杂度要大于其它的算法。6 基本思路：基本思路： （1）找出最优解的性质，并刻画其结构特征。）找出最优解的

5、性质，并刻画其结构特征。 （2）递归地定义最优值。）递归地定义最优值。 （3）以）以自底向上自底向上的方式计算出最优值。的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个）根据计算最优值时得到的信息，构造一个最优解。最优解。 与分治法比较与分治法比较 都将问题划分为若干个子问题都将问题划分为若干个子问题 分治法中各子问题相互独立，而动态规划中各子问分治法中各子问题相互独立，而动态规划中各子问题允许相互交叠题允许相互交叠7 注意：注意： 动态规划一般用于多阶段最优化问题动态规划一般用于多阶段最优化问题 但是书中但是书中 8.1 计算二项式系数计算二项式系数 8.2.1 warsha

6、ll 并不是最优化问题。并不是最优化问题。 8.2.2 floyed 8.3 最优二叉查找树最优二叉查找树 8.4 背包问题背包问题 才是最优化问题才是最优化问题对于交叠的子问题，对于交叠的子问题，无需一次又一次的求无需一次又一次的求解，只需将每个较小解，只需将每个较小子问题求解一次并把子问题求解一次并把结果记录在表中。结果记录在表中。8910 二项式系数，记作二项式系数，记作C(n,k)或者或者 ，是来自于一个，是来自于一个n元素集合的元素集合的k元素组合元素组合(子集子集)的数量的数量(0kn) 该名字来源于二项式公式该名字来源于二项式公式 递推式递推式(特性特性) C(n, k) = C

7、(n-1, k-1) + C(n-1, k), 当当n k 0 C(n, 0) = C(n, n) = 1 因此计算因此计算C(n, k) 变为变为C(n-1, k-1) 和和C(n-1, k)两个较小的交叠问题两个较小的交叠问题nk ()( ,0).( , ).( , )nnn iinabC naC n i abC n n b11 动态规划算法动态规划算法 把二项式系数记录在一张把二项式系数记录在一张n+1行行k+1列的表中列的表中C(i,j)的值记录的值记录在第在第i行，第行，第j列列12 算法算法 Binomial(n,k) /用动态规划算法计算用动态规划算法计算C(n,k) /输入：输

8、入：对非负整数对非负整数n=k=0 /输出：输出：C(n,k)的值的值 for i 0 to n do for j 0 to min(i,k) do if j=0 or j=i Ci,j 1 else Ci,j Ci-1,j-1+Ci-1,j return Cn,k 13 时间效率分析时间效率分析 基本操作：加法基本操作：加法14 Warshall 算法用于计算有向图传递闭包算法用于计算有向图传递闭包 Floyd算法用于计算全部最短路径算法用于计算全部最短路径15 传递闭包定义传递闭包定义: 一个一个n顶点有向图的传递闭包可顶点有向图的传递闭包可以定义为一个以定义为一个n阶布尔矩阵阶布尔矩阵T

9、=tij，如果从第如果从第i个个顶点到第顶点到第j个顶点之间存在一条有效的有向路径个顶点之间存在一条有效的有向路径，矩阵第矩阵第i行行(1in)第第j列列(1jn)的元素为的元素为1；否则，；否则，tij为为 0换言之：对给定的有向图，换言之：对给定的有向图， 求出每个点能到达的所有点求出每个点能到达的所有点16dcba邻接矩阵邻接矩阵 a b c da 0 1 0 0b 0 0 0 1c 0 0 0 0d 1 0 1 0传递闭包传递闭包 a b c da 1 1 1 1b 1 1 1 1c 0 0 0 0d 1 1 1 1对给定的有向图，对给定的有向图， 求出每个点能到达的所有点求出每个点能

10、到达的所有点17 求传递闭包是图论中一个非常重要的问题，例如求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。的方法获知任意两个地点之间是否有路相连通。 用深度优先查找和广度优先查找如何生成传递闭用深度优先查找和广度优先查找如何生成传递闭包？包？18 动态规划求解思路动态规划求解思路 动态规划将问题分段，动态规划将问题分段，Warshall算法是通过一算法是通过一系列系列n阶矩阵阶矩阵R（k）来构造最终阶段来构造最终阶段n阶传递闭包阶传递闭包矩阵矩阵R（n）, k =0, 1,

11、 ,n-1.19R（k）由它的前趋由它的前趋 R（k-1）计算得到（分级推进计算）计算得到（分级推进计算） 允许路径中包含前允许路径中包含前k个顶点作为中间顶点个顶点作为中间顶点 R（0） 该矩阵不允许它的路径中包含任何中间该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的任意顶点出发的路径不含有中顶点，即从该矩阵的任意顶点出发的路径不含有中间顶点，此即间顶点，此即邻接矩阵邻接矩阵。 R（1） 允许路径中包含第允许路径中包含第1个顶点作为中间顶个顶点作为中间顶点。点。20 R（2） 允许路径中包含前允许路径中包含前2个顶点作为中间顶点个顶点作为中间顶点。 . R（k） 允许路径中包含前允许路

12、径中包含前k个顶点作为中间顶点个顶点作为中间顶点。 R（n） 允许路径中包含全部允许路径中包含全部 n 个顶点作为中间个顶点作为中间顶点。顶点。 每个后继矩阵每个后继矩阵 R（k）对其前趋对其前趋 R（k-1） 来说，在路径来说，在路径上允许增加一个顶点，上允许增加一个顶点， 因此有可能包含更多的因此有可能包含更多的1（增加前为增加前为1的在增加后依然为的在增加后依然为1）。）。21用与或式可以直接写成下式：用与或式可以直接写成下式：不包含第不包含第k个节点个节点 包含第包含第k个节点个节点22 WARSHALL算法的时间复杂度为算法的时间复杂度为O(n3)。23 算法思想说明算法思想说明 搭

13、桥找路径搭桥找路径 选取一个顶点作为桥梁，考察所有顶点，是否选取一个顶点作为桥梁，考察所有顶点，是否可以通过桥梁到达其它的顶点。可以通过桥梁到达其它的顶点。 用用i控制依次选择各顶点做桥梁。控制依次选择各顶点做桥梁。 用用j控制当选定某顶点做为桥梁时，依次考察所控制当选定某顶点做为桥梁时，依次考察所有顶点。有顶点。 用用k控制当桥梁选定时，考察某一顶点通过该桥控制当桥梁选定时，考察某一顶点通过该桥梁是否可以到达其它顶点。梁是否可以到达其它顶点。24 外循环第一次，选择外循环第一次，选择0作为桥梁作为桥梁 考察考察0是否可以通过是否可以通过0到达其它顶点到达其它顶点 1 0 1 0 0 1 考察

14、考察1是否可以通过是否可以通过0到达其它顶点到达其它顶点 1 1 1 0 0 1 考察考察2是否可以通过是否可以通过0到达其它顶点到达其它顶点 0 1 1 0 0 0 考察考察3 0 0 1 1 1 0 考察考察4 0 0 0 0 1 1 考察考察5 0 0 0 0 1 11234050 1 2 3 4 50 1 0 1 0 0 11 1 1 0 0 0 02 0 1 1 0 0 03 0 0 1 1 1 04 0 0 0 0 1 15 0 0 0 0 1 1用用i控制控制用用j控制控制用用k控制控制25 外循环第二次，增加外循环第二次，增加1为桥梁为桥梁 考察考察0是否可以通过是否可以通过1

15、到达其它顶点到达其它顶点 1 0 1 0 0 1 考察考察1是否可以通过是否可以通过1到达其它顶点到达其它顶点 1 1 1 0 0 1 考察考察2是否可以通过是否可以通过1到达其它顶点到达其它顶点 1 1 1 0 0 1 考察考察3 0 0 1 1 1 0 考察考察4 0 0 0 0 1 1 考察考察5 0 0 0 0 1 10 1 2 3 4 50 1 0 1 0 0 11 1 1 1 0 0 12 0 1 1 0 0 03 0 0 1 1 1 04 0 0 0 0 1 15 0 0 0 0 1 1123405可看成是动态可看成是动态规划的阶段性，规划的阶段性，意味着可以通意味着可以通过过0

16、，1。即当。即当前是否有路径前是否有路径可以建立在可以建立在前前一阶段一阶段的路径的路径基础上。基础上。26 循环循环6次结束，次结束，M最终记录了闭包矩最终记录了闭包矩阵的信息。阵的信息。 实现细节说明之一实现细节说明之一 if(M j，iT) for (k=1; i n; i+ ) 当当M j，iF时说明什么？时说明什么？ 考察的顶点考察的顶点j到到桥梁桥梁i没有路径，没有路径， 也就意味着该顶点不可能通过选择的桥梁建立到也就意味着该顶点不可能通过选择的桥梁建立到其它顶点的路径，因此不必考察它通过该桥梁是其它顶点的路径，因此不必考察它通过该桥梁是否可以到达其它顶点，即内循环不用做。否可以到

17、达其它顶点，即内循环不用做。27 完全最短路径问题：完全最短路径问题： 找到从每个顶点到其他所有顶点之间的距离找到从每个顶点到其他所有顶点之间的距离(最短路径的长度最短路径的长度) dcba23671 权重矩阵 0 3 2 0 7 0 1 6 0 距离矩阵 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 028 Floyd算法中体现的动态规划思路：算法中体现的动态规划思路： 用一系列用一系列n阶矩阵来计算一个阶矩阵来计算一个n顶点加权图的距离顶点加权图的距离矩阵矩阵 矩阵矩阵D(k)的第的第i行第行第j列的元素列的元素dij (k)为从第为从第i个顶点到个顶点到第第j个顶点之间

18、最短路径的长度，个顶点之间最短路径的长度，并且路径的每一并且路径的每一个中间顶点的编号不大于个中间顶点的编号不大于k (0)(1)( )( ),., ,.,kknDDDD29 D(0) 为权重矩阵为权重矩阵D(n)为距离矩阵为距离矩阵 （1）找出最优解的性质，并刻画其结构特征）找出最优解的性质，并刻画其结构特征 （2）并递归地定义最优值。）并递归地定义最优值。(0)( )(1)(1)(0)1,min,kkkijijijijikkjkdwdddd当时不包含第不包含第k个节点：个节点： dij (k-1) 包含第包含第k个节点：个节点： dik (k-1) + dkj (k-1)k-130注：注：

19、从任意节点i到任意节点j的最短路径不外乎2种可能， Case 1. 直接从i到j， Case 2. 从i 经过若干个节点k 到j。 我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立， 如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)， 这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。31 （3）以）以自底向上自底向上的方式计算出最优值。的方式计算出最优值。 （4）根据计算最优值时得

20、到的信息，构造一个最优解。）根据计算最优值时得到的信息，构造一个最优解。32dcba23671 D(0) 0 3 2 0 7 0 1 6 0 D(1) 0 3 2 0 5 7 0 1 6 9 0 D(2) 0 3 2 0 5 9 7 0 1 6 9 0 D(3) 0 10 3 4 2 0 5 6 9 7 0 1 6 16 9 0 D(4) 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 033算法算法 Floyd(W1.n,1.n) / 实现计算完全最短路径的实现计算完全最短路径的Floyd算法算法 / 输入：图的权重矩阵输入：图的权重矩阵W / 输出：包含最短路径长度的距离矩

21、阵输出：包含最短路径长度的距离矩阵 for 1 to do for 1 to do for j1 to do , min , , , + , return DWkninnD i jD i j D i kD k jD算法效率算法效率(n3)34问题描述问题描述 给定给定n个键个键a1, a2, a3, ., an,其相应的查其相应的查找概率为找概率为p1, p2, p3, ., pn。构成最优。构成最优BST,表示为表示为T1n ，求这棵树的，求这棵树的平均查找次数平均查找次数C1, n（耗费最低（耗费最低)。 换言之，如何构造这棵最优换言之，如何构造这棵最优BST，使得，使得C1, n 最小。

22、最小。35 它在查找中的它在查找中的平均比较次数是最低平均比较次数是最低的的 平均比较次数的计算：所有节点上平均比较次数的计算：所有节点上 概率与比较次数的乘积之和概率与比较次数的乘积之和 例子：非最优二叉查找树例子：非最优二叉查找树 ABCDABCD36 动态规划法策略是将问题分成多个阶段，逐段推动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得进计算，后继实例解由其直接前趋实例解计算得到。到。 对于最优对于最优BST问题，利用减一技术和最优性原则，问题，利用减一技术和最优性原则，如果前如果前n-1个节点构成最优个节点构成最优BST，加入一个节点，加入一个节

23、点an 后要求构成规模后要求构成规模n的最优的最优BST。 按按 n-1, n-2 , . , 2, 1 递归，问题可解。自底向上递归，问题可解。自底向上计算：计算：C1, 2C1, 3 . C1, n。37 用用Ci, j 表示由表示由a1, a2, ., an构成的构成的BST的耗费的耗费。其中。其中1i j n。这棵树表示为。这棵树表示为Tij。 从中选择一个键从中选择一个键ak作根节点，它的左子树为作根节点，它的左子树为Ti, k-1，右子树为，右子树为Tk+1,j。要求选择的。要求选择的k 使得整棵树的平均使得整棵树的平均查找次数查找次数Ci, j最小。最小。 左右子树递归执行此过程

24、。（根的生成过程）左右子树递归执行此过程。（根的生成过程）3839 可能的最优二叉查找树形式可能的最优二叉查找树形式 其中其中Ti, k-1 , Tk+1, j 是两棵最优二叉查找子树是两棵最优二叉查找子树 注意这只是注意这只是可能的最优二叉查找树形式，可能的最优二叉查找树形式，注意树的表注意树的表示符号示符号40Ci,j表示这棵树表示这棵树中成功查找的最小中成功查找的最小的平均查找次数的平均查找次数41 考虑用二维表记录考虑用二维表记录Ci,j 当当i在在1和和n+1之间时，之间时，Ci,i-1为多少？为多少？ 当当i在在1和和n之间时，之间时，Ci,i为多少？为多少？ 我们的目标是求什么？

25、我们的目标是求什么？0 p1 目标 0 p2 Ci,j pn 001jnn+11 i仅求出仅求出C1,n是否是否可以获得最优二叉可以获得最优二叉查找树本身查找树本身42 例：例： 键键 A B C D查找概率查找概率 0.1 0.2 0.4 0.3 初始表43 最终表 计算C1,244 为了获得最优二叉树本身需要记录什么？为了获得最优二叉树本身需要记录什么？45得到最优二叉查找树46算法算法 OptimalBST(P1.n) / 用动态规划算法求最优二叉查找树用动态规划算法求最优二叉查找树 /输入：一个输入：一个n个键的有序列表的查找概率数组个键的有序列表的查找概率数组P1.n /输出：在最优

26、输出：在最优BST中成功查找的平均比较次数，以及最优中成功查找的平均比较次数，以及最优BST中子树的根中子树的根表表R for i1 to n do Ci,i-10 Ci,iPi Ri,ii Cn+1,ni for d1 to n-1 do /对角线计数对角线计数 for i1 to n-d do ji+d minval for ki to j do if Ci,k-1+Ck+1,j w. Item k cant be part of the solution, since if it was, the total weight would be w, which is unacceptabl

27、e Second case: wk =w. Then the item k can be in the solution, and we choose the case with greater valueelse , 1, 1max if , 1,kkkbwwkBwkBwwwkBwkB3/1/2022for w = 0 to WB0,w = 0for i = 0 to nBi,0 = 0for w = 0 to Wif wi Bi-1,wBi,w = bi + Bi-1,w- wielseBi,w = Bi-1,welse Bi,w = Bi-1,w / wi w 3/1/2022for w

28、 = 0 to WB0,w = 0for i = 0 to nBi,0 = 0for w = 0 to W算法运行时间O(W)O(W)Repeat n timesO(n*W)蛮力法：蛮力法：O(2n)3/1/2022583/1/202259for w = 0 to WB0,w = 0000000W012345i01234n = 4 ( 4个物品)W = 5 (最大容量)物品 (重量， 收益):(2,3), (3,4), (4,5), (5,6)3/1/202260for i = 0 to nBi,0 = 0000000W012345i0123000043/1/202261 if wi Bi-1

29、,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=1w-wi =-1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403/1/202262 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=2w-wi =0Items:1:

30、(2,3)2: (3,4)3: (4,5) 4: (5,6)4033/1/202263 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=3w-wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333/1/202264 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi

31、w 000000W012345i01230000i=1bi=3wi=2w=4w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403333/1/202265 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=5w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033333/1/202266 if wi Bi-1,w Bi,w = bi

32、 + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=1w-wi=-2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333303/1/202267 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=2w-wi=-1Items:1: (2,3)2:

33、(3,4)3: (4,5) 4: (5,6)403333033/1/202268 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=3w-wi=0Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033330343/1/202269 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / w

34、i w 000000W012345i01230000i=2bi=4wi=3w=4w-wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333303443/1/202270 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=5w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403333034473/1/202271 if wi Bi-1

35、,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=1.3Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033330 034470343/1/202272 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=4w- wi=0I

36、tems:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 03447034533333/1/202273 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=5w- wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 034470345733333/1/202274 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=1.4Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 0344703457034533333/1/202275 if wi Bi-