CSCE 411 Lecture 11

From Notes
Jump to navigation Jump to search
Lecture Slides

« previous | Wednesday, September 19, 2012 | next »


Dynamic Programming

Matrix Chain Algoritm

Multiplying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times m} matrix with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \times p} : naïve algorithm takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,m\,p} multiplications and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,(m-1)\,p} additions

Chained multiplications can add up quickly:

Order Matters

Multiplying the following matrices:

  • A : 30 × 1
  • B : 1 × 40
  • C : 40 × 10
  • D : 10 × 25

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ((A\,B)\,(C\,D))} requires 41,200 multiplications, but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A\,((B\,C)\,D))} requires 1400

Matrix Chain Order Problem

Use dynamic programming to find the optimum chaining to give minimum number of operations:

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} matrices such that their sizes are compatible for multiplication.

Define Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(i,j)} to be the minimum number of operations needed to compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i \, A_{i+1} \, \dots \, A_j} .

Goal: find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(1,n)} Basis: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(i,i) = 0}

  1. Consider all possible ways to split Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i} through Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_j} into two pieces
  2. Compare best case cost for computing product of two pieces (plus cost of multiplying two products)
  3. Take the best one such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(i,j) = \min_k(M(i,k) + M(k+1,j) + d_{i-1} \, d_k \, d_j)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \underbrace{(A_i \, \dots \, A_k)}_{P_1} \, \underbrace{(A_{k+1} \, \dots \, A_j)}_{P_2}}

  • minimum cost to compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_(i,k)}
  • minimum cost to compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_2} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_(k+1,j)}
  • cost of computing product of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1 \, P_2} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{i-1} \, d_k \, d_j}

Find Dependencies

Fill in our table for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M}

  1 2 3 4 5
1 0       (goal)
2 n/a 0      
3 n/a n/a 0    
3 n/a n/a n/a 0  
4 n/a n/a n/a n/a 0

Compute cells adjacent to values we already know first (work from diagonal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(1,5)} )

Pseudocode

(1..m).each {|i| M[i][i] = 0}
(1..n-1).each do |d| # diagonals
  (1..n-d).each do |i| # rows w/ an entry on dth diagonal
    j = i+d # column corresponding to row i on dth diagonal
    M[i][j] = Infinity
    (1..j-1).each do |k|
      M[i][j] = min(M[i][j], M[i][k] + M[k+1][j]+d[i-1]d[k]d[j])
    end
  end
end
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_411_Lecture_11&oldid=3289"