Les algorithmes gloutons

1. Problèmes d'optimisation et idée gloutonne

Un problème d'optimisation consiste à trouver, parmi un ensemble (souvent énorme) de solutions possibles, une solution qui maximise ou minimise une certaine quantité, appelée fonction objectif. Exemples : rendre une somme avec le moins de pièces possible, remplir un sac pour maximiser la valeur transportée, coder un texte avec le moins de bits possible.

Explorer toutes les solutions (force brute) est en général trop coûteux : le nombre de combinaisons explose exponentiellement. On cherche donc des méthodes plus malines. L'approche gloutonne (en anglais greedy, « gourmande ») est l'une des plus simples :

L'algorithme est donc rapide et facile à écrire. Sa faiblesse est dans le mot « localement » : un enchaînement de choix optimaux sur le moment ne donne pas forcément la meilleure solution globale. Tout l'enjeu du chapitre est de distinguer les cas où le glouton est correct de ceux où il échoue.

2. Structure d'un algorithme glouton

Un algorithme glouton suit toujours le même schéma : tant que la solution n'est pas complète, choisir le « meilleur » candidat restant et l'ajouter s'il est compatible.

# Schéma général d'un algorithme glouton
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

Pour qu'un tel algorithme produise une solution optimale, le problème doit posséder deux propriétés.

La sous-structure optimale est aussi le fondement de la programmation dynamique (chapitre suivant). La différence : le glouton fait un seul choix — celui qui paraît le meilleur — et ne le remet jamais en cause ; la programmation dynamique examine plusieurs choix et garde le meilleur. Le glouton est donc plus rapide, mais correct seulement lorsque la propriété du choix glouton est vérifiée.

3. Le rendu de monnaie

Problème. On dispose d'un système de pièces (par exemple 1, 2, 5, 10, 20, 50 centimes…) en quantité illimitée. Pour rendre une somme S, on veut utiliser le nombre minimal de pièces.

Stratégie gloutonne. À chaque étape, prendre la plus grande pièce qui ne dépasse pas la somme restante, puis recommencer.

def rendu_monnaie(systeme, S):
    # systeme : pièces triées par ordre décroissant
    rendu = []
    for piece in systeme:
        while S >= piece:
            rendu.append(piece)
            S = S - piece
    return rendu

Pour rendre 68 centimes avec (50, 20, 10, 5, 2, 1) : on prend 50, puis 10, puis 5, puis 2, puis 1, soit 5 pièces : 50 + 10 + 5 + 2 + 1 = 68. C'est bien optimal.

Conclusion : le rendu de monnaie illustre parfaitement la nuance du chapitre. Le même algorithme glouton est optimal pour certains systèmes et sous-optimal pour d'autres. Pour un système quelconque, il faut la programmation dynamique pour garantir l'optimum.

4. Le problème du sac à dos

Problème. On dispose d'objets, chacun ayant un poids p_i et une valeur v_i, et d'un sac de capacité maximale C. On veut emporter un ensemble d'objets de valeur totale maximale sans dépasser C.

Il existe deux versions, et c'est précisément là que se joue la différence.

4.1 — Sac à dos fractionnaire

On peut prendre des fractions d'objet (par exemple de la poudre d'or, du sable, un liquide). La stratégie gloutonne est : trier les objets par valeur par unité de poids (v_i / p_i) décroissante, puis remplir le sac en prenant d'abord les objets les plus « rentables », et terminer en prenant une fraction du dernier objet pour combler exactement la capacité.

def sac_fractionnaire(objets, C):
    # objets : liste de (valeur, poids)
    objets = sorted(objets, key=lambda o: o[0] / o[1], reverse=True)
    valeur = 0.0
    for v, p in objets:
        if C >= p:                 # on prend l'objet entier
            valeur += v; C -= p
        else:                       # on prend une fraction et on s'arrête
            valeur += v * (C / p); C = 0
            break
    return valeur

4.2 — Sac à dos 0/1

Cette fois, chaque objet est indivisible : on le prend en entier (1) ou pas du tout (0). Le même glouton « le plus rentable d'abord » n'est plus optimal.

Le sac à dos 0/1 ne vérifie pas la propriété du choix glouton : il faut la programmation dynamique (chapitre suivant) pour le résoudre exactement. C'est l'exemple canonique d'un problème où « gourmand » ne rime pas avec « optimal ».

5. L'arbre de Huffman (codage optimal)

Problème. On veut compresser un texte. Plutôt que de coder chaque caractère sur le même nombre de bits (codage à longueur fixe), on donne des codes courts aux caractères fréquents et des codes longs aux caractères rares. Pour pouvoir décoder sans ambiguïté, aucun code ne doit être le préfixe d'un autre : c'est un code préfixe, représenté par un arbre binaire dont les feuilles sont les caractères (gauche = 0, droite = 1).

Algorithme de Huffman (glouton). On part d'une forêt où chaque caractère est un arbre isolé, pondéré par sa fréquence. Tant qu'il reste plus d'un arbre :

1. choisir les deux arbres de plus petite fréquence (le choix glouton) ;
2. les fusionner sous une nouvelle racine, de fréquence égale à la somme des deux ;
3. replacer ce nouvel arbre dans la forêt.

Le dernier arbre restant est l'arbre de Huffman. On lit le code de chaque caractère en descendant de la racine jusqu'à sa feuille.

import heapq

def huffman(freq):
    # freq : dict {caractère: fréquence}
    tas = [[f, c, None, None] for c, f in freq.items()]
    heapq.heapify(tas)
    while len(tas) > 1:
        g = heapq.heappop(tas)          # plus petite fréquence
        d = heapq.heappop(tas)          # deuxième plus petite
        heapq.heappush(tas, [g[0] + d[0], None, g, d])
    return tas[0]          # racine de l'arbre de Huffman

Exemple. Fréquences A:5, B:2, C:1, D:1. On fusionne d'abord C et D (1 + 1 = 2), puis ce nœud avec B (2 + 2 = 4), puis avec A (4 + 5 = 9). On obtient les codes A:0, B:11, C:100, D:101 — les caractères fréquents (A) sont sur 1 bit, les rares (C, D) sur 3 bits.

6. Quand le glouton fonctionne-t-il ? — récapitulatif

CPGE MP/PSI — Informatique · Chapitre : Les algorithmes gloutons · Conforme au programme officiel 2023