This problem is the most popular example of DP. In this problem, we determine the optimal sequence of multiplication operations for a series of matrices. This technique is also used for code optimization in compiler design.
Let us consider a chain of n matrices A1 A2 ... An. As matrix multiplication is an associative operation, we can parenthesize them without performing any rearrangement. Moreover, first, we need to check the order of the matrices, to verify whether the operations can be performed on that sequence or not.
Suppose, matrix A has dimension p x q which is being multiplied with another matrix B of dimensions q x r, and the result will be a matrix C with dimensions p x r.
Algorithm to calculate the optimal cost
Algorithm to parenthesize the matrix sequnce
In particular, for 1 ≤ i ≤ p and 1 ≤ j ≤ r, we have
C[i, j] = Σqk=1 A[i, k] B[k, j].
To compute matrix C, we have to calculate p x r number of elements. And to calculate one element of C we have to perform q number of multiplications. Hence, to compute C, p x q x r number of multiplications are required.
Let us consider that the dimensions of the given matrices are p0, p1, p2, ..., pn, where i = 1, 2, ..., n. Hence, matrix Ai has dimension pi - 1 x pi.
To multiply Ai and Ai + 1 total number of required multiplication is pi - 1 x pi x pi + 1.
Example
Implementation in C Language
#include <stdio.h>
#include <limits.h>
void parenthesize(int **s, int i, int j) {
if (i == j)
printf(" A%d ", i);
else {
printf(" ( ");
parenthesize(s, i, s[i][j]);
parenthesize(s, s[i][j] + 1, j);
printf(" ) ");
}
}
void matChainOrder(int n, int *p) {
int i, j, q, k, l;
int **m;
int **s;
m = (int **) malloc((n + 1) * sizeof(int *));
for(i = 0; i <= n; i++)
m[i] = (int *) malloc((n + 1) * sizeof(int));
s = (int **) malloc((n + 1) * sizeof(int *));
for(i = 0; i <= n; i++)
s[i] = (int *) malloc((n + 1) * sizeof(int));
for(i = 0; i <= n; i++)
for(j = 0; j <= n; j++)
m[i][j] = 0;
for(i = 0; i <= n; i++)
for(j = 0; j <= n; j++)
s[i][j] = 0;
for (l = 2; l <= n; l++) {
for (i = 1; i <= n - l + 1; i++) {
j = i + l - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
q = (m[i][k]) + (m[k + 1][j]) + (p[i - 1] * p[k] * p[j]);
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
printf("\nSequence is :\n");
parenthesize(s, i - 1, j);
printf("\n\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
printf(" %5d", m[i][j]);
}
printf("\n");
}
printf("\nTotal requried multiplication is : %d\n", m[1][n]);
}
int main(void) {
int i, n;
int *p;
printf("\nEnter No. of matrix");
scanf("%d", &n);
p = (int *)malloc((n+1) * sizeof(int));
printf("\nEnter matrix %d diamentions\n", n + 1);
for (i = 0; i <= n; i++) {
scanf("%d", &p[i]);
}
matChainOrder(n, p);
return 0;
}
Posts
No comments:
Post a Comment