Algoritmo di ricerca Greedy (Greedy Search) in C++- Spiegazione, esempio e codice

L'algoritmo Greedy Search è un approccio di risoluzione dei problemi che sceglie sempre la migliore opzione disponibile in ogni fase senza considerare l'impatto a lungo termine della decisione. Sebbene non garantisca di trovare la soluzione ottimale a livello globale, questo metodo spesso funziona rapidamente ed è semplice da implementare.

Come funziona

1. Inizializzazione: inizia con una soluzione vuota o iniziale.
2. Scelta ottimale locale: ad ogni passaggio, scegli la scelta ottimale locale in base alla funzione obiettivo o ai criteri definiti.
3. Applica scelta: applica la scelta ottimale alla soluzione corrente.
4. Ripeti: ripeti i passaggi da 2 a 4 fino a quando non è possibile effettuare una scelta locale migliore.

Esempio: Knapsack Problem

Considera la Knapsack Problem, dove abbiamo uno zaino con un peso massimo e un elenco di articoli con pesi e valori. L'obiettivo è selezionare gli elementi per massimizzare il valore totale nello zaino. Un approccio Greedy Search per questo problema consiste nel selezionare gli articoli in base al rapporto valore/peso più elevato.

Esempio di codice 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 questo esempio, utilizziamo l'approccio Greedy Search per risolvere il problema Knapsack Problem. Ordiniamo gli articoli in base al rapporto valore/peso decrescente e selezioniamo gli articoli con il rapporto più alto che rientrano ancora nel limite di peso dello zaino.