- 矩阵连乘问题
- 问题描述：给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的，i=1,2,...,n-1。如何确定矩阵连乘乘积的计算次序，使得依此次序计算矩阵连乘乘积所需要的数乘次数最少。
- 小栗子：有四个矩阵A,B,C,D,它们的维数分别是：A=50*10, B=10*40, C=40*30, D=30*5，连乘顺序用括号的方式表达，连乘乘积ABCD的优先顺序共有5种：(A((BC)D)) 16000 (A(B(CD))) 10500 ((AB)(CD)) 36000 (((AB)C)D) 87500 ((A(BC))D) 34500，序列后面的数字表示按此计算需要计算的乘法次数。
- 动态规划：将矩阵连乘乘积AiAi+1...Aj简记为A[i:j],i<=j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i<=k<j，则A[i:j]的计算量为：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[k+1,j]相乘的计算量。
- 整个栗子：6个矩阵A~F，它们的维数分别是：A=20*25, B=25*5, C=5*15, D=15*10, E=10*20, F=20*25, 求出最优的的连乘序列。
C语言实现：
// Hello, i'm JJU-干干
/* +++++++++++++++++++++++++++++++++++++++++++++++++++++ + + 用一个二维数组m存放最优值，即矩阵连乘做乘法计算的最少次数 + 用一个二维数组s存放断开的位置 + 用一个一维数组p存放各矩阵的维度数，n个矩阵，就有n+1个维度数 + + +++++++++++++++++++++++++++++++++++++++++++++++++++++ */ #include <stdio.h> #include<stdlib.h> #define size 100 void MatrixChain( int n, int m[][size] , int s[][size], int p[]) { int i, r, j, k,temp; for( i=1; i<=n; i++) //对存放最优值的二维数组进行初始化，初始化为0 m[i][i]=0; /* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + + 第一层for循环用来搞矩阵连乘的长度，即矩阵的个数，r的 + 初始值为2，很明显，只有一个矩阵就没有连乘的意义了。 + + 第二层for循环用来确定矩阵连乘片段的左右边界 + + 第三层for循环用来搞断开位置 + + 注意：假设p[0]是第一个矩阵的行数，p[1]是第一个矩阵 + 的列数，p[2]是第二个矩阵的行数，p[3]是第二个矩阵的 + 列数 ，...... , p[n-1]是第n个矩阵的行数，p[n-1]是第n个矩 + 阵的列数。 + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */ for( r=2; r<=n; r++) for( i=1; i<=n-r+1; i++) // i为左边界，即所求连乘片段的第一个矩阵；j为右边界，即所求连乘片段的最后一个矩阵 { j=i+r-1; m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]; // 先假定断开最左边的矩阵作为最优断开位置 s[i][j] = i; for( k=i+1; k<j; k++) //从i+1断开开始是因为上面已经算完了从i断开，即算完了断开最左边 { temp = m[i][k] + m[k+1][j] +p[i-1]*p[k]*p[j]; // 计算做乘法计算的次数 if(temp<m[i][j]) // 最优值的更替 { m[i][j] = temp; s[i][j] = k; } } } } void TraceBack( int i,int j, int s[][size]) //打印括号的函数，运用了分治的思想 { char ch='A'; if(i==j) //递归出口：矩阵连乘片段切分成只有一个矩阵是 {printf("%c",ch+i-1); return;} // 注意：记得写return，返回值为空 printf("("); TraceBack(i, s[i][j],s); TraceBack(s[i][j]+1,j,s); printf(")"); } void main() { int n,i; int m[size][size],s[size][size], p[size]; printf("请输入矩阵连乘的个数："); scanf("%d", &n); printf("请顺序输入%d个矩阵的各个维度（共%d个数）",n,n+1); for(i=0; i<=n; i++) scanf("%d", &p[i]); MatrixChain(n, m, s, p); printf("最优连乘次序为："); TraceBack(1,n,s); printf(" "); system("pause"); }
运行结果：
Python实现：
# Hello, i'm JJU-干干 def MatrixChain(n,m,s,p): for i in range(1,n+1): m[i][i] = 0 for r in range(2,n+1): for i in range(1,n-r+2): j = i+r-1 m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j] s[i][j] = i for k in range(i+1,j): temp= m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] if temp < m[i][j]: m[i][j] = temp s[i][j] = k def TraceBack(i,j,s): ch = ord('A') if i==j: print(chr(ch+i-1),end="") return print("(",end="") TraceBack(i,s[i][j],s) TraceBack(s[i][j]+1,j,s) print(")",end="") if __name__ == '__main__': m = [[0 for i in range(100)] for j in range(100)] s = [[0 for i in range(100)] for j in range(100)] n = int(input("请输入矩阵连乘的个数：")) p=eval(input("请输入%d个矩阵的各维度数（共%d个数）："%(n,n+1))) MatrixChain(n,m,s,p) print("最优的矩阵连乘序列为：",end="") TraceBack(1, n, s)
运行结果：
