Prouver qu’un algorithme glouton donne toujours la meilleure solution n’est pas une simple formalité. Derrière une stratégie souvent intuitive — choisir à chaque étape l’option qui semble la plus avantageuse — se cache une question centrale : ce choix local garantit-il vraiment une solution optimale globale ? C’est précisément ce que doit démontrer une preuve rigoureuse.
Un algorithme glouton, ou greedy algorithm, construit une solution étape par étape en prenant à chaque fois la décision qui paraît la meilleure selon un critère donné. Cette méthode est séduisante parce qu’elle est souvent simple, rapide et facile à implémenter. Mais cette simplicité peut être trompeuse : un choix qui semble optimal maintenant peut bloquer une meilleure solution plus tard.
La preuve d’optimalité sert donc à établir que la stratégie locale n’est pas seulement raisonnable, mais mathématiquement suffisante. Sans cette démonstration, l’algorithme peut produire de bons résultats sur quelques exemples tout en échouant sur des cas moins évidents. C’est notamment le cas du problème du rendu de monnaie : avec certains systèmes de pièces, choisir toujours la plus grande pièce possible fonctionne ; avec d’autres, cette règle peut être sous-optimale.
La difficulté vient du fait que l’on ne compare pas seulement une exécution particulière à quelques solutions concurrentes. Il faut prouver que, pour toutes les instances possibles du problème, aucune autre méthode ne peut faire mieux. C’est ce passage de l’intuition à la généralisation qui constitue le cœur de la preuve.
Avant d’écrire une preuve, il faut comprendre pourquoi le problème pourrait accepter une approche gloutonne. Deux propriétés sont généralement recherchées : la propriété de choix glouton et la sous-structure optimale. La première signifie qu’il existe toujours une solution optimale qui commence par le choix effectué par l’algorithme. La seconde indique qu’une fois ce choix fixé, le reste du problème reste lui-même un problème optimal de même nature.
Cette analyse évite de confondre algorithme glouton et simple heuristique. Une heuristique peut être utile sans garantie ; un algorithme glouton prouvé optimal repose sur une structure exploitable. Dans certains domaines, la comparaison avec le cadre de l’optimisation convexe aide à comprendre cette idée : lorsque la structure du problème est favorable, des garanties fortes deviennent possibles.
Il est donc utile de commencer par formuler clairement le problème : quelles sont les contraintes ? Qu’est-ce qu’une solution valide ? Quelle fonction cherche-t-on à minimiser ou maximiser ? Une preuve fragile vient souvent d’une définition imprécise de l’objectif ou des objets manipulés.
L’une des techniques les plus utilisées pour prouver l’optimalité d’un algorithme glouton est l’argument d’échange. L’idée est de partir d’une solution optimale quelconque et de montrer qu’on peut la transformer, étape par étape, en une solution qui contient les choix gloutons, sans dégrader sa qualité.
Supposons qu’un algorithme choisisse un élément A en premier. On prend une solution optimale qui ne contient pas A. La preuve doit montrer qu’il est possible de remplacer dans cette solution un autre élément par A, tout en conservant une solution valide et de même valeur, ou meilleure. Si cette opération est toujours possible, alors il existe au moins une solution optimale compatible avec le premier choix glouton.
Ce raisonnement est fréquent dans les problèmes d’ordonnancement. Par exemple, pour sélectionner un nombre maximal d’activités compatibles, la stratégie classique consiste à choisir d’abord l’activité qui se termine le plus tôt. La preuve montre qu’une solution optimale peut toujours être modifiée pour inclure cette activité, car elle libère au moins autant de place que toute autre activité choisie en premier. Le choix local devient alors sans perte de généralité.
Une fois le premier choix justifié, la preuve par induction permet souvent de conclure. Elle consiste à établir que si le choix glouton est sûr au départ, alors le même raisonnement s’applique au sous-problème restant. On prouve ainsi que chaque étape conserve la possibilité d’atteindre une solution optimale complète.
La structure d’une telle preuve est assez régulière. On commence par un cas de base, souvent trivial : un problème vide, un seul élément ou une instance minimale. Puis on suppose que l’algorithme est optimal pour les instances plus petites. Enfin, on démontre que le premier choix glouton réduit le problème à une instance plus petite sur laquelle l’hypothèse d’induction s’applique.
Cette méthode est puissante, mais elle demande de bien définir le sous-problème restant. Si le choix initial modifie les contraintes de manière irrégulière, l’induction peut devenir difficile, voire impossible. C’est un signal important : le problème n’a peut-être pas la structure adaptée à une approche gloutonne.
Une autre méthode consiste à montrer que l’algorithme glouton “reste toujours devant” toute solution concurrente. On compare les solutions après un certain nombre d’étapes et l’on prouve que la solution gloutonne n’est jamais en retard selon une mesure pertinente : coût cumulé, nombre d’éléments choisis, temps disponible, distance couverte ou valeur obtenue.
Cette approche fonctionne bien lorsque la progression de l’algorithme est facilement mesurable. Dans certains problèmes, on peut démontrer qu’après k choix, l’algorithme glouton a utilisé moins de ressource ou obtenu au moins autant de gain que n’importe quelle solution optimale partielle. La preuve repose alors sur un invariant de comparaison maintenu à chaque étape.
Le choix de la mesure est essentiel. Une comparaison mal choisie peut donner une impression de supériorité sans prouver l’optimalité réelle. Il faut relier directement cette mesure à l’objectif final du problème. Sinon, la démonstration risque de prouver une propriété vraie mais insuffisante.
Dans les graphes, certaines preuves gloutonnes s’appuient sur des propriétés dites de coupe. C’est le cas des algorithmes de Kruskal et de Prim pour construire un arbre couvrant de poids minimal. Le principe est de montrer qu’à chaque étape, l’arête choisie est sûre, c’est-à-dire qu’elle peut appartenir à au moins un arbre couvrant optimal.
Une coupe sépare les sommets du graphe en deux ensembles. Si une arête de poids minimal traverse cette coupe, elle peut être ajoutée sans compromettre l’optimalité. La preuve ne repose donc pas sur une intuition vague, mais sur une propriété structurelle du graphe. Chaque choix local est certifié par un raisonnement global.
Ce type de preuve illustre une idée importante : un algorithme glouton est rarement optimal parce qu’il “va vite vers le meilleur”. Il est optimal parce que le problème possède des propriétés qui rendent certains choix irréversibles mais sûrs.
Pour éviter les démonstrations incomplètes, il est utile de suivre une démarche structurée. La preuve doit expliquer non seulement pourquoi le choix paraît bon, mais pourquoi aucun autre choix ne peut conduire à un meilleur résultat. Voici une liste pratique pour cadrer le raisonnement :
Cette grille ne remplace pas la preuve, mais elle permet de repérer les failles courantes. Par exemple, dire qu’un choix “semble minimiser le coût” ne suffit pas. Il faut établir que ce coût local influence correctement l’objectif global.
Avant de chercher une preuve longue, il est souvent judicieux de tester l’algorithme sur de petites instances. Les contre-exemples sont précieux : ils montrent rapidement qu’une stratégie gloutonne ne peut pas être optimale dans sa forme actuelle. Une seule instance où l’algorithme échoue suffit à invalider la garantie.
Cette étape est particulièrement utile dans les problèmes combinatoires complexes, où les choix interagissent fortement. Lorsque les décisions locales créent des effets à long terme difficiles à contrôler, on se tourne parfois vers des méthodes adaptées aux problèmes très difficiles, qui cherchent de bonnes solutions sans promettre systématiquement l’optimalité.
Un contre-exemple ne signifie pas que toute approche gloutonne est impossible. Il peut simplement indiquer que le critère de choix est mal choisi. Modifier la règle, ajouter un tri préalable ou reformuler le problème peut parfois faire apparaître une stratégie correcte.
La première erreur consiste à prouver que le choix glouton est “raisonnable” au lieu de prouver qu’il est nécessairement compatible avec une solution optimale. Une preuve doit traiter les cas adverses, pas seulement les exemples favorables. L’intuition algorithmique est utile pour concevoir, mais insuffisante pour garantir.
Une autre erreur consiste à supposer implicitement la conclusion. Par exemple, affirmer que choisir l’élément le plus rentable est optimal parce qu’il maximise le gain immédiat revient souvent à ignorer les contraintes futures. Il faut démontrer que ces contraintes ne peuvent pas annuler l’avantage initial.
Enfin, certaines preuves oublient la faisabilité. Remplacer un élément dans une solution optimale n’est valable que si la solution modifiée respecte encore toutes les contraintes. Dans un argument d’échange, cette vérification est aussi importante que la comparaison des valeurs.
Prouver l’optimalité d’un algorithme glouton revient à montrer que le problème autorise des décisions locales définitives. Les outils les plus courants sont l’argument d’échange, l’induction, la comparaison “reste toujours devant” et les propriétés structurelles comme les coupes dans les graphes.
La bonne preuve ne se contente pas de justifier une intuition : elle établit que chaque choix glouton peut appartenir à une solution optimale, puis que le raisonnement se répète jusqu’à la fin. C’est ce qui distingue un algorithme rapide et convaincant d’un algorithme réellement garanti.
