Situatie
Write a C program for a given dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum.
Solutie
Pasi de urmat
- Create a recursive function that takes i and j as parameters that determines the range of a group.
- Iterate from k = i to j to partition the given range into two groups.
- Call the recursive function for these groups.
- Return the minimum value among all the partitions as the required minimum number of multiplications to multiply all the matrices of this group.
- The minimum value returned for the range 0 to N-1 is the required answer.
// C code to implement the
// matrix chain multiplication using recursion
#include <limits.h>
#include <stdio.h>
// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1 . . . n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// 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 (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i – 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
printf(“Minimum number of multiplications is %d “,
MatrixChainOrder(arr, 1, N – 1));
getchar();
return 0;
}
C Program for Matrix Chain Multiplication using Dynamic Programming (Memoization):
Step-by-step approach:
- Build a matrix dp[][] of size N*N for memoization purposes.
- Use the same recursive call as done in the above approach:
- When we find a range (i, j) for which the value is already calculated, return the minimum value for that range (i.e., dp[i][j]).
- Otherwise, perform the recursive calls as mentioned earlier.
- The value stored at dp[0][N-1] is the required answer.
#include <stdio.h>
#include <limits.h>
int dp[100][100];
// Function for matrix chain multiplication
int matrixChainMemoised(int p[], int i, int j) {
if (i == j) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
dp[i][j] = (dp[i][j] < (matrixChainMemoised(p, i, k)
+ matrixChainMemoised(p, k + 1, j)
+ p[i – 1] * p[k] * p[j])) ? dp[i][j] : (matrixChainMemoised(p, i, k)
+ matrixChainMemoised(p, k + 1, j)
+ p[i – 1] * p[k] * p[j]);
}
return dp[i][j];
}
int MatrixChainOrder(int p[], int n) {
int i = 1, j = n – 1;
return matrixChainMemoised(p, i, j);
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]); // Corrected this line
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
dp[i][j] = -1;
}
}
printf(“Minimum number of multiplications is %d\n”, MatrixChainOrder(arr, n));
return 0;
}
Leave A Comment?