算法设计与分析 课件 5.5.2-动态规划应用-矩阵连乘-动态规划求解

信息工程大学算法设计与分析动态规划—矩阵连乘之动态规划求解国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版动态规划解题步骤：找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。定义：m[i,j]表示AiAi+1…Aj矩阵连乘问题的最少乘法次数。1.找出最优解性质，刻画结构特征

m[i,j]表示Ai…Aj矩阵连乘问题的最少乘法次数。2.递归地定义最优值

3.以自底向上的方式计算最优值1234…n1234…nm[i,j]表示Ai…Aj矩阵连乘问题的最少乘法次数。1个矩阵2个矩阵3个矩阵4个矩阵…n个矩阵123456123456m[i,j]A1A2252020

15A3A415

55

10A5A610

2020

30p0p1p2p3p4p5P625201551020301.初始化m[i,i]=0，i=1~62.计算相邻2个矩阵m[1,2]=7500m[2,3]=1500m[3,4]=750m[4,5]=1000m[5,6]=6000p数组存放矩阵的行、列n=6个矩阵相乘07500000001500750100060001234561075002015003075040100050600060m[i,j]p0p1p2p3p4p5P62520155102030单选题。算一算，m[1,3]等于（）A.1500B.4000C.7500p数组存放矩阵的行、列12345610750040005250201500250045003075025006250401000400050600060m[i,j]p0p1p2p3p4p5P625201551020303.计算相邻3个矩阵m[1,3],m[2,4],m[3,5],m[4,6]4.计算相邻4个矩阵m[1,4],m[2,5],m[3,6]p数组存放矩阵的行、列p0p1p2p3p4p5P625201551020305.计算相邻5个矩阵m[1,5]=7500m[2,6]=85006.计算相邻6个矩阵m[1,6]=11750p数组存放矩阵的行、列123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]for(intr=2;r<=n;r++)/*r表示长度*/

for(inti=1;i<=n-r+1;i++)/*i表示起点*/{intj=i+r-1;/*j表示终点*/for(intk=i;k<j;k++)/*k表示断开位置*/

m[i][j]=min(m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];}123456123456求解矩阵连乘问题的代码框架1.voidMatrixChain(int*p，intn，int**m，int**s)2.{3.for(inti=1;i<=n;i++)m[i][i]=0;4.for(intr=2;r<=n;r++){/*r是矩阵的数量*/5.for(inti=1;i<=n-r+1;i++)/*i是起始矩阵的编号*/6.{intj=i+r-1;/*j是终止矩阵的编号*/7.m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];8.s[i][j]=i;9.for(intk=i+1;k<j;k++){/*k是断开的位置*/10.intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];11.if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}12.}13.}14.}空间复杂度：O(n2)时间复杂度：O(n3)123456123456123456123456单选题。矩阵连乘问题求解最优值采用如图(a)所示的计算次序，图(b)给出了另一种计算次序，正确吗？A.不正确B.正确(a)(b)123456101133320233330333404550560s[i,j]s[1,6]=3，得到(A1A2A3)(A4A5A6)s[1,3]=1，得到(A1(A2A3))s[4,6]=5，得到((A4A5)A6)最优解为：((A1(A2A3))((A4A5)A6))4.根据计算最优值时得到的信息，构造最优解voidtraceback(int**s,inti,intj){if(i==j){printf(“A%d“,i);return;}intk=s[i][j];printf(“(“);traceback(s,i,k);traceback(s,k+1,j);printf(“)“);}4.根据计算最优值时得到的信息，构造最优解分析括号((A1(A2A3))

((A4A5)A6))每个问题（矩阵长度超过1）的解方案外有一对括号思考：是否可以进行空间优化？采用下标转换法，用一维数组代替二维数组，可以节省(N2-N)/2的空间。123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]石子合并问题：

有n堆石子排成一排，依次编号为1~n。现要将石子有次序地合并为一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为本次合并的得分。

试设计一算法，计算将n堆石子合并成一堆的最大得分。以n=4为例，每堆石子的个数为：3465，共5种合并方案。346510151810+15+18=43346511151811+15+18=4434657187+11+18=3611分析：每次只能选相邻2堆石子合并，最后一次合并是左边若干堆石子与右边若干堆石子进行合并，与矩阵连乘问题类似。sum(i,j)表