《第3章 动态规划课件》由会员分享，可在线阅读，更多相关《第3章 动态规划课件（30页珍藏版）》请在金锄头文库上搜索。
1、Software College, NEU,1,第3章 动态规划Dynamic Programming,Software College, NEU,2,本章主要内容,矩阵连乘问题 Matrix-Chain Multiplication 动态规划算法的基本要素 Elements of Dynamic Programming 流水作业调度 Scheduling to Maximize Profit 0-1背包问题 0-1 knapsack problem 最优二叉搜索树 Optimal Binary Search Trees,Software College, NEU,3,1 n=0 F(n)=
2、1 n=1 F(n-1)+F(n-2) n1,例31,Fibonacci numbers,F(4),F(3),F(2),F(2),F(1),F(1),F(0),动态规划算法,F(1),F(0),Software College, NEU,4,Computing the nth fibonacci number using bottom-up iteration: f(0) = 0 f(1) = 1 f(2) = 0+1 = 1 f(3) = 1+1 = 2 f(4) = 1+2 = 3 f(5) = 2+3 = 5 f(n-2) = f(n-1) = f(n) = f(n-1) + f(n-2
3、),Software College, NEU,5,动态规划算法,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。,算法思想,Software College, NEU,6,动态规划与分治的联系区别,都是分解成子问题，由子问题的解得到原问题的解。 分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。,Software College, NEU,7,3.1 矩阵连乘问题Matrix-Chain Multiplication,给定n个矩阵A1, A2, , An，其中Ai 是一个ri-1ri 矩
4、阵( 1in)，即AiAi+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。,问题提出,设三个矩阵A1, A2, A3大小分别为10100，1005，550，考虑(A1( A2 A3), (A1A2) A3)的结果与相乘的次数。,Software College, NEU,8,矩阵相乘满足结合律，连乘积可以有许多不同的次序。这种次序可以用加括号的方式确定。 考查两个矩阵相乘的情形：C=AB。如果矩阵A，B分别时pr和rq 矩阵，则它们的乘积C 将是pq 矩阵，其(i, j)元素为 则共需要pqr次数乘。,3.1矩阵连乘问题,A1, A2, A3大小分别为10100，1005，550
5、， (A1( A2 A3), (A1A2) A3)的结果相同，都是1050的矩阵，计算量分别为75000，7500。,Software College, NEU,9,完全加括号的矩阵连乘积 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,考虑n=4 的情况，此时矩阵运算A*B*C*D可按以下方式（顺序）计算(完全加括号方式)： A* ( (B*C) *D) ， A* (B* (C*D) ， (A*B) * (C*D) ， (A* (B*C) ) *D,3.1矩阵连乘问题,Software College, NE
6、U,10,两个矩阵的乘法,void MatrixMultiply(int *a, int *b, int *c, int ra, int ca, int rb, int cb) if(ca! = 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; ,3.1矩阵连乘问题,Software College, NEU,11,穷举搜索法,对于n个矩阵的连乘积，设
7、有p(n)个计算次序。我们可以在第k个和第k1个矩阵之间将原矩阵划分为两个子矩阵序列，然后分别对这两个矩阵子序列完全加括号，最后对所得的结果加括号，则 其中P(n)=C(n-1)，,3.1矩阵连乘问题,Software College, NEU,12,1.分析最优解的结构,设A i: j 为矩阵连乘积AiAi+1Aj 计算A1: n的最优次序，设该次序在矩阵Ak和Ak1之间断开，1kn,则完全加括号方式为(A1Ak) (Ak+1An) 总计算量为A 1: k 的加上A k+1: n 的计算量，再加上A 1: k 和A k+1: n 相乘的计算量。,3.1矩阵连乘问题,Software Coll
8、ege, NEU,13,最优子结构特征,计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。 矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。,3.1矩阵连乘问题,考虑A1:k 和Ak+1:n相乘所需的计算量，A i: k 和A k+1:j 相乘呢?,A1:k 的结果为r1*rk的矩阵，Ak+1:n的结果为rk+1*rn的矩阵，则它们相乘的计算量为p1*pk*pn,Software College, NEU,14,2.建立递归关系,设计算A i: j 所需的最少次数为mij,原问题的最优解为m1n。 当 i = j 时: A i :
9、 j = Ai ,m i i = 0,i=1,2,n。 当 i j 时: m i j =m i k + m k+1 j + pi-1pkpj k i, i+1, , j-1 ,3.1矩阵连乘问题,Software College, NEU,15,采用递归方法计算,int RecurMatrixChain( int i, int, j, int p) if ( ) return 0; int u=RecurMatrixChain(i, i)+RecurMatrixChain(i+1,j) +pi-1*pi*pj; sij=i; for(int k=i+1; kj; k+) int t=Recur
10、MatrixChain(i,k)+RecurMatrixChain(k+1,j) +pi-1*pk*pj; if (tu) u=t; sij=k; return u; ,参加运算矩阵链起始位置,矩阵链终止位置,i=j,取第一个断开位置时计算量,记录当前断开位置,循环取k的可取断开位置,3.1矩阵连乘问题,Software College, NEU,16,递归树,14,11,24,12,34,13,44,22,34,23,44,11,22,33,44,11,23,12,33,33,44,22,33,22,33,11,22,3.1矩阵连乘问题,Software College, NEU,17,可以
11、证明该算法的计算时间T(n)有指数下界，设算法中判断语句和赋值语句花费常数时间，则由算法的递归部分可得关T(n)的递归不等式如下：,因此，当n1时，,可用数学归纳法证明,3.1矩阵连乘问题,Software College, NEU,18,对于1i j n，不同的有序对(i,j)对应于不同的子问题mij，因此，不同的子问题的个数最多只有 用动态规划解此问题时，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简单地查一下，从而避免了大量的重复计算。,3.1矩阵连乘问题,Software College, NEU,19,24,22,34,12,33,44,11,14,13
12、,23,3.1矩阵连乘问题,3.计算最优值,Software College, NEU,20,3.计算最优值,对于m1n可以按照下面顺序构成 m12 m23 m34 m45 mn-1n m13 m24 m35 mn-2n m14 m25 m36 mn-3n m1n-1 m2n m1n,3.1矩阵连乘问题,计算m i j 时，只用到已计算出的m i k 和m k+1 j ,Software College, NEU,21,3.计算最优值,置所有只有一个矩阵的矩阵链计算量为0，即mii=0， i=1,2,n。 通过上一步的结果可以得到所有矩阵链长度为2的子问题的最优计算量。 通过上两步的结果可以得
13、到所有矩阵链长度为3的子问题的最优计算量 ,3.1矩阵连乘问题,计算m i j 时，只用到已计算出的m i k 和m k+1 j ,Software College, NEU,22,A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025,例32,设要计算矩阵连乘积A1A2A3A4A5A6 ,其中各矩阵的维数分别为,1 2 3 4 5 6,15750,2625,750,1000,5000,m11 + m23+p0p1p3=7875 m13=min m12 + m33 + p0p2p3=18000,9375,11875,15125,4375,7125,10500
14、,2500,5375,3500,7875,i,j,Software College, NEU,23,3.计算最优值,void MatrixChain(int p, int n, int * *m, int * *s) for (int i=1; i=n; i+) mii= ;/单个矩阵的计算量 for (int r=2; r=n; r+) /r为每次循环矩阵链的长度 for (int i=1; i= ; i+) int j=i+r-1; mij= mi+1j+pi-1*pi*pj; sij=i; for (int k=i+1; kj; k+) int t= mik+ mk+1j+ ; if (
15、t mij) mij=t; sij=k; ,3.1矩阵连乘问题,0,n r + 1,取第一个可取位置，即断开位置为i,循环取k的可取位置,pi-1*pk*pj,Software College, NEU,24,计算过程,先计算出mii=0, i=1,2,n,然后，依次计算mii+1,i=1,2,n-1(矩阵长度为2)；mii+2,i=1,2,n-2,(矩阵链长度为3)；.每次计算只用到已计算出的mik和mk+1j 计算顺序 m11,m22,m33.mnn m12,m23,m34mn-1n m13,m24,m35mn-2n m1n-1,m2n m1n,3.1矩阵连乘问题,Software College, NEU,25,算法复杂度,算法MatrixChain 的主要计算量取决于程序中对r, i 和k 的三重循环。 循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。,3.1矩阵连乘问题,Software College, NEU,26,4. 构造最优解,上述算法只是明确
