Pourquoi un algorithme glouton ne donne-t-il pas toujours la meilleure solution ?
Réponse courte
Un algorithme glouton choisit l’option qui paraît la meilleure à l’étape courante sans revenir en arrière. Or ce choix peut empêcher une combinaison ultérieure plus avantageuse. Il peut donc produire une solution correcte, mais moins bonne que l’optimum global.
Comprendre
Le choix local ne voit pas toute la suite
La règle gloutonne évalue les options immédiates puis en choisit une définitivement. Ce qui paraît avantageux maintenant peut réduire les possibilités restantes. Comme l’algorithme ne revient pas sur son choix, il peut manquer une combinaison globale plus efficace. Pour conclure à l’optimalité, il faut démontrer que cette règle fonctionne pour le problème étudié.
Contre-exemple avec des pièces
Supposons que les pièces disponibles, en quantité illimitée, valent 4, 3 et 1. Pour rendre 6 en prenant toujours la plus grande pièce possible, on choisit 4, puis il reste 2 : on prend deux pièces de 1. Le glouton utilise trois pièces. Pourtant, 3 + 3 rend aussi 6 avec seulement deux pièces. Une seule pièce ne vaut pas 6, donc deux pièces forment ici une solution optimale.
Un contre-exemple borne la conclusion
Ce cas prouve que la règle « prendre la plus grande pièce » n’est pas toujours optimale pour ce système. Il ne prouve pas que toutes les stratégies gloutonnes échouent sur tous les problèmes. Pour vérifier un algorithme, distingue trois questions : termine-t-il, produit-il une solution qui respecte les contraintes, et cette solution est-elle la meilleure selon l’objectif ? Ces propriétés demandent des justifications séparées.
Exemples
- Pour rendre 6 avec les pièces 4, 3 et 1, le glouton choisit 4 + 1 + 1 : trois pièces, contre 3 + 3 : deux pièces.
- Dans un sac de capacité 10, un choix local peut prendre un objet de masse 6 et valeur 12 ; deux objets de masse 5 et valeur 9 donnent ensemble 18.
- Pour les pièces 10, 5, 2 et 1, rendre 18 par 10 + 5 + 2 + 1 réussit, mais cet exemple seul ne démontre aucune garantie générale.
Pièges fréquents
- Déduire d’un seul exemple réussi que le glouton est toujours optimal : une garantie universelle demande un raisonnement général.
- Conclure d’un contre-exemple que toutes les méthodes gloutonnes sont mauvaises : le cas réfute seulement la règle et le problème concernés.
