ULUMINE · Numérique et sciences informatiques (NSI) · Première
Les algorithmes gloutons
Un algorithme glouton construit sa solution par choix successifs localement optimaux : rapide, mais pas toujours optimal.
Rendu de monnaie
- Pièces triées par valeur décroissante ; tant que somme ≥ p, rendre p.
- Optimal pour l’euro (système canonique) ; pas pour 1, 3, 4 avec la somme 6.
Sac à dos
- Trier par rapport valeur/poids décroissant ; prendre chaque objet s’il rentre.
- Contre-exemple : 10 kg, X (6 kg, 30 €), Y et Z (5 kg, 20 €) → glouton 30 €, optimum 40 €.
- Recherche exhaustive : 2ⁿ sous-ensembles.
Méthode
- Identifier le critère de choix glouton.
- Dérouler étape par étape, sans retour en arrière.
- Pour réfuter l’optimalité : un contre-exemple.
Pièges à éviter
- Croire qu’un glouton est toujours optimal.
- Oublier de trier les données selon le critère glouton.
- Arrêter le sac à dos dès qu’un objet ne rentre pas (un objet suivant, plus léger, peut encore rentrer).