Algorithme
Algorithmes Gloutons : La gourmandise mène à la solution
Les algorithmes gloutons, une approche intuitive pour résoudre des problèmes complexes.
Dans le monde vaste et parfois intimidant de l’algorithmique, il existe une famille de solutions séduisante par sa simplicité et souvent redoutable d’efficacité, les algorithmes gloutons (ou greedy algorithms). Que vous soyez en train d’optimiser le trajet d’un robot ou simplement de rendre la monnaie à la caisse d’une épicerie, vous appliquez sans doute, sans le savoir, cette logique.
Cependant, comme nous allons le voir, la simplicité a un prix. Si cette méthode brille par sa rapidité, elle ne garantit pas toujours la meilleure solution possible. Plongeons ensemble dans la mécanique de ces algorithmes pour comprendre quand les utiliser et, surtout, quand s’en méfier.
Fondamentaux et Philosophie du Glouton
Principe de la décision locale
L’essence même d’un algorithme glouton réside dans sa stratégie de prise de décision. Face à un problème complexe qui nécessite une suite d’actions, l’algorithme fait le choix qui lui semble le meilleur à l’instant présent, sans se soucier des conséquences futures. C’est ce qu’on appelle un optimum local.
L’idée est de construire la solution étape par étape. À chaque étape, l’algorithme sélectionne l’option la plus avantageuse immédiatement disponible et valide ce choix de manière définitive. Il n’y a pas de retour en arrière possible (backtracking). L’algorithme parie sur le fait qu’une suite de bonnes décisions locales mènera inévitablement à une solution globalement optimale. C’est une philosophie de l’instant, on prend le plus gros morceau disponible tout de suite, d’où le terme « glouton ».
Distinction entre algorithme et heuristique
Il est crucial pour un développeur de bien distinguer ces deux termes, car le résultat final en dépend. Lorsque la méthode gloutonne garantit mathématiquement d’obtenir la solution optimale (la meilleure possible) à tous les coups, on parle légitimement d’algorithme glouton. C’est le cas idéal.
En revanche, pour de nombreux problèmes complexes, cette stratégie fournit une solution « suffisante » ou « acceptable », mais pas forcément la meilleure absolue. Dans ce cas, on ne parle plus d’algorithme au sens strict, mais d’une heuristique gloutonne. C’est une méthode de résolution approchée. Elle est très utile lorsque la recherche de la solution parfaite demanderait un temps de calcul déraisonnable (comme tester toutes les combinaisons possibles). L’heuristique est un compromis pragmatique entre précision et temps de réponse.
Efficacité et performance
Pourquoi utiliser une approche gloutonne si elle n’est pas toujours parfaite ? La réponse tient en un mot : efficacité. Comme l’algorithme ne remet jamais en cause ses choix précédents, il progresse de manière linéaire vers la solution. Il n’a pas besoin d’explorer toutes les branches d’un arbre de possibilités.
Cette caractéristique rend les algorithmes gloutons extrêmement rapides et faciles à implémenter. Leur complexité est souvent faible, car le gros du travail réside généralement dans un prétraitement des données, comme un tri initial. Pour un ingénieur, c’est souvent la première piste à explorer, une solution gloutonne est rapide à coder et peut servir de référence (baseline) pour mesurer la performance de solutions plus complexes.
Le cas d’école : Le problème du rendu de monnaie
Modélisation du rôle du caissier
L’exemple le plus célèbre pour illustrer ce concept est le problème du rendu de monnaie. Imaginez que vous êtes un caissier. Vous devez rendre une somme exacte (par exemple 49 centimes) à un client, en utilisant le moins de pièces possible. Vous disposez d’un stock illimité de pièces de différentes valeurs (le système monétaire).
C’est un problème d’optimisation classique. L’entrée est le montant à rendre et la liste des pièces disponibles. La sortie attendue est la liste minimale de pièces dont la somme égale le montant. L’approche intuitive de tout être humain est naturellement gloutonne, on prend la plus grosse pièce possible qui ne dépasse pas la somme restante, et on recommence jusqu’à atteindre zéro.
Implémentation Technique en Python
Traduisons cette logique en code. L’algorithme consiste à parcourir les pièces, de la plus grande valeur à la plus petite, et à en prendre autant que possible tant que le montant restant le permet.
Voici une implémentation standard en Python :
def rendu_glouton(restant, pieces):
# On suppose que le tableau 'pieces' est trié par ordre croissant
# On commence par la plus grande pièce (la fin du tableau)
indice_pieces = len(pieces) - 1
rendu = []
while restant > 0 and indice_pieces >= 0:
valeur_piece = pieces[indice_pieces]
if valeur_piece <= restant:
# On prend la pièce : choix glouton
restant = restant - valeur_piece
rendu.append(valeur_piece)
else:
# La pièce est trop grande, on passe à la suivante
indice_pieces = indice_pieces - 1
return rendu
# Exemple avec le système Euro
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
print(rendu_glouton(49, systeme_euro))
# Résultat attendu : [20, 20, 5, 2, 2]Dans ce script, la boucle while représente la répétition du choix local. À chaque itération, nous effectuons le meilleur choix possible (la plus grosse pièce) pour réduire la dette, sans jamais revenir sur les pièces déjà rendues.
Analyse de la Terminaison
Une question fondamentale en algorithmique est de savoir si le programme va s’arrêter. Dans le cas du rendu de monnaie, l’algorithme glouton se termine toujours, à une condition précise : le système monétaire doit contenir la pièce unité (la valeur 1).
En effet, si nous disposons d’une pièce de valeur 1, il sera toujours possible de compléter le rendu, quelle que soit la somme restante. L’algorithme ne peut pas rester bloqué dans une boucle infinie ou échouer à rendre la somme exacte. C’est une garantie de robustesse importante pour ce type de système.
3. Les pièges de l’approche : Quand l’intuition échoue
Illustration par le Contre-Exemple
C’est ici que les choses deviennent intéressantes. L’algorithme glouton semble infaillible avec nos Euros, mais il peut échouer lamentablement avec d’autres systèmes de pièces. Prenons un système fictif avec les pièces (1, 3, 4) et essayons de rendre la somme de 6.
L’algorithme glouton va appliquer sa logique aveugle :
- Il cherche la plus grande pièce inférieure ou égale à 6. Il choisit 4.
- Il reste 2 à rendre (6 – 4).
- La plus grande pièce inférieure ou égale à 2 est 1.
- Il reste 1. Il prend encore 1.
Résultat glouton : 4 + 1 + 1 (soit 3 pièces).
Pourtant, un regard humain voit immédiatement une solution plus optimale : 3 + 3. Cela ne fait que 2 pièces ! Dans ce cas précis, le choix localement optimal (prendre le 4) a empêché d’atteindre l’optimum global. L’algorithme n’est pas « correct » pour ce système.
Notion de système canonique
Pourquoi cela fonctionne-t-il avec l’euro et pas avec le système (1, 3, 4) ? Les systèmes monétaires pour lesquels l’algorithme glouton donne toujours la solution optimale sont appelés des systèmes canoniques.
Il n’existe malheureusement pas de critère simple et universel pour déterminer du premier coup d’œil si un système est canonique ou non. Cependant, on peut démontrer mathématiquement que le système européen est canonique. C’est une propriété heureuse qui facilite la vie de nos commerçants et de nos automates bancaires, mais ce n’est pas une règle générale en optimisation.
Le dilemme du maximum local
Pour visualiser ce piège, on utilise souvent l’analogie de l’alpiniste (ou Hill Climbing). Imaginez que vous êtes dans le brouillard sur un relief montagneux et que vous cherchez à atteindre le point le plus haut (le maximum global M).
Votre stratégie « gloutonne » consiste à toujours monter la pente la plus raide à partir de là où vous êtes. En suivant cette règle, vous finirez certainement par atteindre un sommet. Mais rien ne garantit que ce soit le plus haut de la chaîne ! Vous pourriez vous retrouver bloqué sur un pic secondaire (un maximum local, noté m), alors que le véritable sommet (M) se trouve de l’autre côté de la vallée. Comme l’algorithme glouton ne redescend jamais (pas de retour arrière), il reste coincé sur ce résultat sous-optimal.
Applications avancées : Graphes et voyageurs
Optimisation des réseaux (Prim et Kruskal)
Au-delà de la monnaie, les algorithmes gloutons sont les rois de la théorie des graphes, notamment pour résoudre le problème de l’Arbre Couvrant Minimal. Imaginez devoir relier plusieurs villes avec de la fibre optique en minimisant la longueur totale de câble.
Les algorithmes de Prim et de Kruskal sont deux exemples brillants d’approche gloutonne qui fonctionnent parfaitement ici.
- Prim part d’un nœud et fait « grandir » l’arbre en ajoutant toujours la connexion la moins chère accessible.
- Kruskal trie toutes les connexions possibles par coût et les ajoute une par une, tant qu’elles ne créent pas de boucle.
Dans ces cas précis, la magie opère, la suite de choix locaux économiques garantit la structure la moins chère au global.
Stratégies pour le voyageur de commerce
Le célèbre problème du Voyageur de Commerce (visiter une liste de villes et revenir au point de départ en minimisant la distance) est beaucoup plus coriace. Il n’existe pas d’algorithme efficace pour trouver la solution parfaite en un temps raisonnable (c’est un problème NP-complet).
Ici, l’approche gloutonne devient une heuristique précieuse. La méthode du « plus proche voisin » consiste à aller systématiquement vers la ville non visitée la plus proche. Bien que cette méthode ne donne pas le trajet le plus court absolu, elle fournit une solution très rapidement. D’autres variantes, comme la « meilleure insertion » (insérer une ville dans le circuit là où elle coûte le moins cher), permettent d’affiner le résultat.
Gestion des Contraintes (Coloration de Graphe)
Enfin, terminons sur un problème de planification, la coloration de graphe. L’objectif est d’attribuer une couleur à chaque nœud d’un réseau de sorte que deux nœuds voisins n’aient jamais la même couleur, tout en utilisant le moins de couleurs possible.
Là encore, trouver le minimum absolu (le nombre chromatique) est extrêmement difficile pour des graphes complexes. Une heuristique gloutonne simple consiste à parcourir les sommets un par un et à leur attribuer la première couleur disponible qui n’est pas utilisée par leurs voisins déjà colorés. Le résultat sera une coloration valide, rapide à obtenir, même si elle utilise parfois plus de couleurs que le strict minimum théorique.
