Les algorithmes gloutons

Cours complet · NSI (terminale), chapitre 8 · terminale, spécialité numérique et sciences informatiques

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Face à un problème d'optimisation, on cherche souvent la meilleure solution parmi un très grand nombre de possibilités. Explorer toutes les combinaisons est généralement trop coûteux. Les algorithmes gloutons (en anglais greedy algorithms) proposent une stratégie simple et rapide : à chaque étape, on effectue le choix qui paraît le meilleur sur le moment, sans jamais remettre en cause les décisions déjà prises.

Cette approche est séduisante par sa simplicité, mais elle ne fournit pas toujours la solution optimale. L'enjeu de ce chapitre est double : comprendre comment construire un algorithme glouton, et surtout savoir reconnaître les situations où il est garanti de donner la meilleure réponse, par opposition à celles où il échoue. Nous étudierons le rendu de monnaie, le sac à dos fractionnaire et l'ordonnancement de tâches, avant de comparer cette méthode à la programmation dynamique.

8.1 Principe d'un algorithme glouton

Définition 8.1Algorithme glouton

Un algorithme glouton construit une solution étape par étape. À chaque étape, il sélectionne, parmi les choix possibles, celui qui optimise un critère local immédiat (le choix glouton), puis il poursuit avec le sous-problème restant. Une fois un choix effectué, il n'est jamais reconsidéré.

L'idée centrale est donc le choix localement optimal : on espère qu'en empilant des décisions individuellement bonnes, on obtiendra une solution globalement bonne.

Définition 8.2Problème d'optimisation

Un problème d'optimisation consiste à trouver, parmi un ensemble de solutions dites réalisables (respectant des contraintes), une solution qui maximise ou minimise une grandeur appelée fonction objectif.

Méthode : Concevoir un algorithme glouton

Pour construire un algorithme glouton, on identifie :

l'ensemble des candidats parmi lesquels choisir ;
un critère de sélection (le choix glouton) qui désigne le « meilleur » candidat à chaque étape ;
un test de faisabilité qui vérifie que l'on peut ajouter ce candidat à la solution partielle ;
un test d'arrêt indiquant que la solution est complète.

Très souvent, le critère de sélection se traduit par un tri préalable des candidats.

Proposition 8.3Avantages et limites

Les algorithmes gloutons sont en général simples à programmer et rapides, car ils n'explorent pas l'arbre complet des possibilités. En contrepartie, ils ne garantissent pas toujours l'optimalité : un bon choix local peut conduire à une impasse globale. Il faut donc, au cas par cas, prouver que la stratégie gloutonne est correcte, ou bien accepter qu'elle ne fournisse qu'une solution approchée.

Exemple 8.4Une journée optimisée... ou pas

Imaginons que l'on veuille visiter le maximum de musées dans une ville en une journée. Une stratégie gloutonne pourrait être : « aller toujours au musée le plus proche non encore visité ». Ce choix local est raisonnable, mais il peut nous entraîner dans un quartier isolé et nous faire perdre du temps ensuite. C'est l'illustration typique d'un glouton qui ne garantit pas l'optimum.

8.2 Le rendu de monnaie

Le problème du rendu de monnaie est l'exemple historique des algorithmes gloutons. Un commerçant doit rendre une somme donnée en utilisant le moins de pièces possible.

Définition 8.5Problème du rendu de monnaie

Étant donné un système de pièces (un ensemble de valeurs) et une somme $S$ à rendre, on cherche à exprimer $S$ comme une somme de pièces du système, en minimisant le nombre total de pièces utilisées.

Méthode : Stratégie gloutonne du rendu de monnaie

À chaque étape, on choisit la plus grande pièce dont la valeur ne dépasse pas la somme restante à rendre. On retire cette valeur de la somme restante et on recommence, jusqu'à atteindre $0$ .

Exemple 8.6Rendre 67 centimes

Avec le système européen ${1, 2, 5, 10, 20, 50}$ , pour rendre $67$ centimes :

on prend $50$ (reste $17$ ) ;
on prend $10$ (reste $7$ ) ;
on prend $5$ (reste $2$ ) ;
on prend $2$ (reste $0$ ).

Soit $4$ pièces : $50 + 10 + 5 + 2 = 67$ . C'est bien le nombre minimal.

Voici l'implémentation Python correspondante.


def rendu_monnaie(systeme, somme):
    """Rend la somme avec le moins de pieces possible (approche gloutonne).
    systeme : liste des valeurs de pieces, triee par ordre decroissant."""
    pieces = []
    for valeur in systeme:
        while somme >= valeur:
            somme -= valeur
            pieces.append(valeur)
    return pieces

systeme = [50, 20, 10, 5, 2, 1]
print(rendu_monnaie(systeme, 67))   # [50, 10, 5, 2]

Proposition 8.7Complexité du rendu glouton

Si le système comporte $p$ valeurs de pièces et que la plus petite pièce vaut $1$ , le rendu glouton s'effectue en $O (p + n)$ où $n$ est le nombre de pièces rendues. Avec une variante utilisant la division entière (quotient et reste), on atteint $O (p)$ .


def rendu_monnaie_rapide(systeme, somme):
    """Version utilisant la division entiere : O(p)."""
    resultat = {}
    for valeur in systeme:
        nb = somme // valeur
        if nb > 0:
            resultat[valeur] = nb
            somme -= nb * valeur
    return resultat

print(rendu_monnaie_rapide([50, 20, 10, 5, 2, 1], 67))
# {50: 1, 10: 1, 5: 1, 2: 1}

Proposition 8.8Quand le glouton est-il optimal ?

Pour le rendu de monnaie, l'algorithme glouton fournit toujours la solution optimale lorsque le système de pièces est canonique. Les systèmes monétaires usuels (euros, dollars) sont canoniques. En revanche, pour certains systèmes, le glouton échoue.

Exemple 8.9Un système où le glouton échoue

Considérons le système ${1, 3, 4}$ et la somme $S = 6$ .

Le glouton prend $4$ (reste $2$ ), puis $1$ et $1$ : soit $3$ pièces ( $4 + 1 + 1$ ).
La solution optimale est $3 + 3$ : seulement $2$ pièces.

Le choix localement optimal (la plus grande pièce) conduit ici à une solution non optimale. Pour ce type de système, il faut recourir à la programmation dynamique.

8.3 Le problème du sac à dos

Définition 8.10Problème du sac à dos

On dispose d'un sac de capacité maximale $W$ et d'un ensemble d'objets, chacun caractérisé par un poids $w_{i}$ et une valeur $v_{i}$ . On cherche à remplir le sac de manière à maximiser la valeur totale transportée, sans dépasser la capacité $W$ .

Il existe deux variantes essentielles à bien distinguer.

Définition 8.11Sac à dos entier et sac à dos fractionnaire

Dans le sac à dos entier (0/1 knapsack), chaque objet est pris en entier ou pas du tout.
Dans le sac à dos fractionnaire, on peut prendre une fraction d'un objet (par exemple une portion d'un sac de farine), sa valeur étant alors proportionnelle à la fraction prise.

Proposition 8.12Glouton et sac à dos

La version fractionnaire se résout de façon optimale par un algorithme glouton. En revanche, la version entière ne peut pas, en général, être résolue optimalement par un glouton : elle relève de la programmation dynamique.

Méthode : Glouton pour le sac à dos fractionnaire

Pour maximiser la valeur :

Calculer pour chaque objet son rapport valeur/poids (sa « densité » de valeur).
Trier les objets par rapport décroissant.
Remplir le sac en prenant les objets dans cet ordre. Pour le dernier objet qui ne tient pas en entier, en prendre la fraction qui complète exactement la capacité.

Exemple 8.13Remplir le sac fractionnaire

Capacité $W = 50$ . Objets (poids, valeur) : $A = (10, 60)$ , $B = (20, 100)$ , $C = (30, 120)$ . Rapports : $A : 6$ , $B : 5$ , $C : 4$ .

On prend $A$ en entier (poids $10$ , valeur $60$ , reste $40$ ).
On prend $B$ en entier (poids $20$ , valeur $100$ , reste $20$ ).
On prend $\frac{20}{30}$ de $C$ : valeur $\frac{2}{3} \times 120 = 80$ .

Valeur totale : $60 + 100 + 80 = 240$ . C'est l'optimum.


def sac_a_dos_fractionnaire(objets, capacite):
    """objets : liste de tuples (poids, valeur).
    Retourne la valeur maximale transportable."""
    # Tri par rapport valeur/poids decroissant
    objets = sorted(objets, key=lambda o: o[1] / o[0], reverse=True)
    valeur_totale = 0.0
    reste = capacite
    for poids, valeur in objets:
        if reste <= 0:
            break
        if poids <= reste:
            reste -= poids
            valeur_totale += valeur
        else:
            fraction = reste / poids
            valeur_totale += valeur * fraction
            reste = 0
    return valeur_totale

objets = [(10, 60), (20, 100), (30, 120)]
print(sac_a_dos_fractionnaire(objets, 50))   # 240.0

Proposition 8.14Complexité

L'algorithme est dominé par le tri des objets selon leur rapport valeur/poids : sa complexité est $O (n lo g n)$ pour $n$ objets, le parcours de remplissage étant en $O (n)$ .

8.4 L'ordonnancement de tâches

Un autre domaine d'application classique des gloutons est la planification de tâches, par exemple la sélection d'un maximum d'activités compatibles.

Définition 8.15Sélection d'activités

On dispose de $n$ activités, chacune définie par une heure de début et une heure de fin. Deux activités sont compatibles si elles ne se chevauchent pas dans le temps. On cherche à sélectionner le plus grand nombre d'activités deux à deux compatibles.

Méthode : Glouton de l'ordonnancement

La stratégie optimale consiste à trier les activités par heure de fin croissante, puis à les parcourir dans cet ordre : on sélectionne une activité si son heure de début est postérieure (ou égale) à l'heure de fin de la dernière activité retenue. Choisir l'activité qui se termine le plus tôt laisse en effet le maximum de temps disponible pour les suivantes.

Exemple 8.16Choisir ses activités

Activités (début, fin) : $(1, 4)$ , $(3, 5)$ , $(0, 6)$ , $(5, 7)$ , $(8, 9)$ , $(5, 9)$ . Triées par fin : $(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)$ .

On prend $(1, 4)$ (fin $= 4$ ).
$(3, 5)$ commence avant $4$ : rejetée. $(0, 6)$ : rejetée.
$(5, 7)$ : $5 \geq 4$ , prise (fin $= 7$ ).
$(8, 9)$ : $8 \geq 7$ , prise.

On retient $3$ activités : $(1, 4), (5, 7), (8, 9)$ . C'est le maximum.


def selection_activites(activites):
    """activites : liste de tuples (debut, fin).
    Retourne la liste maximale d'activites compatibles."""
    activites = sorted(activites, key=lambda a: a[1])  # tri par fin
    selection = []
    fin_courante = float("-inf")
    for debut, fin in activites:
        if debut >= fin_courante:
            selection.append((debut, fin))
            fin_courante = fin
    return selection

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(selection_activites(acts))   # [(1, 4), (5, 7), (8, 9)]

Proposition 8.17Optimalité et complexité

Le critère « plus petite heure de fin » garantit ici l'optimalité : on peut prouver par échange (argument d'échange) que toute solution optimale peut être transformée en celle du glouton sans réduire le nombre d'activités. La complexité est $O (n lo g n)$ , dominée par le tri.

8.5 Comparaison avec la programmation dynamique

Lorsque le choix glouton ne garantit pas l'optimum, on recourt souvent à la programmation dynamique, étudiée dans un autre chapitre.

Définition 8.18Programmation dynamique

La programmation dynamique résout un problème en le décomposant en sous-problèmes qui se recouvrent, en mémorisant les résultats de ces sous-problèmes pour les réutiliser. Contrairement au glouton, elle explore plusieurs combinaisons et garantit l'optimum dès lors que le problème possède la propriété de sous-structure optimale.

Proposition 8.19Glouton vs programmation dynamique

Le glouton fait un unique choix à chaque étape (jamais reconsidéré) : il est rapide ( $O (n)$ ou $O (n lo g n)$ ) mais correct seulement si le problème a la propriété du choix glouton.
La programmation dynamique examine plusieurs choix et combine les solutions des sous-problèmes : elle est plus coûteuse (souvent $O (n \times W)$ pour le sac à dos) mais garantit l'optimum sur une classe plus large de problèmes.

En résumé : « tout problème résoluble par un glouton est résoluble par la programmation dynamique, mais l'inverse est faux ».

Exemple 8.20Sac à dos entier : le glouton échoue

Capacité $W = 50$ , objets $A = (10, 60)$ , $B = (20, 100)$ , $C = (30, 120)$ indivisibles.

Le glouton (par rapport décroissant) prend $A$ puis $B$ : valeur $160$ , poids $30$ , et $C$ ne tient plus.
L'optimum est $B + C$ : valeur $220$ , poids $50$ .

Le glouton donne $160$ au lieu de $220$ : seule la programmation dynamique retrouve ici l'optimum.

Continuer sur Adloun : animation, QCM, fiches, exercices