This article describes the Java matrix multiplication problem (dynamic programming) algorithm. Share it for your reference, as follows:
Problem description: Given n matrices: A1, A2,...,An, where Ai and Ai+1 are multipliable, i=1, 2..., n-1. Determine the calculation order of calculating the matrix continuous product, so that the number of multiplications required to calculate the matrix continuous product in this order is the least. The input data is the number of matrices and the size of each matrix, and the output result is the calculation order and the minimum number of multiplications for the continuous product of the matrix.
Problem analysis: Since matrix multiplication satisfies the law of association, there can be many different calculation orders to calculate the continuous product of the matrix. This calculation order can be determined by adding brackets. If the order of calculation of a matrix continuous product is completely determined, that is, the continuous product has been fully bracketed, then the standard algorithm for multiplication of two matrices can be repeatedly called in this order to calculate the matrix continuous product.
A completely parenthesed matrix product can be recursively defined as:
(1) The single matrix is completely bracketed;
(2) The matrix product A is completely bracketed, then A can be represented as the product of 2 completely bracketed matrix products B and C and added brackets, that is, A=(BC)
For example, there are 5 different ways to completely bracket the matrix product A1A2A3A4: (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4). Each method of fully bracketing corresponds to the calculation order of a matrix-connected product, which determines the amount of calculation required to make the product.
See the following example, calculate the three matrix multiplication {A1, A2, A3}; the dimensions are 10*100, 100*5, 5*50 respectively. Calculate the required number of times in this order ((A1*A2)*A3): 10X100X5+10X5X50=7500 times, calculate the required number of times in this order (A1*(A2*A3)): 10*5*50+10*100*50=75000 times
So the question is: how to determine the order of operations so that the calculation amount can be minimized.
Algorithm ideas:
Example: Suppose you want to calculate the matrix multiplication product A1A2A3A4A5A6, where the dimensions of each matrix are:
A1:30*35; A2:35*15; A3:15*5; A4:5*10; A5:10*20; A6:20*25
Recursive relationship:
The design calculation A[i:j], 1≤i≤j≤n, and the minimum number of multiplications required m[i,j], then the optimal value of the original problem is m[1,n].
When i=j, A[i:j]=Ai, therefore, m[i][i]=0, i=1,2,…,n
When i<j, if the optimal order of A[i:j] is disconnected between Ak and Ak+1, i<=k<j, then: m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj. Since the position of the disconnection point k is not known during calculation, k has not yet been determined. However, there is only ji possible for K position. Therefore, k is the position where the ji position minimizes the calculation amount.
In summary, there are recursive relationships as follows:
Construct the optimal solution:
If the disconnection position k of the corresponding m[i][j] is denoted as s[i][j], after calculating the optimal value m[i][j], the corresponding optimal solution can be constructed recursively from s[i][j]. The number in s[i][j] shows that the best way to calculate the matrix chain A[i:j] should be disconnected between the matrix Ak and Ak+1, that is, the optimal parentheses should be (A[i:k]) (A[k+1:j). Therefore, from the information recorded by s[1][n], we can see that the optimal parentheses for calculating A[1:n] is (A[1:s[1][n]])(A[s[1][n]+1:n]). Further recursively, the optimal parentheses for A[1:s[1][s[1][s[1][n]]) is (A[s[1][s[1][n]]+1:s[1][s[1][s[1][s[1][n]]). Similarly, it can be determined that the optimal parentheses of A[s[1][n]+1:n] is broken at s[s[1][n]+1][n]... If we continue to recurse this, we can finally determine the optimal complete parentheses of A[1:n] and construct an optimal solution to the problem.
package Matrix;public class Matrix { public static void MatrixChain(int[] p,int n, int[][] m, int[][] s) { for (int i = 1; i <= n; i++) { m[i][i] = 0; } for(int r = 2;r <= n; r++ ) { for(int i = 1; i <= n-r+1; i++) { int j = i+r-1; m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]; s[i][j] = i; for(int k = i+1; k < j; k++) { int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } } public static void Traceback(int i, int j, int[][] s) { if(i == j) return; Traceback(i,s[i][j],s); Traceback(s[i][j] + 1,j,s); System.out.println("Multiply A" + i + "," + s[i][j] + "and A" + (s[i][j] + 1) + "," + j); } public static void main(String[] args) { System.out.println("Wulin.com test results:"); Matrix mc = new Matrix(); int n = 7; int p[] = { 30, 35, 15, 5, 10, 20, 25 }; int m[][] = new int[n][n]; int s[][] = new int[n][n]; int l = p.length-1; mc.MatrixChain(p, l,m, s); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { System.out.print(m[i][j] + "/t"); } System.out.println(); } System.out.println(); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { System.out.print(s[i][j]+" "); } System.out.println(); } mc.Traceback( 1, 6, s); }}Running results:
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.