The solution, as we will see, is to break up the problem into a set of related subproblems. Now that we have identified the problem, how do we determine the optimal parenthesization of a product of n matrices? We could go through each possible parenthesization (brute force), but this would require time exponential in the number of matrices, which is very slow and impractical for large n. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, if we had four matrices A, B, C, and D, we would have: ( ABC) D = ( AB)( CD) = A( BCD) = A( BC) D =. In other words, no matter how we parenthesize the product, the result will be the same. We have many options because matrix multiplication is associative. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. Matrix chain multiplication is an optimization problem that can be solved using dynamic programming.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |