Les algorithmes gloutons

Pr. EL HADIQ Zouhair

Résoudre des problèmes d'optimisation, un choix local à la fois — CPGE MP/PSI

1 / 13

Problèmes d'optimisationIntro

Trouver, parmi un très grand nombre de solutions, celle qui minimise ou maximise une fonction objectif.

Force brute : explorer toutes les combinaisons coûte un temps exponentiel — irréaliste.
2 / 13

L'idée gloutonnePrincipe

Construire la solution pas à pas. À chaque étape, faire le choix localement optimal (le plus « gourmand »), sans jamais revenir en arrière.

def glouton(candidats): solution = [] while not complet(solution) and candidats: x = meilleur_candidat(candidats) # choix glouton candidats.remove(x) if compatible(solution, x): solution.append(x) return solution
Rapide et simple — mais « localement » ne veut pas dire « globalement » optimal.
3 / 13

Les deux ingrédientsThéorie

1. Propriété du choix glouton. Il existe une solution optimale contenant le choix localement optimal de la première étape : ce choix ne ferme jamais la porte à l'optimum.
2. Sous-structure optimale. Une solution optimale contient des solutions optimales des sous-problèmes : après un choix, il reste un problème de même nature, plus petit.

Si l'une manque → le glouton peut échouer.

4 / 13

Glouton vs programmation dynamiqueComparaison

GloutonProgrammation dynamique
Un seul choix par étapePlusieurs choix examinés
Jamais de retour en arrièreCombine les sous-problèmes
Très rapidePlus coûteuse
Correct si choix glouton vérifiéToujours optimale
5 / 13

Rendu de monnaieExemple 1

Rendre une somme $S$ avec le moins de pièces. Glouton : prendre la plus grande pièce $\le$ reste.

def rendu_monnaie(systeme, S): rendu = [] for piece in systeme: # décroissant while S >= piece: rendu.append(piece) S = S - piece return rendu
68 = 50 + 10 + 5 + 2 + 1 → 5 pièces (optimal).
6 / 13

Rendu : ça dépend du système !Contre-exemple

Système euro (canonique). Le glouton donne toujours le nombre minimal de pièces.
Système (1, 3, 4), rendre 6 :
Glouton → 4 + 1 + 1 = 3 pièces.
Optimal → 3 + 3 = 2 pièces !

Prendre 4 d'abord a fermé la porte à l'optimum : ce système ne vérifie pas la propriété du choix glouton.

7 / 13

Sac à dos fractionnaireExemple 2

Objets divisibles. Glouton : trier par valeur/poids $v_i/p_i$ décroissant, remplir, finir par une fraction.

def sac_fractionnaire(objets, C): objets = sorted(objets, key=lambda o: o[0]/o[1], reverse=True) valeur = 0.0 for v, p in objets: if C >= p: valeur += v; C -= p else: valeur += v * (C / p); break return valeur
✅ Optimal (preuve par échange).
8 / 13

Sac à dos 0/1Contre-exemple

Objets indivisibles (0 ou 1). Le même glouton échoue. Capacité $C = 50$ :

ObjetValeurPoidsv/p
A60106
B100205
C120304
Glouton (A puis B) → 160.   Optimal (B + C) → 220 !

Il faut la programmation dynamique.

9 / 13

Codage de HuffmanExemple 3

Compresser : codes courts pour caractères fréquents. Code préfixe = arbre binaire (gauche 0, droite 1).

Glouton. Tant qu'il reste > 1 arbre : fusionner les deux plus petites fréquences sous une racine de poids = leur somme.

Forêt initiale : un arbre par caractère, pondéré par sa fréquence.
10 / 13

Huffman : implémentationCode

import heapq def huffman(freq): tas = [[f, c, None, None] for c, f in freq.items()] heapq.heapify(tas) while len(tas) > 1: g = heapq.heappop(tas) # 2 plus petites d = heapq.heappop(tas) heapq.heappush(tas, [g[0]+d[0], None, g, d]) return tas[0]
A:5,B:2,C:1,D:1 → A:0, B:11, C:100, D:101. ✅ Longueur moyenne minimale.
11 / 13

Quand le glouton est-il optimal ?Bilan

ProblèmeOptimal ?
Rendu monnaie (euro)✅ Oui
Rendu monnaie (1,3,4)❌ Non
Sac à dos fractionnaire✅ Oui
Sac à dos 0/1❌ Non
Codage de Huffman✅ Oui
12 / 13

À retenirSynthèse

13 / 13