Le principe glouton☘

Un algorithme glouton procède étape par étape.
Une règle de choix lui permet d’obtenir une solution optimale d’une étape à la suivante. Ce choix est réalisé pour être le meilleur sur le moment, dans l'espoir que cela mène à une solution optimale pour le problème posé. En effet, un algorithme glouton ne revient jamais en arrière (il ne remet jamais en question les choix déjà effectués).

En anglais

Algorithme glouton : greedy algorithm.
Greedy pourrait aussi se traduire par « avide ».

Rendu de monnaie☘

Cet exemple est un « grand classique » des algorithmes gloutons. Il faut le connaître et ce TP vous conduira à l'implémenter en Python.

Énoncé du problème☘

On souhaite programmer un distributeur automatique pour qu'il rende la monnaie de manière optimale, c'est-à-dire en utilisant le minimum de pièces et de billets.

Pour cela, on admet que l'on dispose d'un réserve illimitée de pièces et de billets ayant les valeurs suivantes : 1, 2, 5, 10, 20, 50, 100 et 200.

Pourquoi glouton ?☘

Une stratégie gloutonne est bin adaptée à ce problème :

Il faut sélectionner des montants de pièces et de billets.
On optimise en sélectionnant le moins de pièces et de billets possibles.
Les contraintes étant le montant à rendre (qui doit être atteint exactement*) et les valerus faciales des pièces et billets.

Règle de choix☘

On commence par rendre la pièce (ou le billet) de la plus grande valeur possible tout en restant inférieure au montant à rendre ;
On actualise le montant à rendre (par soustraction).
Le montant (qui reste) à rendre est plus petit que le précédent : le problème a été simplifié.
On recommence le 1. jusqu'à obtenir un montant égal à zéro.
On renvoie la liste des « valeurs rendues ».

Application « à la main »☘

Le montant à rendre est 47 euros.
La liste des valeurs possibles pour les pièces et les billets est : [50, 20, 10, 5, 2, 1].

On utilise les notations suivantes :

a_rendre = 47 ;
liste_valeurs = [50, 20, 10, 5, 2, 1] ;
resultat = [].

Sur votre cahier, écrivez les étapes de recherche (avec cette stratégie gloutonne) de la décomposition du montant à rendre avec la liste des valeurs données.

Une solution

Initialisation :

liste_valeurs a_rendre resultat

[50, 20, 10, 5, 2, 1] 47 [ ]
Lecture de la première valeur de la liste : 50.

valeur_actuelle a_rendre valeur actuelle ≤ a_rendre ? resultat

50 47 Non [ ]

Cette valeur est supérieure au montant à rendre : on recommence en passant à la valeur suivante dans la liste.

Lecture de la valeur suivante de la liste : 20.

valeur_actuelle	`a_rendre`	valeur actuelle ≤ `a_rendre` ?	`resultat`	Nouvelle valeur de `a_rendre`
20	47	Oui	[20]	47-20 = 27

a_rendre est supérieur à zéro : on recommence.

Valeur actuelle de la liste : 20.

valeur_actuelle	`a_rendre`	valeur actuelle ≤ `a_rendre` ?	`resultat`	Nouvelle valeur de `a_rendre`
20	27	Oui	[20, 20]	27-20 = 7

a_rendre est supérieur à zéro : on recommence.

Valeur actuelle de la liste : 20.

valeur_actuelle a_rendre valeur actuelle ≤ a_rendre ? resultat

20 7 Non [20, 20]

Cette valeur est supérieure au montant à rendre : on recommence en passant à la valeur suivante dans la liste.
Lecture de la valeur suivante de la liste : 10.

valeur_actuelle a_rendre valeur actuelle ≤ a_rendre ? resultat

10 7 Non [20, 20]

Cette valeur est supérieure au montant à rendre : on recommence en passant à la valeur suivante dans la liste.

Lecture de la valeur suivante de la liste : 5.

valeur_actuelle	`a_rendre`	valeur actuelle ≤ `a_rendre` ?	`resultat`	Nouvelle valeur de `a_rendre`
5	7	Oui	[20, 20, 5]	7-5 = 2

a_rendre est supérieur à zéro : on recommence.

Valeur actuelle de la liste : 5.

valeur_actuelle a_rendre valeur actuelle ≤ a_rendre ? resultat

2 5 Non [20, 20, 5]

Cette valeur est supérieure au montant à rendre : on recommence en passant à la valeur suivante dans la liste.

Lecture de la valeur suivante de la liste : 2.

valeur_actuelle	`a_rendre`	valeur actuelle ≤ `a_rendre` ?	`resultat`	Nouvelle valeur de `a_rendre`
2	2	Oui	[20, 20, 5, 2]	2-2 = 0

a_rendre est égal à zéro : on s'arrête.

La décomposition de 47 euros avec la liste [50, 20, 10, 5, 2, 1] est [20, 20, 5, 2].

Un algorithme optimal ?☘

On pourrait croire que l'algorithme glouton du rendu de monnaie donne la meilleure solution possible quel que soit le montant à rendre (c'est-à-dire le nombre minimal de pièces et/ou de billets pour décomposer ce montant) n'est-ce pas ?

Dans les exemples suivants, « déroulez » les étapes de recherche (par algorithme glouton) de la décomposition du montant à rendre avec la liste des valeurs données.

Indiquez ensuite si cette décomposition est optimale ou pas (c'est-à-dire utilise le moins de valeurs possibles).

Exemple n°1☘

Montant à décomposer : 121
Liste des « pièces » disponibles : [50, 20, 10, 5, 2, 1]

Une réponse

Au départ, la liste de décomposition est vide : resultat = [].
La première valeur de « pièce » est 50.
Puisque 121 ≥ 50, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [50] ;
- montant = 121-50 = 71.
La valeur en cours est 50.
Puisque 71 ≥ 50, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [50, 50] ;
- montant = 71-50 = 21.
La valeur en cours est 50.
Puisque 21 < 50, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 20.
Puisque 21 ≥ 20, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [50, 50, 20] ;
- montant = 21-20 = 1.
La valeur en cours est 20.
Puisque 1 < 20, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 10.
Puisque 1 < 10, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 5.
Puisque 1 < 5, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 2.
Puisque 1 < 2, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 1.
Puisque 1 ≥ 1, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [50, 50, 20, 1] ;
- montant = 1-1 = 0.
montant est nul, l'algorithme se termine et renvoie la liste de décomposition [50, 50, 20, 1].
Cette décomposition est optimale.

Exemple n°2☘

Montant à décomposer : 121
Liste des « pièces » disponibles : [100, 60, 1]

Une réponse

Au départ, la liste de décomposition est vide : resultat = [].
La première valeur de « pièce » est 100.
Puisque 121 ≥ 100, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [100] ;
- montant = 121-100 = 21.
La valeur en cours est 100. Puisque 21 < 100, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 60.
Puisque 21 < 60, on passe à la « pièce » suivante de la liste des « pièces » disponibles.
La valeur suivante est 1.
Puisque 21 ≥ 1, on place cette valeur dans la liste resultat et on l'enlève du montant à décomposer :
- resultat = [100, 1] ;
- montant = 21-1 = 20.
La valeur en cours est 1. On recommence 20 fois l'étape précédente :
- resultat = [100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ;
- montant = 1-1 = 0.
montant est nul, l'algorithme se termine et renvoie la liste de décomposition [100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
Cette décomposition n'est pas optimale puisque la liste [60, 60, 1] permet de décomposer le montant 121 à l'aide de trois valeurs seulement au lieu de 22...

Conclusion☘

Un algorithme glouton recherche (et trouve s'il est bien programmé !) une solution optimale d'une étape à la suivante mais il ne permet pas forcément d'obtenir une solution optimale pour l'ensemble du problème à résoudre.