Les algorithmes gloutons (ou greedy algorithms en anglais) sont des algorithmes de
résolution de problèmes qui prennent une série de décisions en choisissant à chaque étape
l’option la plus avantageuse sans tenir compte des conséquences futures.
Un algorithme glouton fonctionne selon ces étapes :
1. Choix glouton : À chaque étape, choisir la solution qui semble la meilleure à ce
moment-là.
2. Faisabilité : Vérifier si ce choix est valide (respecte les contraintes du problème).
3. Optimalité locale : Supposer que ce choix mène à une solution optimale globale.
4. Problème réduit : Réduire le problème à une taille plus petite et recommencer.
Exemples d’algorithmes gloutons:
1. Problème du sac à dos fractionnaire :
○ On a un sac d'une capacité limitée et des objets avec des poids et des
valeurs.
○ Objectif : Maximiser la valeur totale du sac.
○ Stratégie gloutonne : Prendre les objets avec le meilleur ratio (valeur/poids)
jusqu’à remplir le sac.
2. Problème de la monnaie :
○ On doit rendre une somme d'argent avec le minimum de pièces possible.
○ Stratégie gloutonne : Toujours choisir la pièce de plus grande valeur possible.
○ Cela fonctionne uniquement si le système de pièces est canonique (comme
l’euro ou le dollar).
3. Problème de l’ordonnancement des tâches :
○ On a des tâches avec des délais et des bénéfices.
○ Stratégie gloutonne : Prioriser les tâches avec les bénéfices les plus élevés.
