Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algorithmes gloutons

Déjà plus de

1 million

d'inscrits !

Introduction :

Les méthodes algorithmiques peuvent être regroupées en familles, parmi lesquelles figure celle des algorithmes dits gloutons.

Nous allons dans un premier temps, définir ce qui caractérise un algorithme glouton, puis nous implémenterons plusieurs algorithmes gloutons pour résoudre différents problèmes d’optimisation.

Caractéristiques des algorithmes gloutons

Les algorithmes gloutons sont des algorithmes assez simples dans leur logique. Ainsi que leur nom le suggère, ils sont conçus pour prendre le maximum de ce qui est disponible à un moment donné.

Exemple introductif

Nous cherchons à écrire le plus grand nombre possible à partir d’un ensemble donné de chiffres. Chaque chiffre ne peut être utilisé qu’une seule fois.

L’ensemble de chiffres dont nous disposons est 22, 99, 77, 44, 88, 11. Nous parvenons rapidement à composer le nombre 987421987421.

Ce nombre est effectivement le plus grand nombre possible. Pour le former à partir de l’ensemble de chiffres dont nous disposions, nous avons d’abord cherché le plus grand chiffre disponible, qui était le 99.

Une fois le 99 utilisé pour composer le premier chiffre du nombre, nous avons cherché parmi les chiffres restant le plus grand chiffre possible, qui était le 88. Ensuite, le plus grand chiffre restant était le 77, que nous avons utilisé à son tour, et ainsi de suite jusqu’à épuisement des chiffres disponibles.

  • Nous avons appliqué un algorithme glouton pour former ce nombre.

Principe général

L’algorithme glouton choisit la solution optimale qui se présente à lui à chaque instant, sans se préoccuper, ni du passé ni de l’avenir. Il répète cette même stratégie à chaque étape jusqu’à avoir entièrement résolu le problème.

bannière definition

Définition

Algorithme glouton :

Un algorithme glouton est un algorithme qui effectue à chaque instant, le meilleur choix possible sur le moment, sans retour en arrière ni anticipation des étapes suivantes, dans l’objectif d’atteindre au final un résultat optimal.

bannière astuce

Astuce

Les algorithmes gloutons sont parfois appelés algorithmes gourmands ou encore algorithmes voraces.

La répétition de cette stratégie très simple, permet de résoudre rapidement et de manière souvent satisfaisante des problèmes d’optimisation sans avoir à tester systématiquement toutes les possibilités.

  • Cependant un algorithme glouton ne fournit pas toujours le meilleur résultat possible.

Relativité de l’optimisation

bannière à retenir

À retenir

La solution obtenue par un algorithme glouton est le résultat d’une suite de choix gloutons, sans prise en compte des choix passés, ni anticipation de choix futurs.

  • L’optimisation est donc potentiellement moindre qu’un algorithme effectuant une exploration systématique de toutes les possibilités.

Toutefois, les algorithmes gloutons sont généralement moins coûteux qu’une exploration systématique. Ils sont ainsi capables de produire rapidement des résultats qui s’avèrent, dans de nombreux cas, suffisamment optimisés pour être acceptables.

Cas d’usages d’algorithmes gloutons

Les algorithmes gloutons sont souvent employés pour résoudre des problèmes d’optimisation.

bannière exemple

Exemple

Les algorithmes gloutons se montrent efficaces pour :

  • déterminer le plus court chemin dans un réseau ;
  • optimiser la mise en cache de données ;
  • compresser des données ;
  • organiser au mieux le parcours d’un voyageur visitant un ensemble de villes ;
  • organiser au mieux des plannings d’activité ou d’occupations de salles.

Les algorithmes gloutons sont simples dans leur logique et donc faciles à implémenter, même si la détermination du choix glouton pertinent est plus ou moins évidente selon les cas.

Nous allons maintenant étudier différents problèmes d’optimisation et implémenter des algorithmes gloutons pour résoudre les problèmes exposés.

Rendu de monnaie

Énoncé du problème

Nous programmons un outil de rendu de monnaie. Il pourra être intégré à un automate distributeur ou à une caisse enregistreuse afin de proposer un rendu de monnaie, permettant de préserver le fonds de caisse. Le fonds de caisse est constitué d’un nombre limité de pièces de monnaie et de billets de banque servant à restituer le trop-perçu dans une transaction d’espèces.

Intuitivement, on préférera rendre un billet de 10 euros plutôt que 5 pièces de 2 euros afin de conserver une monnaie suffisante dans notre fonds de caisse, et ainsi pouvoir continuer à rendre la monnaie le plus longtemps possible.

Stratégie gloutonne

  • Notre stratégie gloutonne consiste à rendre à chaque fois les plus gros billets ou les plus grosses pièces possibles, dans la plus grande quantité possible.

Nous devons donc déterminer pour tout montant quel est le plus gros billet ou la plus grosse pièce qu’il est possible de rendre, et combien on peut en donner sans dépasser le montant restant à rendre.

Implémentation

Nous définissons notre monnaie, c’est-à-dire l’ensemble des valeurs faciales des pièces et des billets que nous pourrons utiliser pour notre fonds de caisse, triées par ordre croissant.

monnaie = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Par simplification, notre algorithme ne traite que les euros entiers, sans les centimes.

def rendu_monnaie(montant, monnaie):

rendu = 0

# rendu est une variable qui compte le nombre de pièces+billets rendus

reste = montant

nombre_valeurs_faciales = len(monnaie)

for i in range(nombre_valeurs_faciales - 1, -1, -1):

valeur_faciale = monnaie[i]

rendu += reste // valeur_faciale

reste = reste % valeur_faciale

return rendu

  • Notre fonction comporte deux paramètres :
  • le montant à rendre ;
  • les valeurs faciales.

Nous parcourons avec la boucle for, la liste des valeurs faciales disponibles en commençant par les plus importantes. C’est pourquoi la fonction range est paramétrée pour retourner les nombres correspondant aux indices de la liste, depuis le dernier jusqu’au premier.

  • Notre algorithme calcule pour chaque valeur faciale :
  • la quantité maximale de chaque valeur faciale qu’il est possible de rendre avec une division entière et l’ajoute au nombre de pièces et de billets à rendre ;
  • le nouveau reste. Il retourne le nombre de pièces et de billets à rendre.

Testons notre fonction avec différents montants à rendre.

print(rendu_monnaie(48, monnaie))

# affiche 5

Le résultat est correct.
Pour rendre 48 euros, en optimisant le fonds de caisse, on rendra 5 billets et pièces : 2 billets de 20 euros, 1 billet de 5 euros, 1 pièce de 2 euros et 1 pièce d’1 euros.

print(rendu_monnaie(81, monnaie))

# affiche 4

Le résultat est correct.
Pour rendre 81 euros en optimisant le fonds de caisse, on rendra 4 billets et pièces : 1 billet de 50 euros, 1 billet de 20 euros, 1 billet de 10 euros et 1 pièce d’1 euros.

  • Notre fonction se contente de nous indiquer le nombre de billets ou de pièces à rendre. Nous pouvons l’améliorer pour qu’elle retourne les quantités à rendre pour chaque valeur faciale.

def rendu_monnaie(montant, monnaie):

rendu = []

reste = montant

nombre_valeurs_faciales = len(monnaie)

for i in range(nombre_valeurs_faciales - 1, -1, -1):

valeur_faciale = monnaie[i]

quantite = reste // valeur_faciale

rendu.append((quantite, valeur_faciale))

reste = reste % valeur_faciale

return rendu

  • Notre fonction ainsi modifiée retourne une liste de tuples contenant chacun la quantité et la valeur faciale des billets ou pièces à rendre.

print(rendu_monnaie(48, monnaie))

# affiche [(0, 500), (0, 200), (0, 100), (0, 50), (2, 20), (0, 10), (1, 5), (1, 2), (1, 1)]

print(rendu_monnaie(81, monnaie))

# affiche [(0, 500), (0, 200), (0, 100), (1, 50), (1, 20), (1, 10), (0, 5), (0, 2), (1, 1)]

print(rendu_monnaie(12357, monnaie))

# affiche [(24, 500), (1, 200), (1, 100), (1, 50), (0, 20), (0, 10), (1, 5), (1, 2), (0, 1)]

  • Présentons maintenant le résultat de notre algorithme glouton d’une manière plus facilement compréhensible par un humain, avec une procédure qui détaille la monnaie rendue et qui occulte les quantités nulles.

def restitution(repartion_rendu):

for element in repartion_rendu:

quantite, valeur_faciale = element

if quantite == 0:

continue

if valeur_faciale >= 5:

support = 'billet'

else:

support = 'pièce'

if quantite > 1:

support += 's' # met le mot pièce ou billet au pluriel lorsque la quantité correspondant à rendre est de plus de 1

print('je rends', quantite, support, 'de', valeur_faciale, 'euros')

print('et le compte est bon.')

Testons le résultat obtenu :

restitution(rendu_monnaie(97, monnaie))

Produit l’affichage suivant :

je rends 1 billet de 50 euros
je rends 2 billets de 20 euros
je rends 1 billet de 5 euros
je rends 1 pièce de 2 euros
et le compte est bon.

Découvrons maintenant une autre application possible des algorithmes gloutons.

Problème du sac à dos

Nous allons nous intéresser maintenant au remplissage d’un sac à dos à l’aide d’algorithmes gloutons.

Exposé de la problématique

Nous disposons d’un sac à dos d’une contenance limitée. Nous avons à notre disposition différents types d’objets, de poids et de valeurs variables.

  • Notre objectif est d’optimiser le chargement de notre sac, c’est-à-dire le remplir avec le plus de valeurs possible, sans dépasser le poids maximum autorisé par sa contenance.
bannière attention

Attention

Il existe plusieurs versions du problème du sac à dos. Selon les versions, les objets proposés sont ou non divisibles. Quand ils sont divisibles, on peut choisir d’en emporter seulement une partie. Quand ils ne le sont pas, on doit soit prendre l’objet en totalité, soit le laisser.

Dans certaines versions, tous les objets ont la même valeur et on s’intéresse uniquement à leur poids. Dans d’autres versions, les différents objets peuvent avoir une valeur variable pour un même poids.

bannière reflexion

Réflexion

Dans notre cas d’étude, nous allons travailler avec des objets fractionnables et dont la valeur par unité de poids peut différer d’un objet à l’autre.

Pour concrétiser ce cas, imaginons que nous nous apprêtons à partir en randonnée. Nous voulons remplir notre sac de nourriture. Nous disposons d’un stock limité d’aliments divers qui ont chacun leur propre valeur énergétique. Ces aliments sont fractionnables : nous pourrons donc si nécessaire en emporter qu’une portion d’un aliment donné.

Stratégie gloutonne

  • Nous voulons emporter la valeur énergétique maximale dans la limite de la capacité du sac. Notre objectif est de pouvoir nous alimenter le plus longtemps possible en cas d’imprévu au cours de notre randonnée.

Pour optimiser notre chargement nous allons nous intéresser à la densité énergétique des aliments disponibles, c’est-à-dire à leur nombre de calories par unité de poids.

Notre stratégie gloutonne sera alors de toujours commencer par prendre l’aliment le plus dense énergétiquement, et dans la plus grande quantité possible. Nous pourrons le prendre en partie ou en totalité, selon le poids encore admissible dans le sac.

Implémentation

Notre implémentation retournera la valeur énergétique totale disponible dans le sac et les quantités prises pour chaque aliment.
Nous devons lui communiquer en entrée la capacité du sac à dos, la quantité de chaque aliment sous forme de liste, ainsi que leur densité énergétique correspondante sous forme de liste également (non forcément ordonnée).

Tant que le sac à dos n’est pas plein, nous choisissons l’aliment dont la densité énergétique est la plus élevée. Si la quantité disponible entre en totalité dans le sac, nous prenons tout. Sinon, nous prenons tout ce qui peut encore entrer dans le sac.

def sac_dos(capacite, quantites_aliments, densites_aliments):

capacite_restante_sac = capacite:

nombre_aliments = len(quantites_aliments):

quantites = [0] * nombre_aliments:

valeur_energetique = 0:

for i in range(nombre_aliments):

if capacite_restante_sac == 0:

return valeur_energetique, quantites:

maxi = 0:

pos_meilleur = 0:

for j in range(nombre_aliments):

if quantites_aliments[j] == 0:

continue:

if densites_aliments[j] > maxi:

maxi = densites_aliments[j]:

pos_meilleur = j:

qte_dispo = quantites_aliments[pos_meilleur]:

if qte_dispo < capacite_restante_sac:

quantite_prise = qte_dispo:

quantites_aliments[pos_meilleur] = 0:

else::

quantite_prise = capacite_restante_sac:

valeur_energetique += densites_aliments[pos_meilleur] * quantite_prise:

quantites[pos_meilleur] = quantite_prise:

capacite_restante_sac -= quantite_prise:

return valeur_energetique, quantites:

La liste nommée quantite, créée en début d’algorithme, est destinée à contenir les poids que nous aurons réussi à charger pour chaque aliment. Elle est initialisée avec des valeurs à zéro pour la totalité des aliments.

  • À l’issue de l’exécution de la fonction, cette liste est retournée en même temps que la valeur énergétique totale du contenu du sac.

L’aliment le plus énergétique possible est recherché à chaque fois. On évalue ensuite, s’il est possible de le prendre ou non en totalité. La quantité restante disponible est mise à jour en fonction de la quantité mise dans le sac. La capacité restante du sac est pareillement mise à jour à chaque tour de boucle.

  • Testons notre fonction de chargement de sac à dos avec les valeurs suivantes :
  • contenance du sac à dos limitée à 15 kilogrammes ;
  • quantités disponibles en kilogrammes [5, 4, 2, 5, 3] ;
  • densité énergétique des aliments [2, 8, 3, 5, 9].

print(sac_dos(15, [5, 4, 2, 5, 3], [2, 8, 3, 5, 9]))

# affiche (92, [1, 4, 2, 5, 3])

Notre algorithme nous indique bien quelle quantité prendre pour chaque aliment, mais le résultat ne nous renseigne pas sur l’ordre dans lequel il a pris ces aliments.

Pour bien comprendre comment procède notre algorithme glouton, nous allons insérer des affichages au sein de la fonction pour retracer l’évolution de la capacité du sac et du stock d’aliments au fur à mesure du remplissage.

def sac_dos(capacite, quantites_aliments, densites_aliments):

capacite_restante_sac = capacite

nombre_aliments = len(quantites_aliments)

quantites = [0] * nombre_aliments

valeur_energetique = 0

for i in range(nombre_aliments):

print('densité des aliments :', densites_aliments)

print('quantité disponible :', quantites_aliments)

if capacite_restante_sac == 0:

return valeur_energetique, quantites

maxi = 0

pos_meilleur = 0

for j in range(nombre_aliments):

if quantites_aliments[j] == 0:

continue

if densites_aliments[j] > maxi:

maxi = densites_aliments[j]

pos_meilleur = j

print('le meilleur aliment restant disponible est en position :', pos_meilleur)

qte_dispo = quantites_aliments[pos_meilleur]

print('la quantité disponible pour cet aliment est de :', qte_dispo)

print('la capacité de stockage restante du sac est de :', capacite_restante_sac)

if qte_dispo < capacite_restante_sac: # on prend tout

quantite_prise = qte_dispo

quantites_aliments[pos_meilleur] = 0

else:

quantite_prise = capacite_restante_sac

print('quantité prise :', quantite_prise)

valeur_energetique += densites_aliments[pos_meilleur] * quantite_prise

quantites[pos_meilleur] = quantite_prise

capacite_restante_sac -= quantite_prise

print('capacité restante du sac en fin de boucle :', capacite_restante_sac)

print('\n')

return valeur_energetique, quantites

Notre programme est désormais plus bavard.

print(sac_dos(15, [5, 4, 2, 5, 3], [2, 8, 3, 5, 9]))

Il produit l’affichage suivant :

densité des aliments : [2, 8, 3, 5, 9]
quantité disponible : [5, 4, 2, 5, 3]
le meilleur aliment restant disponible est en position : 4
la quantité disponible pour cet aliment est de : 3
la capacité de stockage restante du sac est de : 15
quantité prise : 3
capacité restante du sac en fin de boucle : 12

densité des aliments : [2, 8, 3, 5, 9]
quantité disponible : [5, 4, 2, 5, 0]
le meilleur aliment restant disponible est en position : 1
la quantité disponible pour cet aliment est de : 4
la capacité de stockage restante du sac est de : 12
quantité prise : 4
capacité restante du sac en fin de boucle : 8

densité des aliments : [2, 8, 3, 5, 9]
quantité disponible : [5, 0, 2, 5, 0]
le meilleur aliment restant disponible est en position : 3
la quantité disponible pour cet aliment est de : 5
la capacité de stockage restante du sac est de : 8
quantité prise : 5
capacité restante du sac en fin de boucle : 3

densité des aliments : [2, 8, 3, 5, 9]
quantité disponible : [5, 0, 2, 0, 0]
le meilleur aliment restant disponible est en position : 2
la quantité disponible pour cet aliment est de : 2
la capacité de stockage restante du sac est de : 3
quantité prise : 2
capacité restante du sac en fin de boucle : 1

densité des aliments : [2, 8, 3, 5, 9]
quantité disponible : [5, 0, 0, 0, 0]
le meilleur aliment restant disponible est en position : 0
la quantité disponible pour cet aliment est de : 5
la capacité de stockage restante du sac est de : 1
quantité prise : 1
capacité restante du sac en fin de boucle : 0

(92, [1, 4, 2, 5, 3])

  • Ces affichages nous permettent de vérifier que notre algorithme glouton se comporte comme nous le souhaitons.

On peut constater la diminution de la capacité de stockage du sac et la mise à jour des stocks d’aliments au fur à mesure des mises en sac.

  • Notre algorithme glouton produit bien le résultat attendu, mais avec ses boucles imbriquées, sa complexité temporelle est O(n2)\text{O}(\text{n}^2). Nous recherchons chaque fois dans la boucle interne le meilleur aliment restant parmi ceux disponibles.

Imaginons une autre approche : nous pourrions préalablement repérer l’ordre des aliments par densité énergétique. Cela nous permettrait d’accéder plus facilement et plus rapidement au meilleur aliment parmi ceux restant disponibles.

Optimisation

Nous allons générer un index spécifique qui fournira l’ordre dans lequel lire les densités et les quantités correspondantes, en nous basant sur des densités décroissantes. Cela nous permettra ensuite, de consulter les éléments individuels des listes de densités et de quantités selon les positions indiquées par cet index.

Pour construire notre index, nous mettrons à profit les possibilités de tri avec un critère personnalisé proposés optionnellement par la méthode sort(), abordée dans le cours précédent « Traitement de tables matricielles (tableur) ».

  • Dans un premier temps nous constituons une liste d’index de la longueur des aliments disponibles.

densites_aliments = [2, 8, 3, 5, 9]

index = list(range(len(densites_aliments)))

Affichons notre index de départ.

print(index)

# affiche [0, 1, 2, 3, 4]

Sans surprise la séquence est ordonnée, et de la longueur de la liste des densités. Trions maintenant cette liste index avec un critère personnalisé basé sur la densité des aliments.

index.sort(key=lambda i: densites_aliments[i], reverse=True)

print(index)

# affiche [4, 1, 3, 2, 0]

Notre index est désormais trié par ordre décroissant de densité énergétique. Nous devrons d’abord prendre l’aliment situé en position 4, puis celui en position 1, puis celui en position 3, puis celui en position 2 et enfin celui en position 0.

bannière astuce

Astuce

L’expression lambda utilisée dans ce tri est une fonction anonyme. C’est un raccourci pour nous éviter de créer une fonction uniquement pour préciser notre critère de tri par densité énergétique. Le paramètre optionnel reverse étant par ailleurs précisé, notre liste est triée par ordre décroissant.

bannière rappel

Rappel

La méthode sort() effectue un tri en place de la liste sur laquelle elle est appliquée. Elle ne retourne rien mais modifie la liste.

  • En intégrant ce tri personnalisé préalable, nous pouvons simplifier notre algorithme glouton.

Nous n’avons plus à, rechercher chaque fois l’aliment restant le plus intéressant sur le plan énergétique : nous savons que c’est le premier parmi ceux restant disponibles au fur à mesure de notre consommation lorsque nous parcourons l’index réorganisé sur la base des valeurs énergétiques décroissantes.

def sac_dos(capacite, quantites_aliments, densites_aliments):

capacite_restante_sac = capacite

nombre_aliments = len(quantites_aliments)

quantites = [0] * nombre_aliments

valeur_energetique = 0

index = list(range(len(densites_aliments)))

index.sort(key=lambda i: densites_aliments[i], reverse=True)

for i in index:

if capacite_restante_sac == 0:

return valeur_energetique, quantites

pos_meilleur = i

qte_dispo = quantites_aliments[pos_meilleur]

if qte_dispo < capacite_restante_sac:

quantite_prise = qte_dispo

quantites_aliments[pos_meilleur] = 0

else:

quantite_prise = capacite_restante_sac

valeur_energetique += densites_aliments[pos_meilleur] * quantite_prise

quantites[pos_meilleur] = quantite_prise

capacite_restante_sac -= quantite_prise

return valeur_energetique, quantites

Testons notre nouvelle version.

print(sac_dos(15, [5, 4, 2, 5, 3], [2, 8, 3, 5, 9]))

# affiche (92, [1, 4, 2, 5, 3])

Nous obtenons bien le résultat attendu.

Notre nouvelle implémentation a permis de réduire la complexité temporelle de l’algorithme.

  • Nous avons supprimé l’imbrication de boucle, réduisant le coût cette partie de l’algorithme de O(n2)\text{O}(\text{n}^2) à O(n)\text{O}(\text{n}).

Nous avons d’un autre côté ajouté le tri préalable qui a rendu cette suppression possible. La complexité de ce tri étant pseudo-linéaire, le coût temporel global de notre nouvel algorithme est donc O(nlogn)\text{O}(\text{n}\,\text{log}\,\text{n}).

Conclusion :

Nous avons décrit les principales caractéristiques des algorithmes gloutons. Nous avons précisé que s'ils ne fournissent pas toujours la solution optimale, ils sont généralement capables de fournir rapidement des solutions satisfaisantes. Nous avons ensuite implémenté différents algorithmes gloutons pour résoudre des problèmes d'optimisation : nous avons d'abord traité le rendu de monnaie, puis nous avons effectué le remplissage d'un sac à dos avec un algorithme glouton dont nous avons dans un second temps amélioré l'efficacité.