যদি ম্যাট্রিক্সের একটি চেইন দেওয়া থাকে, তবে আমাদের সঠিক ক্রমে ম্যাট্রিক্সগুলো গুণ করার জন্য ন্যূনতম সংখ্যক অপারেশন বের করতে হবে।
আমরা জানি ম্যাট্রিক্স গুণন অ্যাসোসিয়েটিভ, তাই চারটি ম্যাট্রিক্স ABCD-এর জন্য A(BCD), (AB)(CD), (ABC)D, A(BC)D gibi ক্রমে গুণ করা যায়। এই ক্রমগুলোর মধ্যে কোনটি দক্ষতাপূর্ণ সেটা খুঁজে বের করা আমাদের কাজ।
ইনপুটে একটি অ্যারে থাকে যেমন arr[] = {1, 2, 3, 4}। এর অর্থ হল ম্যাট্রিক্সগুলোর ক্রম (1×2), (2×3), (3×4)।
ইনপুট এবং আউটপুট
ইনপুট: ইনপুট ম্যাট্রিক্সগুলোর ক্রম।
{1, 2, 3, 4} অর্থাৎ ম্যাট্রিক্সগুলো: {(1×2), (2×3), (3×4)}।
আউটপুট: এই তিনটি ম্যাট্রিক্স গুণ করার জন্য ন্যূনতম অপারেশন সংখ্যা। এখানে ফলাফল ১৮।
অ্যালগরিদম
matOrder(array, n)
ইনপুট: ম্যাট্রিক্সের তালিকা, তালিকায় ম্যাট্রিক্স সংখ্যা।
আউটপুট: ন্যূনতম ম্যাট্রিক্স গুণনের সংখ্যা।
শুরু
n x n আকারের minMul টেবিল সংজ্ঞায়িত করুন, প্রাথমিকভাবে সব ০ দিয়ে পূরণ
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
আউটপুট
Minimum number of matrix multiplications: 18
