程序代写代做代考 chain algorithm CSC373H Matrix Chain

CSC373H Matrix Chain
Dan Zingaro
October 2016

Matrices: Order of Multiplication
􏹩 Multiplying two matrices of dimensions pq and qr takes pqr multiplications
􏹩 Consider these three matrices: 􏹩 Ais1x10
􏹩 Bis10x10 􏹩 Cis10x100
􏹩 We want the product ABC
􏹩 Two choices: (AB)C or A(BC)
􏹩 Does it matter which one we choose?

Matrices: Order of Multiplication…
A1x10,B 10×10,C 10×100
􏹩 (AB)C
􏹩 AB takes1∗10∗10=100multiplicationsandyieldsa1x10
matrix
􏹩 Then, (AB)C takes 1 ∗ 10 ∗ 100 = 1000 multiplications
􏹩 Total multiplications is 1100
􏹩 Now figure out how many multiplications for A(BC)! Hint: it’s way worse!

Matrix Chain Multiplication
􏹩 The matrix-chain multiplication problem asks for the best way to parenthesize a product of matrices to minimize total multiplications
􏹩 Input: Matrices A0, A1, . . . , An−1 with dimensions d0 x d1, d1 xd2,…,dn−1 xdn
􏹩 Output: fully parenthesized product that gives minimum number of multiplications
􏹩 Brute force is impractical: there are Ω(4n) ways to parenthesize a product of n matrices

Matrix Chain: Greedy?
Perhaps we can do the product of smallest cost first? No. Smallest counterexample:
A10x1,B 1×10,C 10×100
Product of largest cost first?
No again. Smallest counterexample is one we saw before: A1x10,B 10×10,C 10×100
Greedy isn’t going to work.

Matrix Chain: Step 1
On to dynamic programming!
􏹩 Consider where to put the last product 􏹩 Therearen−1choicesforthis
􏹩 A0(A1 . . . An−1)
􏹩 (A0A1)(A2 . . . An−1)
􏹩 …
􏹩 (A0A1 . . . An−2)An−1
􏹩 If we knew the cost of each of these n − 1 choices, we could pick the best one

Matrix Chain: Step 1…
Optimal substructure of matrix chain multiplication
􏹩 Supposethebestsplitisp1=A0A1…Ak−1and p2 =AkAk+1…An−1 forsome1≤k≤n−1
􏹩 Then the overall solution must contain optimal solutions to p1 and p2. Why?
􏹩 For contradiction, suppose the optimal solution uses some suboptimal solution for p1
􏹩 Then replace that suboptimal solution to p1 with the optimal solution to p1 to get a better overall solution
􏹩 (Analogous proof by contradiction for p2)

Matrix Chain: Step 2
􏹩 We have a 2d array this time
􏹩 N[i,j]isthesmallestcostofmultiplyingAiAi+1…Aj

Matrix Chain: Step 3
􏹩 The cost of multiplying one matrix is 0 􏹩 Otherwise, we do three kinds of work
􏹩 N[i, k − 1] for the multiplication of the left subproduct
􏹩 N[k,j] for the multiplication of the right subproduct
􏹩 didkdj+1 for the final multiplication
􏰎0, if i = j
N[i,j] =
i