Greedy Algorithms
Un algorithme glouton (Greedy Algorithm en anglais) est une approche paradigmatique en algorithmique qui construit une solution à un problème d’optimisation étape par étape. À chaque étape, l’algorithme fait le choix qui semble le meilleur à ce moment précis, selon un critère d’optimalité local, sans considérer les conséquences futures de ce choix sur les étapes suivantes. L’objectif est que cette séquence de choix localement optimaux mène à une solution globalement optimale ou, du moins, à une bonne approximation.
Les concepts fondamentaux des algorithmes gloutons reposent sur l’idée de prendre la décision la plus avantageuse immédiatement disponible. Le principe essentiel est celui du choix localement optimal : à chaque point de décision, l’algorithme sélectionne l’option qui maximise ou minimise un critère donné, sans réévaluer les décisions passées. Pour qu’un algorithme glouton garantisse une solution globalement optimale, le problème sous-jacent doit généralement posséder deux propriétés clés. La première est la propriété de sous-structure optimale, signifiant qu’une solution optimale au problème global contient des solutions optimales à ses sous-problèmes. La seconde, plus cruciale pour les algorithmes gloutons, est la propriété du choix glouton (Greedy Choice Property). Cette propriété stipule qu’un choix localement optimal peut être étendu pour aboutir à une solution globalement optimale. Autrement dit, le premier choix fait par l’algorithme doit faire partie d’au moins une solution optimale globale. Les algorithmes gloutons sont typiquement irrévocables : une fois qu’un choix est fait, il n’est jamais remis en question (pas de retour en arrière ou backtracking).
L’importance des algorithmes gloutons réside dans leur simplicité conceptuelle et leur facilité de mise en œuvre comparées à d’autres techniques d’optimisation plus complexes comme la programmation dynamique ou la recherche exhaustive. Ils sont souvent très efficaces en termes de temps de calcul, aboutissant fréquemment à des solutions rapides (souvent en temps polynomial). Cette efficacité les rend pertinents pour résoudre de grands problèmes où des méthodes plus lentes seraient impraticables. Dans le domaine de l’éducation en informatique, ils constituent une introduction fondamentale aux techniques de conception d’algorithmes. Leur impact s’étend aussi aux problèmes pour lesquels trouver une solution optimale exacte est trop coûteux (NP-difficile) ; dans ces cas, une approche gloutonne peut servir d’heuristique pour trouver rapidement une solution approximative de bonne qualité.
Les algorithmes gloutons trouvent de nombreuses applications pratiques. Un exemple classique est le problème du rendu de monnaie dans certains systèmes monétaires (comme l’euro ou le dollar américain) : pour rendre une somme donnée avec le moins de pièces possible, on prend répétitivement la pièce de la plus grande valeur possible qui ne dépasse pas la somme restante. Un autre exemple est le problème du sac à dos fractionnaire, où l’on doit remplir un sac de capacité limitée avec des objets (dont on peut prendre des fractions) pour maximiser la valeur totale ; l’approche gloutonne consiste à prendre les objets par ordre décroissant de leur ratio valeur/poids. Les algorithmes de Prim et de Kruskal, qui trouvent un arbre couvrant minimal dans un graphe pondéré, sont des algorithmes gloutons fondamentaux. L’algorithme de Dijkstra pour calculer les plus courts chemins depuis une source unique dans un graphe à poids positifs est également une application gloutonne célèbre. Le codage de Huffman, utilisé en compression de données, construit un codage préfixe optimal en fusionnant itérativement les deux symboles de plus faible fréquence. Le problème de sélection d’activités, visant à planifier un maximum d’activités non conflictuelles, se résout aussi par une stratégie gloutonne (choisir l’activité se terminant le plus tôt).
Il existe des nuances importantes concernant les algorithmes gloutons. Le terme « glouton » fait référence à la stratégie de décision à court terme, mais ne garantit pas intrinsèquement l’optimalité globale. Un algorithme glouton ne produit la solution exacte que si le problème possède les propriétés structurelles adéquates (choix glouton et sous-structure optimale). Lorsque ces propriétés ne sont pas satisfaites, l’approche gloutonne peut échouer à trouver la meilleure solution, comme dans le cas général du problème du rendu de monnaie avec des systèmes de pièces arbitraires ou le problème du sac à dos 0/1 (où l’on ne peut pas prendre de fractions d’objets). Dans de tels cas, l’algorithme glouton est souvent qualifié d’heuristique gloutonne : il fournit une solution rapidement, mais sans garantie d’optimalité. Il existe peu de variations pures du concept glouton, car sa nature est de faire un choix unique et définitif à chaque étape, mais on peut imaginer des approches « semi-gloutonnes » qui explorent un nombre limité d’options locales avant de s’engager.
Plusieurs concepts sont étroitement liés aux algorithmes gloutons. La programmation dynamique est souvent comparée et contrastée : elle résout aussi des problèmes avec sous-structure optimale, mais elle explore systématiquement les solutions des sous-problèmes, les mémorise et les combine, au lieu de faire un unique choix irrévocable à chaque étape. Elle est plus puissante mais souvent moins efficace que l’approche gloutonne quand celle-ci fonctionne. Les heuristiques sont une catégorie plus large qui inclut les algorithmes gloutons utilisés pour l’approximation. Les algorithmes d’approximation sont conçus pour trouver des solutions proches de l’optimal pour des problèmes difficiles, et les stratégies gloutonnes en sont une source fréquente. L’optimisation combinatoire est le domaine mathématique qui étudie de nombreux problèmes auxquels les algorithmes gloutons sont appliqués. Comme antonymes ou approches alternatives, on trouve la recherche exhaustive (Brute Force), le backtracking (qui explore des chemins et revient en arrière si nécessaire), les méthodes Branch and Bound (qui explorent l’espace des solutions en élaguant les branches non prometteuses) et la programmation dynamique mentionnée précédemment. Il n’y a pas de synonyme direct largement utilisé, mais on pourrait parler d’approche « myope » ou « à court terme ».
L’approche gloutonne est conceptuellement simple et intuitive, et il est probable qu’elle ait été utilisée de manière informelle depuis longtemps pour prendre des décisions séquentielles. Cependant, sa formalisation en tant que technique algorithmique distincte date du milieu du 20ème siècle avec le développement de l’informatique théorique. Des algorithmes comme ceux de Kruskal (1956), Prim (1957, mais découvert plus tôt par Jarník en 1930) pour l’arbre couvrant minimal, et Dijkstra (1959, publié en 1959 mais conçu en 1956) pour les plus courts chemins sont des exemples canoniques précoces d’algorithmes gloutons prouvés corrects. Le terme « greedy » lui-même s’est imposé pour décrire cette stratégie directe et focalisée sur le gain immédiat.
Les avantages des algorithmes gloutons incluent leur simplicité de conception et d’implémentation, ainsi que leur efficacité en temps. Pour les problèmes où ils fonctionnent, ils sont souvent parmi les algorithmes les plus rapides possibles. Leur nature intuitive les rend faciles à comprendre. Cependant, leur principal inconvénient est leur portée limitée : ils ne garantissent pas l’optimalité pour tous les problèmes d’optimisation. Leur « myopie » – l’incapacité de voir au-delà du choix immédiat – peut les conduire à des solutions globales médiocres ou incorrectes. Un défi majeur est de déterminer si une approche gloutonne est applicable et correcte pour un problème donné. La preuve de correction d’un algorithme glouton n’est pas toujours triviale et requiert souvent des arguments mathématiques spécifiques, comme une preuve par échange (montrer que tout écart par rapport au choix glouton peut être corrigé sans dégrader la solution) ou une preuve par induction sur les étapes de l’algorithme. Leurs limitations sont claires : ils échouent sur des problèmes d’optimisation classiques comme le problème du voyageur de commerce (trouver le circuit le plus court visitant toutes les villes une fois) ou le problème du sac à dos 0/1.