11 — Algorithmes Gloutons : Cours complet

Niveau : Université — Durée : 4h de cours + 4h de TP Un algorithme glouton prend, à chaque étape, la décision localement optimale en espérant que l'accumulation des décisions locales soit globalement optimale.

---

Partie I — Le principe glouton

1.1 Définition

Un algorithme glouton (greedy) :

• choisit à chaque étape l'option qui semble la meilleure maintenant ;
• ne revient jamais en arrière (pas de backtrack) ;
• n'explore qu'une seule séquence de choix.

Diagramme en cours de génération...

1.2 Les 4 ingrédients

1. Propriété du choix glouton : il existe une solution optimale qui commence par le choix glouton.
2. Sous-structure optimale : après le choix glouton, le sous-problème restant doit être résolu de manière optimale.
3. Tri ou file prioritaire : souvent l'implémentation commence par trier les éléments (sur un critère).
4. Preuve : l'optimalité n'est JAMAIS évidente — elle se démontre.

⚠️ Règle d'or : un greedy non prouvé est un bug potentiel. Toujours tester sur des contre-exemples avant de l'adopter.

1.3 Quand penser greedy ?

• L'énoncé contient "maximiser/minimiser un nombre d'éléments, un poids, un coût".
• On peut trier par un critère naturel (fin de tâche, ratio, fréquence).
• Un choix ne compromet pas les choix futurs (au moins intuitivement).

---

Partie II — Comment prouver l'optimalité

Deux techniques classiques :

2.1 L'argument d'échange (exchange argument)

Soit OPT une solution optimale et G la solution gloutonne. Si elles diffèrent, on transforme OPT en G sans dégrader la qualité, en une série d'échanges locaux.

Structure d'une preuve par échange :

1. Considérer le premier point où G et OPT divergent.
2. Montrer qu'on peut remplacer le choix de OPT par celui de G sans perte (ou avec gain).
3. Itérer → G est au moins aussi bonne que OPT.

2.2 Greedy stays ahead (le glouton garde l'avance)

On montre que la solution partielle du greedy est au moins aussi bonne que celle de toute solution optimale, à chaque étape. À la fin, le greedy est optimal.

Exemple : activity selection — montrer que la k-ième activité choisie par le greedy se termine au plus tard que la k-ième de toute autre solution.

---

Partie III — Activity Selection

Problème : n activités avec (start[i], end[i]). Maximiser le nombre d'activités compatibles (disjointes en temps).

Stratégie gloutonne : choisir l'activité qui finit le plus tôt (early finish time), puis récurser sur celles qui commencent après.

def activity_selection(start, end):
    n = len(start)
    order = sorted(range(n), key=lambda i: end[i])   # trier par fin
    selected, last_end = [], -1
    for i in order:
        if start[i] >= last_end:      # compatible ?
            selected.append(i)
            last_end = end[i]
    return selected

Preuve (exchange) : soit e l'activité qui finit le plus tôt. Toute solution optimale peut être transformée pour contenir e (remplacer sa première activité par e — elle finit plus tôt donc ne crée pas de conflit). Par récurrence, le greedy est optimal.

Complexité : O(n log n) (tri).

---

Partie IV — Fractional Knapsack

Problème : remplir un sac de capacité C avec des objets fractionnables (farine, liquides) de valeur v[i] et poids w[i]. Maximiser la valeur totale.

Stratégie : trier par ratio v[i]/w[i] décroissant, prendre en entier puis fractionner le dernier.

def fractional_knapsack(items, C):
    items.sort(key=lambda x: x[1] / x[0], reverse=True)   # tri par ratio
    value = 0.0
    for w, v in items:
        if C >= w:
            C -= w
            value += v
        else:
            value += v * C / w        # fraction
            break
    return value

Complexité : O(n log n).

⚠️ Contraste important : le knapsack 0/1 (entier) n'est PAS résoluble par greedy — il faut la DP (chapitre 10). Le greedy échoue car le meilleur ratio local peut bloquer la capacité pour une combinaison globale meilleure.

---

Partie V — Huffman Coding

Problème : construire un code binaire préfixe optimal (minimiser la longueur moyenne du codage) pour des symboles de fréquences f[i].

Stratégie : fusionner à chaque étape les 2 symboles de plus petite fréquence ; chaque fusion crée un nœud dont la fréquence est la somme.

import heapq

class Node:
    def __init__(self, freq, ch=None, left=None, right=None):
        self.freq = freq; self.ch = ch; self.left = left; self.right = right
    def __lt__(self, other): return self.freq < other.freq

def huffman(freqs):          # freqs: dict char -> freq
    heap = [Node(f, ch) for ch, f in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, Node(a.freq + b.freq, left=a, right=b))
    return heap[0]

def build_codes(node, prefix="", codes=None):
    if codes is None: codes = {}
    if node.ch is not None:
        codes[node.ch] = prefix
    else:
        build_codes(node.left, prefix + "0", codes)
        build_codes(node.right, prefix + "1", codes)
    return codes

Preuve (exchange) : les 2 symboles les moins fréquents peuvent être frères dans un code optimal ; on les fusionne. Propriété : le code de Huffman est un code préfixe optimal — c'est un cas particulier d'arbre de décision.

Complexité : O(n log n) avec tas binaire.

---

Partie VI — Minimum Coins et Job Scheduling

6.1 Minimum coins (système canonique)

Problème : rendre A avec le minimum de pièces, pièces illimitées.

Greedy : toujours prendre la plus grosse pièce possible.

def min_coins(coins, amount):
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        count += amount // c
        amount %= c
    return count

⚠️ Le greedy n'est optimal que pour les systèmes canoniques (EUR/USD : 1, 2, 5, 10, 20, 50, 100, 200). Contre-exemple : pièces {1, 3, 4}, montant 6 → greedy donne 4+1+1 = 3 pièces, optimum 3+3 = 2 pièces. Dans le cas général → DP (chapitre 10).

6.2 Job Scheduling (ordonnancement)

Problème : n tâches, chacune avec deadline d[i] et profit p[i]. Une tâche prend 1 unité de temps. Maximiser le profit des tâches planifiées avant leur deadline.

Greedy : trier par profit décroissant ; placer chaque tâche le plus tard possible (juste avant sa deadline) dans les créneaux libres.

def job_scheduling(jobs):          # jobs: [(profit, deadline)]
    jobs.sort(reverse=True)        # tri par profit décroissant
    max_deadline = max(d for _, d in jobs)
    slots = [False] * (max_deadline + 1)   # créneaux 1..max_deadline
    profit = 0
    for p, d in jobs:
        for t in range(d, 0, -1):          # le plus tard possible
            if not slots[t]:
                slots[t] = True
                profit += p
                break
    return profit

Complexité : O(n·max_deadline) naïf ; O(n log n) avec un union-find pour trouver le créneau libre.

---

Partie VII — Interval Partitioning

Problème : n cours avec (start[i], end[i]). Minimiser le nombre de salles nécessaires pour que les cours ne se chevauchent pas.

Greedy : trier par début ; pour chaque cours, le mettre dans la salle libérée la plus tôt (min-heap des fins de cours). Le nombre minimal de salles = profondeur maximale des intervalles.

import heapq

def interval_partitioning(intervals):
    intervals.sort()                     # tri par début
    heap = []                            # fins des salles en cours d'usage
    for s, e in intervals:
        if heap and heap[0] <= s:        # une salle est libre
            heapq.heapreplace(heap, e)
        else:
            heapq.heappush(heap, e)      # nouvelle salle
    return len(heap)

Preuve (lower bound) : on ne peut jamais utiliser moins de salles que la profondeur maximale ; le greedy atteint exactement cette borne.

Complexité : O(n log n).

---

Partie VIII — Dijkstra et Prim vus comme greedy

8.1 Dijkstra (plus court chemin à source unique, poids ≥ 0)

Diagramme en cours de génération...

• Le choix "sommet de plus petite distance" est localement optimal et globalement correct grâce aux poids non négatifs.
• Avec des poids négatifs → échec (il faut Bellman-Ford).

8.2 Prim (arbre couvrant minimal)

• À chaque étape : ajouter l'arête de poids minimal reliant l'arbre courant à un sommet extérieur.
• Preuve par échange (cut property) : toute arête légère coupant un ensemble est sûre.

Kruskal est aussi un greedy (tri par poids, union-find) — cf. chapitre 08.

---

Partie IX — Matroïdes : la théorie de l'optimalité greedy

9.1 Définition

Un matroïde (E, I) est un ensemble d'éléments E avec une famille d'ensembles indépendants I telle que :

1. Non-vacuité : ∅ ∈ I.
2. Hérédité : si A ∈ I, alors tout sous-ensemble de A est dans I.
3. Échange (Augmentation) : si A, B ∈ I et |A| < |B|, alors il existe x ∈ B \ A tel que A ∪ {x} ∈ I.

9.2 Théorème fondamental

Si (E, I) est un matroïde et chaque élément a un poids, alors le greedy par poids décroissant (ou croissant) trouve un ensemble indépendant de poids optimal — maximal pour l'inclusion.

9.3 Exemples de matroïdes

9.4 Pourquoi c'est utile

Si votre problème a la structure d'un matroïde → le greedy est prouvé optimal sans effort de preuve ad hoc. Si la structure n'est pas un matroïde → le greedy peut échouer, il faut le prouver autrement ou utiliser la DP.

---

Partie X — Quand le greedy échoue

10.1 Contre-exemples classiques

10.2 Greedy vs DP : table de décision

Règle : si la propriété du choix glouton est vraie → greedy. Sinon, si les sous-problèmes se recouvrent → DP. Sinon → backtracking.

---

Partie XI — Récapitulatif des complexités

---

Check-list de maîtrise

• Je sais expliquer la propriété du choix glouton.
• Je sais prouver par échange (activity selection).
• Je sais prouver par greedy stays ahead.
• Je connais les 6 problèmes classiques par cœur.
• Je sais justifier pourquoi le knapsack 0/1 n'est pas greedy.
• Je sais reconnaître un matroïde et appliquer le théorème.
• Je sais construire un contre-exemple pour invalider un greedy.