La méthode gloutonne est une technique bien connue pour résoudre divers problèmes afin d'optimiser (minimiser ou maximiser) les fonctions d'objectif spécifiques.
la méthode gloutonne est une stratégie de recherche contrôlée qui sélectionne l'état suivant pour obtenir la plus grande amélioration possible de la valeur d'une mesure qui peut ou non être la fonction objective.

«On choisit celui qui profite au maximum des choix multiples» est l’idée de base de la méthode gloutonne. Une méthode gloutonne parvient à une solution en faisant une séquence de choix, dont chacun semble tout simplement le meilleur du moment.

cette stratégie suit l'algorithme ci-dessous

Procedure AGloutonne(solution partielle S, sous-problème P):
    générer tous les choix possibles en tant que liste L pour le sous-problème actuel P;
    Tant que (L n'est pas vide OU une autre condition n'est pas remplie)
        calculer le bénéfice de chaque choix en L;
        modifier S et P en prenant le choix avec la valeur de bénéfice la plus élevée;
        mettre à jour L selon S et P;
    FinTanque
    retourner la solution complète;

Pour un problème d'optimisation, ce qui reste est appelé un sous-problème après avoir fait une ou plusieurs étapes d'un choix gloutons. Pour le problème ou le sous-problème P, prenons S la solution partielle, et L la liste des choix du candidat au moment actuel.

Pour ordonner ou hiérarchiser les choix, certains critères d'évaluation sont utilisés pour exprimer la valeur de bénéfice. Selon l'algorithme AGloutonne, le choix du candidat avec la valeur de bénéfice la plus élevée est sélectionné et la solution partielle est mise à jour en conséquence. Cette procédure est répétée étape par étape jusqu'à l'obtention d'une solution complète.

La représentation de l'algorithme AGloutonne peut être illustrée par un arbre de recherche, comme illustré à la Figure ci-dessous Chaque noeud de l’arbre de recherche correspond à une solution partielle et une ligne entre deux noeuds représente la décision d’ajouter un choix de candidat à la solution partielle existante. Par conséquent, les nœuds d'extrémité à la fin de l'arbre correspondent à des solutions complètes.

Sur la Figure, le cercle bleu au niveau 1 désigne une solution partielle initiale. Au niveau 2, il existe quatre choix candidats pour la solution partielle actuelle, ce qui correspond à quatre nœuds. Afin de sélectionner le meilleur nœud, la promesse de chaque nœud doit être déterminée. Après avoir utilisé une fonction d'évaluation, le deuxième nœud présentant le plus grand avantage (le cercle en vert au niveau 2) est sélectionné. Ensuite, la solution partielle et le sous-problème sont mis à jour en conséquence.

Deux caractéristiques importantes de la méthode gloutonne la rendent si populaire: sa mise en œuvre simple et son efficacité. Aussi simple qu’il soit, l’algorithme AGloutonne est très efficace et il peut parfois produire une solution optimale à certains problèmes d’optimisation. Par exemple, pour des problèmes tels que le problème de sélection d'activité, le problème de sac à dos fractionnel et le problème de recouvrement minimum, l'algorithme AGloutonne peut obtenir une solution optimale en faisant une série de choix gloutons. Pour que l'algorithme AGloutonne puisse obtenir la solution optimale, il existe un point commun: la solution optimale au problème contient des solutions optimales aux sous-problèmes.

Cependant, pour d'autres problèmes d'optimisation qui ne présentent pas cette propriété, l'algorithme AGloutonne ne conduira pas à une solution optimale. Surtout pour les problèmes d'optimisation combinatoire ou NP-hard, la solution par l'algorithme AGloutonne est loin d'être satisfaisante.

Dans l'algorithme AGloutonne, nous faisons le choix qui nous semble le mieux pour le moment, puis nous résolvons le sous-problème survenant après le choix. C'est-à-dire que le bénéfice n'est évalué que localement. Par conséquent, même si nous sélectionnons les meilleurs à chaque étape, nous n’avons toujours pas trouvé la solution optimale. Tout en aimant jouer aux échecs, un joueur qui est entièrement concentré sur un avantage immédiat est facile à vaincre, le joueur qui peut penser à plusieurs pas en avant gagnera avec plus de chances.

• Problème de sélection d'activité
• Problème de séquencement des tâches
• Codage de Huffman
• Arbre de couvrement minimum de Kruskal
• Arbre de couvrement minimum de Prim
• Algorithme du chemin le plus court de Dijkstra
• algorithme First Fit dans la gestion de la mémoire
• algorithme Best Fit dans la gestion de la mémoire
• algorithme First Job First dans l'ordonnancement
• Problème de voyageur de commerce
• Coloration de graphe
• Problème de sac à dos
• Nombre Minimum de pièces requis