Algorithmes gloutons

En clair. Choix locaux optimaux

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Algorithmes gloutons », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

Introduction

Un algorithme glouton (greedy) construit une solution pas à pas : à chaque étape il retient le choix qui paraît le meilleur localement, sans jamais revenir en arrière. Simple et rapide, il ne garantit l'optimum global que sous certaines conditions.

1. Principe et structure

Schéma général :

def glouton(candidats):
    solution = []
    for c in trier(candidats):      # tri selon un critère de "meilleur choix"
        if realisable(solution, c):
            solution.append(c)
    return solution

Trois ingrédients : un critère de sélection, un test de faisabilité, une condition d'arrêt. Le coût est souvent dominé par le tri : $O(n \log n)$.

2. Exemple 1 : rendu de monnaie

Rendre 67 € avec le système européen [50, 20, 10, 5, 2, 1] :

def rendu(montant, pieces):
    res = []
    for p in sorted(pieces, reverse=True):
        while montant >= p:
            montant -= p
            res.append(p)
    return res

rendu(67, [50,20,10,5,2,1]) → [50, 10, 5, 2], soit 4 pièces : c'est l'optimum. Mais avec le système fictif [1, 3, 4] et un montant de 6, le glouton donne 4 + 1 + 1 (3 pièces) alors que l'optimum est 3 + 3 (2 pièces). Le système européen est canonique, pas tous les systèmes.

3. Exemple 2 : sélection d'activités

On dispose de réunions $(début, fin)$ et d'une seule salle. Le critère gagnant est de trier par fin croissante :

def selection(activites):
    activites = sorted(activites, key=lambda a: a[1])
    retenues, fin_courante = [], 0
    for debut, fin in activites:
        if debut >= fin_courante:
            retenues.append((debut, fin))
            fin_courante = fin
    return retenues

Avec [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)], on retient (1,4), (5,7), (8,9) : 3 activités, c'est l'optimum prouvé. Trier par durée ou par début ne donnerait pas le maximum.

4. Exemple 3 : sac à dos

Contre-exemple entier : capacité 10, objets A(poids 6, valeur 7 → ratio 1,17), B(5, 5), C(5, 5). Le glouton prend A puis rien (place restante 4) → valeur 7 ; l'optimum est B + C → 10.

5. Comparaison avec les autres méthodes

Le glouton est donc l'outil du compromis : très rapide, il sert d'heuristique quand l'optimum exact coûte trop cher (routage, ordonnancement, compression de Huffman — qui, elle, est bien optimale).

Erreurs fréquentes

• Affirmer qu'un glouton est toujours optimal : il faut le prouver (ou fournir un contre-exemple).
• Oublier le tri initial, qui conditionne tout le résultat.
• Choisir le mauvais critère (durée au lieu de fin de créneau).
• Confondre glouton et programmation dynamique : le glouton ne mémorise pas de sous-solutions.

À retenir

Un glouton = tri + choix local irrévocable. Optimal pour la sélection d'activités, le sac à dos fractionnaire et Huffman ; approché pour le sac à dos entier et les systèmes de monnaie non canoniques.

Quiz de révision

Question 1

Pour la sélection d'activités, quel critère de tri garantit l'optimum ?

• A. durée croissante
• B. heure de début croissante
• C. heure de fin croissante
• D. ordre aléatoire

Question 2

La complexité dominante d'un algorithme glouton avec tri préalable est :

• A. $O(1)$
• B. $O(n)$
• C. $O(n \log n)$
• D. $O(2^n)$

Question 3

Le glouton est optimal pour :

• A. le sac à dos en nombres entiers
• B. le sac à dos fractionnaire
• C. tous les systèmes de monnaie
• D. le problème du voyageur de commerce

Corrigé détaillé

Correction question 1

Réponse : C — Terminer au plus tôt laisse le maximum de temps disponible pour la suite.

Correction question 2

Réponse : C — Le parcours est linéaire, mais le tri coûte $O(n \log n)$.

Correction question 3

Réponse : B — On peut fractionner le dernier objet, ce qui rend le choix par ratio optimal.