Optimiser un problème, c’est déterminer les conditions dans lesquelles ce problème

présente une caractéristique spécifique. Par exemple, déterminer le minimum ou le maximum

d’une fonction est un problème d’optimisation. On peut également citer la répartition

optimale des emplois du temps, le problème du rendu de monnaie, le problème du sac à dos,

la recherche d’un plus court chemin dans un graphe.

De nombreuses techniques informatiques sont susceptibles d’apporter une solution

exacte ou approchée à ces problèmes.

Certaines de ces techniques, comme l’énumération exhaustive de toutes les solutions,

ont un coût machine qui les rend souvent peu pertinentes au regard de contraintes extérieures

imposées (temps de réponse imposé, moyens machines limités).

Les techniques de programmation dynamique ou d’optimisation linéaire peuvent

apporter une solution. Mais les algorithmes gloutons constituent une alternative dont le

résultat n’est pas toujours optimal. Plus précisément, ces algorithmes déterminent une

solution optimale en effectuant successivement des choix locaux, jamais remis en cause.

Au cours de la construction de la solution, l’algorithme glouton résout une partie du

problème puis se focalise ensuite sur le sous-problème restant à résoudre. Une différence

essentielle avec la programmation dynamique est que celle-ci peut remettre en cause des

solutions déjà établies.

Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre. En

outre, dans certaines situations dites canoniques, il arrive qu’ils renvoient non pas une "bonne

solution" mais la "meilleure solution" d’un problème, la solution optimale.