Un algorithme glouton fait à chaque étape le choix qui semble le meilleur, sans jamais revenir en arrière. Il est rapide et simple, mais il n’est correct que si le problème a la bonne structure.
Un classique qui fonctionne : la sélection d’activités
Imaginons une liste de réunions avec heures de début et de fin, et l’objectif d’en planifier le plus possible sans chevauchement. On les trie par heure de fin, on prend la première, puis on prend à chaque fois la réunion suivante qui commence après la fin de la précédente. Choisir la fin la plus précoce laisse le plus de place pour le reste.
Un classique qui échoue : certains systèmes de pièces
Avec des pièces de 1, 3 et 4 et une cible de 6, le glouton prend 4 + 1 + 1, soit trois pièces. La meilleure réponse est 3 + 3, soit deux. Le glouton fonctionne pour beaucoup de monnaies réelles, mais pas pour tous les jeux de pièces.
Comment vérifier que le glouton est sûr
Deux propriétés comptent. La propriété du choix glouton affirme qu’une solution optimale commence par le choix glouton. La sous-structure optimale affirme que ce qui reste après ce choix est un problème plus petit du même type. Une technique de preuve courante est l’argument d’échange : montrer que remplacer le premier choix d’une solution optimale par le choix glouton ne la dégrade pas.
Des algorithmes gloutons que vous connaissez déjà
Les algorithmes de Kruskal et de Prim pour les arbres couvrants minimaux sont gloutons et corrects. L’algorithme de Dijkstra pour les plus courts chemins l’est aussi, à condition que les poids des arêtes soient positifs ou nuls.
Conseil pratique
Testez vos idées gloutonnes sur de petits contre-exemples avant de leur faire confiance. S’il en apparaît un, le problème demande généralement de la programmation dynamique.
Pour aller plus loin
Retrouvez le traitement complet, les exemples et les exercices dans Les algorithmes en clair.
Adapté de Les algorithmes en clair, publié par Choral Software. Texte de l’article et exemples originaux © 2026 Choral Software. Tous droits réservés.