Un algorithme glouton est un algorithme qui, à chaque étape, choisit la variante optimale (au sein de l'étape en cours) dans l'espoir que la solution finale sera optimale au sens global.
Petit exemple :
Supposons que nous ayons un nombre illimité de pièces de différentes dénominations et que nous devions collecter le montant S. Considérons deux cas spécifiques, que nous essaierons de résoudre chacun avec un algorithme glouton.
À savoir, nous agirons comme suit : à chaque étape, nous prendrons une pièce de la valeur nominale la plus élevée (la meilleure option dans l'étape), qui ne dépasse pas le montant restant.
a) Supposons que les pièces soient 1, 5 et 10, et S = 27.
1) Prenez 10, S : 27 -> ; 17
2) Prenez 10, S : 17 -> ; 7
3) Prenez 5, S : 7 -> ; 2
4) Prenez 1, S : 2 -> ; 1
5) Prenez 1, S : 1 -> ; 0
En conséquence, ils ont marqué le montant de cinq pièces. Vous pouvez indépendamment (par exemple, la force brute) vous assurer que pour 4 pièces ou moins, vous ne pourrez pas marquer 27.
b) Soit les valeurs nominales des pièces de monnaie 1, 5 et 7, et S = 24.
1) Prenez 7, S : 24 -> ; 17
2) Prenez 7, S : 17 -> ; 10
3) Prenez 7, S : 10 -> ; 3
4) Prenez 1, S : 3 -> ; 2
5) Prenez 1, S : 2 -> ; 1
6) Prenez 1, S : 1 -> ; 0.
Nous avons marqué avec six pièces, mais nous avons pu marquer S avec quatre pièces - deux d'une valeur nominale de 7 et deux d'une valeur nominale de 5.
Comme on peut le voir sur l'exemple, il n'est pas toujours possible de résoudre des problèmes avec un algorithme glouton. Mais si cela conduit à une réponse globale optimale, ce sera généralement plus facile que d'utiliser la programmation dynamique ou d'autres méthodes.