Greedy Search (Greedy Search) -algoritme in C ++- uitleg, voorbeeld en code

Het Greedy Search-algoritme is een probleemoplossende benadering die bij elke stap altijd de best beschikbare optie kiest zonder rekening te houden met de langetermijneffecten van de beslissing. Hoewel het niet garandeert dat de wereldwijd optimale oplossing wordt gevonden, werkt deze methode vaak snel en is ze eenvoudig te implementeren.

Hoe het werkt

1. Initialisatie: Begin met een lege of initiële oplossing.
2. Lokale optimale keuze: kies bij elke stap de lokaal optimale keuze op basis van de objectieve functie of gedefinieerde criteria.
3. Keuze toepassen: Pas de optimale keuze toe op de huidige oplossing.
4. Herhaal: herhaal stap 2 tot en met 4 totdat er geen betere lokale keuze kan worden gemaakt.

Voorbeeld: Knapsack Problem

Denk aan de Knapsack Problem, waar we een knapzak hebben met een maximaal gewicht en een lijst met items met gewichten en waarden. Het doel is om items te selecteren om de totale waarde in de knapzak te maximaliseren. Een Greedy Search-benadering voor dit probleem is om items te selecteren op basis van de hoogste waarde-gewichtsverhouding.

Codevoorbeeld in 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;  
}  

In dit voorbeeld gebruiken we de Greedy Search-benadering om de Knapsack Problem. We sorteren de items op basis van de dalende waarde-gewichtsverhouding en selecteren items met de hoogste verhouding die nog binnen de gewichtslimiet van de knapzak passen.