matrixmul.java

矩阵连乘算法

  class MatrixOder
    {
        public static final int INFINITY = Integer.MAX_VALUE;

        /**
         * 矩阵连乘排序
         * c 数组包含元素为每个矩阵的列数
         * 而其中c[ 0 ]为第一个矩阵的行数 
         * D矩阵的下标是从1开始的
         */
         void optMatrix( int [ ] c,int [ ][ ]D,int x,int y)
        {   for(int k=1;k<5;k++)//打印出各个矩阵的行列数
            System.out.println("M"+k+"是"+c[k-1]+"行"+c[k]+"列");
            System.out.println(" ");

            int n = c.length - 1;//n是D矩阵的阶数
            for( int left = 1; left <= n; left++ )//将D矩阵的主对角线置0
                D[ left ][ left ] = 0;
            
            for( int k = 1; k < n; k++ )// k控制D矩阵的对角线
                for( int left = 1; left <= n - k; left++ )
                {
                    int right = left + k;
                    D[ left ][ right ] = INFINITY;
                    for( int i = left; i < right; i++ )//i为断点
                    {
                        int thisCost = D[ left ][  i ] + D[ i + 1 ][ right ]+ c[ left - 1 ] * c[ i ] * c[ right ];
                        //计算两个矩阵相乘的运算量
                        if( thisCost < D[ left ][ right ] ) //将最小运算量和断点记录在D矩阵
                        {
                            D[ left ][ right ] = thisCost;
                            D[ right ][ left ] = i;
                        }
                    }
                }
         System.out.println("生成D矩阵");
         for( int left = 1; left <= 4; left++ )
            {
                for( int right = 1; right <= 4; right++ )
                    System.out.print( D[ left ][ right ] + "    " );
                System.out.println( );
            }
         System.out.println(" ");   
         System.out.println("矩阵连乘的顺序为：") ; 
         Oder(x,y,D);//调用Oder
         System.out.println(" ");
        }
                       
         void Oder(int i,int j,int[][]D)
         {//加括号
            if(i==j) System.out.print("M"+i);
        	else if(i+1==j) System.out.print("(M"+i+"M"+j+")");
        	  else{
        	  int T =D[j][i];
        	  System.out.print("(");
        	  Oder(i,T,D);
        	  Oder(T+1,j,D);
        	  System.out.print(")");}
         }
    }   	  
             
    public class MatrixMul{    	  
        public static void main( String [ ] args )
        { int [ ] c = { 10, 30, 70, 1, 200 };
          int [ ][ ] D = new int [ 5 ][ 5 ];
          int x = 1;
          int y = c.length-1;  
        	
          MatrixOder  matrix = new MatrixOder();
          matrix.optMatrix(c,D,1,y);
        }
    }