Example analysis of Java matrix multiplication problem (dynamic programming) algorithm

This paper describes the Java matrix multiplication problem (dynamic programming) algorithm. Share with you for your reference, as follows:

Problem Description: given n matrices: A1, A2, An, where AI and AI + 1 are multiplicative, I = 1, 2, n-1。 Determine the calculation order of calculating the matrix continued product, so that the number of times required to calculate the matrix continued product according to this order is the least. The input data is the number of matrices and the scale of each matrix, and the output result is the calculation order and the minimum multiplication times of the matrix continued product.

Problem analysis: since the matrix multiplication satisfies the combination law, there can be many different calculation orders for calculating the continued product of the matrix. This calculation order can be determined in parentheses. If the calculation order of a matrix continued product is completely determined, that is, the continued product has been completely bracketed, the standard algorithm for multiplying two matrices can be repeatedly called in this order to calculate the matrix continued product.

The fully bracketed matrix continued product can be recursively defined as:

(1) A single matrix is completely bracketed; (2) if matrix concatenation product a is completely bracketed, then a can be expressed as the product of two completely bracketed matrix concatenation products B and C and bracketed, that is, a = (BC)

For example, matrix concatenation product a1a2a3a4 has five different completely bracketed ways: (A1 (A2 (a3a4)), (A1 ((a2a3) A4)), ((A1A2) (a3a4)), ((A1 (a2a3)) A4), ((A1A2) A3) A4). Each completely bracketed method corresponds to the calculation order of a matrix continuous product, which determines the amount of calculation required to make the product.

Look at the following example to calculate the multiplication of three matrices {A1, A2, A3}; The dimensions are 10 * 100100 * 5 and 5 * 50 respectively. Calculate the required times in this order ((A1 * A2) * A3): 10x100x5 + 10x5x5x50 = 7500 times. Calculate the required times in this order (A1 * (A2 * A3)): 10 * 5 * 50 + 10 * 100 * 50 = 75000 times

So the problem is: how to determine the operation order can minimize the amount of calculation.

Algorithm idea:

For example, let the matrix multiplication product a1a2a3a4a5a6 be calculated, 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

Recurrence relation:

Let the minimum number of times required to calculate a [I: J], 1 ≤ I ≤ J ≤ n, 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 in the calculation, K has not been determined. But there are only J-I possible locations for K. Therefore, K is the position where these J-I positions minimize the amount of calculation.

To sum up, the recurrence relationship is as follows:

Construct the optimal solution:

If the disconnection position K corresponding to m [i] [J] is recorded as s [i] [J], after calculating the optimal value m [i] [J], the corresponding optimal solution can be recursively constructed from s [i] [J]. The number in s [i] [J] indicates that the best way to calculate matrix chain a [I: J] should be to disconnect between matrices AK and AK + 1, that is, the best bracketing method should be (a [I: k]) (a [K + 1: J). Therefore, from the information recorded in s [1] [n], it can be seen that the best bracketing method to calculate a [1: n] is (a [1: s [1] [n]] (a [s [1] [n] + 1: n]), which is further recursive, The optimal bracketing method for a [1: s [1] [s [1] [n]] (a [s [1] [s [1] [n]] + 1: s [1] [s [1] [n]]). Similarly, it can be determined that the optimal bracketing method of a [s [1] [n] + 1: n] is disconnected at s [s [1] [n] + 1] [n] According to this recurrence, we can finally determine the optimal complete bracketed method of a [1: n] and construct an optimal solution of the problem.

Operation results:

For more information about Java algorithms, readers who are interested can see the topics on this site: Java data structure and algorithm tutorial, summary of Java DOM node operation skills, summary of java file and directory operation skills, and summary of Java cache operation skills