এই পোস্টে আমরা লালচী অ্যালগরিদম (greedy algorithm) এবং ডাইনামিক প্রোগ্রামিং (dynamic programming) মেথডের পার্থক্য বুঝব।
লালচী অ্যালগরিদম (Greedy algorithm)
এটি একটি অ্যালগরিদমিক প্যারাডাইম যা একটি সমাধান কয়েকটি পার্টে, ধাপে ধাপে বিল্ড আপ করে। পরবর্তী স্টেপটি এমনভাবে চয়ন করা হয় যাতে তা সবচেয়ে očיבিড এবং তৎক্ষণিক সুবিধা দেয়।
- যেসম সমস্যাগুলো লোকাল অপ্টিমাল ভ্যালু চয়ন করলে গ্লোবাল অপ্টিমাল ভ্যালু/সমাধান চয়ন করতে সাহায্য করে, সেসব সমস্যা লালচী অ্যালগরিদমের সাথে জড়িত।
- এক লালচী অ্যালগরিদম অপ্টিমাল সমাধান দেবে এমন কোনো গ্যারান্টি নেই।
- প্রোবলেমের প্রতিটি স্টেজে একটি অপ্টিমাল চয়ন করা হয়, অর্থাৎ লোকাল অপ্টিমাল সমাধান।
- মেমরি ইউজের দৃষ্টিতে এটি ইফিশিয়েন্ট কারণ পেছনে ফিরে বা পূর্বের সমাধান/ভ্যালু পরিবর্তন করার কোনো প্রশ্নই নেই।
- সাধারণত, ডাইনামিক প্রোগ্রামিং টেকনিকের তুলনায় এগুলো দ্রুত।
- উদাহরণ: ডাইজক্সট্রার শর্টেস্ট পাথ অ্যালগরिदম যা O(ELogV + VLogV) টাইম নেয়।
- লালচী অ্যালগরিদমে সমাধান ফরওয়ার্ড মেথডে কম্পিউট করা হয়, কখনো পূর্বের ভ্যালু/সমাধান ভিজিট বা চেঞ্জ করা হয় না।
ডাইনামিক প্রোগ্রামিং (Dynamic Programming)
এটি একটি অপ্টিমাইজেশন টেকনিক যা সাব-প্রোবলেমের রেজাল্ট স্টোর করে রাখে যাতে ভবিষ্যতে প্রয়োজনে সেগুলো রি-কম্পিউট না করতে হয়। সেগুলো প্রি-কম্পিউটেড সেট থেকে সরাসরি এক্সট্রাক্ট করা যায়। এটি টাইম কমপ্লেক্সিটি এক্সপোনেনশিয়াল থেকে পলিনোমিয়াল কমপ্লেক্সিটিতে নামিয়ে আনে।
- উদাহরণস্বরূপ: একটি রিকার্সিভ সমাধানকে ডাইনামিক প্রোগ্রামিং প্রোবলেমে রূপান্তর করা যায় কম্পিউট করে।
- এখানে, প্রতিটি স্টেপে করা সিদ্ধান্ত বর্তমান সমস্যা এবং পূর্বে সমাধান করা সাব-প্রোবলেমের সমাধান বিবেচনা করে করা হয়। এটি গ্লোবাল অপ্টিমাল ভ্যালু/সমাধান ক্যালকুলেট করতে ব্যবহৃত হয়।
- এক ডাইনামিক প্রোগ্রামিং প্রোবলেমের সমাধান অপ্টিমাল হবে তা গ্যারান্টিদ。
1006083326 লালচী পদ্ধতি (Greedy Method) এবং ডাইনামিক প্রোগ্রামিং (Dynamic Programming) এর পার্থক্য
এই পোস্টে আমরা লালচী অ্যালগরিদম (greedy algorithm) এবং ডাইনামিক প্রোগ্রামিং (dynamic programming) মেথডের পার্থক্য বুঝব।
লালচী অ্যালগরিদম (Greedy algorithm)
এটি একটি অ্যালগরিদমিক প্যারাডাইম যা একটি সমাধান কয়েকটি পার্টে, ধাপে ধাপে বিল্ড আপ করে। পরবর্তী স্টেপটি এমনভাবে চয়ন করা হয় যাতে তা সবচেয়ে očibিড এবং তৎক্ষণিক সুবিধা দেয়।
- যেসম সমস্যাগুলো লোকাল অপ্টিমাল ভ্যালু চয়ন করলে গ্লোবাল অপ্টিমাল ভ্যালু/সমাধান চয়ন করতে সাহায্য করে, সেসব সমস্যা লালচী অ্যালগরিদমের সাথে জড়িত।
- এক লালচী অ্যালগরিদম অপ্টিমাল সমাধান দেবে এমন কোনো গ্যারান্টি নেই।
- প্রোবলেমের প্রতিটি স্টেজে একটি অপ্টিমাল চয়ন করা হয়, অর্থাৎ লোকাল অপ্টিমাল সমাধান।
- মেমরি ইউজের দৃষ্টিতে এটি ইফিশিয়েন্ট কারণ পেছনে ফিরে বা পূর্বের সমাধান/ভ্যালু পরিবর্তন করার কোনো প্রশ্নই নেই।
- সাধারণত, ডাইনামিক প্রোগ্রামিং টেকনিকের তুলনায় এগুলো দ্রুত।
- উদাহরণ: ডাইজক্সট্রার শর্টেস্ট পাথ অ্যালগরিদম যা O(ELogV + VLogV) টাইম নেয়।
- লালচী অ্যালগরিদমে সমাধান ফরওয়ার্ড মেথডে কম্পিউট করা হয়, কখনো পূর্বের ভ্যালু/সমাধান ভিজিট বা চেঞ্জ করা হয় না।
ডাইনামিক প্রোগ্রামিং (Dynamic Programming)
এটি একটি অপ্টিমাইজেশন টেকনিক যা সাব-প্রোবলেমের রেজাল্ট স্টোর করে রাখে যাতে ভবিষ্যতে প্রয়োজনে সেগুলো রি-কম্পিউট না করতে হয়। সেগুলো প্রি-কম্পিউটেড সেট থেকে সরাসরি এক্সট্রাক্ট করা যায়। এটি টাইম কমপ্লেক্সিটি এক্সপোনেনশিয়াল থেকে পলিনোমিয়াল কমপ্লেক্সিটিতে নামিয়ে আনে।
- উদাহরণস্বরূপ: একটি রিকার্সিভ সমাধানকে ডাইনামিক প্রোগ্রামিং প্রোবলেমে রূপান্তর করা যায় কম্পিউট করে।
- এখানে, প্রতিটি স্টেপে করা সিদ্ধান্ত বর্তমান সমস্যা এবং পূর্বে সমাধান করা সাব-প্রোবলেমের সমাধান বিবেচনা করে করা হয়। এটি গ্লোবাল অপ্টিমাল ভ্যালু/সমাধান ক্যালকুলেট করতে ব্যবহৃত হয়।
- এক ডাইনামিক প্রোগ্রামিং প্রোবলেমের সমাধান অপ্টিমাল হবে তা গ্যারান্টিড।
- এখানে চয়ন করা অপ্টিমাল সমাধান একটি গ্লোবালি অপ্টিমাল। এটি কিছু ফর্মুলা ব্যবহার করে যা পূর্বে ক্যালকুলেট করা স্টেট ভ্যালু স্টোর করতে হয়।
- মেমোরাইজেশনের জন্য ডাইনামিক প্রোগ্রামিং টেবিল দরকার। এটা মেমরি কমপ্লেক্সিটি বাড়ায়।
- এটি তুলনামূলকভাবে ধীর।
- উদাহরণ: বেলমান ফোর্ড অ্যালগরিদম যা O(VE) টাইম নেয়।
- ডাইনামিক প্রোগ্রামিং বটম-আপ বা টপ-ডাউন অপ্রোচ দিয়ে সমাধান নির্ধারণ করে, ছোট ছোট অপ্টিমাল সমাধান वाले প্রোবলেম থেকে বিল্ড আপ করে।
