Numérique et sciences informatiques (spécialité) · Première · Algorithmique

Algorithmes gloutons

• Un algorithme glouton construit sa solution étape par étape, en prenant à chaque fois le meilleur choix local, sans jamais revenir en arrière.
• Exemple type : le rendu de monnaie. On répète le choix de la plus grande pièce qui ne dépasse pas la somme restante, jusqu'à obtenir un reste nul.
• L'avantage principal est la facilité de mise en œuvre, mais le résultat n'est pas toujours optimal.
• Avec le système (1, 3, 4), le glouton rend 6 par 4+1+1 alors que 3+3 est meilleur : un seul contre-exemple suffit à montrer qu'un glouton n'est pas optimal.