যদি একটি ম্যাট্রিক্স চেইন দেওয়া থাকে, তবে আমাদের সঠিক সিকোয়েন্সে ম্যাট্রিক্স গুলো গুণ করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।
আমরা জানি ম্যাট্রিক্স মাল্টিপ্লিকেশন এসোসিয়েটিভ, তাই চারটি ম্যাট্রিক্স ABCD কে আমরা A(BCD), (AB)(CD), (ABC)D, A(BC)D এই সিকোয়েন্স গুলোতে গুণ করতে পারি। এই সিকোয়েন্স গুলোর মতোই, আমাদের কাজ হল কোন অর্ডারটি গুণ করার জন্য দক্ষ।
দিয়ে गये ইনপুট-এ একটি অ্যারে থাকে, যেমন arr[] = {1, 2, 3, 4}। এর মানে হল ম্যাট্রিক্স গুলোর অর্ডার (1 x 2), (2 x 3), (3 x 4)।
ইনপুট
ইনপুট ম্যাট্রিক্স গুলোর অর্ডার। {1, 2, 3, 4}। এর মানে ম্যাট্রিক্স গুলো হল
{(1 x 2), (2 x 3), (3 x 4)}.
আউটপুট
এই তিনটি ম্যাট্রিক্স গুণ করার জন্য ন্যূনতম অপারেশন সংখ্যা। এখানে ফলাফল ১৮।
অ্যালগরিদম
matOrder(array, n)
ইনপুট: ম্যাট্রিক্স গুলোর তালিকা, তালিকা-এ ম্যাট্রিক্স সংখ্যা।
আউটপুট: ন্যূনতম ম্যাট্রিক্স মাল্টিপ্লিকেশন সংখ্যা।
শুরু
minMul টেবিল ডিফাইন করো সাইজ n x n, প্রাথমিকভাবে সব ০ দিয়ে ফিল করো
length := 2 থেকে n পর্যন্ত, করো
i := 1 থেকে n-length পর্যন্ত, করো
j := i + length - 1
minMul[i, j] := ∞
k := i থেকে j-1 পর্যন্ত, করো
q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
যদি q < minMul[i, j], তবে
minMul[i, j] := q
শেষ যদি
শেষ
শেষ
শেষ
minMul[1, n-1] রিটার্ন করো
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
using namespace std;
int matOrder(int array[], int n) {
int minMul[n][n]; // সক্যালার মাল্টিপ্লিকেশনের জন্য প্রয়োজনীয় সংখ্যা ধারণ করবে
for (int i = 1; i < n; i++)
minMul[i][i] = 0; // ১টি ম্যাট্রিক্স দিয়ে গুণ করার কস্ট ০
for (int length = 2; length < n; length++) { // চেইন দৈর্ঘ্য ২ থেকে শুরু করো
for (int i = 1; i < n - length + 1; i++) {
int j = i + length - 1;
minMul[i][j] = INT_MAX; // ইনফিনিটি সেট করো
for (int k = i; k <= j - 1; k++) {
// প্রতি মাল্টিপ্লিকেশনের কস্ট স্টোর করো
int q = minMul[i][k] + minMul[k+1][j] + array[i-1]*array[k]*array[j];
if (q < minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n-1];
}
int main() {
int arr[] = {1, 2, 3, 4};
int size = 4;
cout << "Minimum number of matrix multiplications: " << matOrder(arr, size);
}
আউটপুট
Minimum number of matrix multiplications: 18
