Algorithme glouton
I. Découverte⚓︎
Les algorithmes gloutons ou "greedy algorithms" forment une catégorie d’algorithmes permettant de donner une solution à des problèmes d’optimisation qui visent à maximiser/minimiser une quantité (GPS (plus court chemin, temps minimum, côut minimum) - plus petit temps d’exécution, meilleure organisation d’un emploi du temps, ....)
Principe d'un algorithme glouton
Un algorithme glouton est un algorithme qui suit le principe suivant :
- résout le problème étape par étape, en faisant un choix optimum local dans l'espoir d'obtenir un résultat optimum global.
- Ce choix d'étape n'est jamais remis en cause lors des étapes suivantes.
Un exemple⚓︎
Sur la grille ci-dessus, on part de la case tout à gauche marquée de la lettre D.
On souhaite atteindre les cases vides sur la partie droite en se déplaçant de case en case.
Lorsqu'on est sur une case on peut se déplacer sur une des deux cases voisines situées sur la droite. On note S la somme de toutes les cases traversées.
Par exemple on peut effectuer la trajectoire suivante (on ne note pas la dernière case, qui est vide) : D - 7 – 5 – 3 – 5 – 7 – 9 – 8 – 9 – 6 qui conduit à S = 59.
🤔 On cherche à effectuer la trajectoire qui rend la somme S la plus petite possible. Pour cela, on va utiliser un algorithme glouton. * A chaque étape, nous choisissons le plus petit nombre. * Nous ne revenons jamais en arrière.
trajectoire gloutonne
Quelle trajectoire et quelle somme S obtenez-vous sur cet exemple avec votre algorithme glouton ?
Solution
D – 4 – 4 – 2 – 5 – 7 – 7 – 8 – 8 – 1
S = 46
Trajectoire optimale
Sur cette grille, en cherchant bien, la trajectoire optimale donne une somme S = 23. Déterminer le chemin correspondant
Solution
D - 4 - 4 - 3 - 2 - 3 - 1 - 3 - 1 - 2
Algorithme par force brute
Pour obtenir la solution optimale de façon certaine on souhaite trouver toutes les trajectoires possibles et calculer pour chacune d'elles la somme associée.
On doit faire 9 déplacements, et à chaque déplacement on a deux possibilités.
On a donc \(2^9=512\) trajectoires différentes. Il faudrait donc calculer la somme pour chacune de ces 512 trajectoires différentes.
🌵 Cette méthode est exacte, mais beaucoup plus coûteuse en termes de calculs.
II. Le rendu de monnaie⚓︎
Situation :
Dans le pays nommé New Land, la monnaie est constituée de pièces de 4 nl, 3 nl et 1 nl.
L’unité de monnaie est le newland, symbolisé par nl.
Alice et Bob sont deux commerçants qui disposent dans leur caisse de beaucoup de pièces de chaque type, mais ils veulent rendre la monnaie en utilisant le moins de pièces possible.
1. La méthode de Bob : algorithme glouton⚓︎
La méthode gloutonne
Bob a une idée : il se dit que plus il rendra de pièces de grandes valeurs, mieux cela sera.
Pour donner 10 nl :
- Il donne une pièce de 4 nl, il lui reste à rendre 6 nl,
- puis il donne une pièce de 4 nl, il lui reste à rendre 2 nl,
- puis il donne une pièce de 1 nl, il lui reste à rendre 1 nl,
- puis il donne une pièce de 1 nl, il lui reste à rendre 0 nl.
La fonction monnaie_Glouton prend en paramètre un entier qui est le montant en nl, et renvoie la liste des pièces correspondantes, obtenue par l'algorithme glouton.
Exemple
>>>monnaie_Glouton(6)
[4, 1, 1]
>>>monnaie_Glouton(9)
[4, 4, 1]
Compléter ci-dessous
2. La méthode d'Alice : La force brute⚓︎
La méthode par force brute
Alice est très méthodique. Elle va chercher toutes les possibilités dont la somme correspond, puis ensuite elle prendra celle qui correspond au plus petit nombre de pièces. Cette méthode, qui consiste à chercher toutes les possibilités s'appelle une méthode par force brute. Le nombre maximal de pièces est la somme totale (si on la donne uniquement avec des pièces de 1)
La fonction possibilites renvoie une liste de listes. Chaque liste donne une possibilité pour rendre le montant.
Par exemple [1, 0, 2] signifie qu'on rend une pièce de 4, 0 pièce de 3, et 2 pièces de 1.
Exemple
>>> possibilites(6)
[[0, 0, 6], [0, 1, 3], [0, 2, 0], [1, 0, 2]]
La fonction monnaie_brute renvoie un tuple dont le premier élément est la liste optimale comme décrite ci-dessus, et le deuxième le nombre de pièces.
Exemple
>>> monnaie_brute(6)
([0, 2, 0], 2)
Compléter les fonctions :
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Comparaison des méthodes⚓︎
Le moins de pièces possibles à rendre
Comparer le résultat obtenu pour la méthode par algorithme glouton, ou par force brute pour le cas d'un rendu de monnaie de 6 nl, 10 nl, 22nl . Que constatez vous ?
Solution
| montant | algorithme glouton (liste triée) | algorithme par force brute (liste triée) |
|---|---|---|
| 6 | [1, 1, 4] | [3, 3] |
| 10 | [1, 1, 4, 4] | [3, 3, 4] |
| 22 | [1, 1, 4, 4, 4, 4, 4] | [3, 3, 4, 4, 4, 4] |
L'algorithme glouton donne un résultat très rapidement, mais il n'est pas forcément optimal.
3. Utilisation d'un algorithme glouton récursif⚓︎
On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous forme d’une liste :
VALEURS = [100, 50, 20, 10, 5, 2, 1].
On suppose que les pièces et billets sont disponibles sans limitation.
On cherche à donner la liste des valeurs à rendre pour une somme donnée en argument. L’algorithme utilisé est de type glouton.
Compléter le code Python ci-dessous. La fonction rendu_glouton prend en paramètre un entier a_rendre qui est la somme à rendre, et un entier rang, qui correspond à l'indice du tableau VALEURS à partir duquel on peut prendre les valeurs du tableau VALEURS. Cette fonction renvoie la liste des pièces à rendre par l'algorithme glouton.
On garantit que la somme à rendre est supérieure ou égale à 1.
Exemple
>>> rendu_glouton(67, 0)
[50, 10, 5, 2]
>>> rendu_glouton(291, 0)
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291, 1) # On ne peut utiliser que les valeurs de VALEURS[1:]
[50, 50, 50, 50, 50, 20, 20, 1]
>>> rendu_glouton(33, 3) # On ne peut utiliser que les valeurs de VALEURS[3:]
[10, 10, 10, 2, 1]
Compléter
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Astuce
Avez-vous pensé à la concaténation des tableaux ?
III. Le problème du sac à dos ("Knapsack Problem")⚓︎
Le problème est celui-ci : vous disposez d'un sac d'une contenance limitée (sur le dessin ci-dessus, 15kg) et vous souhaitez maximiser la valeur totale des objets que vous mettez dans votre sac. Evidemment, la somme de leur masse ne doit pas dépasser 15 kg.
Ce problème (de la catégorie des problème dits d'analyse combinatoire) malgré sa simplicité est un problème majeur d'optimisation.
Actuellement :
- On sait trouver LA meilleure solution, mais en explorant toutes les combinaisons une par une. Cette méthode par force brute est inapplicable si beaucoup d'objets sont en jeu.
- On sait facilement trouver une bonne solution, mais pas forcément la meilleure, par exemple en adoptant une stratégie gloutonne.
- On ne sait pas trouver facilement (en temps polynomial) la meilleure solution. Si vous y arrivez, 1 Million de $ sont pour vous.
1. Petite aide technique avant de commencer⚓︎
Tri par deuxième élément
Supposons qu'on dispose d'une liste mylist = [["A",3], ["B",2], ["C",8]].
Comment classer les éléments de cette liste par leur deuxième élément ???
Nous allons procéder en 2 temps :
- création d'une fonction qui renvoie le deuxième élément d'un objet
liste - tri de la liste grâce à cette fonction
Tester ci-dessous
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
Il s'affiche : [['C', 8], ['A', 3], ['B', 2]]
2. Retour sur le problème du sac à dos⚓︎
On considère un sac de 40 kg et les objets suivants :
| objet | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| masse | 13 | 12 | 8 | 10 | 14 | 18 |
| valeur | 700 | 500 | 200 | 300 | 600 | 800 |
Quels objets faut-il prendre ?
Stratégie gloutonne
- on va classer les objets dans l'ordre décroissant de leur taux de valeur (taux de valeur = valeur / masse). Ainsi le premier élément de la liste sera celui ayant le meilleur rapport valeur/masse.
- on prend le premier élément de la liste, puis le deuxième, etc., tant que le sac peut encore les contenir.
trier dans l'ordre décroissant de leur taux de valeur
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Résoudre le problème par la méthode gloutonne
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
Il faut donc choisir la combinaison A, F, C. Elle est bien valide (poids 39) et rapporte 1700.
Question
L'algorithme glouton nous a-t-il donné la solution optimale ?
Nous allons pour cela avoir recours à la force brute pour tester toutes les combinaisons possibles.
3. Force brute⚓︎
La méthode par force brute
Nous allons chercher toutes les possibilités pour lequel le poids total est inférieur au poids total autorisé, puis ensuite nous chercherons la possibilité qui donne la valeur totale maximale. Cette méthode, qui consiste à chercher toutes les possibilités s'appelle une méthode par force brute.
La fonction possibilites prend en paramètres la liste objets et l'entier poids qui est le poids maximal. Cette fonction renvoie une liste de listes. Chaque liste donne une possibilité de choix d'objets
Par exemple [1, 1, 0, 1, 0, 1] signifie qu'on prend l'objet A, le B, pas le C, le D, pas le E et le F.
Exemple
On a :
objets = [["A", 13, 700], ["B", 12, 500], ["C", 8, 200],\
["D", 10, 300], ["E", 14, 600], ["F", 18, 800]]
possibilites
>>> possibilités(objets, 15)
[[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0]]
>>>
La fonction butin_brut renvoie un tuple dont le premier élément est la liste optimale comme décrite ci-dessus, et le deuxième le magot obtenu.
Exemple
>>> butin_brut(objets, 25)
([1, 0, 0, 1, 0, 0], 1000)
Compléter les fonctions :
# Tests (insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
La combinaison A-B-E est bien valide (poids total 39) et rapporte 1800
Mon info
La force brute a mis en évidence une combinaison meilleure que celle donnée par l'algorithme glouton.
En effet la combinaison A-B-E est bien valide (poids total 39) et rapporte 1800, donc 100 de mieux que la solution gloutonne.
Par contre, la force brute est inenvisageable pour si le nombre d'objets est grand, alors que la stratégie gloutonne reste très rapide.
4. Pour approfondir⚓︎
V. La chasse au trésor⚓︎
⌛ Elle arrive ...
VI. Conclusion⚓︎
Mon info
La stratégie gloutonne donne très rapidement des solutions satisfaisantes mais pas forcément optimales. Pour beaucoup de problèmes (dont le problème du sac à dos), la recherche d'une solution optimale sans passer par la force brute semble impossible (mais n'est pas démontrée).
Dans ce cas-là, la stratégie gloutonne peut être employée pour avoir vite et bien une solution convenable, même si peut-être non optimale. On dit que la stratégie gloutonne est une heuristique de résolution. On sait que ce n'est pas forcément optimal, mais faute de mieux, on s'en contente...
VII. Crédits⚓︎
Le III. La résolution gloutonne du problème du sac à dos est une mise en forme du travail de Gilles Lassus.
# Tests(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)