Greedy-Suchalgorithmus (Greedy Search) in C++ – Erklärung, Beispiel und Code

Der Greedy-Search-Algorithmus ist ein Problemlösungsansatz, der bei jedem Schritt immer die beste verfügbare Option auswählt, ohne die langfristigen Auswirkungen der Entscheidung zu berücksichtigen. Obwohl es nicht garantiert, dass die global optimale Lösung gefunden wird, funktioniert diese Methode oft schnell und ist einfach umzusetzen.

Wie es funktioniert

1. Initialisierung: Beginnen Sie mit einer leeren oder anfänglichen Lösung.
2. Lokale optimale Wahl: Wählen Sie bei jedem Schritt die lokal optimale Wahl basierend auf der Zielfunktion oder definierten Kriterien.
3. Auswahl anwenden: Wenden Sie die optimale Auswahl auf die aktuelle Lösung an.
4. Wiederholen: Wiederholen Sie die Schritte 2 bis 4, bis keine bessere lokale Wahl getroffen werden kann.

Beispiel: Knapsack Problem

Betrachten Sie das Knapsack Problem, wo wir einen Rucksack mit einem Maximalgewicht und eine Liste von Gegenständen mit Gewichten und Werten haben. Ziel ist es, Gegenstände so auszuwählen, dass der Gesamtwert im Rucksack maximiert wird. Ein Greedy-Search-Ansatz für dieses Problem besteht darin, Artikel anhand des höchsten Wert-Gewichts-Verhältnisses auszuwählen.

Codebeispiel 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 diesem Beispiel verwenden wir den Greedy-Search-Ansatz, um das Problem zu lösen Knapsack Problem. Wir sortieren die Artikel nach absteigendem Wert-Gewichts-Verhältnis und wählen Artikel mit dem höchsten Verhältnis aus, die noch in die Gewichtsbeschränkung des Rucksacks passen.