L'algorithme glouton est une technique de résolution de problèmes qui consiste à faire des choix localement optimaux à chaque étape, sans se soucier des conséquences globales. Il vise à trouver une solution qui semble être la meilleure à chaque étape.
2. Méthodologie
Initialisation: Définir un critère de sélection et initialiser la solution.
Sélection gloutonne: À chaque étape, choisir la meilleure option selon le critère de sélection établi.
Vérification de la faisabilité: Vérifier si la solution partielle est réalisable.
Mise à jour de la solution: Mettre à jour la solution avec le choix fait à chaque étape.
Arrêt: Répéter les étapes jusqu'à atteindre une solution complète ou une condition d'arrêt.
3. Applications
Problème du rendu de monnaie: Trouver la combinaison minimale de pièces pour rendre une somme donnée.
Problème du sac à dos (variantes): Maximiser la valeur totale des objets dans un sac tout en respectant la capacité du sac.
Ordonnancement des tâches: Ordonner les tâches pour minimiser le temps total.
Codage de Huffman: Minimiser la longueur totale de codage binaire pour un texte donné.
4. Avantages et Limitations
Avantages:Algorithme rapide et simple à implémenter.
Peut donner des solutions acceptables pour certains problèmes.
Limitations:Ne garantit pas toujours la solution optimale.
N'est pas toujours applicable à tous les problèmes.
La solution peut être suboptimale ou incorrecte dans certains cas.
5. Exemple
Problème du rendu de monnaie: Sélectionner la plus grande pièce possible à chaque étape jusqu'à atteindre la somme désirée.
Points Clés
Comprendre le concept de choix local optimal.
Savoir choisir et définir un critère de sélection approprié.
Reconnaître les problèmes pour lesquels l'algorithme glouton est efficace.
