Ctrl+K

Algorithme glouton

Algorithme glouton#

Certains problèmes ont plusieurs combinaisons possibles qui conduisent à la solution possible. Selon le problème, le nombre de combinaisons est très important. Il est parfois si important que la recherche de toutes les combinaisons peut être extrêmement gourmand en ressources et en temps d’exécution.

Une stratégie, dite glouton optimise le temps de recherche en donnant la bonne solution dans certains cas, mais pas toujours. Le problème du rendu de monnaie en est un bon exemple.

Problème du rendu de monnaie#

On cherche à égaler une somme à rendre en utilisant le moins d’unités possible prises parmi un sytème défini à l’avance et dont le nombre est illimité. Cela signifie qu’on dispose d’assez d’unités pour rendre une somme quelle qu’elle soit.

Ici on suppose que le système d’unités est le suivant : [100, 50, 20, 10, 5, 2, 1].

  1. Pour rendre la somme de 9 unités, la combinaison qui utlise le moins d’unités est 3 : [5, 2, 2].

  2. Un algorithme dit glouton résout ce problème. Cet algorithme enlève la plus grosse unité possible à la somme à rendre jusqu’à ce que la somme à rendre soit nulle.

    En l’appliquant à la somme à rendre de 9 euros :

    • on enlève la valeur 5 (la plus grande possible) ; il reste à rendre 4 unités

    • on enlève la valeur 2 ; il reste à rendre 2 unités

    • on enlève la valeur 2 ; il reste 0 unité à rendre

    La combinaison est bien de trois unités, solution optimale.

  3. Cet algorithme donne une solution mais elle n’est pas toujours optimale comme le montre l’exemple suivant.

    Prenons comme système monétaire les valeurs 1, 3, 6, 12, 24 et 30.

    1. Comment rendre la somme de 48 unités de manière optimisée ?

      En appliquant l’algorithme glouton, on obtient :

      • on enlève la plus grande valeur possible 30 ; il reste 18 unités à rendre

      • on enlève la plus grande valeur possible 12 ; il reste 6 unités à rendre

      • on enlève la plus grande valeur possible 6 ; il reste 0 unité à rendre

      La solution donnée par l’algorithme glouton est 3 unités (30, 12 et 6). Elle n’est pas optimale car on peut rendre la somme de 48 unités avec 2 unitéss de valeur 24.

Note

  1. L’intérêt de l’algorithme glouton se situe dans le temps d’exécution très rapide comparativement à un algorithme naïf qui cherche toutes les possibilités.

  2. Pour certains problèmes, on est capable de savoir si l’algorithme glouton renvoie toujours la meilleure solution.

Programmation python#

Un algorithme glouton appliqué au problème du rendu de monnaie se présente ainsi :

tableau des unités = [200, 100, 50, 20, 10, 5, 2, 1] (ordre décroissant)
nombre_unités = 0
On prend la première pièce du tableau des unités (la plus grande)
Tant que la somme à rendre est supérieure à 0:
   Si la pièce est plus grande que la somme à rendre:
      on la soustrait de la somme à rendre
      nombre_unités augmente de 1
   sinon:
      on passe à la pièce suivante

Il existe différentes écritures de cet algorithme en Python.

  1. En utilisant une seule boucle while:

     1def rendu_monnaie(somme_a_rendre):
 2    tableau_des_unites = [100,50,20,10,5,2,1]
 3    nombre_unites = 0
 4    i = 0
 5    piece = tableau_des_unites[i]
 6    while somme_a_rendre > 0:
 7        if somme_a_rendre >= piece:
 8            somme_a_rendre = somme_a_rendre - piece
 9            nombre_unites = nombre_unites + 1
10        else:
11            i = i + 1
12            piece = tableau_des_unites[i]
13    return nombre_unites

    >>> rendu_monnaie(48)
5

  2. En utilisant 2 boucles imbriquées :

    1def rendu_monnaie(somme_a_rendre):
2    """somme à rendre (int) -> nombre de pièces (int)"""
3    pieces = [200,100,50,20,10,5,2,1]
4    n = 0 # nombre pièces
5    for p in pieces:
6        while somme_a_rendre >= p:
7            somme_a_rendre = somme_a_rendre - p
8            n = n + 1
9    return n

    >>> rendu_monnaie(48)
5
Contenu