WikiGalaxy
Matrix Chain Multiplication: Introduction
Understanding the Problem:
Matrix chain multiplication is an optimization problem that involves finding the most efficient way to multiply a given sequence of matrices. The goal is to minimize the number of scalar multiplications.
Dynamic Programming Approach:
The problem can be solved using dynamic programming by breaking it down into simpler sub-problems and storing the solutions to avoid redundant calculations.
Example Scenario:
Consider matrices A1, A2, A3 with dimensions 10x30, 30x5, and 5x60. The optimal order of multiplication will minimize the total number of operations.
public class MatrixChainMultiplication {
static int matrixChainOrder(int p[], int n) {
int m[][] = new int[n][n];
for (int i = 1; i < n; i++)
m[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
if (j == n) continue;
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j - 1; k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
public static void main(String args[]) {
int arr[] = new int[] {10, 30, 5, 60};
int size = arr.length;
System.out.println("Minimum number of multiplications is " + matrixChainOrder(arr, size));
}
}
Console Output:
Minimum number of multiplications is 4500
Matrix Chain Multiplication: Recursive Solution
Recursive Approach:
A recursive solution to matrix chain multiplication involves dividing the problem into smaller sub-problems and solving each recursively. However, this approach can be inefficient due to overlapping sub-problems.
Recursive Formula:
The recursive formula is defined as: M(i, j) = min(M(i, k) + M(k+1, j) + p[i-1]*p[k]*p[j]) for all i ≤ k < j.
public class RecursiveMatrixChain {
static int MatrixChainOrder(int p[], int i, int j) {
if (i == j)
return 0;
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
return min;
}
public static void main(String args[]) {
int arr[] = new int[] {10, 30, 5, 60};
int n = arr.length;
System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr, 1, n - 1));
}
}
Console Output:
Minimum number of multiplications is 4500
Matrix Chain Multiplication: Memoization
Memoization Technique:
Memoization is an optimization technique that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Implementation Strategy:
In matrix chain multiplication, memoization is used to store the results of the sub-problems in a table and reuse them whenever needed.
import java.util.Arrays;
public class MemoizedMatrixChain {
static int[][] dp;
static int MatrixChainOrder(int p[], int i, int j) {
if (i == j)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j];
if (count < dp[i][j])
dp[i][j] = count;
}
return dp[i][j];
}
public static void main(String args[]) {
int arr[] = new int[] {10, 30, 5, 60};
int n = arr.length;
dp = new int[n][n];
for (int[] row : dp)
Arrays.fill(row, -1);
System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr, 1, n - 1));
}
}
Console Output:
Minimum number of multiplications is 4500
Matrix Chain Multiplication: Bottom-Up Approach
Bottom-Up Dynamic Programming:
The bottom-up approach solves the problem iteratively by building a solution from the smallest sub-problems to the larger ones, filling up a table with solutions.
Table Construction:
A table is constructed where each entry m[i][j] contains the minimum number of multiplications needed to multiply the matrices Ai through Aj.
public class BottomUpMatrixChain {
static int matrixChainOrder(int p[], int n) {
int m[][] = new int[n][n];
for (int i = 1; i < n; i++)
m[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
if (j == n) continue;
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j - 1; k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
public static void main(String args[]) {
int arr[] = new int[] {10, 30, 5, 60};
int size = arr.length;
System.out.println("Minimum number of multiplications is " + matrixChainOrder(arr, size));
}
}
Console Output:
Minimum number of multiplications is 4500
Matrix Chain Multiplication: Space Optimization
Optimizing Space Complexity:
Space optimization involves reducing the memory usage of the solution by storing only necessary information, often by using a single-dimensional array instead of a two-dimensional table.
Implementation Insight:
In some cases, only a part of the table is needed at any time, allowing us to reduce the space complexity from O(n^2) to O(n).
public class SpaceOptimizedMatrixChain {
static int matrixChainOrder(int p[], int n) {
int dp[] = new int[n];
for (int i = 1; i < n; i++)
dp[i] = 0;
for (int L = 2; L < n; L++) {
for (int i = n - L; i > 0; i--) {
int j = i + L - 1;
if (j == n) continue;
dp[i] = Integer.MAX_VALUE;
for (int k = i; k <= j - 1; k++) {
int q = dp[i] + dp[k + 1] + p[i - 1] * p[k] * p[j];
if (q < dp[i])
dp[i] = q;
}
}
}
return dp[1];
}
public static void main(String args[]) {
int arr[] = new int[] {10, 30, 5, 60};
int size = arr.length;
System.out.println("Minimum number of multiplications is " + matrixChainOrder(arr, size));
}
}
Console Output:
Minimum number of multiplications is 4500
