思路是在矩阵链的每一个地方分别分开,然后找最小
Given a sequence of matrices, find the most efficient way to multiply these matrices together.The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = ....
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, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first method is the more efficient.
Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.
Input: p[] = {40, 20, 30, 10, 30}
Output: 26000
There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
Let the input 4 matrices be A, B, C and D. The minimum number of
multiplications are obtained by putting parenthesis in following way
(A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30
Input: p[] = {10, 20, 30, 40, 30}
Output: 30000
There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30.
Let the input 4 matrices be A, B, C and D. The minimum number of
multiplications are obtained by putting parenthesis in following way
((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30
Input: p[] = {10, 20, 30}
Output: 6000
There are only two matrices of dimensions 10x20 and 20x30. So there
is only one way to multiply the matrices, cost of which is 10*20*30
1) Optimal Substructure:
A simple solution is to place parenthesis at all possible places, calculate the cost for each placement and return the minimum value. In a chain of matrices of size n, we can place the first set of parenthesis in n-1 ways. For example, if the given chain is
of 4 matrices. let the chain be ABCD, then there are 3 way to place first set of parenthesis: A(BCD), (AB)CD and (ABC)D. So when we place a set of parenthesis, we divide the problem into subproblems of smaller size. Therefore, the problem has optimal substructure
property and can be easily solved using recursion.
Minimum number of multiplication needed to multiply a chain of size n = Minimum of all n-1 placements (these placements create subproblems of smaller size)
2) Overlapping Subproblems
Following is a recursive implementation that simply follows the above optimal substructure property.
package DP;
public class MatrixChainMultiplication {
public static void main(String[] args) {
int[] dm = {1, 2, 3, 4};
int begin = 1;
int end = dm.length-1;
System.out.println(matrixChainOrderRec(dm, begin, end));
System.out.println(matrixChainOrderDP(dm, dm.length));
}
// Matrix Ai has dimension dm[i-1] x dm[i] for i = 1..n
public static int matrixChainOrderRec(int[] dm, int begin, int end){
if(begin == end){
return 0;
}
int min = Integer.MAX_VALUE;
// place parenthesis at different places between first and last matrix,
// recursively calculate count of multiplications for each parenthesis
// placement and return the minimum count
for(int k=begin; k<end; k++){
int count = matrixChainOrderRec(dm, begin, k) +
matrixChainOrderRec(dm, k+1, end) +
dm[begin-1]*dm[k]*dm[end];
min = Math.min(min, count);
}
return min;
}
// Matrix Ai has dimension dm[i-1] x dm[i] for i = 1..n
// Time Complexity: O(n^3), Auxiliary Space: O(n^2)
public static int matrixChainOrderDP(int[] dm, int n){
/* For simplicity of the program, one extra row and one extra column are
allocated in dp[][]. 0th row and 0th column of m[][] are not used */
int[][] dp = new int[n+1][n+1];
/* dp[i,j] = Minimum number of scalar multiplications needed to compute
the matrix A[i]A[i+1]...A[j] = A[i..j] where dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for(int i=1; i<n; i++){
dp[i][i] = 0;
}
// L is chain length. L starts from 2
for(int L=2; L<n; L++){
for(int begin=1; begin<n-L+1; begin++){
int end = begin+L-1;
dp[begin][end] = Integer.MAX_VALUE;
for(int k=begin; k<=end-1; k++){
// q = cost/scalar multiplications
int q = dp[begin][k] + dp[k+1][end] + dm[begin-1]*dm[k]*dm[end];
dp[begin][end] = Math.min(dp[begin][end], q);
}
}
}
return dp[1][n-1];
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
分享到:
相关推荐
输入n个矩阵的维度和一些矩阵链乘表达式,输出乘法的次数。如果乘法无法进行,输出error。假定A是m*n矩阵,B是n*p矩阵,那么AB是m*p矩阵,乘法次数为m*n*p。如果A的列数和B的行数不同,则乘法无法进行。 例如,A是50...
struct Matrix { int a, b; Matrix(int a = 0,int b=0):a(a),b(b){} }m[26]; stack s; int main() { int n; cin >> n; for (int i = 0; i > name; int k = name[0] - 'A'; cin >> m[k].a >> m[k].b; } ...
Efficient matrix multiplication
最快的稀疏矩阵乘法运算,英文版 Let A and B two n £ n matrices over a ring R (e.g., the reals or the integers) each containing at most m non-zero elements. We present a new algorithm that multiplies A...
大数据实验报告Hadoop编程实现MatrixMultiplication矩阵相乘程序附源码.doc
C#,数值计算,矩阵相乘的斯特拉森(Strassen’s Matrix Multiplication)分治算法与源代码 矩阵乘法是机器学习中最基本的运算之一,对其进行优化是多种优化的关键。通常,将两个大小为N X N的矩阵相乘需要N^3次运算...
matrix multiplication (see laochanlam/matrix-multiplication in github)
快速矩阵乘法 Fast and Stable matrix multiplication Coppersmith and Winograd's Algorithm 时间复杂度O(n^2.38)
1.自动随机生成5000*5000的2个矩阵 2.使用MPI对矩阵相乘进行并行处理 3.加速比接近10倍
Matrix_multiplication.c
see jaeho3690/Matrix_multiplication_python in github
一个fortran的小程序,用于计算矩阵乘法
matrix-multiplication:Java矩阵乘法
快速 Kronecker 矩阵乘法,适用于全矩阵和稀疏矩阵任何大小。 从不计算实际的 Kronecker 矩阵并省略乘以单位矩阵。 y = kronm(Q,x) 计算y = (Q{k} kron ... Q{2} kron Q{1})*x 如果 Q 仅包含两个矩阵且 x 是向量,则...
Batched Sparse Matrix Multiplication for Accelerating Graph Convolutional Networks 对图卷积网络进行加速的批量稀疏矩阵乘法 作者的ppt的pdf版本
Matrix Chain Multiplication is perhaps the quintessential example of dynamic programming. The problem can be stated as follows: given a chain <A1, A2,..., An> of n matrices, where for i = 1, 2,....
Source Code for 2009 Supercomputing Paper Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors
矩阵乘法 使用 Verilog 设计 4 x 4 矩阵乘法 该设计已通过以下数据验证 设计文件可以在 /src 下找到 可以在 /tb 下找到测试平台 请注意,所有输入数据均应使用8位符号进行签名,而输出数据应使用11位符号进行签名。...
矩阵乘法 链矩阵乘法的动态规划算法的实现
矩阵链乘法 该程序找到了最有效的乘法矩阵的方法。 该程序实现的复杂度为O(n ^ 3),并用O(n)括住最终输出 输入规范:第一行包含n,下一行包含a0,...,an,以空格分隔。 假定所有数字都是正数且适合int且n最多为...