close

C++ में लालची खोज (Greedy Search) एल्गोरिथम- स्पष्टीकरण, उदाहरण और कोड

लालची खोज एल्गोरिथ्म एक समस्या-समाधान दृष्टिकोण है जो निर्णय के दीर्घकालिक प्रभाव पर विचार किए बिना हमेशा प्रत्येक चरण में सर्वोत्तम उपलब्ध विकल्प चुनता है। हालाँकि यह विश्व स्तर पर इष्टतम समाधान खोजने की गारंटी नहीं देता है, यह विधि अक्सर जल्दी से काम करती है और इसे लागू करना आसान है।

यह काम किस प्रकार करता है

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