Qu’est-ce qu’un algorithme glouton ?
Réponse courte
Un algorithme glouton construit une solution par étapes, en choisissant à chaque fois l’option qui paraît la plus avantageuse selon une règle locale. Il ne revient pas sur ses choix. Cette méthode peut produire une solution réalisable, sans garantir qu’elle soit optimale.
Comprendre
Un choix à chaque étape
Un algorithme glouton suit une règle locale : à chaque étape, il sélectionne l’option qui semble la plus intéressante parmi celles disponibles, puis poursuit avec ce choix. Il ne revient pas en arrière pour le remplacer. La règle doit être formulée précisément, ainsi que les contraintes et l’objectif du problème.
Exemple de rendu de monnaie
Avec les pièces 10, 5, 2 et 1, rendre 18 en prenant à chaque fois la plus grande pièce possible donne 10, puis 5, puis 2 et 1. Le reste diminue de 18 à 8, puis 3, 1 et 0. La somme rendue est correcte et la procédure termine. Cet exemple ne prouve toutefois pas que la même stratégie minimise toujours le nombre de pièces pour tout système de valeurs.
Distinguer réussite et optimum
Une solution est réalisable si elle respecte les contraintes et atteint l’objectif demandé. Elle est optimale si aucune autre solution admissible n’est meilleure selon cet objectif. Par exemple, avec les pièces 4, 3 et 1, pour rendre 6, le glouton prend 4, 1 et 1, soit trois pièces. La solution 3 + 3 en utilise deux. Le choix local a bien rendu 6, mais n’a pas trouvé le minimum. Il faut une preuve générale pour annoncer une garantie d’optimalité.
Exemples
- Avec les pièces 10, 5, 2 et 1, le choix glouton rend 18 avec 10 + 5 + 2 + 1.
- Avec les pièces 4, 3 et 1, le glouton rend 6 par 4 + 1 + 1, alors que 3 + 3 demande seulement deux pièces.
- Dans le sac à dos de capacité 10, choisir un objet de masse 6 et valeur 12 peut laisser de côté deux objets de masse 5 et valeur 9 chacun, dont la valeur totale est 18.
Pièges fréquents
- Dire qu’un glouton donne toujours l’optimum parce que chaque étape paraît avantageuse : un choix local n’est pas une preuve globale.
- Confondre somme correcte et meilleur nombre de pièces : le glouton peut rendre le bon montant en utilisant davantage de pièces qu’une autre solution.
