欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

矩阵连乘 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();
        }
    }

}

矩阵连乘 java(最接近算法描述的代码,详细注释)