Les algorithmes greedy

Greedy est un paradigme algorithmique qui construit une solution pièce par pièce, en choisissant toujours la pièce suivante qui offre l'avantage le plus évident et le plus immédiat. Ainsi, les problèmes où le choix de l'optimum local conduit également à une solution globale sont les mieux adaptés à Greedy.

Par exemple, considérez le problème fractionnaire du sac à dos . La stratégie optimale locale consiste à choisir l'élément qui a le rapport valeur/poids maximal. Cette stratégie conduit également à une solution globalement optimale car nous sommes autorisés à prendre des fractions d'un élément.