矩阵连乘问题中,将j-1+1个短阵连乘积 AAH1…A,记为A:小,其所需最少数乘次数记为m可记。现有矩阵A1、A2、A3、A4、 A5和 A6,它们的维度分别为 30×35、 35×15、15x5、 5×10、10×20和20x25,可得m[2][5] 的值是 给出过程
时间: 2023-12-28 16:37:59 浏览: 75
矩阵连乘问题可以使用动态规划算法来解决。定义m[i][j]表示从第i个矩阵到第j个矩阵连乘所需最少的数乘次数,p数组表示矩阵的维度,其中p[i-1]和p[i]表示第i个矩阵的行数和列数。
根据动态规划的思想,可以得到如下状态转移方程:
m[i][j] = min{m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]}, i <= k < j
其中,k表示分界点,m[i][k]表示从第i个矩阵到第k个矩阵连乘所需最少的数乘次数,m[k+1][j]表示从第k+1个矩阵到第j个矩阵连乘所需最少的数乘次数,p[i-1]*p[k]*p[j]表示连乘的代价。
根据这个状态转移方程,可以得到m[2][5]的值为:
m[2][5] = min{m[2][3] + m[4][5] + p[1]*p[3]*p[5], m[2][4] + m[5][5] + p[1]*p[4]*p[5]}
其中,m[2][3]、m[4][5]、m[2][4]和m[5][5]可以根据上述状态转移方程递推得到,p数组已知。
具体计算过程如下:
m[3][3] = 0(单个矩阵不需要乘)
m[4][4] = 0
m[5][5] = 0
m[2][3] = m[2][2] + m[3][3] + p[1]*p[2]*p[3] = 0 + 0 + 30*35*15 = 15750
m[4][5] = m[4][4] + m[5][5] + p[3]*p[4]*p[5] = 0 + 0 + 5*10*20 = 1000
m[2][4] = m[2][2] + m[3][4] + p[1]*p[2]*p[4] = 0 + m[3][4] + 30*35*10 = 15750 + 5250 = 21000
m[3][4] = m[3][3] + m[4][4] + p[2]*p[3]*p[4] = 0 + 0 + 15*5*10 = 750
m[2][5] = min{m[2][3] + m[4][5] + p[1]*p[3]*p[5], m[2][4] + m[5][5] + p[1]*p[4]*p[5]}
= min{15750 + 1000 + 30*15*20, 21000 + 0 + 30*10*20}
= min{33750, 24000}
= 24000
因此,m[2][5]的值为24000。
阅读全文