Menu
Here is an interesting problem that I encountered in a programming competition:
Problem statement: Given the dimensions of n matrices, determine if there exists an ordering such that the matrices can be multiplied. If there exists one, print out the size (product of the dimensions) of the resultant matrix.
My observations: This reduces to the NP-complete hamiltonian path problem if you consider each matrix as a vertex and draw a directed edge between matrices that can be multiplied. I solved this by simply brute-forcing the problem but this is clearly very slow. I was wondering if there are any clever optimizations for this particular instance of the problem.
454
You can only multiply two matrices if their dimensions are compatible , which means the number of columns in the first matrix is the same as the number of rows in the second matrix. If A=[aij] is an m×n matrix and B=[bij] is an n×p matrix, the product AB is an m×p matrix.
For example, the 2 × 2 and 2 × 3 matrices of multiplication are possible and the resultant matrix is a 2 × 3 matrix.
The product of two matrices will be defined if the number of columns in the first matrix is equal to the number of rows in the second matrix. If the product is defined, the resulting matrix will have the same number of rows as the first matrix and the same number of columns as the second matrix.
Create a node for each dimension length. That is, if there is a matrix of dimension (m,n), then m and n will be vertices in the graph.
For every matrix of size (m,n) connect nodes m and n with a directed edge (there can be multiple edges between two nodes).
Now finding a eularian trail would give the multiplication order.
See http://en.wikipedia.org/wiki/Euler_path for finding Eularian trails. Complexity is pretty close to linear ( O(nlog^3n loglogn) where n is the number of edges = number of matrices) .
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
