第3章 动态规划(1-例子).pdf

《第3章 动态规划(1-例子).pdf》由会员分享，可在线阅读，更多相关《第3章 动态规划(1-例子).pdf（44页珍藏版）》请在三一文库上搜索。

1、1 完全加括号的矩阵连乘积可递归地定义为： 设有四个矩阵 ，它们的维数分别是： 总共有五种完全加括号的方式 （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AA BC )(BCA DCBA , , , 1050A4010B3040C 530D )(DBCA )(DCAB)(DBCA )(CDBA )(CDAB 16000, 10500, 36000, 87500, 34500 完全加括号的矩阵连乘积完全加括号的矩阵连乘积 2 再看一例子： A1:10100, A2:1005, A3:550 乘法次序 (A1A2

2、)A3: 10 100 5 + 10 5 50 = 7500 A1(A2A3): 10 100 50 + 100 5 50 = 75000 完全加括号的矩阵连乘积完全加括号的矩阵连乘积 3 矩阵连乘问题矩阵连乘问题 给定n个矩阵 ， 其中 与 是可乘 的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以 有许多不同的计算次序。这种计算次序可以用加括号 的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该 连乘积已完全加括号，则可以依此次序反复调用2个矩 阵相乘的标准算法计算出矩阵连乘积。 ,., 21n AAA i A 1i A 1,.,2 , 1ni n

3、AAA. 21 4 给定n个矩阵A1 ,A2 ,An，其中Ai与Ai+1是可乘的， i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得 依此次序计算矩阵连乘积需要的数乘次数最少。 穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计 算次序相应需要的数乘次数，从中找出一种数乘次数最少的 计算次序。 算法复杂度分析：算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1 .Ak )(Ak+1 An )可以得到关于P(n)的递推式如下： )/4 ()( 1 1 )()( 1 )( 2/ 3 1 1 nnP

4、n n knPkP nP n n k 矩阵连乘问题矩阵连乘问题 5 Catalan数很神奇，常出现在组合数学中各种计数 问题。 其n阶递推关系： h(0)=1,h(1)=1,h(n)=h(0)*h(n-1) + h(1)*h(n- 2) + . + h(n-1)h(0) (其中n=2) 递推关系解的一般公式：C(2n,n)/(n+1) 前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 矩阵连乘问题矩阵连乘问题 对于n个矩阵连乘积的不同计算

5、次序数P(n)，P(n)是 Catalan数。 小课堂小课堂 6 矩阵连乘问题矩阵连乘问题 什么样的计数值是什么样的计数值是什么样的计数值是什么样的计数值是CatalanCatalan数，如下例子：数，如下例子：数，如下例子：数，如下例子： 有n+1个矩阵连乘的加括弧的方式数 有n+1个叶节点的二叉树共有多少种形状？例如4个叶节点： 将一个凸n边形区域分成三角形区域的方法数? 例如6边形分 割： 小课堂小课堂 7 矩阵连乘问题矩阵连乘问题 在n*n的方格地图中，从一个角到另外一个角，不跨越对角线 的路径数，例如44地图中的路径有： 进栈序列为1,2,3,.n(栈无穷大)有多少种不同的出栈序列?

6、 在圆上选择2n个人,两两握手，但无交叉的方案数。 n对括号(左括号和右括号)有多少种匹配方式？ 在Enumerative Combinatorics一书中，竟然提到了多达 66种组合问题和卡特兰数有关。 小课堂小课堂 8 矩阵连乘问题矩阵连乘问题 穷举法穷举法 动态规划动态规划 将矩阵连乘积 简记为Ai:j ，这里ij jii AAA. 1 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全 加括号方式为).)(.( 211jkkkii AAAAAA 计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上 Ai:k和Ak+1:j相乘的

7、计算量。 9 特征：计算Ai:j的最优次序所包含的计算矩阵子 链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题 的最优解。这种性质称为最优子结构性质最优子结构性质。问题 的最优子结构性质是该问题可用动态规划算法求 解的显著特征。 分析最优解的结构分析最优解的结构 20 2510 205 1015 535 1530 35 A6A5A4A3A2A1 最优计算次序为：最优计算次序为：(A1 (A2 A3 )(A4 A5 )A6 ) 若：若：A1 A2 A3的最优次序是：的最优次序是：A1 (A2 A3 ) 或若或若A4 A5 A6的最优次序是：的最优次序是：(

8、A4 A5 )A6 假设A i : k 不是最优，可用最优的 替换原来计算次序，得到A i : j 更 好的次序。矛盾矛盾 10 建立递归关系建立递归关系 设计算Ai:j，1ijn，所需要的最少数乘次数mi,j， 则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n 当ij时， 可以递归地定义mi,j为： jki pppjkmkimjim 1 , 1, 这里 的维数为 i A ii pp 1 jipppjkmkim ji jim jki , 1,min 0 , 1 jki 的位置只有 种可能 kij 11 计算最优值计算最优值 对于1ijn不同的有序对(i

9、,j)对应于不同的子问 题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多 次 许多子问题被重复计算多 次。这也是该问题可用动态规划算法求解的又一显著 特征。 用动态规划算法解此问题，可依据其递归式以自底向 上的方式进行计算。在计算过程中，保存已解决的子 问题答案。每个子问题只计算一次，而在后面需要时 只要简单查一下，从而避免大量的重复计算，最终得 到多项式时间的算法。 )( 2 2 nn n 12 计算最优值计算最优值 在递归计算时，许多子问题被重复计算多次在递归计算时，许多子问题被重复计算多次 13 方法一：递归算法求解方法一：递归算法求解 14 递归算法复

10、杂性递归算法复杂性 看出：递归算法的计算时间随着看出：递归算法的计算时间随着n指数增长为下 界，即 指数增长为下 界，即(2n)。 15 递归算法复杂性递归算法复杂性 16 方法二：用动态规划法求最优解方法二：用动态规划法求最优解 - 算法算法 void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj

11、; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 17 方法二：用动态规划法求最优解方法二：用动态规划法求最优解 - 算法算法 算法复杂度分析：算法复杂度分析： 算法matrixChain的主要计算量取决于算 法中对r，i和k的3重循环。循环体内的计 算量为O(1)，而3重循环的总次数为 O(n3)。 因此算法的计算时间上界为O(n3)。算法所 占用的空间显然为O(n2)。 18 用动态规划法求最优解用动态规划法求最优解 - 子问题计算顺序子问

12、题计算顺序 19 用动态规划法求最优解用动态规划法求最优解 - 实例、填充方法实例、填充方法 A1A2A3A4A5A6 30 3535 1515 55 1010 2020 25 11375201035043755542 7125205351000262554 32 13000201535250005322 min52 541 531 521 pppmm pppmm pppmm m 例：例：P= 20 用动态规划法求最优解用动态规划法求最优解 - 实例、填充方法实例、填充方法 A1A2A3A4A5A6 30 3535 1515 55 1010 2020 25 例：例：P= S2,5=3 最终结果

13、： m1,6 =15125 S1,6 = 3 (A1A2A3)(A4A5A6) S1,3 = 1 (A1)(A2A3) S4,6 = 5 (A4A5)(A6) 21 用动态规划法求最优解用动态规划法求最优解 - s s数组的作用数组的作用 算法MatrixChain只计算出了最优值，但未给出最优 解。也就是说，通过算法MatrixChain的计算，只知道 了用多少次数乘次数是最少的，但还不知道具体应该按 照什么次序做矩阵的乘法才能达到最少数乘次数。 算法MatrixChain过程中已经记录了构造最优解所需 的全部信息。即Sij中记录的值k表明矩阵链Ai:j 的最佳方式（即最优解）为(Ai:k)

14、(Ak+1:j)。 简言之：为了确定加括号的次序，设计一个表简言之：为了确定加括号的次序，设计一个表si, j 来记录求 得最优时最后一次运算的位置。 来记录求 得最优时最后一次运算的位置。 22 用动态规划法求最优解用动态规划法求最优解 - s s数组的作用数组的作用 因此，从s1n记录的信息可知计算A1:n的最优加 括号方式为：(A1 : s1n)(As1n+1 : n) 如：根据sij的记录，可以计算A1:6的最优加括号 方式： (A1A2A3)(A4A5A6) s1n=3 (A1(A2A3)(A4A5)A6) s13=1, s46=5 (A1(A2A3)(A4A5)A6) s23=2,

15、 s45=4 23 两种算法的比较两种算法的比较 24 相似问题的扩展相似问题的扩展 思考：思考： （1）一行的石子合并 有n堆石子形成一行(a1,a2,an，ai为第i堆石子个 数)，相邻两堆可合并，合并的分值为新堆的石子数。 求合并为一堆的最低得分(或最高得分也同理)。 （2）一圈的石子合并 和前述思考题(1)类似，但n堆石子是围成一圈，求合 并为一堆的最低得分(或最高得分)。 25 相似问题的扩展相似问题的扩展 思考：思考： （1）一行的石子合并 假设mi,j为合并石子AiAj, 1ijn，所 得到的最小得分，若没有“合并”这个动作，则为 0。原问题所求的最优值即为m1,n。 jitaj

16、kmkim ji j it jki , 1,min 0 jmi, 填充mi,j即可得到任意行状摆放的石子合并的最 小得分。 26 相似问题的扩展相似问题的扩展 思考：思考： （2）一圈的石子合并 先将圆圈排列的石头直线化： 在这个直线化的行状排列的石头堆中进行合并，并 且合并的石头链长不超过n。 假设mi,j为合并石子AiAj, 1ij2n-1，所 得到的最小得分。 27 相似问题的扩展相似问题的扩展 思考：思考： （2）一圈的石子合并 原问题所求的最小得分是m1,n, m2,n+1, , mn,2n-1中的最小值，即： 1 min ,1 i n m i ni 28 动态规划算法的基本要素动态

17、规划算法的基本要素 一、最优子结构一、最优子结构一、最优子结构一、最优子结构 原问题的最优解包含着其子问题的最优解。这种性质称 为最优子结构性质最优子结构性质。矩阵连乘计算次序具有此性质。 如何分析最优子结构性质？反证。 首先假设由问题的最优解导出的子问题的解不是最 优的，然后再设法说明在这个假设下可构造出比原问题最 优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，自底向上地、递归地从子 问题的最优解逐步构造出整个问题的最优解。 最优子结构最优子结构是问题能用动态规划算法求解的前提。是问题能用动态规划算法求解的前提。 29 动态规划算法的基本要素动态规划算法的基本要素 二、重叠子问题二

18、、重叠子问题二、重叠子问题二、重叠子问题 递归算法求解问题时，每次产生的子问题并不总是新问题，有 些子问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在 一个表格中，当再次需要解此子问题时，只是简单地用常数时 间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长多项式增长。因此用动 态规划算法只需要多项式时间，从而获得较高的解题效率。 30 动态规划算法的基本要素动态规划算法的基本要素 二、重叠子问题二、重叠子问题二、重叠子问题二、重叠子问题 对矩阵连乘问题，前面分析了：不同子问题个数为 。 直接递归算法效率分析

19、： 设该算法的计算时间为T(n)，由算法的递归部分可得到关于 T(n)的递归不等式： 由数学归纳法可得： )( 2 n 1 1 111 11 n k nknTkT nO nT )()( )( )( )()( nn nT22 1 31 动态规划算法的基本要素动态规划算法的基本要素 三、备忘录方法三、备忘录方法三、备忘录方法三、备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同，区 别在于备忘录方法为每个解过的子问题建立了备忘录以备需要 时查看，避免了相同子问题的重复求解。 int LookupChain (int i，int j) if (mij 0) return mij; if (

20、i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 32 动态规划算法的基本要素动态规划算法的基本要素 三、备忘录方法三、备忘录方法三、备忘录方法三、备忘录方法 关于是使用动态规划动态规划还是使用备忘录方法备忘录方法的

21、选择： 一般来讲，当一个问题的所有子问题都至少要解一 次时（前提），用动态规划算法比用备忘录法好。此 时，动态规划算法没有任何多余的计算，对于许多问 题，常可利用规则的表格存取，减少动态规划算法的 时间和空间需求。 当子问题空间中的部分子问题可不必求解时，用备 忘录法则更为有利，因为从其控制结构可以看出，备 忘录法只解那些确实需要求解的子问题。 33 最长公共子序列最长公共子序列 若给定序列X=x1 ,x2 ,xm ，则另一序列 Z=z1 ,z2 ,zk ，是X的子序列是指存在一个严格递增下 标序列i1 ,i2 ,ik 使得对于所有j=1,2,k有：zj =xij 。例 如，序列Z=B，C，D

22、，B是序列X=A，B，C，B， D，A，B的子序列，相应的递增下标序列为2，3，5， 7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y 的子序列时，称Z是序列X和Y的公共子序列公共子序列。 给定2个序列X=x给定2个序列X=x1 1 ,x,x2 2 , ,x,xm m 和 Y=y 和 Y=y1 1 ,y,y2 2 , ,y,yn n ，找出X和Y的最长公共子序列。，找出X和Y的最长公共子序列。 34 最长公共子序列的例子最长公共子序列的例子 最长公共子序列可能并不唯一，但最长公 共子序列的长度 最长公 共子序列的长度可唯一确定。 35 子序列个数子序列个数 长度为m的X序列共有多少个

23、子序列呢？ 由于X的每个子序列对应于下标集1,2,m的一个子 集，因此X的所有子序列个数是指数数量的，共有 个不同的子序列。 因为： 因此，穷举法需要指数时间。 m 2 m m mmm 2 10 . 36 最长公共子序列的最优子结构最长公共子序列的最优子结构 设序列X=x1 ,x2 ,xm 和Y=y1 ,y2 ,yn 的最长公共子序列为 Z=z1 ,z2 ,zk ，则 (1)若xm =yn，则zk =xm =yn，且Z k-1是Xm-1和Yn-1的最长公共 子序列。 (2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列

24、。 由此可见，2个序列的最长公共子序列包含了这2个序列的 前缀的最长公共子序列。因此，最长公共子序列问题具有 最优子结构性质最优子结构性质。 37 子问题的递归结构子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值 的递归关系。用cij记录序列和的最长公共子序列的长度。 其中， Xi =x1 ,x2 ,xi ；Yj =y1 ,y2 ,yj 。当i=0或j=0时，空序 列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况 下，由最优子结构性质可建立递归关系如下： ji ji yxji yxji ji jicjic jicjic ; 0, ; 0, 0, 0 1,1max

25、 1 11 0 38 计算最优值计算最优值 由于在所考虑的子问题空间中，总共有(mn)个不同的子 问题，因此，用动态规划算法自底向上地计算最优值能提 高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3;

26、构造最长公共子序列构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1, j-1, x, b); cout=0), f(j,0) = 0 (j=0) 字符串字符串21232523311324 字符串字符串312123223445 44 问题扩展问题扩展 思考：思考： （3）求多个字符串(而不是两个字符串)的最长公共子 序列。 采用动态规划，多维数组，多维的维数由多个字符串的个数采用动态规划，多维数组，多维的维数由多个字符串的个数n确定。确定。 F(x1 ,x2 ,xn

27、 )表示第表示第i(i=1,2,n)个串的前个串的前xi 个字符组成的子序列集合中最长的公共 子序列的长度。 个字符组成的子序列集合中最长的公共 子序列的长度。 若若xi =0(i=1,2,n)，有，有F(x1 ,x2 ,xn )=0； 若对每个串，第若对每个串，第xi (i=1,2,n)个字符都相等，则个字符都相等，则 F(x1 ,x2 ,xn )= F(x1 -1,x2 -1,xn -1)+1 否则否则F(x1 ,x2 ,xn )= max F(x1 -1,x2 ,xn ), F(x1 ,x2 -1,xn ), F(x1 ,x2 ,xn -1) 由于多维数组的维数由由于多维数组的维数由n确

28、定，是无法事先确立维数的，因此不能直接用多维数组来 记录这个 确定，是无法事先确立维数的，因此不能直接用多维数组来 记录这个F最优值，但可以把各个状态映射到一维数组的前面若干项。具体的说，若 所有串长乘积的最大范围为 最优值，但可以把各个状态映射到一维数组的前面若干项。具体的说，若 所有串长乘积的最大范围为1000000，把状态，把状态F(x1 ,x2 ,xn )记录到一维数组 记录到一维数组 a01000000的元素的元素a (x1 -1)+(x2 -1)*len1 +(x3 -1)*len1 *len2 +(xn - 1)*len1 *len2 *lenn-1 ，其中，其中leni 表示第表示第i个串的长度。个串的长度。