Le problème : rendre une somme en utilisant le moins de pièces possible.3 La stratégie gloutonne consiste, à chaque étape, à prendre la pièce la plus élevée parmi celles qui tiennent encore dans ce qu'il reste à rendre.3 On s'arrête quand il ne reste plus rien à rendre.2
Quand le glouton est-il optimal ?
Autres exemples de problèmes gloutons
Le principe dépasse le rendu de monnaie :
Fractions égyptiennes : pour écrire un rationnel strictement positif comme somme de fractions unitaires distinctes (par exemple 5/6 = 1/2 + 1/3), on choisit à chaque étape la plus grande fraction unitaire possible inférieure au nombre considéré.4
Algorithmes de Prim et de Kruskal : ce sont deux algorithmes gloutons, où chaque augmentation se fait de la manière la plus économique possible.3
Décomposition d'un entier en somme d'éléments d'un ensemble contenant 1 : elle se fait par l'algorithme glouton.3
Méthode pour répondre à une question de contrôle
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Le glouton fait un choix optimal local à chaque étape en espérant un optimum global.3 Tester toutes les solutions est une recherche exhaustive, pas un glouton ; diviser en deux moitiés évoque la recherche dichotomique.
Le glouton prend d'abord 4, puis il reste 2, qu'il rend avec 1 + 1.3 La réponse 3 + 3 est la solution optimale, mais ce n'est pas celle du glouton. 4 + 3 dépasse 6.
C'est faux : le résultat n'est pas toujours optimal.2 Le système {1, 3, 4} en est un contre-exemple. L'idée tentante vient du fait qu'il est optimal pour certains systèmes comme le système européen.
37 = 20 + 10 + 5 + 2, soit 4 pièces.3 Se tromper en comptant 5 pièces vient souvent d'un oubli de la pièce de 20.
Les questions qu'on se pose
Comment savoir si un algorithme glouton est optimal pour un problème ?
Il faut le démontrer pour le problème étudié. Pour le rendu de monnaie, cela dépend du système de pièces : optimal pour le système européen, non optimal pour {1, 3, 4}.3 Pour prouver qu'il n'est pas optimal, un seul contre-exemple suffit.
Pourquoi utiliser un algorithme glouton s'il peut se tromper ?
Parce qu'il est simple à mettre en œuvre.2 Quand l'optimalité n'est pas garantie, on le voit comme une heuristique qui donne une bonne solution rapidement.3
Quel lien avec les algorithmes de la classe de Première ?
Comme les tris ou la recherche dichotomique, le glouton se décrit en pseudo-code puis s'écrit en Python. Sa spécificité est de reposer sur un critère de choix local à chaque itération.3