第3章动态规划1.

SoftwareCollege,NEU1第3章动态规划DynamicProgrammingSoftwareCollege,NEU2本章主要内容矩阵连乘问题Matrix-ChainMultiplication动态规划算法的基本要素ElementsofDynamicProgramming流水作业调度SchedulingtoMaximizeProfit0-1背包问题0-1knapsackproblem最优二叉搜索树OptimalBinarySearchTreesSoftwareCollege,NEU31n=0F(n)=1n=1F(n-1)+F(n-2)n1例3－1FibonaccinumbersF(4)F(3)F(2)F(2)F(1)F(1)F(0)动态规划算法F(1)F(0)SoftwareCollege,NEU4Computingthenthfibonaccinumberusingbottom-upiteration:•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)SoftwareCollege,NEU5动态规划算法将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。算法思想SoftwareCollege,NEU6动态规划与分治的联系区别•都是分解成子问题，由子问题的解得到原问题的解。•分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。SoftwareCollege,NEU73.1矩阵连乘问题Matrix-ChainMultiplication给定n个矩阵{A1,A2,…,An}，其中Ai是一个ri-1×ri矩阵(1≤i≤n)，即Ai×Ai+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。问题提出设三个矩阵A1,A2,A3大小分别为10×100，100×5，5×50，考虑(A1(A2A3)),(A1A2)A3)的结果与相乘的次数。SoftwareCollege,NEU8矩阵相乘满足结合律，连乘积可以有许多不同的次序。这种次序可以用加括号的方式确定。考查两个矩阵相乘的情形：C=AB。如果矩阵A，B分别时p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i,j)元素为则共需要pqr次数乘。3.1矩阵连乘问题A1,A2,A3大小分别为10×100，100×5，5×50，(A1(A2A3)),((A1A2)A3)的结果相同，都是10×50的矩阵，计算量分别为75000，7500。SoftwareCollege,NEU9完全加括号的矩阵连乘积–单个矩阵是完全加括号的；–矩阵连乘积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))*D3.1矩阵连乘问题SoftwareCollege,NEU10两个矩阵的乘法voidMatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)error(“矩阵不可乘”)；for(inti=0;ira;i++)for(intj=0;jcb;j++){intsum=a[i][0]*b[0][j];for(intk=1;kca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}3.1矩阵连乘问题SoftwareCollege,NEU11穷举搜索法•对于n个矩阵的连乘积，设有p(n)个计算次序。我们可以在第k个和第k＋1个矩阵之间将原矩阵划分为两个子矩阵序列，然后分别对这两个矩阵子序列完全加括号，最后对所得的结果加括号，则•其中P(n)=C(n-1)，1)()(11)(11nknPkPnnPnk)/4(211)(23nnnnnCn3.1矩阵连乘问题SoftwareCollege,NEU121.分析最优解的结构•设A[i:j]为矩阵连乘积AiAi+1···Aj•计算A[1:n]的最优次序，设该次序在矩阵Ak和Ak＋1之间断开，1≤kn,则完全加括号方式为((A1···Ak)(Ak+1···An))•总计算量为A[1:k]的加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量。3.1矩阵连乘问题SoftwareCollege,NEU13最优子结构特征•计算A[1:n]的一个最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。•矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。3.1矩阵连乘问题考虑A[1:k]和A[k+1:n]相乘所需的计算量，A[i:k]和A[k+1:j]相乘呢?A[1:k]的结果为r1*rk的矩阵，A[k+1:n]的结果为rk+1*rn的矩阵，则它们相乘的计算量为p1*pk*pnSoftwareCollege,NEU142.建立递归关系•设计算A[i:j]所需的最少次数为m[i][j],原问题的最优解为m[1][n]。•当i=j时:A[i:j]=Ai,m[i][i]=0,i=1,2,···,n。当ij时:m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpjk∈{i,i+1,···,j-1}jipppjkmkimjijimjkijki}]][1[]][[{min0]][[13.1矩阵连乘问题SoftwareCollege,NEU15采用递归方法计算intRecurMatrixChain(inti,int,j,intp[]){if()return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];if(tu){u=t;s[i][j]=k;}}returnu;}参加运算矩阵链起始位置矩阵链终止位置i==j取第一个断开位置时计算量记录当前断开位置循环取k的可取断开位置3.1矩阵连乘问题SoftwareCollege,NEU16递归树1······41······12······41······23······41······34······42······23······42······34······41······12······23······34······41······12······31······23······33······34······42······23······32······23······31······12······23.1矩阵连乘问题SoftwareCollege,NEU17•可以证明该算法的计算时间T(n)有指数下界，设算法中判断语句和赋值语句花费常数时间，则由算法的递归部分可得关T(n)的递归不等式如下：111)1)()((11)1()(nknknTkTnOnT因此，当n1时，111111)(2)()()1(1)(nknknkkTnknTkTnnT可用数学归纳法证明)2(2)(1nnnT3.1矩阵连乘问题SoftwareCollege,NEU18•对于1≤i≤j≤n，不同的有序对(i,j)对应于不同的子问题m[i][j]，因此，不同的子问题的个数最多只有•用动态规划解此问题时，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简单地查一下，从而避免了大量的重复计算。)(22nnn3.1矩阵连乘问题SoftwareCollege,NEU192······42······23······41······23······34······41······11······41······32······33.1矩阵连乘问题3.计算最优值SoftwareCollege,NEU203.计算最优值对于m[1][n]可以按照下面顺序构成m[1][2]m[2][3]m[3][4]m[4][5]……m[n-1][n]m[1][3]m[2][4]m[3][5]……m[n-2][n]m[1][4]m[2][5]m[3][6]……m[n-3][n]m[1][n-1]m[2][n]m[1][n]3.1矩阵连乘问题计算m[i][j]时，只用到已计算出的m[i][k]和m[k+1][j]SoftwareCollege,NEU213.计算最优值•置所有只有一个矩阵的矩阵链计算量为0，即m[i][i]=0，i=1,2,···,n。•通过上一步的结果可以得到所有矩阵链长度为2的子问题的最优计算量。•通过上两步的结果可以得到所有矩阵链长度为3的子问题的最优计算量………………………………3.1矩阵连乘问题计算m[i][j]时，只用到已计算出的m[i][k]和m[k+1][j]SoftwareCollege,NEU22A1A2A3A4A5A630×3535×1515×55×1010×2020×25例3－2设要计算矩阵连乘积A1A2A3A4A5A6,其中各矩阵的维数分别为1234561.2.3.4.5.6.00000015750262575010005000m[1][1]+m[2][3]+p0p1p3=7875m[1][3]=minm[1][2]+m[3][3]+p0p2p3=180009375118751512543757125105002500537535007875ijSoftwareCollege,NEU233.计算最优值voidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i=n;i++)m[i][i]=;//单个矩阵的计算量for(intr=2;r=n;r++){//r为每次循环矩阵链的长度for(inti=1;i=;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+;if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}}3.1矩阵连乘问题0n–r+1取第一个可取位置，即断开位置为i循环取k的可取位置p[i-1]*p[k]*p[j]SoftwareCollege,NEU24计算过程•先计算出m[i][i]=0,i=1,2,···,n,然后，依次计算m[i][i+1],i=1,2,···,n-1(矩阵长度为2)；m[i][i+2],i=1,2,···,n-2,(矩阵链长度为3)；···.每次计算只用到已计算出的m[i][k]和m[k+1][j]•计算顺序m[1][1],m[2][2],m[3][3]….m[n][n]m[1][2],m[2][3],m[3][4]····m[n-1][n]m[1][3],m[2][4],m[3][5]····m[n-2][n]·····m[1][n-1],m[2][n]m[1][n]3.1矩阵连乘问题SoftwareCollege,NEU25算法复杂度•算法MatrixChain的主要计算量取决于程序中对r,i和k的三重循环。•循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。3.1矩阵连乘问题SoftwareC