Algorithmes gloutons : le meilleur choix immédiat

Un algorithme glouton construit une solution étape par étape. À chaque étape, il fait le choix qui paraît le meilleur sur le moment, et il ne revient jamais sur ce choix.

Le modèle de rendu de monnaie. Les montants sont entiers dans une unité fixée, les valeurs des pièces sont strictement positives, triées par ordre décroissant, et chaque valeur est disponible en quantité illimitée. Un commerçant doit rendre une somme avec le moins de pièces possible. Stratégie gloutonne : donner à chaque fois la plus grande pièce qui ne dépasse pas ce qu'il reste à rendre.

def rendu(somme, pieces):
    rendues = []
    for p in pieces:
        while somme >= p:
            somme = somme - p
            rendues.append(p)
    return rendues

print(rendu(87, [50, 20, 10, 5, 2, 1]))

[50, 20, 10, 5, 2]

Les pièces sont parcourues de la plus grande à la plus petite ; pour chacune, on la donne tant qu'elle « rentre » dans la somme restante. Pour 87, on rend 50 + 20 + 10 + 5 + 2 : cinq pièces.

Avantage. Un algorithme glouton peut être simple et peu coûteux ; son coût précis reste à analyser pour le problème choisi : il ne compare pas toutes les solutions possibles, il en construit une seule.

Limite. Le choix le meilleur sur le moment n'est pas toujours le meilleur au total. Avec des pièces de 4, 3 et 1, rendons 6 :

def rendu(somme, pieces):
    rendues = []
    for p in pieces:
        while somme >= p:
            somme = somme - p
            rendues.append(p)
    return rendues

print(rendu(6, [4, 3, 1]))

[4, 1, 1]

Le glouton rend trois pièces, alors que 3 + 3 n'en utilise que deux. En choisissant la pièce de 4, il s'est interdit la meilleure solution.

Pour le système européen de pièces de valeurs 200, 100, 50, 20, 10, 5, 2 et 1 centimes, avec les réserves illimitées du modèle, le glouton donne un nombre minimal de pièces (on dit que ce système est canonique) ; ce n'est pas vrai de tout système de pièces.

Le sac à dos. On veut remplir un sac de capacité limitée avec des objets indivisibles de masse et de valeur données, pour une valeur totale maximale. Une stratégie gloutonne prend les objets par ordre décroissant de valeur par kilogramme, tant qu'ils rentrent. Elle donne souvent une bonne solution, mais pas toujours la meilleure.

Énoncé. Avec des pièces de 10, 7 et 1, on rend 15. Le glouton est-il optimal ?

1. Glouton. 10 rentre dans 15 : il reste 5. 7 ne rentre pas. 1 cinq fois. Total : 10 + 1 + 1 + 1 + 1 + 1, soit 6 pièces.
2. Recherche d'une meilleure solution. Sans la pièce de 10 : 7 + 7 + 1 = 15, soit 3 pièces.
3. Conclusion. Le glouton n'est pas optimal pour cette somme avec ce système.

Avec le même système, pour rendre 12, le glouton donne 10 + 1 + 1 (3 pièces) ; 7 + 1 × 5 en demande 6 : ici le glouton est optimal. L'optimalité dépend du système ET de la somme.