Choisir à chaque étape ce qui paraît le meilleur semble souvent raisonnable. En algorithmique, cette intuition porte un nom : la méthode gloutonne. Rapide, élégante et parfois redoutablement efficace, elle cache pourtant une limite majeure : une bonne décision locale ne garantit pas toujours la meilleure solution globale.
La méthode gloutonne, ou algorithme glouton, consiste à construire une solution pas à pas en choisissant, à chaque étape, l’option qui semble immédiatement la plus avantageuse. L’idée est simple : ne jamais revenir en arrière, ne pas tester toutes les combinaisons possibles, mais avancer selon un critère local.
Cette approche est très utilisée en optimisation algorithmique, car elle est souvent rapide et peu coûteuse en mémoire. Elle peut servir à sélectionner des tâches, construire un chemin, répartir des ressources ou compresser des données. Mais son principal défaut tient dans son principe même : elle privilégie le court terme. Or, dans de nombreux problèmes, le meilleur choix immédiat peut bloquer une meilleure solution plus loin.
La différence essentielle se situe entre optimum local et optimum global. Un optimum local est une solution qui paraît meilleure que les alternatives voisines à un moment donné. L’optimum global, lui, est la meilleure solution possible sur l’ensemble du problème. Un algorithme glouton peut très bien atteindre un excellent résultat partiel, tout en ratant la solution optimale.
On peut comparer cela à un randonneur qui veut atteindre le point le plus haut d’une région brumeuse. S’il monte toujours vers la pente la plus forte autour de lui, il peut arriver au sommet d’une colline. Mais rien ne garantit que cette colline soit la montagne la plus élevée du massif. L’algorithme glouton fonctionne de manière similaire : il suit la meilleure pente visible, sans vision complète du paysage.
Le rendu de monnaie est l’un des exemples classiques pour comprendre la méthode gloutonne. Supposons que l’on dispose de pièces de 1, 2, 5, 10 et 20 centimes. Pour rendre 37 centimes, une stratégie gloutonne consiste à prendre d’abord 20, puis 10, puis 5, puis 2. Le résultat est optimal : quatre pièces. Dans les systèmes monétaires courants, cette méthode fonctionne souvent très bien.
Mais changeons les pièces disponibles. Imaginons un système avec des pièces de 1, 3 et 4 unités. Pour rendre 6 unités, l’algorithme glouton choisit d’abord 4, puis 1, puis 1. Il utilise donc trois pièces. Pourtant, la solution optimale est 3 + 3, soit seulement deux pièces. Ce petit exemple montre clairement pourquoi une décision localement logique peut conduire à un résultat globalement moins bon.
La méthode gloutonne n’est pas une mauvaise méthode. Elle est même optimale pour certains problèmes bien structurés. C’est le cas lorsque le problème possède ce que les informaticiens appellent une propriété de choix glouton : un choix local optimal peut faire partie d’une solution globale optimale. Dans ce cas, avancer sans revenir en arrière ne compromet pas la qualité du résultat.
Un exemple célèbre est le problème de sélection d’activités. Si l’on veut organiser le plus grand nombre possible de réunions dans une salle, avec des horaires fixes, une stratégie efficace consiste à choisir d’abord l’activité qui se termine le plus tôt. Ensuite, on répète l’opération avec les activités compatibles restantes. Cette règle simple permet d’obtenir une solution optimale, car elle libère au plus vite la ressource commune : la salle.
La fiabilité d’un algorithme glouton dépend donc moins de son apparente logique que de la structure mathématique du problème. Certains problèmes possèdent une forme d’indépendance entre les décisions successives. D’autres, au contraire, imposent des interactions fortes : un choix précoce peut modifier profondément les possibilités futures.
C’est ce qui rend les problèmes d’optimisation difficiles à généraliser. Deux problèmes qui se ressemblent en surface peuvent nécessiter des méthodes très différentes. Le rendu de monnaie fonctionne dans certains systèmes de pièces, mais échoue dans d’autres. La planification de tâches peut être résolue simplement dans un cadre précis, mais devenir complexe si l’on ajoute des priorités, des dépendances ou des coûts variables.
Lorsque la méthode gloutonne échoue, une autre approche peut être plus adaptée : la programmation dynamique. Elle consiste à découper un problème en sous-problèmes, à mémoriser leurs solutions, puis à les combiner pour obtenir un résultat optimal. Contrairement à l’approche gloutonne, elle accepte de comparer plusieurs possibilités avant de trancher.
Cette méthode est souvent utilisée pour des problèmes comme le sac à dos, l’alignement de séquences, le calcul de distances ou certaines formes de rendu de monnaie. Elle demande généralement plus de mémoire et de temps qu’un algorithme glouton, mais elle apporte une garantie plus forte lorsque le problème présente des sous-structures optimales. Une explication détaillée de cette approche par sous-problèmes mémorisés permet de mieux comprendre pourquoi elle surpasse parfois les choix immédiats.
L’algorithme de Dijkstra est souvent cité comme un exemple réussi de stratégie gloutonne. Il sert à trouver les plus courts chemins depuis un sommet de départ dans un graphe dont les arêtes ont des poids positifs ou nuls. À chaque étape, il sélectionne le sommet non traité ayant la plus petite distance provisoire. Ce choix local devient définitif, car aucun chemin ultérieur ne pourra l’améliorer si les poids restent non négatifs.
La précision est importante. Si le graphe contient des poids négatifs, le raisonnement ne tient plus. Un chemin découvert plus tard pourrait réduire une distance déjà validée. Dans ce cas, Dijkstra peut produire un résultat incorrect, et d’autres algorithmes sont nécessaires. Pour replacer ce mécanisme dans le contexte des graphes pondérés, l’analyse du calcul progressif des plus courts chemins montre bien pourquoi les conditions d’application sont déterminantes.
Avant d’utiliser un algorithme glouton, il faut vérifier qu’il ne se contente pas de donner une solution plausible. En algorithmique, une intuition ne suffit pas. Il faut démontrer que le choix effectué à chaque étape peut toujours conduire à une solution optimale. Cette preuve passe souvent par un argument d’échange : on montre qu’une solution optimale peut être transformée pour inclure le choix glouton sans perdre en qualité.
Il faut aussi examiner les contre-exemples. Un seul cas où la méthode échoue suffit à prouver qu’elle n’est pas toujours optimale. Le test sur de petites instances est souvent révélateur, car les erreurs apparaissent dans des configurations simples. C’est une bonne pratique en conception d’algorithmes : confronter une stratégie séduisante à des cas limites, plutôt que de s’appuyer uniquement sur son efficacité apparente.
La méthode gloutonne reste un outil central en informatique. Elle produit des algorithmes simples, rapides et faciles à implémenter. Dans des contextes bien définis, elle offre même une solution optimale avec une efficacité remarquable. C’est pourquoi elle apparaît dans de nombreux domaines : réseaux, planification, compression, graphes, allocation de ressources ou approximation de problèmes complexes.
Mais son efficacité ne doit pas être confondue avec une garantie universelle. Le risque vient de la confusion entre meilleur choix immédiat et meilleure solution finale. Pour certains problèmes, cette intuition est exacte. Pour d’autres, elle mène à une impasse discrète mais réelle. Comprendre cette limite est essentiel pour choisir le bon algorithme, évaluer la qualité d’une solution et éviter qu’une optimisation rapide ne devienne une mauvaise décision technique.
