Un algorithme est qualifié de glouton si le problème qu’il essaie de résoudre est décomposé en une succession de problèmes identiques pour lesquels l’algorithme va chercher une solution optimale.
Un algorithme glouton est donc un algorithme qui suivant le principe de faire, étape par étape, un choix optimum local, dans l’objectif d’obtenir un résultat optimum global.
Ces algorithmes sont utilisés principalement dans des problèmes d’optimisation.
Un problème d’optimisation consiste à déterminer les valeurs des paramètres permettant de :
- Minimiser ou maximiser une fonction objectif.
- Satisfaire une ou des fonctions contraintes (il existe des problèmes avec ou sans contrainte).
Ces valeurs correspondent à une solution optimale que l’on obtient en effectuant une suite de meilleurs choix pour chaque étape de l’algorithme (à chaque étape, on fait le meilleur choix possible).
Dans l’algorithme, il n’y pas de retour en arrière : lorsqu’un choix est fait à une étape, il n’est pas modifié ultérieurement et il ne modifie pas les choix précédents.
Une autre caractéristique des algorithmes gloutons : la progression descendante. Cette caractéristique est traduite par le fait que lorsqu’un choix est fait, on tente de résoudre un problème plus petit.
Exemple du rendu de monnaie.
Le problème du rendu de monnaie est un problème d’algorithmique qui s’énonce de la façon suivante : étant donné un système de monnaie, comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ?
Dans la zone euro, le système en vigueur, en mettant de côté les centimes d’euros, met à disposition des pièces ou billets de : 1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€.
On suppose que nous avons à notre disposition un nombre illimité de ces pièces ou billets.
Voici un exemple de code permettant de résoudre ce problème :
https://colab.research.google.com/drive/1X1Ed2Y26axXMSA_5TbvkjbmMPDBDUGjj?usp=sharing
Aucune réponse