close

(Greedy Search) C++-এ লোভী সার্চ অ্যালগরিদম- ব্যাখ্যা, উদাহরণ এবং কোড

লোভী অনুসন্ধান অ্যালগরিদম হল একটি সমস্যা-সমাধান পদ্ধতি যা সিদ্ধান্তের দীর্ঘমেয়াদী প্রভাব বিবেচনা না করে সর্বদা প্রতিটি ধাপে সেরা উপলব্ধ বিকল্পটি বেছে নেয়। যদিও এটি বিশ্বব্যাপী সর্বোত্তম সমাধান খুঁজে পাওয়ার গ্যারান্টি দেয় না, এই পদ্ধতিটি প্রায়শই দ্রুত কাজ করে এবং প্রয়োগ করা সহজ।

কিভাবে এটা কাজ করে

  1. সূচনা: একটি খালি বা প্রাথমিক সমাধান দিয়ে শুরু করুন।
  2. স্থানীয় সর্বোত্তম পছন্দ: প্রতিটি ধাপে, উদ্দেশ্য ফাংশন বা সংজ্ঞায়িত মানদণ্ডের উপর ভিত্তি করে স্থানীয়ভাবে সর্বোত্তম পছন্দ নির্বাচন করুন।
  3. পছন্দ প্রয়োগ করুন: বর্তমান সমাধানে সর্বোত্তম পছন্দ প্রয়োগ করুন।
  4. পুনরাবৃত্তি করুন: পদক্ষেপ 2 থেকে 4 এর মাধ্যমে পুনরাবৃত্তি করুন যতক্ষণ না কোন ভাল স্থানীয় পছন্দ করা যায়।

উদাহরণ: Knapsack Problem

বিবেচনা করুন Knapsack Problem, যেখানে আমাদের সর্বাধিক ওজন সহ একটি ন্যাপস্যাক এবং ওজন এবং মান সহ আইটেমগুলির একটি তালিকা রয়েছে। লক্ষ্য হল ন্যাপস্যাকের মোট মান সর্বাধিক করার জন্য আইটেম নির্বাচন করা। এই সমস্যার জন্য একটি লোভী অনুসন্ধান পদ্ধতি হল সর্বোচ্চ মান-টু-ওজন অনুপাতের উপর ভিত্তি করে আইটেম নির্বাচন করা।

C++ এ কোডের উদাহরণ 

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Item {  
    int weight;  
    int value;  
};  
  
bool compare(Item a, Item b) {  
    double ratioA =(double)a.value / a.weight;  
    double ratioB =(double)b.value / b.weight;  
    return ratioA > ratioB;  
}  
  
double greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}

এই উদাহরণে, আমরা সমাধান করতে লোভী অনুসন্ধান পদ্ধতি ব্যবহার করি Knapsack Problem । আমরা আইটেমগুলিকে অবরোহমান মান-থেকে-ওজন অনুপাতের উপর ভিত্তি করে বাছাই করি এবং সর্বোচ্চ অনুপাত সহ আইটেমগুলি নির্বাচন করি যা এখনও ন্যাপস্যাকের ওজন সীমার মধ্যে ফিট করে৷