使用java实现动态规划法-矩阵链乘（java实现，很清楚）

小灰灰 2021-01-22 18:07 453阅读 0赞

public class MatrixChain { 
        private int[][] arr;
        private static int[][] s;
        private int[] p;
        
        public MatrixChain(int[] p,int[][] arr,int[][] s)
        { 
            this.p=p;
            this.arr=arr;
            this.s=s;
        }
        public int[][] matrixChain()
        { 
            int n=arr.length;
            //对角线上矩阵乘法的运算次数是0，因为是自己和自己，不用乘
            for(int i=0;i<n;i++)
            { 
                arr[i][i]=0;
            }
            //三重循环
            //矩阵规模（从两个矩阵的乘法到n个矩阵的乘法）
            for(int r=2;r<=n;r++)
            { 
                //初始和结尾矩阵
                for(int i=0;i<=arr.length-r;i++)
                { 
                    int j=i+r-1;
                    //假设决策为i时最优解，方便后面的比较
                    arr[i][j]=arr[i+1][j]+p[i]*p[i+1]*p[j+1];
                    s[i][j]=i;
                    //最优决策从i+1到j-1，如果k=2，规模为5，说明先做A0到A2的乘法，再做A3到A4的乘法是最优解，
                    //AO到A2和A3到A4因为是规模比本次规模小的情况，其最优解已经记录在矩阵中了
                    for(int k=i+1;k<j;k++)
                    { 
                        int temp=arr[i][k]+arr[k+1][j]+p[i]*p[k+1]*p[j+1];
                        if(temp<arr[i][j])
                        { 
                            arr[i][j]=temp;
                            s[i][j]=k;
                        }
                    }
                }
            }    
            return s;
        }
        
        //递归地输出问题解的格式
        public void show(int[][] s,int start,int end)
        { 
            if(start!=end)
            { 
                System.out.print("(");
                show(s,start,s[start][end]);
                show(s,s[start][end]+1,end);
                System.out.print(")");
            }
            else
                System.out.print("A"+(start+1));
        }
        //主函数
        public static void main(String[] args)
        { 
        //P指的是原始矩阵链的信息，例如A1-30*35,A2-35*15,A3—15*5,A4-5*10,A5-10*20,A6-20*25
            int[] p=new int[] { 30,35,15,5,10,20,25};
            int[][] arr=new int[6][6];
            int[][] s=new int[6][6];
            MatrixChain mc=new MatrixChain(p,arr,s);
            s=mc.matrixChain();
            System.out.println("最少乘法计算次数是"+mc.arr[0][5]);
            System.out.println("按照如下格式计算可获得最优解");
            mc.show(s,0,5);    
        }
    }