ম্যাট্রিক্সের একটি সিকোয়েন্স (অ্যারে) দেওয়া আছে। এগুলোর গুণ করার কার্যকর প্যারেন্থেসাইজেশন বের করতে হবে যাতে স্ক্যালার মাল্টিপ্লিকেশন সংখ্যা ন্যূনতম হয়। অ্যারে arr[]-এর i-তম ম্যাট্রিক্সের ডাইমেনশন arr[i-1] × arr[i]।
উদাহরণ
ইনপুট: array[] = {3, 4, 5, 6}
ম্যাট্রিক্স: Mat1=3×4, Mat2=4×5, Mat3=5×6
দুটি প্যারেন্থেসাইজেশন:
- Mat1×(Mat2×Mat3) → (3×4×6)+(4×5×6)=72+120=192
- (Mat1×Mat2)×Mat3 → (3×4×5)+(3×5×6)=60+90=150
ন্যূনতম মাল্টিপ্লিকেশন: 150
পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
- minMul[i][j] = i থেকে j ম্যাট্রিক্স গুণ করার ন্যূনতম কস্ট।
- ডায়াগোনাল ০ (একটি ম্যাট্রিক্সের কস্ট ০)।
- চেইন লেন্থ L=2 থেকে n-1: সব i,j কে চেক করে minMul[i][j] আপডেট।
- ফাইনাল উত্তর minMul[1][n-1]।
C প্রোগ্রাম উদাহরণ
#include <stdio.h>
int MatrixChainMultiplication(int arr[], int n) {
int minMul[n][n];
for (int i = 1; i < n; i++) minMul[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
minMul[i][j] = 99999999;
for (int k = i; k <= j-1; k++) {
int q = minMul[i][k] + minMul[k+1][j] + arr[i-1]*arr[k]*arr[j];
if (q < minMul[i][j]) minMul[i][j] = q;
}
}
}
return minMul[1][n-1];
}
int main() {
int arr[] = {3,4,5,6,7,8};
int size = sizeof(arr)/sizeof(arr[0]);
printf("ন্যূনতম মাল্টিপ্লিকেশন: %d", MatrixChainMultiplication(arr, size));
return 0;
}
আউটপুট
ন্যূনতম মাল্টিপ্লিকেশন: 444
