Go语言视频零基础入门到精通

javalearner

矩阵链乘法最优结合问题
一、《问题的引出》
    看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 ;
按此顺序计算需要的次数
（（A1*A2）*A3）:10X100X5+10X5X50=7500次  按此顺序计算需要的次数
（A1*（A2*A3））:10X5X50+10X100X50=75000次  所以问题是：如何确定运算顺序，可以使计算量达到最小化。

二、问题描述
已知：给定n个矩阵构成的一个矩阵链(A1, A2, ..., An)，矩阵Ai的维数为pi-1×pi,
求：决定该矩阵链的乘法结合顺序（即加括号），使得矩阵链乘法的运行时间最短  
  
   
   

     
   

     
   
  

三、几个前提概念
矩阵链乘法的运行时间将以乘法（单行×单列）的次数来衡量
A是p×q矩阵，B是q×r矩阵，则A×B的运行时间为pqr
矩阵乘法满足结合律

四、首先判断是否具有最优子结构
假设Ai...Aj的矩阵链乘法的最优解是在Ak与Ak+1之间分开的，即(Ai...Ak)(Ak+1...Aj)，则子序列也必定是矩阵链乘法的最优解。  由此可知，问题的最优解包含子问题的最优解，满足最优子结构  五、递归表达式
设m[i, j]为矩阵链Ai...Aj的乘法的最短运行时间，m[1, n]即为问题所求的最优解的值
设s[i, j]为运行时间为m[i, j]时的k值，此函数用于递归构造最优解
递归表达式如下   其中矩阵Ai的维数为pi-1 x pi  六、然后进行自底向上的求解  矩阵m是一个上三角矩阵（不需要考虑i>j的情况），且对角线上的元素值均为0  由上面的递归表达式知，m[i, j]的值只取决于m[i, k]和m[k+1, j]（k≥i且k＜j），
因此自底向上的求解过程实际是按子序列的长度递增来进行的
  最后构造最优解  在推导过程中记录s[i, j]的值，用于递归构造最优解（即矩阵链的圆括号添加顺序）

1. import java.util.Scanner;
   
2. public class MatrixChain {
   
3.    private int[] p;
   
4.    private long[][] m;
   
5.    private int[][] s;
   
6.     public MatrixChain(int[] p,long[][] m,int[][] s){
   
7.        this.p=p;
   
8.        this.m=m;
   
9.        this.s=s;
   
10.     }
    
11.     public long matrixChain() {
    
12.         int n = p.length - 1;
    
13.         for (int i = 1; i <= n; i++) {
    
14.             m[i][i] = 0;
    
15.         }
    
16.          for (int r = 2; r <= n; r++) {
    
17.             for (int i = 1; i <= n - r + 1; i++) {
    
18.                 int j = i + r - 1;
    
19.                 m[i][j] = m[i][i]+m[i + 1][j] + p[i - 1] * p[i] * p[j];
    
20.                 s[i][j] = i;
    
21.                 for (int k = i + 1; k < j; k++) {
    
22.                     long t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
    
23.                     if (t < m[i][j]) {
    
24.                         m[i][j] = t;
    
25.                         s[i][j] = k;
    
26.                     }
    
27.                 }
    
28.            }
    
29.        }
    
30.       return m[1][n];
    
31.     }
    
32.    
    
33.    public  void printResult(int i,int j)//输出最优加括号方式
    
34. {
    
35.          if(i==j)
    
36.           System.out.print("A"+i);
    
37.          else{
    
38.           System.out.print("(");
    
39.           printResult(i,s[i][j]);
    
40.           printResult(s[i][j]+1,j);
    
41.           System.out.print(")");
    
42.          }
    
43.    }
    
44.       
    
45.     public static void main(String[] args) {
    
46.         Scanner in=new Scanner(System.in);
    
47.         int n=in.nextInt()+1;//矩阵个数
    
48.         int p[]=new int[n];
    
49.         for(int i=0;i< n;i++)
    
50.           p[i]=in.nextInt();//矩阵维数
    
51.    
    
52.         long m[][] = new long[n][n];
    
53.         int s[][] = new int[n][n];
    
54.          MatrixChain mc = new MatrixChain(p,m,s);
    
55.         System.out.println("最短运行时间="+mc.matrixChain());
    
56.          for (int i = 1; i < n; i++) {
    
57.             for (int j = 1; j < n; j++) {
    
58.                 System.out.print(m[i][j] + "     ");
    
59.             }
    
60.            System.out.println();
    
61.         }
    
62.         System.out.println();
    
63.         for (int i = 1; i < n; i++) {
    
64.             for (int j = 1; j < n; j++) {
    
65.                 System.out.print(s[i][j]+"  ");
    
66.             }
    
67.             System.out.println();
    
68.         }
    
69.        System.out.println("最好的结合顺序");
    
70.        mc.printResult(1,n-1);
    
71.      }
    
72. }  
    
73. 两次运行：
    
74. C:        est>java  MatrixChain
    
75. 4
    
76. 50 10 40 30 5
    
77. 最短运行时间=10500
    
78. 0     20000     27000     10500
    
79. 0     0     12000     8000
    
80. 0     0     0     6000
    
81. 0     0     0     0
    
82. 0  1  1  1
    
83. 0  0  2  2
    
84. 0  0  0  3
    
85. 0  0  0  0
    
86. 最好的结合顺序
    
87. (A1(A2(A3A4)))
    
88. C:        est>java  MatrixChain
    
89. 6
    
90. 30 35 15 5 10 20 25
    
91. 最短运行时间=15125
    
92. 0     15750     7875     9375     11875     15125
    
93. 0     0     2625     4375     7125     10500
    
94. 0     0     0     750     2500     5375
    
95. 0     0     0     0     1000     3500
    
96. 0     0     0     0     0     5000
    
97. 0     0     0     0     0     0
    
98. 0  1  1  3  3  3
    
99. 0  0  2  3  3  3
    
100. 0  0  0  3  3  3
     
101. 0  0  0  0  4  5
     
102. 0  0  0  0  0  5
     
103. 0  0  0  0  0  0
     
104. 最好的结合顺序
     
105. ((A1(A2A3))((A4A5)A6))
     
106.                   

复制代码

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/5/001032687.zip