Les algorithmes gloutons
Cours · NSI (terminale), chapitre 8 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
Face à un problème d'optimisation, on cherche souvent la meilleure solution parmi un très grand nombre de possibilités. Explorer toutes les combinaisons est généralement trop coûteux. Les algorithmes gloutons (en anglais greedy algorithms) proposent une stratégie simple et rapide : à chaque étape, on effectue le choix qui paraît le meilleur sur le moment, sans jamais remettre en cause les décisions déjà prises.
Cette approche est séduisante par sa simplicité, mais elle ne fournit pas toujours la solution optimale. L'enjeu de ce chapitre est double : comprendre comment construire un algorithme glouton, et surtout savoir reconnaître les situations où il est garanti de donner la meilleure réponse, par opposition à celles où il échoue. Nous étudierons le rendu de monnaie, le sac à dos fractionnaire et l'ordonnancement de tâches, avant de comparer cette méthode à la programmation dynamique.
8.1 Principe d'un algorithme glouton
Un algorithme glouton construit une solution étape par étape. À chaque étape, il sélectionne, parmi les choix possibles, celui qui optimise un critère local immédiat (le choix glouton), puis il poursuit avec le sous-problème restant. Une fois un choix effectué, il n'est jamais reconsidéré.
L'idée centrale est donc le choix localement optimal : on espère qu'en empilant des décisions individuellement bonnes, on obtiendra une solution globalement bonne.
Un problème d'optimisation consiste à trouver, parmi un ensemble de solutions dites réalisables (respectant des contraintes), une solution qui maximise ou minimise une grandeur appelée fonction objectif.
Méthode : Concevoir un algorithme glouton
Pour construire un algorithme glouton, on identifie :
- l'ensemble des candidats parmi lesquels choisir ;
- un critère de sélection (le choix glouton) qui désigne le « meilleur » candidat à chaque étape ;
- un test de faisabilité qui vérifie que l'on peut ajouter ce candidat à la solution partielle ;
- un test d'arrêt indiquant que la solution est complète.
Très souvent, le critère de sélection se traduit par un tri préalable des candidats.
Les algorithmes gloutons sont en général simples à programmer et rapides, car ils n'explorent pas l'arbre complet des possibilités. En contrepartie, ils ne garantissent pas toujours l'optimalité : un bon choix local peut conduire à une impasse globale. Il faut donc, au cas par cas, prouver que la stratégie gloutonne est correcte, ou bien accepter qu'elle ne fournisse qu'une solution approchée.
Imaginons que l'on veuille visiter le maximum de musées dans une ville en une journée. Une stratégie gloutonne pourrait être : « aller toujours au musée le plus proche non encore visité ». Ce choix local est raisonnable, mais il peut nous entraîner dans un quartier isolé et nous faire perdre du temps ensuite. C'est l'illustration typique d'un glouton qui ne garantit pas l'optimum.
8.2 Le rendu de monnaie
Le problème du rendu de monnaie est l'exemple historique des algorithmes gloutons. Un commerçant doit rendre une somme donnée en utilisant le moins de pièces possible.
Étant donné un système de pièces (un ensemble de valeurs) et une somme à rendre, on cherche à exprimer comme une somme de pièces du système, en minimisant le nombre total de pièces utilisées.
Méthode : Stratégie gloutonne du rendu de monnaie
À chaque étape, on choisit la plus grande pièce dont la valeur ne dépasse pas la somme restante à rendre. On retire cette valeur de la somme restante et on recommence, jusqu'à atteindre .