Un algorithme glouton est utilisé dans un problème d’optimisation, on l’utilise pour effectuer chaque étape du programme donné et ainsi choisir la meilleure option disponible pour exécuter l’étape d’un programme.
Après l’avoir cité ci-dessus, nous savons que les algorithmes gloutons sont utilisé pour des problèmes d’optimisation. Sachant qu’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).
A noter qu’un algorithme glouton ne fait point machine arrière, une fois que la meilleure option pour une étape est appliquée alors cette dernière ne peut être changée. Les algorithmes gloutons ont une autre option, lorsqu’un choix est fait, on tente de résoudre un problème plus petit. On appelle cela la progression descendante.
Nous allons étudier cela en prenant un exemple précis qui est le suivant : On a une somme de 423 € et on souhaite donner le moins de billet possible. Comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ? :
system_euro=[500,200,100,50,20,10,5,2,1]
def rendu_monnaie(somme,systeme):
liste_pieces=[]
for valeur in systeme:
while somme>=valeur:
liste_pieces.append(valeur)
somme=somme-valeur
return liste_pieces
Nous définissons la somme qui est de 423 € mais aussi on crée une liste qu’on nomme « liste_pieces » où chaque valeur trouvée sera placées dans cette dernière. Nous allons trouvé ses valeurs grâce à une boucle qu’on va établir « for valeur in système » où système = system euro. Nous disons tant que la somme est strictement supérieur aux valeurs alors nous les ajoutons dans la liste »liste_pieces » et nous retirons à la somme la valeur prise dernièrement.
Vous pourrez retrouver sur le lien ci-dessous une application numérique où le code sera exécutable :
Aucune réponse