矩阵连乘 java(最接近算法描述的代码,详细注释)
程序员文章站
2022-07-03 14:40:15
...
public class StrassenMul {
// 填 m s 表,计算最优值
public static void matrixChain(int[] p, int[][] m, int[][] s){
// 填 m s 表
// 填主对角线的值为 0, 此处写法虽有点啰嗦,但与 r>1 能统一起来,便于整体理解算法
for(int r = 1; r < 2; r++)//链长为1,即有1个矩阵相乘
{
for (int i = 0; i <= m.length-r; i++)// m 表对角线全为0
m[i][i] = 0;
for (int i = 0; i < m.length; i++)// m 表上三角的值赋值为 无穷大 便于后期填表比较
for (int j = i+1; j < m.length; j++)
m[i][j] = Integer.MAX_VALUE;
}
// 填m表上三角的值和s表, r 依次遍历上三角的每一条斜线
for(int r = 2; r <= m.length; r++)//链长为2到6,即有2个矩阵相乘 到 有6个矩阵相乘
{
for(int i = 0; i <= m.length-r; i++)//r=2时,m[i][j]中i取值0,1,2,3,4,即 0 ~ m.length-r
{
int j=i+r-1;//单独定义出来j,便于后期调用,由i,r推出j值,m[i][j]从i到j共r个元素,因为r=j-i+1,所以j的值为j=r+i-1
for(int k = i; k < j; k++)// i <= k < j
{
int temp = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];//暂时计算m[i][j],取最小的值及对应的k,核心公式,网上好多错的,可以通过检查 m s 表的值来校验
if(temp < m[i][j])
{
m[i][j] = temp;
s[i][j] = k;
}
}
}
}
}
// 构造最优解
public static void traceBack(int[][] s,int a,int b){
if(a==b)
System.out.print("A"+a);
else {
System.out.print("(");
traceBack(s, a, s[a][b]);
traceBack(s, s[a][b]+1, b);
System.out.print(")");
}
}
public static void main(String[] args) {
int p[] = new int[]{30,35,15,5,10,20,25}; // 定义矩阵 A0,A1,A2,...,A5 其中 Ai 为p[i]行,p[i+1]列
int m[][] = new int[p.length-1][p.length-1]; // 定义相应大小的 m 表
int s[][] = new int[p.length-1][p.length-1]; // 定义相应大小的 s 表
matrixChain(p, m, s); // 调用算法,填 m s 表,计算最优值
traceBack(s, 0, p.length-2); // 调用算法,构造最优解
// 打印 m 表的值
System.out.println();
System.out.println("表 m 的值:");
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m.length; j++)
System.out.printf("%-8d" , m[i][j]);
System.out.println();
}
// 打印 s 表的值
System.out.println("表 s 的值:");
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s.length; j++)
System.out.printf("%-8d" , s[i][j]);
System.out.println();
}
}
}
下一篇: 契丹首任太子耶律倍,他的一生是什么样的?