Sur cette page
Un exemple concret
Pour rendre 8 € avec des pièces de 5, 2 et 1 €, l'algorithme prend d'abord la plus grosse pièce possible : 5, puis 2, puis 1, soit 3 pièces, ce qui est optimal. Avec un système de pièces 4, 3 et 1, rendre 6 donne 4 + 1 + 1, soit 3 pièces, alors que 3 + 3 n'en utilise que 2.
Le piège à éviter
Ne dis pas qu'un algorithme glouton donne toujours la meilleure solution. Il fournit une solution rapide, parfois seulement approchée : il faut justifier ou tester son optimalité pour chaque problème.
Pour aller plus loin
Un problème d'optimisation cherche, parmi de nombreuses solutions possibles, celle qui minimise ou maximise une quantité : le nombre de pièces, la valeur d'un sac, la durée d'un trajet. La recherche exhaustive teste toutes les possibilités, mais leur nombre explose vite. L'approche gloutonne construit la solution pas à pas en prenant chaque fois l'élément le plus avantageux selon un critère fixé, ce qui la rend très rapide.
Deux exemples sont au programme de Première. Le rendu de monnaie : avec les pièces et billets en euros, le glouton donne toujours le nombre minimal de pièces, mais ce n'est pas vrai pour n'importe quel système, comme le montre le contre-exemple 4, 3, 1. Le problème du sac à dos : on veut emporter des objets de valeur maximale sans dépasser une masse donnée. Un glouton trie les objets selon un critère, par exemple le rapport valeur sur masse, et les ajoute tant que ça rentre ; le résultat est bon mais pas forcément optimal.
Pour démontrer qu'un glouton échoue, il suffit d'un contre-exemple. Pour démontrer qu'il réussit, il faut une preuve, ce qui dépasse en général le niveau attendu. Au bac et en contrôle, on te demande surtout de dérouler l'algorithme à la main, d'écrire la fonction en Python avec une boucle sur une liste triée, puis de comparer le résultat avec la solution optimale trouvée par une autre méthode.
Ne pas confondre
- Recherche exhaustive : Elle teste toutes les solutions et garantit l'optimum, mais son coût peut devenir énorme ; le glouton ne teste qu'un seul chemin.
- Programmation dynamique : Elle explore tous les sous-problèmes utiles et mémorise leurs résultats, ce qui garantit l'optimum là où le glouton peut échouer.
Dans ta copie
Un algorithme glouton construit une solution étape par étape en faisant à chaque fois le choix localement optimal, sans revenir en arrière. Par exemple, pour le rendu de monnaie, il choisit à chaque étape la plus grande pièce inférieure ou égale à la somme restante. Cette méthode est rapide, mais elle ne garantit pas toujours la solution optimale : avec des pièces de 4, 3 et 1, rendre 6 donne trois pièces alors que deux pièces de 3 suffisent. Son optimalité dépend donc du problème.
À retenir
- Un glouton fait le meilleur choix local à chaque étape.
- Il ne revient jamais sur une décision déjà prise.
- Il est rapide mais pas toujours optimal.
- Un seul contre-exemple suffit à prouver qu'il n'est pas optimal.
Teste-toi
NSI · question corrigée
Quel est le principe d'un algorithme glouton ?
Voir la réponse
Réponse D. Le glouton choisit l'option localement la meilleure à chaque étape, sans retour en arrière.
NSI · question corrigée
Avec des pièces de 6, 4 et 1, combien de pièces le glouton utilise-t-il pour rendre 8 ?
Voir la réponse
Réponse D. Il prend 6, puis 1 et 1, soit 3 pièces, alors que 4 + 4 n'en demande que 2.
Questions fréquentes
Pourquoi utiliser un glouton s'il n'est pas toujours optimal ?
Parce qu'il est très rapide et souvent suffisant. Quand une recherche exhaustive prendrait des années, une bonne solution obtenue en une fraction de seconde vaut mieux que rien.
Faut-il trier les données avant ?
Très souvent, oui. Pour le rendu de monnaie, on parcourt les pièces de la plus grande à la plus petite ; pour le sac à dos, on trie selon le critère choisi.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.