#Algorithmes gloutonsCopier le lien

Prérequis : tris et comparaisons O(n log n) ; notions de preuve par échange ; chapitre Programmation dynamique pour le contrepoint sac à dos.

Objectifs : formuler le choix glouton et son critère de tri ; prouver l'optimalité par argument d'échange ; reconnaître les problèmes où le glouton échoue ; estimer la complexité (souvent dominée par le tri).

#1. Le schéma gloutonCopier le lien

Un algorithme glouton suit une heuristique simple : à chaque étape, il fait le choix qui semble le meilleur sur le moment, sans jamais revenir en arrière. Trois caractéristiques :

• Choix glouton : une règle locale décide, par exemple « la pièce la plus grande qui reste inférieure au montant ».
• Sous-structure optimale : une fois le premier choix fait, le reste du problème se résout de la même façon.
• Pas de retour arrière : un choix n'est jamais révisé ; c'est la force (vitesse) et la faiblesse (aucune garantie sans preuve).

La question centrale n'est pas « le code marche-t-il ? » (il marche toujours) mais « le résultat est-il optimal ? ». Cette preuve se fait par argument d'échange : on montre que toute solution optimale peut être transformée, sans perdre en qualité, en la solution que le glouton construit.

#2. Exemple classique : rendu de monnaieCopier le lien

Trouver le nombre minimal de pièces pour rendre une somme, avec un système de pièces donné :

1def rendre_monnaie_glouton(montant, pieces):2    """pieces doit être trié par valeur décroissante."""3    resultat = []4    for piece in pieces:5        while montant >= piece:6            resultat.append(piece)7            montant -= piece8    return resultat9 10pieces = [100, 50, 20, 10, 5, 2, 1]   # en centimes11rendu = rendre_monnaie_glouton(287, pieces)12print(rendu, "soit", len(rendu), "pièces")   # [100, 100, 50, 20, 10, 5, 2] : 7 pièces

Ce glouton est optimal pour le système européen, et la preuve par échange tient : toute solution optimale utilisant une pièce plus petite là où une plus grande rent peut être améliorée, contradiction. Mais la propriété dépend du système, pas de l'algorithme. Avec 4 et un montant de 6, ce glouton rend 4+1+1 (trois pièces) alors que 3+3 est optimal. La solution robuste est la programmation dynamique, détaillée au chapitre correspondant.

#3. Dijkstra : un glouton sur les distancesCopier le lien

L'algorithme de Dijkstra est glouton : il fixe définitivement, à chaque étape, le sommet de plus petite distance provisoire, en pariant que cette distance est déjà optimale. Le pari tient parce que tous les poids sont non négatifs : aucun détour ne peut raccourcir un chemin déjà minimal. L'argument complet (invariant d'exploration par distances croissantes) est développé au chapitre Dijkstra ; voici l'implémentation de référence :

1import heapq2 3def dijkstra(graphe, depart):4    """Distances minimales depuis depart ; poids tous non négatifs.5    graphe : dict sommet -> dict voisin -> poids"""6    distances = {s: float('inf') for s in graphe}7    distances[depart] = 08    file = [(0, depart)]9    while file:10        d, u = heapq.heappop(file)11        if d > distances[u]:12            continue                     # entrée périmée : ignorer13        for v, poids in graphe[u].items():14            candidat = d + poids

#Animation interactiveCopier le lien

La visualisation ci-dessous montre le déroulé : à chaque tour, le sommet de plus petite distance est figé (couleur définitive) et ses arêtes relâchées. Essayez de prédire le prochain sommet figé avant de cliquer ; c'est le meilleur test de compréhension de l'invariant.

Entrées de la visualisation : un graphe pondéré fixé, un sommet source au choix. Sorties : l'ordre de figement des sommets et la distance finale de chacun. Observez qu'un sommet figé n'est jamais re-visité : c'est le pari glouton.

#4. Ordonnancement d'intervalles : la preuve par échangeCopier le lien

Sélectionner le maximum d'intervalles deux à deux disjoints. Le choix glouton : trier par fin croissante, prendre le premier, puis toujours le premier compatible.

1def planification_intervalles(intervalles):2    """intervalles : liste de (debut, fin) ; renvoie une sélection maximale."""3    tries = sorted(intervalles, key=lambda x: x[1])4    selection = []5    derniere_fin = float('-inf')6    for debut, fin in tries:7        if debut >= derniere_fin:8            selection.append((debut, fin))9            derniere_fin = fin10    return selection11 12intervalles = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),13               (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]14print(planification_intervalles(intervalles))

La preuve en deux phrases : soit une solution optimale O et soit g le premier intervalle choisi par le glouton (celui qui finit le plus tôt). Comme g finit au plus tard aussi tôt que le premier intervalle de O, remplacer celui-ci par g préserve la compatibilité ; on répète l'échange sur le reste, d'où une solution gloutonne de même taille que l'optimum. Complexité : O(n log n) pour le tri, O(n) pour la sélection.

#5. Problèmes où le glouton est optimalCopier le lien

1. Arbre couvrant minimal : Kruskal (tri des arêtes, union-find) et Prim ; preuves par échange sur l'arête de poids minimal traversant une coupe.
2. Ordonnancement d'intervalles : tri par fin croissante, démontré ci-dessus.
3. Sac à dos fractionnaire : tri par ratio valeur/poids, on peut couper le dernier objet ; la coupure est impossible en 0/1, d'où l'échec.
4. Codage de Huffman : fusion des deux nœuds de plus faible fréquence ; chapitre dédié.
5. Rendu de monnaie : optimal pour certains systèmes (européen), pas pour tous.

#6. Limites : quand le glouton échoueCopier le lien

Sans preuve, le glouton est une heuristique dont l'écart à l'optimum peut être arbitrairement grand. Trois réflexes devant un nouveau problème :

• Chercher un contre-exemple minimal : deux ou trois objets suffisent souvent (sac à dos 0/1 avec {poids, valeurs} bien choisis).
• Chercher l'argument d'échange ; s'il échoue sur un cas, la DP ou la recherche exhaustive reprennent la main.
• À défaut d'optimalité, viser une garantie d'approximation (par exemple, le glouton du sac à dos 0/1 par ratio atteint au moins la moitié de l'optimum) et l'énoncer explicitement.

#7. Exercices avec vérificationCopier le lien

1. Intervalles pondérés : chaque intervalle a une valeur ; maximiser la valeur totale devenue impossible pour le glouton simple. Vérification : sur les intervalles [(1,4,10), (3,5,20), (5,7,15)] avec valeurs 10, 20, 15, l'optimum vaut 25 (intervalles 1 et 3) alors que le glouton par valeur ou par durée échoue ; il faut la DP.
2. Contre-exemple monnaie : trouvez un système de pièces et un montant où le glouton rend strictement plus de pièces que l'optimum. Vérification : 4 et 6 donnent 3 contre 2.
3. Réunion de points (facile, pour se chauffer) : n points sur une droite, couvrir tous les points avec le minimum de segments de longueur fixe k. Vérification : points [1, 2, 3, 9, 10] avec k=1, la réponse est 3 segments.

Éléments de correction pour l'exercice 3 : trier les points, placer un segment dès le premier point non couvert, en partant de ce point (il couvre jusqu'à x+k), compter et recommencer. L'argument d'échange : tout optimum doit couvrir le premier point, et le segment le plaçant à son extrémité gauche couvre au moins autant de points.

#8. ComplexitéCopier le lien

La plupart des gloutons coûtent un tri plus un balayage :

• Rendu de monnaie : O(n) après tri des pièces, O(n log n) si le tri est à votre charge.
• Ordonnancement d'intervalles : O(n log n) dominé par le tri.
• Dijkstra : O((V + E) log V) avec un tas binaire.
• Kruskal : O(E log E) dominé par le tri des arêtes.