Since we are talking about Dynamic Programming we will demonstrate that DP is in fact a good approach for the matrix chain multiplication problem. So we are convinced now that brute force is not a good approach. ![]() P ( n ) = Sum ( P ( k ) P ( n- k ) ) and ( k ) goes from ( 1 ) to ( n- 1 ) ![]() ![]() This solution is suicidal because the running time is exponential. We can use brute force to get all possible ways to parenthesize the matrix chain then choose the one with minimum number of scalar multiplications. ![]() Formulate an algorithm to parenthesize the matrix multiplication chain so that the total number of scalar multiplication is minimal. We did not define our problem yet due to the long introduction so let us do that now. Any two matrices in a row (for example A(i-1) and Ai) must satisfy the following condition: the number of columns (p(i-1)) of the first matrix (A(i-1)) must match the number of rows of the second matrix (Ai). For example p(i-1) does NOT mean (p) multiplied by (i-1) so please keep that in mind. Note that the (i) and (i-1) here are just indexes to denote the position of the matrix within the chain. A ( n- 1 ) x An )Īny matrix in the chain (call it Ai) is a (p(i-1) x pi) matrix which means number of rows = p(i-1) and number of columns = (pi).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |