Algorithmes gloutons

Les algorithmes gloutons (ou voraces, en anglais : greedy) construisent une solution de façon incrémentale, en choisissant à chaque étape la direction qui est la plus prometteuse. Ce choix localement optimal n'a aucune raison de conduire à une solution globalement optimale. Cependant, certains problèmes peuvent être résolus ainsi. La construction d'un code de Huffman est un exemple classique d'algorithme glouton. Dans d'autres cas, la méthode gloutonne est seulement une heuristique qui ne conduit qu'à une solution sous-optimale, mais qui peut être utilisée quand on ne connaît pas d'algorithme exact efficace. Notons qu'on ne peut recourir à un algorithme glouton que si une propriété d'optimalité locale est vérifiée. Les deux exemples suivants illustreront cette forme d'algorithme.