Matrix chain multiplication

Dynamic programming

  • What is dynamic programming
    • A method by which a complex primary problem is decomposed into relatively simple subproblems
  • What are the characteristics of dynamic rules
    • Overlapping subproblems: Subproblems occur repeatedly
    • Optimal substructure: The optimal solution of a problem contains the optimal solution of its subproblems
    • No aftereffect: Once the state of a stage is determined, the evolution of the subsequent process is no longer influenced by previous states and decisions
  • Steps to solve dynamic rule problems
    • Deterministic subproblem
    • Determine the state transition equation
    • Determining boundary conditions

The title

  • Given n matrix sequences :(A1, A2, A3… , An). Compute their product to minimize multiplication
  • Matrix multiplication is associative, two matrices multiply each other a fixed number of times
    • AabAbcMinimum number of matrix multiplications: A * B * C

Analysis of the

  • For example: P =[5,10,3,12,5],A1->5 * 10 (A1 matrix has 5 rows and 10 columns, similarly below), A2->10 * 3,A3->3 * 12,A4->12 * 5, the calculation cost of matrix multiplication is 405, and the optimal scheme is ((A1A2)(A3A4)).
  • There are 4 calculation methods: A1A2A3A4,A1(A2A3)A4,A1A2(A3A4),A1(A2(A3A4))
  • Give the following table, where m[I,j] represents Ai~jThe minimum number of multiplications of
A1A2A3A4 A1(A2A3)A4 A1A2(A3A4) A1(A2(A3A4))
The first step A1A2 A2A3 A3A3 A3A3
The second step M * A3 [1, 2] A1 * m [2, 3] A1A2 A2 * m (3, 4]
The third step M * A4 [1, 3] M * A4 [1, 3] M * m [1, 2] [3, 4] A1 * m (2, 4]

  • Symbol definition:

  • Solve the above problem with the steps of dynamic programming

  • In subproblem analysis, two-dimensional array is used as the storage structure, then the optimal times of matrix multiplication are as follows:

The number of matrices 1 2 3 4
1 0 M [1, 2] M (1, 3] M [1, 4]
2 0 0 M (2, 3] M (2, 4]
3 0 0 0 M (3, 4]
4 0 0 0 0

  • In this array, the ultimate goal is to find the optimal number of multiplications for m[1,4], A1A2A3A4. Imagine that the final result can be obtained from the results already obtained, using the diagonal order in the array, as shown in the figure below:

    • Find the result on the first diagonal for the first time: m[1,2], m[2,3], m[3,4]

    • Find the second result on the second diagonal: m[1,3], m[2,4]

    • The third time find the result on the third diagonal: m[1,4]

  • The results on the first diagonal are both required, and the results on the second and third lines can be calculated from the values already obtained, for example:

    • M (2, 4) = min (m + m (2, 2] [3, 4] p2 + p1 * * p4, m + m (2, 3] [4] + p1 * * p4 p3)
    • M [1, 4] = min (m + m [1, 1] [2, 4] + p1 p0 * * p4, m + m [1, 2] [3, 4] p2 + p0 * * p4, m (1, 3) + m (4, 4) + p0 * * p4 p3)

  • I for rows, J for columns, d for diagonals,

    • j = d + i
    • The minimum range of I is 1 and the maximum range is equal to the number of matrices -d
    • The range of d = 1 ~ number of matrices -1

Code implementation

  // The minimum number of multiplications
function MatrixChain(p){
    let num = p.length- 1// Number of matrices
    let m = [] M [I,j] = m[I,j]
    let s = [] // Store matrix subscripts
 let d / / diagonal  let template // Times of multiplication   for(let i = 1; i <= num; i++){  m[i] = []  m[i][i] = 0   s[i] = []  s[i][i] = 0  }   for(d = 1; d <= num- 1; d++){ // range of d = 1 ~ number of matrices -1  for(let i = 1; i <= num - d; i++){ // the minimum range of I is 1, and the maximum range is = the number of matrices -d  j = i + d // j = d + i  m[i][j] = Number.MAX_SAFE_INTEGER;  for(let k = i; k <= j - 1; k++){  template = m[i][k] + m[k+1][j] + p[i- 1]*p[k]*p[j];  if(template < m[i][j]){  m[i][j] = template  s[i][j] = k  }  }  }  }  printOrder(s, 1, num);  return m[1][num] }  // The parenthesis order of the optimal solution function printOrder(s,i,j){  if (i == j) {  console.log("A[" + i + "]");  } else {  console.log("(");  printOrder(s, i, s[i][j]);  printOrder(s, s[i][j] + 1, j);  console.log(")");  } }  let p=[10.100.5.50] console.log('Minimum multiplication:',MatrixChain(p)) Copy the code

The complexity of the

  • Time complexity
    • Time to calculate the cost O(n^3)
    • The time O(n) to construct the optimal solution
    • Total time O(n^3)
  • Space complexity O(n^2)

The resources

  • Javascript data structures and algorithms
  • From: original address