Algorithmes heuristiques
Vous avez n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximal d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
Un algorithme glouton (ou greedy algorithm en anglais) adopte une stratégie simple mais puissante : À chaque étape, il choisit le meilleur choix possible selon un critère local, sans jamais remettre en question les choix précédents. Autrement dit, l'algorithme avance pas à pas, en effectuant des choix immédiats qui semblent les plus avantageux sur le moment - d'où le terme "glouton" (celui qui "mange" tout de suite ce qui paraît le meilleur).
L'algorithme a été conçu par Edsger W. Dijkstra en 1956 et publié en 1959. Dans sa lettre originale, il décrit sa découverte comme une solution "en 20 minutes" à un problème posé par un mathématicien non informaticien. La simplicité de sa formulation cache une profondeur conceptuelle qui en fait l'un des joyaux de l'algorithmique des graphes.