Algorithmes gloutons
Cours · informatique (tronc commun des prépas scientifiques), chapitre 7 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
7.1 Introduction et motivation
Le chapitre 6 s'est achevé sur un mur : énumérer toutes les solutions coûte ou , hors de portée dès que dépasse quelques dizaines. Comment choisir, alors, parmi un nombre astronomique de possibilités ? La stratégie la plus simple porte un nom gourmand : l'algorithme glouton (greedy) construit sa solution pas à pas en faisant, à chaque étape, le choix qui paraît localement le meilleur — la plus grosse pièce, l'activité qui finit le plus tôt — sans jamais revenir en arrière.
Cette stratégie a deux visages, et le chapitre les montre tous deux. Sur certains problèmes — la sélection d'activités, l'allocation de salles, le rendu de monnaie en euros — le glouton est non seulement rapide mais exactement optimal, et l'on saura le prouver : c'est l'argument d'échange, le troisième grand schéma de preuve du semestre après l'invariant et la récurrence. Sur d'autres — le rendu de monnaie dans un mauvais système, le sac à dos — le glouton se trompe, et il faut savoir exhiber le contre-exemple. La compétence visée n'est donc pas « appliquer le glouton », mais bien : proposer un critère glouton, et trancher, preuve ou contre-exemple à l'appui, s'il est correct.
7.2 Le principe glouton
Un algorithme glouton construit une solution par une suite de choix tels que :
- chaque choix est fait selon un critère local (le meilleur candidat du moment, pour un certain ordre) ;
- chaque choix est irrévocable : jamais l'algorithme ne revient sur une décision prise.
La structure typique : trier les candidats selon le critère, puis les examiner dans cet ordre en prenant chacun s'il est compatible avec les choix déjà faits.
Le glouton est rapide par construction : un tri (, chapitre 9) suivi d'un parcours (). Toute la question est ailleurs : la suite de choix localement bons est-elle globalement optimale ? En général, non — gravir la pente la plus raide ne mène pas au plus haut sommet. Mais sur des problèmes bien structurés, oui, et c'est démontrable.
7.3 Le rendu de monnaie
7.3.1 L'algorithme
Rendre euros avec le moins de pièces et billets possible : tout le monde fait pareil — un billet de , une pièce de , deux de . C'est le glouton : à chaque étape, la plus grande valeur qui ne dépasse pas le restant. En centimes, avec le système euro (on s'arrête au billet de 5 pour l'exemple) :
def rendu_monnaie(montant: int, systeme: list) -> list:
"""Renvoie la liste des valeurs rendues (avec répétitions).
Préconditions : montant >= 0, systeme trié décroissant et contenant 1."""
rendu = []
for piece in systeme:
# Invariant : montant = montant initial - somme des pièces de rendu,
# et aucune pièce > piece ne peut plus servir
while montant >= piece:
rendu.append(piece)
montant -= piece
return rendu
assert rendu_monnaie(640, [500, 200, 100, 50, 20, 10, 5, 2, 1]) \
== [500, 100, 20, 20]
assert rendu_monnaie(0, [500, 200, 100, 50, 20, 10, 5, 2, 1]) == []Terminaison : à chaque tour de la boucle interne, montant décroît strictement (variant) ; la précondition « le système contient » garantit qu'on atteint toujours — sans elle, rendu_monnaie(3, [2]) laisserait un reste. Coût : pour valeurs et pièces rendues.
