Algoritmi i Kërkimit Greedy (Greedy Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi Greedy Search është një qasje për zgjidhjen e problemeve që zgjedh gjithmonë opsionin më të mirë të disponueshëm në çdo hap pa marrë parasysh ndikimin afatgjatë të vendimit. Ndonëse nuk garanton gjetjen e zgjidhjes optimale globale, kjo metodë shpesh funksionon shpejt dhe është e thjeshtë për t'u zbatuar.

Si punon

1. Inicializimi: Filloni me një zgjidhje boshe ose fillestare.
2. Zgjedhja optimale lokale: Në çdo hap, zgjidhni zgjedhjen lokale optimale bazuar në funksionin objektiv ose kriteret e përcaktuara.
3. Zbatoni zgjedhjen: Aplikoni zgjedhjen optimale për zgjidhjen aktuale.
4. Përsëriteni: Përsëriteni përmes hapave 2 deri në 4 derisa të mos mund të bëhet një zgjedhje më e mirë lokale.

Shembull: Knapsack Problem

Konsideroni Knapsack Problem, ku kemi një çantë me peshë maksimale dhe një listë artikujsh me pesha dhe vlera. Qëllimi është të zgjidhni artikuj për të maksimizuar vlerën totale në çanta. Një qasje Greedy Search për këtë problem është zgjedhja e artikujve bazuar në raportin më të lartë vlerë-peshë.

Shembull kodi në 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;  
}  

Në këtë shembull, ne përdorim qasjen Greedy Search për të zgjidhur problemin Knapsack Problem. Ne i renditim artikujt në bazë të raportit zbritës vlerë-peshë dhe zgjedhim artikujt me raportin më të lartë që ende përshtaten brenda kufirit të peshës së çantës.