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. आम्ही घटत्या मूल्य-ते-वजन गुणोत्तराच्या आधारे आयटमची क्रमवारी लावतो आणि नॅपसॅकच्या वजन मर्यादेत बसणारे सर्वोच्च गुणोत्तर असलेले आयटम निवडतो.