C++ প্রোগ্রাম: ডাইনামিক প্রোগ্রামিং দিয়ে অপ্টিমাল প্যারেনথেসাইজেশন

এলগরিদম

ম্যাট্রিক্স চেইন গুণন সমস্যায়, একটি সিকোয়েন্সে থাকা ম্যাট্রিক্সগুলিকে কীভাবে প্যারেনথেসাইজ করলে স্কেলার গুণনের সংখ্যা ন্যূনতম হবে তা খুঁজে বের করা হয়। ডাইনামিক প্রোগ্রামিং ব্যবহার করে O(n3) সময়ে সমাধান করা যায়।

মূল ধাপসমূহ:

1. m[i][j] = ম্যাট্রিক্স Ai থেকে Aj গুণ করার ন্যূনতম খরচ।
2. চেইন লেন্থ L = 2 থেকে n-1 পর্যন্ত বাড়াতে হবে।
3. প্রতিটি লেন্থের জন্য সম্ভাব্য সব পার্টিশন k ট্রাই করে ন্যূনতম খরচ আপডেট করুন।
4. s[i][j] এ অপ্টিমাল k স্টোর করুন যাতে প্যারেনথেসাইজেশন প্রিন্ট করা যায়।

উদাহরণ কোড

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

int matrixChainOrder(vector<int>& p, vector<vector<int>>& s) {
    int n = p.size() - 1;
    vector<vector<int>> m(n + 1, vector<int>(n + 1, 0));

    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) {
                    m[i][j] = cost;
                    s[i][j] = k;
                }
            }
        }
    }
    return m[1][n];
}

void printOptimalParens(vector<vector<int>>& s, int i, int j) {
    if (i == j) cout << "A" << i;
    else {
        cout << "(";
        printOptimalParens(s, i, s[i][j]);
        printOptimalParens(s, s[i][j] + 1, j);
        cout << ")";
    }
}

int main() {
    cout << "ম্যাট্রিক্সের সংখ্যা: ";
    int n; cin >> n;
    vector<int> p(n + 1);
    cout << "ডাইমেনশন অ্যারে (p0 p1 ... pn): ";
    for (int i = 0; i <= n; i++) cin >> p[i];

    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));
    int minCost = matrixChainOrder(p, s);

    cout << "ন্যূনতম গুণন সংখ্যা: " << minCost << "\n";
    cout << "অপ্টিমাল প্যারেনথেসাইজেশন: ";
    printOptimalParens(s, 1, n);
    cout << "\n";
    return 0;
}

আউটপুট উদাহরণ

ইনপুট:
ম্যাট্রিক্সের সংখ্যা: 4
ডাইমেনশন অ্যারে: 2 3 7 6 4

আউটপুট:
ন্যূনতম গুণন সংখ্যা: 174
অপ্টিমাল প্যারেনথেসাইজেশন: ((A1A2)A3)A4

ব্যাখ্যা

এই অ্যালগরিদমটি বটম-আপ ডাইনামিক প্রোগ্রামিং ব্যবহার করে। প্রতিটি সাব-প্রব্লেমের সমাধান স্টোর করা হয়, যা বড় সাব-প্রব্লেম সমাধানে পুনরায় ব্যবহার করা হয়। s টেবিল থেকে অপ্টিমাল প্যারেনথেসাইজেশন রিকভার করা যায়।