Algorithmes gloutons

Introduction

Quand on cherche à résoudre un problème d'optimisation — minimiser un coût, maximiser un gain — la stratégie la plus naïve consiste à se demander, à chaque étape : « quel est le meilleur choix maintenant ? » Puis à prendre ce choix sans plus se poser de questions. C'est ce qu'on appelle une stratégie gloutonne (en anglais greedy). Elle est rapide et intuitive. Elle marche parfois — c'est même la solution parfaite pour le rendu de monnaie classique. Mais elle peut aussi mener à des résultats sous-optimaux. Savoir reconnaître quand elle marche est une compétence en soi. [PH02]

Le cœur du concept

Un algorithme glouton :

1. Construit la solution pas à pas.
2. À chaque étape, fait le choix qui semble le meilleur localement, sans se soucier des conséquences sur la suite.
3. Ne revient jamais en arrière sur un choix fait.

Exemple canonique — le rendu de monnaie

Problème : rendre une somme $S$ avec le minimum de pièces, parmi des pièces de valeurs données (par exemple 1, 2, 5, 10, 20, 50 centimes, 1 et 2 euros — le système euro).

Stratégie gloutonne : à chaque étape, prendre la plus grosse pièce possible qui ne dépasse pas ce qui reste à rendre.

def rendu_monnaie(somme, pieces):
    """Rend la somme avec la stratégie gloutonne, sur les pieces triées
    par ordre décroissant. Retourne la liste des pièces utilisées."""
    rendu = []
    for piece in pieces:
        while somme >= piece:
            rendu.append(piece)
            somme -= piece
    return rendu

euros = [200, 100, 50, 20, 10, 5, 2, 1]   # en centimes
print(rendu_monnaie(287, euros))
# [200, 50, 20, 10, 5, 2]   — 6 pièces, c'est optimal

Avec le système euro, la stratégie gloutonne donne toujours le rendu optimal. C'est une propriété du système monétaire — pas une vérité universelle.

Le glouton ne marche pas toujours

Imaginons un système de pièces fictif : 1, 6, 10. On veut rendre 12.

• Glouton : prend 10, puis 1, puis 1 → 3 pièces (10 + 1 + 1).
• Optimal : 6 + 6 → 2 pièces.

La stratégie gloutonne, ici, rate la solution optimale. Le choix local « prendre 10 d'abord » empêche d'utiliser deux fois 6 ensuite.

Second exemple — le sac à dos fractionnaire

Problème : vous avez un sac d'une capacité maximale $W$ kg. Vous disposez d'objets, chacun avec un poids et une valeur. On peut fractionner les objets (en prendre une partie). Comment maximiser la valeur totale dans le sac ?

Stratégie gloutonne : trier les objets par ratio valeur / poids décroissant, puis remplir le sac en commençant par les objets les plus « rentables au kilo ».

On effectue le tri via sorted(..., key=...) : key est une fonction qui dit, pour chaque objet, quelle valeur utiliser pour comparer. Ici lambda o: o[2] / o[1] est une mini-fonction qui prend un objet o (un triplet (nom, poids, valeur)) et renvoie son ratio valeur/poids (o[2] / o[1]). On le verra plus en détail au chapitre PG ; ici, lisez juste « trier par ratio décroissant ».

def sac_a_dos(objets, capacite):
    """objets : liste de tuples (nom, poids, valeur).
    Stratégie gloutonne sur le ratio valeur / poids."""
    # Trier par ratio décroissant
    tries = sorted(objets, key=lambda o: o[2] / o[1], reverse=True)
    sac = []
    valeur_totale = 0
    poids_restant = capacite
    for nom, poids, valeur in tries:
        if poids_restant >= poids:
            # On prend l'objet entier
            sac.append((nom, poids))
            valeur_totale += valeur
            poids_restant -= poids
        else:
            # On prend une fraction
            fraction = poids_restant / poids
            sac.append((nom, poids * fraction))
            valeur_totale += valeur * fraction
            poids_restant = 0
            break
    return sac, valeur_totale

objets = [
    ("or",     2, 60),
    ("argent", 5, 50),
    ("cuivre", 10, 30),
]
print(sac_a_dos(objets, 7))
# (..., 95.0)   — on prend tout l'or (2 kg, 60) + tout l'argent (5 kg, 50)

Dans la version fractionnaire du sac à dos, le glouton est optimal. Dans la version où il faut prendre les objets entiers (sac à dos 0/1), il ne l'est plus toujours — ce dernier problème est étudié plus tard avec des techniques plus puissantes (programmation dynamique en Terminale).

Quand essayer un glouton ?

Caractéristiques typiques d'un problème où un glouton mérite d'être testé :

• une fonction de gain ou de coût clairement définie à chaque étape ;
• des choix indépendants ou faiblement dépendants entre eux ;
• un critère local « évident » (le plus gros, le plus rentable, le plus proche, etc.).

Quand le glouton ne marche pas, on se tourne vers d'autres stratégies : programmation dynamique, backtracking (retour sur trace), branch-and-bound. Ces techniques arrivent en Terminale.

Pièges courants

• Croire qu'un glouton est toujours optimal. Toujours vérifier sur des exemples, ou démontrer la propriété de choix glouton.
• Oublier de trier au préalable : pour le sac à dos fractionnaire, c'est le tri qui rend le glouton optimal.
• Confondre rapidité et optimalité : le glouton est rapide (typiquement $\mathcal{O}(n \log n)$ avec un tri préalable), mais rapidité ≠ qualité de la solution.

Pour aller plus loin

Le rendu de monnaie sur n'importe quel système de pièces, en cherchant vraiment l'optimal, exige une stratégie plus puissante : la programmation dynamique. C'est l'un des grands sujets du programme de Terminale. Pour l'instant, retenez le glouton comme un premier réflexe — souvent bon, parfois pas, à vérifier au cas par cas.