Qu'est-ce que Algorithme glouton (greedy) ?

Méthode de conception d'algorithmes qui construit une solution en prenant de façon répétée le choix qui paraît le meilleur sur le moment, sans revenir sur les choix précédents. Elle est rapide et simple, mais ne donne une solution optimale que si le problème a des propriétés particulières, comme avec des systèmes de pièces semblables à celui du Japon ou l'algorithme de Kruskal pour les arbres couvrants de poids minimal.

Nom japonais: 貪欲法

« Algorithme glouton (greedy) » apparaît dans 2 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Algorithme glouton (greedy)

On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?

AL'algorithme glouton atteint lui aussi le minimum de 2 pièces
BL'algorithme glouton utilise 3 pièces et manque le minimum de 2
CL'algorithme glouton utilise 3 pièces, et c'est le minimum

Afficher la réponse et l'explication

Réponse : B. L'algorithme glouton utilise 3 pièces et manque le minimum de 2

L'algorithme glouton prend d'abord une pièce de 6 yens et paie les 2 yens restants avec deux pièces de 1 yen, soit 3 pièces. Or deux pièces de 4 yens suffisent pour payer avec seulement 2 pièces. Comme un algorithme glouton ne fait qu'accumuler le choix qui paraît le meilleur à chaque instant, il n'est pas optimal pour certains systèmes de pièces. La programmation dynamique, qui remplit dans l'ordre croissant une table du nombre minimal de pièces pour chaque montant de 0 à 8 yens, trouve toujours le minimum. Pour des systèmes de pièces comme celui du Japon (1, 5, 10, 50, 100 et 500 yens), l'algorithme glouton donne toujours le minimum.

« Algorithme glouton (greedy) » dans les explications

L'algorithme glouton prend d'abord une pièce de 6 yens et paie les 2 yens restants avec deux pièces de 1 yen, soit 3 pièces.
On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. …
Un algorithme glouton qui place les objets par ordre de valeur par unité de poids prend les objets de poids 2 et 3 (valeur 7), puis plus aucun objet ne tient dans la capacité restante de 3 : il s'arrête donc à 7.
On remplit un sac à dos de capacité 8 avec des objets chois…

Questions mentionnant « Algorithme glouton (greedy) » (2)

Termes associés

Programmation dynamique Algorithme de Dijkstra Arbre binaire de recherche (binary search tree) Complexité temporelle (notation grand O) File d'attente Liste chaînée (linked list) Parcours en largeur (breadth-first search) Parcours en profondeur (depth-first search) Pile (stack) Recherche dichotomique (recherche binaire)

Retour au glossaire