Chamtivý vyhledávací (Greedy Search) algoritmus v C++- vysvětlení, příklad a kód

Algoritmus Greedy Search je přístup k řešení problémů, který vždy v každém kroku vybere nejlepší dostupnou možnost, aniž by zvažoval dlouhodobý dopad rozhodnutí. I když nezaručuje nalezení globálně optimálního řešení, tato metoda často funguje rychle a snadno se implementuje.

Jak to funguje

1. Inicializace: Začněte s prázdným nebo počátečním řešením.
2. Místní optimální volba: V každém kroku vyberte lokálně optimální volbu na základě cílové funkce nebo definovaných kritérií.
3. Použít volbu: Aplikujte optimální volbu na aktuální řešení.
4. Opakujte: Opakujte kroky 2 až 4, dokud nebude možné provést lepší místní volbu.

Příklad: Knapsack Problem

Vezměme si Knapsack Problem, kde máme batoh s maximální hmotností a seznam položek s hmotností a hodnotami. Cílem je vybrat položky tak, abyste maximalizovali celkovou hodnotu v batohu. Přístup Greedy Search pro tento problém spočívá ve výběru položek na základě nejvyššího poměru hodnoty k hmotnosti.

Příklad kódu v 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;  
}  

V tomto příkladu používáme přístup Greedy Search k vyřešení Knapsack Problem. Položky třídíme na základě sestupného poměru hodnoty k hmotnosti a vybíráme položky s nejvyšším poměrem, které se ještě vejdou do váhového limitu batohu.