C++ मा लोभी खोज (Greedy Search) एल्गोरिदम- व्याख्या, उदाहरण र कोड

लोभी खोज एल्गोरिदम एक समस्या समाधान गर्ने दृष्टिकोण हो जसले निर्णयको दीर्घकालीन प्रभावलाई विचार नगरी सधैं प्रत्येक चरणमा उत्तम उपलब्ध विकल्प रोज्छ। यद्यपि यसले विश्वव्यापी रूपमा इष्टतम समाधान खोज्ने ग्यारेन्टी गर्दैन, यो विधि प्रायः छिटो काम गर्दछ र कार्यान्वयन गर्न सीधा छ।

यो कसरी काम गर्दछ

1. प्रारम्भिकरण: खाली वा प्रारम्भिक समाधानको साथ सुरु गर्नुहोस्।
2. स्थानीय इष्टतम छनोट: प्रत्येक चरणमा, उद्देश्य प्रकार्य वा परिभाषित मापदण्डमा आधारित स्थानीय रूपमा इष्टतम छनोट छनौट गर्नुहोस्।
3. विकल्प लागू गर्नुहोस्: हालको समाधानमा इष्टतम विकल्प लागू गर्नुहोस्।
4. दोहोर्याउनुहोस्: 2 देखि 4 चरणहरू दोहोर्याउनुहोस् जबसम्म कुनै राम्रो स्थानीय छनौट गर्न सकिँदैन।

उदाहरण: Knapsack Problem

विचार गर्नुहोस् Knapsack Problem, जहाँ हामीसँग अधिकतम तौल र तौल र मानहरू भएका वस्तुहरूको सूची छ। लक्ष्य भनेको knapsack मा कुल मूल्य अधिकतम गर्न वस्तुहरू चयन गर्नु हो। यस समस्याको लागि लोभी खोजी दृष्टिकोण भनेको उच्चतम मूल्य-देखि-वजन अनुपातमा आधारित वस्तुहरू चयन गर्नु हो।

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 । हामी घट्दो मान-देखि-तौल अनुपातमा आधारित वस्तुहरू क्रमबद्ध गर्छौं र उच्चतम अनुपातमा वस्तुहरू चयन गर्छौं जुन अझै पनि न्यापस्याकको तौल सीमा भित्र फिट हुन्छ।