Greedy Algorithm
Un algorithme glouton fait à chaque étape le choix localement optimal sans retour arrière ; il est simple et efficace mais ne garantit pas un optimum global.
Objectif
Résoudre rapidement et de façon approchée des problèmes d'optimisation, en exigeant la preuve de la propriété de choix glouton.
Mécanisme
Chaque étape prend l'optimum local dans l'espoir d'un optimum global. L'applicabilité requiert la propriété de choix glouton (un optimum local s'étend en un optimum global) plus une sous-structure optimale. Classiques : codage de Huffman, Dijkstra, Kruskal, sac à dos fractionnaire.
Cas d’usage
- Conception d'algorithmes
- Optimisation approchée
- Problèmes d'ordonnancement