《算法设计技巧与分析 第7章 动态规划》由会员分享，可在线阅读，更多相关《算法设计技巧与分析 第7章 动态规划（48页珍藏版）》请在金锄头文库上搜索。
1、算法设计技巧与分析Algorithms Design Techniques and Analysis,南方医科大学医工学院 信息技术系,第7章 动态规划,理解动态规划的基本原理掌握动态规划的算法实例（难点）掌握用动态规划设计算法的方法（重点）,Teaching Request,Content,动态规划原理算法实例最长公共子序列问题矩阵链相乘最短路径问题0-1背包问题动态规划范式,1 n=0 f (n)= 1 n=1 f (n-1)+f (n-2) n1,F(4),F(3),F(2),F(2),F(1),F(1),F(0),Fibonacci Serial Problem,Recursion F
2、orm,算法过程： 1. procedure f(n) 2. if (n=1) or (n=2) then return 1 3. else return f(n-1)+f(n-2),时间复杂性：,1,若n=1 或 n=2,若n3,Dynamic Programming Form,计算过程：从f1开始，自底向上计算到fn。时间复杂性：(n)空间复杂性：(1),Dynamic Programming Principle,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。,Difference between DC and DP,
3、都是分解成子问题，由子问题的解得到原问题的解。分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。,7.2 Longest Common Serial,Problem:给出两个长度为n和m的字符串A和B，A=a1a2an，B=b1b2bm，确定在A和B中最长公共子序列的长度。,Example:若A=zxyxyz，B=xyyzx，则A和B的最长公共子序列为xyyz，其长度为4。,令Li,j表示a1a2ai和b1b2bj的最长公共子序列的长度，如果i和j都大于0，那么若ai=bj，Li,j=Li-1,j-1+1若aibj，Li,j=maxLi,j-1，Li-1,j
4、,观察结论7.1,算法 7.1LCS,输入: 字母表 上的两个字符串A和B，长度分别为n和m 。输出: A和B最长公共了序列的长度。,1. for i 0 to n,2. L i，0 0,3. end for,4. for j 0 to m,5. L 0，j 0,6. end for,7. for i 1 to n,8. for j 1 to m,9. if then Li，j Li-1，j-1+1,10. else Li，j maxi，j-1，Li-1，j,11. end if,12. end for,13. end for,14. return Ln，m,定理 7.1,最长公共子序列问题的
5、最优解能够在 时间和 空间内得到。,7.3 Matrix Chain,给定n个矩阵A1, A2, , An，其中Ai 是一个ri-1ri 矩阵( 1in)，即AiAi+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。,Base Principle,考查两个矩阵相乘的情形：C=AB。如果矩阵A,B分别是pr和rq矩阵，则它们的乘积C 将是pq矩阵，其(i, j)元素为,则共需要prq次数乘。,Base Algorithm,void MatrixMultiply(int *a, int *b, int *c, int ra, int ca, int rb, int cb) if(ca!
6、 = rb ) error(“矩阵不可乘”)； for(int i = 0; i ra; i +) for(int j = 0; j cb; j +) int sum = ai0* b0j; for(int k = 1; k ca; k +) sum + = aik* bkj; cij = sum; ,矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(B*C)。,考虑n=4 的情况，此时矩阵运算A*B*C*D可按以下方式（顺序）计算(完全加括号方式)： A* ( (B*C) *D) ， A* (B* (C*D) ， (A*B) * (C*D) ，
7、(A* (B*C) ) *D ，( (A*B) *C )*D,Matrix Multiplication with Bracket,矩阵相乘满足结合律，连乘积可以有许多不同的次序，可以用加括号的方式确定。,设三个矩阵A1, A2, A3大小分别为210，102，210，考虑(A1( A2 A3), (A1A2) A3)的结果与相乘的次数。,对于n个矩阵的连乘积，设有f(n)个计算次序。我们可以在第k个和第k1个矩阵之间将原矩阵划分为两个子矩阵序列，则：,Catalan,其中f (n)=C (n-1)，,Analyze the structure of the Optimization Resu
8、lt,设Mi: j为矩阵连乘积MiMi+1Mj。计算M1: n的最优次序，设该次序在矩阵Mk-1和Mk之间断开，1kn，则完全加括号方式为(M1Mk-1) (MkMn)。总计算量为M1: k-1的计算量加上Mk: n的计算量，再加上M1: k-1和Mk: n相乘的计算量。,考虑M1:k-1 和Mk:n相乘所需的计算量？,M1:k -1的结果为r1*rk的矩阵，Mk:n的结果为rk*rn+1的矩阵，则它们相乘的计算量为r1*rk*rn+1,Optimization Sub-structure,计算M1:n的一个最优次序所包含的计算矩阵子链M1:k和Mk+1:n的次序也是最优的。矩阵连乘积计算次序
9、问题的最优解包含着其子问题的最优解，也就是最优子结构性质。,设计算Mi: j所需的最少次数为Cij，原问题的最优解为C1n。当 i = j 时，Mi : j= Mi , Cii = 0,i=1,2,n。 当 i j 时， Cij=Cik-1+Ckj+rirkrj+1 ki+1, i+2, , j ,Recursive Formula,对于1i j n不同的有序对(i,j)对应于不同的子问题Cij，因此，不同的子问题的个数最多只有,Size of Sub_Problem,用动态规划解此问题时，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简单地查一下，从而避免了大量的
10、重复计算。,24,22,12,34,33,44,11,14,13,23,Optimization Realization,C11 C12 C13 C14 C1n C22 C23 C24 C2n C33 C34 C3n Cn-1n-1 Cn-1n Cnn,计算C i j 时，只用到已计算出的C i k 和C k+1 j ,Basic Ideal,置所有只有一个矩阵的矩阵链计算量为0，即mii=0， i=1,2,n。通过上一步的结果可以得到所有矩阵链长度为2的子问题的最优计算量。通过上两步的结果可以得到所有矩阵链长度为3的子问题的最优计算量。 ,Problem,设要计算矩阵连乘积A1A2A3A4A
11、5，其中各矩阵的维数分别为: A1 A2 A3 A4 A5 510 104 46 610 102,1 2 3 4 5 1 2 3 4 5,m11+m23+r1r2r(3+1)=240+300=540m13=min m12+m33+r1r3r(3+1)=200+120=320,i,j,算法 7.2MATCHAIN,输入: n 个矩阵的链的维数对应于正整数数组 r1n1，其中r1n是n个矩阵的行数，rn+1是 的列数。输出: n 个矩阵相乘的数量乘法的最小次数。,2. C i，i 0,3. end for,6. j i + d,1. for i 1 to n 填充对角线 ,4. for d 1 t
12、o n-1 填充对角线 到 ,5. for i1 to n-d 填充对角线 的项目,7. comment: 下列三行计算 Ci，j,9. for k i + 1 to j,8. Ci，j ,Ci，j minCi，j，Ci，k-1 Ck，j+rirkrj+1,11. end for,12. end for,13. end for,14. return C1，n,Time Complexity,算法MATCHAIN 的主要计算量取决于程序中对r, i 和k 的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。算法需要的空间取决于三角数组的大小，即(n2)。,定理 7.2,一个由 n 个矩阵组成的链相乘，它所需要数量乘法的最小次数可以在 时间和 空间找出。,令人惊讶的结论：该问题可以在O(nlogn)时间内解出！,
