Memoization এবং Tabulation এর মাধ্যমে সমস্যা সমাধান

Memoization এবং Tabulation এর মাধ্যমে সমস্যা সমাধান

Memoization এবং Tabulation দুটি ডাইনামিক প্রোগ্রামিং (Dynamic Programming, DP) কৌশল যা সমস্যার সমাধানে পুনরাবৃত্তি থেকে পরিহার করতে এবং একাধিক সমাধান পুনরায় না করতে সহায়তা করে। এই দুটি পদ্ধতির মধ্যে পার্থক্য আছে, তবে লক্ষ্য একটাই: উপ-সমস্যাগুলির সমাধান সঞ্চয় (store) করা, যাতে একই সমস্যার পুনরাবৃত্তি এড়ানো যায় এবং সময় সাশ্রয়ী হয়।

Memoization

Memoization একটি টপ-ডাউন (Top-Down) পদ্ধতি, যেখানে সমস্যার সমাধান গণনা করার সময় উপ-সমস্যাগুলি একবার সমাধান করা হয় এবং পরে সেগুলিকে একটি কেশে (cache) সংরক্ষণ করা হয়, যাতে পরবর্তী সময়ে যদি আবার সেই উপ-সমস্যাগুলি আসে, তাহলে পুনরায় গণনা না করে কেবল কেশ থেকে ফলাফল নেওয়া যায়।

Memoization এর ধাপ:

1. প্রাথমিকভাবে একটি রিকার্সিভ ফাংশন তৈরি করা হয় যা সমস্যার সমাধান করে।
2. উপ-সমস্যাগুলির ফলাফল কেশে সংরক্ষণ করা হয় (একটি অ্যারে বা হ্যাশ টেবিল ব্যবহার করা হয়)।
3. যদি কোন উপ-সমস্যার ফলাফল কেশে থাকে, তবে তা ফেরত দেওয়া হয়, অন্যথায় নতুনভাবে গণনা করা হয় এবং কেশে সংরক্ষণ করা হয়।

Memoization এর উদাহরণ: Fibonacci সিরিজ:

#include <stdio.h>

#define MAX 100

// Memoization টেবিল
int memo[MAX];

// ফিবোনাচ্চি সিরিজের রিকার্সিভ ফাংশন
int fibonacci(int n) {
    // বেস কেস
    if (n <= 1) return n;

    // যদি কেশে ফলাফল থাকে, তবে তা ফেরত দাও
    if (memo[n] != -1) return memo[n];

    // রিকার্সিভ কল এবং ফলাফল কেশে সংরক্ষণ
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

int main() {
    // Memoization টেবিলের সব মান -1 দিয়ে শুরু
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }

    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));

    return 0;
}

Memoization এর সুবিধা:

• সময় সাশ্রয়ী: উপ-সমস্যার পুনরাবৃত্তি এড়িয়ে কাজ দ্রুত হয়।
• টপ-ডাউন: রিকার্সিভ কোড ব্যবহার করা হয় যা সাধারণত সহজভাবে বোঝা যায়।

Memoization এর অসুবিধা:

• স্ট্যাক ওভারফ্লো: রিকার্সন গভীর হলে স্ট্যাক সমস্যা হতে পারে, যেমন অত্যধিক রিকার্সিভ কল।

Tabulation

Tabulation একটি বটম-আপ (Bottom-Up) পদ্ধতি, যেখানে উপ-সমস্যাগুলির সমাধান টেবিলের মাধ্যমে তৈরি করা হয় এবং শেষ পর্যন্ত মূল সমস্যার সমাধান বের করা হয়। এটি একটি ইটারেটিভ পদ্ধতি, যেখানে আগের উপ-সমস্যাগুলির ফলাফলগুলি টেবিলে রাখা হয় এবং প্রতিটি উপ-সমস্যার সমাধান পূর্ববর্তী সমাধানগুলির ওপর নির্ভর করে গণনা করা হয়।

Tabulation এর ধাপ:

1. একটি টেবিল তৈরি করা হয় (অর্থাৎ একটি অ্যারে বা 2D টেবিল) যা উপ-সমস্যাগুলির সমাধান ধারণ করবে।
2. ছোট উপ-সমস্যাগুলি থেকে শুরু করে বড় সমস্যার সমাধান ইটারেটিভভাবে গণনা করা হয়।
3. ফলাফল টেবিলের সর্বশেষ উপাদানে পাওয়া যায়।

Tabulation এর উদাহরণ: Fibonacci সিরিজ:

#include <stdio.h>

#define MAX 100

// ট্যাবুলেশন ফাংশন
int fibonacci(int n) {
    // টেবিল তৈরি
    int dp[MAX];
    
    // বেস কেস
    dp[0] = 0;
    dp[1] = 1;

    // ট্যাবুলেশন: পূর্ববর্তী ফলাফল ব্যবহার করে পরবর্তী ফলাফল হিসাব করা
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));

    return 0;
}

Tabulation এর সুবিধা:

• কম স্পেস: রিকার্সন ব্যবহার না করার কারণে স্ট্যাক সমস্যা হয় না।
• টপ-ডাউন পদ্ধতির চেয়ে দ্রুত: ইটারেটিভ পদ্ধতি ট্যাবুলেশন ব্যবহার করলে অনেক সময় দ্রুত সমাধান পাওয়া যায়।

Tabulation এর অসুবিধা:

• জটিলতা: কখনও কখনও কোড বুঝতে বা লেখা কঠিন হতে পারে।
• স্মৃতি প্রয়োজন: পুরো টেবিল সংরক্ষণ করতে অনেক মেমরি লাগতে পারে।

Memoization বনাম Tabulation

সারসংক্ষেপ

• Memoization এবং Tabulation উভয়ই ডাইনামিক প্রোগ্রামিং কৌশল, তবে তারা আলাদা পদ্ধতিতে কাজ করে। Memoization টপ-ডাউন পদ্ধতি, যেখানে সমস্যার সমাধান রিকার্সিভভাবে করা হয় এবং উপ-সমস্যাগুলির ফলাফল সংরক্ষণ করা হয়। Tabulation একটি বটম-আপ পদ্ধতি, যেখানে উপ-সমস্যাগুলি ইটারেটিভভাবে সমাধান করা হয়।
• Memoization যেখানে সহজ ও দ্রুত প্রোগ্রামিং প্রদান করে, Tabulation সেখানে অনেক বেশি কার্যকরী হতে পারে যখন বড় পরিমাণ ডেটা বা উপ-সমস্যা থাকলে।
• উভয় পদ্ধতিরই নিজস্ব সুবিধা এবং সীমাবদ্ধতা আছে, এবং সমস্যা অনুযায়ী উপযুক্ত পদ্ধতি নির্বাচন করা উচিত।