backend / algorithmes-structures-donnees
Algorithmes gloutons
Explication
Ce que vous allez apprendre
- Définir un algorithme glouton et l'opposer à la programmation dynamique
- Identifier la "propriété du choix glouton" nécessaire pour prouver qu'un glouton est correct
- Reconnaître un cas où un glouton échoue (rendu de monnaie avec un système de pièces non canonique)
- Résoudre le problème de sélection d'activités en triant par heure de fin, et justifier ce critère précis
- Construire l'arbre de Huffman comme exemple de glouton qui construit une structure entière, pas juste une valeur
Dans quel contexte ?
Un développeur implémente un système de rendu de monnaie pour une caisse enregistreuse avec des pièces de 1, 3 et 4 centimes, en réutilisant "par réflexe" l'algorithme glouton qui fonctionne très bien avec les pièces euro classiques. Pour rendre 6 centimes, le glouton choisit 4 + 1 + 1 (trois pièces), alors que la solution optimale est 3 + 3 (deux pièces). Ce bug silencieux, sans aucune erreur visible, juste un résultat sous-optimal, illustre exactement pourquoi il faut prouver la propriété du choix glouton avant de faire confiance à cette approche.
D'abord, une idée séduisante mais risquée
Un algorithme glouton prend, à chaque étape, la décision qui semble la meilleure sur le moment, sans jamais revenir en arrière ni considérer les conséquences futures. C'est simple et rapide, contrairement à la PD vue précédemment qui explore systématiquement toutes les possibilités.
Le piège le plus fréquent avec cette approche
"Ça semble marcher sur mes exemples" n'est pas une preuve : un glouton mal justifié peut donner un résultat sous-optimal sans même qu'on s'en rende compte.
Piège fréquent
"Ça marche sur mes exemples de test" n'est jamais une preuve qu'un algorithme glouton est correct. Avec le système de pièces (1, 3, 4), un glouton rend 6 centimes en 4+1+1 (3 pièces) alors que l'optimum est 3+3 (2 pièces) — une erreur invisible tant qu'on ne teste pas spécifiquement ce cas.
La condition qui rend un glouton fiable
Un glouton n'est prouvé correct que si le problème possède la "propriété du choix glouton" : il existe toujours une solution optimale qui commence par le choix localement optimal.
Astuce
Pour savoir si un problème admet une solution gloutonne fiable, cherchez une preuve d'échange : montrez que n'importe quelle solution optimale peut être transformée, sans perte, pour commencer par le choix glouton. Si vous ne trouvez pas cette preuve, méfiez-vous et testez la PD à la place.
| Approche | Décision | Garantie d'optimalité | Vitesse typique |
|---|---|---|---|
| Glouton | Un seul choix, jamais reconsidéré | Seulement si la propriété du choix glouton est prouvée | Rapide, souvent O(n log n) |
| Programmation dynamique | Explore systématiquement les sous-problèmes | Toujours optimale | Plus lente, souvent O(n²) ou plus |
Un exemple qui illustre cette limite
Le rendu de monnaie avec les pièces euro illustre un glouton correct. Mais avec un système de pièces différent (1, 3, 4), ce même algorithme glouton peut se tromper, alors que la PD, elle, trouve toujours l'optimum réel.
Étape 1 : un exemple où le glouton fonctionne, mais pas de façon évidente
La sélection d'activités (maximiser le nombre d'activités non chevauchantes) est optimale en triant par heure de FIN, pas par heure de début ni par durée.
Pourquoi ce critère précis fonctionne
L'activité qui se termine le plus tôt laisse toujours le plus de place possible pour les activités suivantes, quelle que soit la solution optimale finale — c'est ce raisonnement qui prouve la correction du glouton ici.
Étape 2 : un glouton qui construit une structure entière, Huffman
Le codage de Huffman fusionne toujours les deux fréquences les plus faibles disponibles pour construire un arbre de codage, sans jamais remettre en question un choix déjà fait.
Le résultat de cette construction répétée
Ce choix local répété produit un arbre où les caractères fréquents obtiennent des codes courts et les caractères rares des codes longs, un résultat globalement optimal en compression.
Vers la suite
Contrairement à un glouton, certains problèmes n'ont pas de raccourci connu et nécessitent d'explorer systématiquement les possibilités tout en revenant en arrière dès qu'un choix échoue : c'est le sujet de la prochaine leçon, le backtracking.
Commandes & code
Algorithmes gloutons (greedy)
# Un algorithme glouton fait le choix localement optimal à chaque étape, SANS revenir en arrière.
# Il ne garantit une solution globalement optimale QUE si le problème a la "propriété du choix glouton".
# --- Rendu de monnaie glouton : optimal pour un système de pièces "canonique" (comme l'euro) ---
def rendu_monnaie_glouton(montant: int, pieces: list[int]) -> list[int]:
pieces = sorted(pieces, reverse=True) # commencer par les plus grosses pièces
resultat = []
for piece in pieces:
while montant >= piece:
montant -= piece
resultat.append(piece)
return resultat if montant == 0 else [] # échoue si aucune combinaison exacte n'existe
assert rendu_monnaie_glouton(67, [50, 20, 10, 5, 2, 1]) == [50, 10, 5, 2]
# ATTENTION : le glouton n'est PAS toujours optimal -- contre-exemple avec un système non canonique
# rendu_monnaie_glouton(6, [1, 3, 4]) donne [4, 1, 1] (3 pièces) au lieu de [3, 3] (2 pièces, optimal)
# -> la programmation dynamique (voir leçon précédente) est nécessaire pour un résultat garanti optimal
# --- Problème de sélection d'activités : maximiser le nombre d'activités non chevauchantes ---
def selection_activites(activites: list[tuple[int, int]]) -> list[tuple[int, int]]:
# Trier par heure de FIN (pas de début !) est la clé de l'optimalité de ce glouton
activites_triees = sorted(activites, key=lambda a: a[1])
selection = [activites_triees[0]]
derniere_fin = activites_triees[0][1]
for debut, fin in activites_triees[1:]:
if debut >= derniere_fin: # ne chevauche pas la dernière activité choisie
selection.append((debut, fin))
derniere_fin = fin
return selection
activites = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
resultat = selection_activites(activites)
assert len(resultat) == 4 # (1,4)(5,7)(8,11)(12,14) -- 4 activités, maximum possible
# --- Problème du rendu de monnaie minimal par DP (référence correcte, contrairement au glouton naïf) ---
def rendu_monnaie_minimal_dp(montant: int, pieces: list[int]) -> int:
infini = float("inf")
table = [0] + [infini] * montant
for m in range(1, montant + 1):
for piece in pieces:
if piece <= m and table[m - piece] + 1 < table[m]:
table[m] = table[m - piece] + 1
return table[montant] if table[montant] != infini else -1
assert rendu_monnaie_minimal_dp(6, [1, 3, 4]) == 2 # [3, 3] -- le glouton se trompait ici
# --- Codage de Huffman : construire un arbre de codage optimal (compression sans perte) ---
import heapq
from collections import Counter
class NoeudHuffman:
def __init__(self, caractere, frequence, gauche=None, droite=None):
self.caractere = caractere
self.frequence = frequence
self.gauche = gauche
self.droite = droite
def __lt__(self, autre): # nécessaire pour que heapq puisse comparer les noeuds
return self.frequence < autre.frequence
def construire_arbre_huffman(texte: str) -> NoeudHuffman:
frequences = Counter(texte)
tas = [NoeudHuffman(c, f) for c, f in frequences.items()]
heapq.heapify(tas)
while len(tas) > 1:
# glouton : fusionne toujours les DEUX noeuds de plus faible fréquence
gauche = heapq.heappop(tas)
droite = heapq.heappop(tas)
fusion = NoeudHuffman(None, gauche.frequence + droite.frequence, gauche, droite)
heapq.heappush(tas, fusion)
return tas[0]
def generer_codes_huffman(noeud: NoeudHuffman, prefixe: str = "", codes: dict | None = None) -> dict:
if codes is None:
codes = {}
if noeud.caractere is not None: # feuille
codes[noeud.caractere] = prefixe or "0"
return codes
generer_codes_huffman(noeud.gauche, prefixe + "0", codes)
generer_codes_huffman(noeud.droite, prefixe + "1", codes)
return codes
arbre = construire_arbre_huffman("abracadabra")
codes = generer_codes_huffman(arbre)
assert all(c in codes for c in "abracadabra") # les caractères fréquents obtiennent des codes plus courts
# --- Interval scheduling avec pénalités : minimiser le nombre de salles de réunion nécessaires ---
def nombre_min_salles(intervalles: list[tuple[int, int]]) -> int:
debuts = sorted(debut for debut, _ in intervalles)
fins = sorted(fin for _, fin in intervalles)
salles = salles_max = 0
i = j = 0
while i < len(debuts):
if debuts[i] < fins[j]:
salles += 1
salles_max = max(salles_max, salles)
i += 1
else:
salles -= 1
j += 1
return salles_max
assert nombre_min_salles([(0, 30), (5, 10), (15, 20)]) == 2Résumé
- Un glouton choisit l'option localement optimale à chaque étape : rapide, mais correct SEULEMENT si le problème a la propriété du choix glouton.
- Le rendu de monnaie glouton échoue sur des systèmes de pièces non canoniques : la DP donne toujours le résultat optimal, le glouton non.
- La sélection d'activités est optimale en triant par heure de FIN, une astuce non intuitive mais démontrable.
- Huffman illustre un glouton élégant : fusionner toujours les deux fréquences les plus faibles produit un codage optimal.
Exercices pratiques
Mission : corriger la caisse enregistreuse qui rend trop de pièces
Objectif : Diagnostiquer l'échec d'un glouton sur un système de pièces non canonique et le remplacer par la solution garantie optimale.
Contexte
Une caisse enregistreuse pour un jeton d'arcade utilise des pièces de valeurs 1, 3 et 4. Le développeur a réutilisé l'algorithme glouton classique (toujours prendre la plus grosse pièce possible), qui fonctionne très bien avec les pièces euro. Pour rendre 6 unités, la caisse rend actuellement 3 pièces au lieu de 2, sans jamais planter ni afficher d'erreur.