Un algorithme glouton est un algorithme qui, à chaque étape de la résolution d'un problème, fait un choix optimal dans l'espoir que le résultat final soit aussi optimal.
Cela fonctionne pour certains types de problèmes ou pour des problèmes dont les paramètres permettent à l'algorithme glouton d'être optimal.
On a un exemple avec les pièces de monnaies. Vous pensez que le choix des valeurs des pièces de monnaies est fait au hasard ? En fait, elles sont choisies pour qu'un algorithme glouton soit optimal.
Comment cela fonctionne-t-il avec la monnaie ? Quand vous devez rendre de la monnaie la manière la plus efficace est de commencer par les pièces de plus grande valeur vers celles de plus petite valeur. À chaque pièce choisie correspond une étape dont la pièce ayant la plus grande valeur possible est un résultat optimal local.
Voyons un contre-exemple. Imaginez que vous n'ayez que des pièces de 6€, 4€ et 1€. Pour rendre la monnaie sur 8€, un algorithme glouton commence par donner 6€, puis il reste 2€ qui seront donnés par deux pièces de 1€, soit au total 3 pièces. Or le choix global optimal est de donner 2 pièces de 4€. L'algorithme glouton ne fonctionne pas ici car le choix des pièces de monnaies disponibles ne permet pas à un tel algorithme d'être optimal.
Autres champs d'application:On peut également faire appel à l'algorithme glouton pour résoudre:
problème du sac à dos Problème du voyageur de commerce
Pour approfondir le sujet, je vous conseille de lire ceci:
Quels sont vos bouquins de références?
Aucun commentaire :
Enregistrer un commentaire