ডাইনামিক প্রোগ্রামিং – ১ (ফিবোনাচ্চি)

ডাইনামিক প্রোগ্রামিং শেখার প্রথম পূর্বশর্ত হলো রিকার্শন বোঝা। রিকার্শন নিয়ে ভালো ধারণা না থাকলে আগে সেটা সম্পর্কে জেনে নেওয়া ভালো।

ডাইনামিক প্রোগ্রামিং

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

ফিবোনাচ্চি সিকুয়েন্স

সবথেকে সহজ উদাহরণ দিয়ে আমরা শুরু করবো। সিরিজটি এরকম: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ….

লক্ষ্য করো ১ম দুটি সংখ্যা ছাড়া প্রতিটি সংখ্যা হলো আগের দুটি সংখ্যার যোগফল। আমরা একটি ফাংশন কল্পনা করি $f(n)$ যা $n$ তম ফিবোনাচ্চি সংখ্যা রিটার্ন করে। ফিবোনাচ্চি সংখ‍্যার ফর্মূলা রিকার্সিভ ফাংশনের মাধ‍্যমে প্রকাশ করলে আমরা পাবো:

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n-1) + f(n-2);
}

আমরা $f(n)$ প্রবলেমটাকে ছোট দুটো সাবপ্রবলেমে ভাগ করে ফেলতে পেরেছি। $0$ থেকে $n$ পর্যন্ত সবগুলো মানের জন‍্য দুটো করে ফাংশন কল হচ্ছে (বেস কেস ছাড়া)। টাইম কমপ্লেক্সিটি গিয়ে দাড়াচ্ছে $O(2^n)$ এ। এটা এক্সপোনেশিয়াল কমপ্লেক্সিটি যা খুব ধীরগতিতে কাজ করবে।

আমি শুরুতেই ডাইনামিক প্রোগ্রামিং নিয়ে বলেছি ” একটা সমস‍্যাকে ছোট ছোট ভাগ করে সাব-প্রবলেমগুলো সমাধান করবো তবে একই সাবপ্রবলেম একবারের বেশি সমাধান করবো না”। এখানে আমরা সাবপ্রবলেমে ঠিকই ভাগ করেছি কিন্তু একই সাবপ্রবলেম বারবার সলভ করছি। তো সেটা না করে সাবপ্রবলেমের রেজাল্টগুলো একটা টেবিলে সেভ করে রাখলেই কিন্তু কাজ হয়ে যায়।

Memoization

আমরা memo নামের একটা অ‍্যারে ব‍্যবহার করেছি সাবপ্রবলেমের রেজাল্টগুলো সেভ করে রাখতে। একদম শুরুতে অ‍্যারেতে এমন ভ‍্যালু রাখতে হবে যেটা কখনোই উত্তর হওয়া সম্ভব না, এক্ষেত্রে আমরা $-1$ ব‍্যবহার করছি। প্রতিবার রিকার্সিভ ফাংশন কল করার আগে দেখছি যে সাবপ্রবলেমটার সমাধান অ‍্যারেতে এরই মধ‍্যে রাখা আছে নাকি, থাকলে সেটা রিটার্ন করে দিচ্ছি।

int memo[100]; // initialize with -1
int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n]; // check if solved
    memo[n] = f(n-1) + f(n-2);
    return memo[n];
}

এবার আমাদের কোডের টাইম কমপ্লেক্সিটি হয়ে যাচ্ছে $O(n)$ কারণ আমাদের $n$ টা সাবপ্রবলেম আছে যেগুলো হলে $f(0), f(1) …. f(n)$ এবং প্রতিটা সাবপ্রবলেম আমরা মাত্র ১বার সমাধান করছি।

এভাবে সাবপ্রবলেমের রেজাল্ট সেভ করে রাখার একটা নাম আছে, সেটা হলো Memoization। ল‍্যাটিন ভাষার শব্দ memorandum থেকে এই শব্দটা তৈরি করেন Donald Mitchie নামক একজন এ.আই রিসার্চার।