এই পোস্টে, আমরা লোভী অ্যালগরিদম এবং গতিশীল প্রোগ্রামিং পদ্ধতির মধ্যে পার্থক্য বুঝতে পারব।
লোভী অ্যালগরিদম
এটি একটি অ্যালগরিদমিক দৃষ্টান্ত যা ধাপে ধাপে অংশে সমাধানের উপর তৈরি হয়। পরবর্তী ধাপটি এমনভাবে বেছে নেওয়া হয়েছে যাতে এটি সবচেয়ে সুস্পষ্ট এবং তাৎক্ষণিক সুবিধা দেয়।
- স্থানীয় সর্বোত্তম মানগুলি বেছে নেওয়ার সাথে জড়িত সমস্যাগুলি সমস্যাটির বৈশ্বিক সর্বোত্তম মান/সমাধান বেছে নিতে সাহায্য করবে। এই ধরনের লোভী অ্যালগরিদমের সাথে সম্পর্কিত সমস্যাগুলি খেয়েছে।
- কোনও নিশ্চয়তা নেই যে একটি লোভী অ্যালগরিদম একটি সর্বোত্তম সমাধানের দিকে নিয়ে যাবে৷
- সমস্যার প্রতিটি পর্যায়ে একটি সর্বোত্তম পছন্দ করা হয়, যেমন স্থানীয় সর্বোত্তম সমাধান।
- এটি মেমরি ব্যবহারের ক্ষেত্রে দক্ষ কারণ ফিরে যাওয়ার বা পূর্ববর্তী সমাধান/মান পরিবর্তন করার কোনো প্রশ্নই আসে না।
- সাধারণত, তারা গতিশীল প্রোগ্রামিং কৌশলগুলির তুলনায় দ্রুত।
- উদাহরণ:ডিজকস্ট্রার সবচেয়ে ছোট পথের অ্যালগরিদম যা O(ELogV + VLogV) সময় নেয়।
- একটি লোভী অ্যালগরিদমের সমাধান একটি ফরোয়ার্ড পদ্ধতিতে গণনা করা হয়, পূর্ববর্তী মান/সমাধানগুলি পরিদর্শন করে না বা পরিবর্তন করে না৷
ডাইনামিক প্রোগ্রামিং
এটি একটি অপ্টিমাইজেশন কৌশল যা সাব-সমস্যাগুলির ফলাফল সংরক্ষণ করতে সাহায্য করে যাতে ভবিষ্যতে প্রয়োজন হলে তাদের পুনরায় গণনা করার প্রয়োজন না হয়। এগুলি কেবল প্রাক-গণনা করা সেট থেকে বের করা যেতে পারে। এটি সূচকীয় থেকে বহুপদী জটিলতায় সময়ের জটিলতা হ্রাস করে।
- উদাহরণস্বরূপ:একটি পুনরাবৃত্ত সমাধানকে কম্পিউটিংয়ের মাধ্যমে একটি গতিশীল প্রোগ্রামিং সমস্যায় পরিণত করা যেতে পারে।
- এতে, প্রতিটি পদক্ষেপে গৃহীত সিদ্ধান্তটি হাতে থাকা বর্তমান সমস্যা, এবং পূর্বে সমাধান করা সমষ্টি-সমস্যার সমাধান বিবেচনা করে করা হয়। এটি সর্বোত্তম মান/সমাধান গণনা করতে ব্যবহার করা হবে।
- এটি নিশ্চিত যে একটি গতিশীল প্রোগ্রামিং সমস্যার সমাধান একটি সর্বোত্তম হবে৷
- এখানে, বেছে নেওয়া সর্বোত্তম সমাধান হল বিশ্বব্যাপী সর্বোত্তম। এটি নির্দিষ্ট সূত্র ব্যবহার করে যা পূর্বে গণনা করা রাষ্ট্রের মান সংরক্ষণ করতে ব্যবহৃত হত।
- মুখস্থ করার জন্য ডায়নামিক প্রোগ্রামিং টেবিল প্রয়োজন। এটি স্মৃতির জটিলতা বাড়ায়।
- এটি তুলনামূলকভাবে ধীর।
- উদাহরণ:বেলম্যান ফোর্ড অ্যালগরিদম যা O(VE) সময় নেয়।
- ডাইনামিক প্রোগ্রামিং একটি বটম আপ বা টপ ডাউন পদ্ধতি ব্যবহার করে সমাধান নির্ধারণ করে, ছোট ছোট সমস্যা থেকে বিকাশ করে যার সর্বোত্তম সমাধান রয়েছে।
