Algorithme de recherche gourmande (Greedy Search) en C++- Explication, exemple et code

L'algorithme Greedy Search est une approche de résolution de problèmes qui choisit toujours la meilleure option disponible à chaque étape sans tenir compte de l'impact à long terme de la décision. Bien qu'elle ne garantisse pas de trouver la solution globalement optimale, cette méthode fonctionne souvent rapidement et est simple à mettre en œuvre.

Comment ça fonctionne

1. Initialisation: Commencez avec une solution vide ou initiale.
2. Choix optimal local : à chaque étape, choisissez le choix optimal local en fonction de la fonction objectif ou des critères définis.
3. Appliquer le choix : appliquez le choix optimal à la solution actuelle.
4. Répétez : Répétez les étapes 2 à 4 jusqu'à ce qu'aucun meilleur choix local ne puisse être fait.

Exemple: Knapsack Problem

Considérez le Knapsack Problem, où nous avons un sac à dos avec un poids maximum et une liste d'articles avec des poids et des valeurs. L'objectif est de sélectionner des éléments pour maximiser la valeur totale dans le sac à dos. Une approche de recherche gourmande pour ce problème consiste à sélectionner les éléments en fonction du rapport valeur/poids le plus élevé.

Exemple de code en 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;  
}  

Dans cet exemple, nous utilisons l'approche Greedy Search pour résoudre le problème Knapsack Problem. Nous trions les articles en fonction du rapport valeur/poids décroissant et sélectionnons les articles avec le rapport le plus élevé qui correspondent toujours à la limite de poids du sac à dos.