This Java program solves the Matrix Chain Multiplication problem using dynamic programming. The objective is to find the most efficient way to multiply a chain of matrices, minimizing the number of scalar multiplications required.
Java Program
public class MatrixChainMultiplication {
// Function to find the optimal order of matrix multiplication
public static int matrixChainOrder(int[] dimensions) {
int n = dimensions.length;
// Create a 2D array to store the minimum multiplication costs
int[][] dp = new int[n][n];
// dp[i][j] represents the minimum cost of multiplying matrices from i to j
// Initialize the diagonal elements to 0, as no multiplications are needed
for (int i = 1; i < n; i++) {
dp[i][i] = 0;
}
// Length of chain (starting from 2, as chain of length 1 is trivial)
for (int chainLength = 2; chainLength < n; chainLength++) {
for (int i = 1; i < n – chainLength + 1; i++) {
int j = i + chainLength – 1;
dp[i][j] = Integer.MAX_VALUE;
// Try all positions to split the chain between i and j
for (int k = i; k < j; k++) {
// Cost of multiplying matrices from i to k and k+1 to j, plus cost of multiplying the result
int cost = dp[i][k] + dp[k + 1][j] + dimensions[i – 1] * dimensions[k] * dimensions[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
// The final answer is stored in dp[1][n-1], which represents the minimum cost of multiplying matrices 1 through n-1
return dp[1][n – 1];
}
public static void main(String[] args) {
// Example dimensions of the matrices: A1(10×30), A2(30×5), A3(5×60), A4(60×10)
// The input is the array of dimensions: [10, 30, 5, 60, 10]
int[] dimensions = {10, 30, 5, 60, 10};
// Calculate the minimum number of multiplications required
int result = matrixChainOrder(dimensions);
System.out.println(“Minimum number of multiplications is: ” + result);
}
}
Explanation of the Program Structure
The Matrix Chain Multiplication problem is solved using a dynamic programming approach. The goal is to minimize the number of scalar multiplications needed to multiply a series of matrices.
- matrixChainOrder function: This function implements the dynamic programming algorithm to find the optimal way to multiply a chain of matrices. It takes an array
dimensions[]as input, where the length of the array isn, and the matrix dimensions areAi = dimensions[i-1] x dimensions[i]. - Dynamic Programming Table (dp): The
dp[i][j]table is used to store the minimum number of scalar multiplications required to multiply matrices fromAitoAj. The idea is to compute the minimum cost for all possible subproblems and store the results in thedptable. - Main logic: The program iterates over all possible lengths of matrix chains (starting from length 2), and for each length, it tries all possible ways to split the chain at different positions
k. For each possible split, it calculates the cost and updates the minimum cost in thedptable. - Base case: The base case is when the chain length is 1 (i.e., only a single matrix), for which no multiplication is required. Therefore, the diagonal elements of the
dptable are set to 0. - main function: This function initializes a sample set of matrix dimensions and calls the
matrixChainOrderfunction to compute the result, which is then printed to the console.
Step-by-Step Process:
- We create a 2D array
dpto store the minimum multiplication costs for each subproblem. - We iterate through all possible chain lengths (from 2 to
n-1) and all possible starting points for these chains. - For each chain, we try every possible position to split the matrices into two smaller chains. The cost of multiplying the two smaller chains, along with the cost of multiplying the results, is calculated and the minimum is stored in the
dptable. - The final result, which is the minimum number of scalar multiplications needed to multiply the entire chain of matrices, is found in
dp[1][n-1].
Example:
Consider the following set of matrices:
A1(10x30), A2(30x5), A3(5x60), A4(60x10)
The corresponding array of dimensions is {10, 30, 5, 60, 10}.
The dynamic programming table will be filled based on the minimum number of scalar multiplications required to multiply each possible subsequence of matrices. The result of this example is that the minimum number of scalar multiplications required to multiply these matrices is:
Minimum number of multiplications is: 4500
Conclusion:
This Java program provides an efficient solution to the Matrix Chain Multiplication problem using dynamic programming. The time complexity of the solution is O(n^3), where n is the number of matrices in the chain. This approach ensures that we minimize the number of scalar multiplications required to multiply a chain of matrices, making it suitable for practical applications where matrix multiplication is computationally expensive.
