Une méthode constructive qui construit une solution étape par étape en faisant à chaque étape un choix localement optimal, utilisée en optimisation combinatoire, en algorithmes d'approximation et en preuves d'existence lorsque des décisions locales conduisent à une solution globalement acceptable.

Principe

À chaque itération, choisir l'option semblant la meilleure selon un critère local (gain immédiat maximal ou coût immédiat minimal) et s'appuyer sur une preuve — souvent via des arguments d'échange ou la structure de matroïdes — montrant que ces choix locaux s'agrègent en une solution globale optimale ou correctement bornée.

Démonstration

L'algorithme de Kruskal pour les arbres couvrants minimaux ajoute successivement l'arête de plus faible poids qui ne crée pas de cycle ; ces choix locaux d'arêtes minimales donnent un arbre couvrant globalement minimal grâce à un argument d'échange lié aux propriétés de coupes ou à la structure de matroïde des graphes.

Mauvaise application

Appliquer une règle gloutonne sans preuve de correction sous-jacente peut produire des solutions arbitrairement mauvaises ; par exemple, sélectionner gloutonnement selon le profit immédiat dans le sac à dos sans considérer la capacité future mène à des totaux sous-optimaux, sauf dans le cas fractionnaire ou de structures particulières.

Conséquence

Lorsque justifiés, les algorithmes gloutons sont simples, rapides et fournissent souvent des solutions optimales ou des approximations à facteur constant avec des preuves de correction transparentes ; ils fournissent aussi des preuves constructives d'existence en combinatoire.

Inversion

La vue inverse recherche d'abord l'optimalité globale et déduit une règle de sélection locale qui reproduirait la solution optimale, utilisant cela pour concevoir des stratégies gloutonnes en caractérisant les conditions locales nécessaires des optimums.

Limite

Efficace quand le problème possède une propriété matroïdale, une propriété de choix glouton, ou quand un argument d'échange s'applique ; échoue pour de nombreux problèmes NP-durs sans telle structure, ou lorsque les interactions futures rendent les choix locaux myopes.

Tension sémantique

En tension avec la programmation dynamique et l'optimisation globale : le glouton est local et rapide mais peut rater des optima globaux que la programmation dynamique ou le branch-and-bound trouveraient ; quand les deux s'appliquent, le glouton offre généralement plus de simplicité et moins de coût.

Synthèse

Les algorithmes gloutons effectuent des choix locaux répétés et se justifient quand la structure du problème (matroïde, propriété d'échange ou borne d'approximation prouvable) garantit que ces choix se combinent en une solution globale quasi-optimale ou optimale ; sans cette structure, ils risquent de mal performer.