Algorithme glouton

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global.
Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Suivant le système de pièces, l'algorithme glouton est optimal ou pas. Dans le système de pièces européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200), où l'algorithme glouton donne la somme suivante pour 37 : 20+10+5+2, on peut montrer que l'algorithme glouton donne toujours une solution optimale. Par contre, dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.
Le site Labo Algo donne un exemple montrant que l'algorithme glouton n'est pas optimal pour le problème du voyageur de commerce.
Cet algorithme si joliment nommé m'a d'abord fait penser à la gloutonnerie des banquiers qui recherchent le profit à court terme, et finalement à toutes les politiques à courte vue, qui présentent un choix optimum local comme devant évidemment mené à un résultat optimum global.
Dans le domaine de la pédagogie, c'est la mode de l'évaluation continue qui relève de l'application de l'algorithme glouton. On évalue localement pour pouvoir faire un choix optimum local en tenant pour évident que cela finira par donner un résultat optimum global.