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. మేము వస్తువులను అవరోహణ విలువ-నుండి-బరువు నిష్పత్తి ఆధారంగా క్రమబద్ధీకరిస్తాము మరియు నాప్‌సాక్ బరువు పరిమితిలో ఇప్పటికీ సరిపోయే అత్యధిక నిష్పత్తితో అంశాలను ఎంచుకుంటాము.