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.
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.