Algorithmes gloutons
Il existe de nombreuses approches pour tenter de résoudre des problèmes algorithmiques. Une de ces approches est l'approche gloutonne. Elle consiste à choisir, à chaque étape de résolution d'un problème, la solution se rapprochant en apparence le plus de la solution du problème. Les algorithmes qui choisissent cette approche sont dit algorithmes gloutons.
Analogie : randonnée
Votre professeur de NSI part faire une randonnée dans le massif de la Chartreuse. A un moment pendant la montée en forêt, il se perds. Il décide d'abandonner la randonnée, mais n'est pas moins perdu pour autant. Comment peut-il faire pour retourner le plus près possible de son point de départ ?
Son point de départ étant en bas de la montagne, il lui suffit de suivre la pente pour redescendre. Comme sur le schéma ci-dessous :
En général, les approches gloutonnes ont l'avantage d'être très simples. Mais parfois, elles sont insuffisantes ou conduisent à un résultat qui n'est pas le meilleur possible (on parle de solution optimale).
Activité
Proposez une situation sur le modèle du schéma présenté plus haut dans laquelle votre professeur ne pourrait pas utiliser se contente de descendre la pente pour retourner à son point de départ.
Changez la forme de la montagne !
Il suffit que la montagne comporte une "bosse", le professeur descendra jusqu'au creux de la bosse et sera ensuite bloqué, puisqu'il n'y aura que de la montée et pas de descente.
On va maintenant voir deux problèmes et l'approche gloutonne qui les résouds.
Rendu de monnaie
On dispose d'un ensemble de valeurs de pièces. Par exemple, 5, 2, et 1. On veut savoir comment rendre la monnaie avec le moins de pièces possible pour une valeur donnée, par exemple 29.
!!! example "Activité"
=== "Enoncé"
Combien de pièces de 5, 2 et 1 faut il pour rendre 29 avec le moins de pièces possible ?
Comment avez-vous procédé ?
=== "Solution"
On rends des pièces une par une, en choisissant toujours la plus grande possible, jusqu'à qu'on ait rendu la monnaie.
```
29 - 5 = 24
24 - 5 = 19
19 - 5 = 14
14 - 5 = 9
9 - 5 = 4
4 - 2 = 2
2 - 2 = 0
```
La solution est donc d'utiliser 5 pièces de 5 et 2 pièces de 2, pour un total de 7 pièces.
Cette approche est la méthode gloutonne.
Activité
Considérons l'ensemble de valeurs de pièces 4, 3, et 1. Donnez une valeur de monnaie à rendre, inférieure à 10, pour laquelle l'algorithme glouton ne donne pas la solution optimale.
Sac à dos
Activité
Robin des bois dévalise une bijouterie de Nottingham, et a uniquement un sac à dos qui peut contenir K (une constante entière) kilogrammes. La bijouterie comporte de nombreux bijoux avec chacun un poids et un prix. Robin veut décider de quels bijoux il doit prendre dans son sac, de manière à emporter la plus grande valeur possible sans que le poids des bijoux dépasse K. Comment peut-il choisir les objets ?
Robin doit privilégier les bijoux à la fois légers et coûteux. Il peut donc calculer pour chaque bijoux son "efficience", rapport entre sa valeur et son poids, et ajouter dans son sac les bijoux par ordre décroissant d'efficience, jusqu'à ce qu'il ne puisse plus en ajouter sans dépasser la limite des K kg. C'est une méthode gloutonne de résolution du problème du sac à dos.
TODO (prof) ajouter schéma
Remarque
Le problème du sac a dos peut être "traduit" dans de nombreux domaines, comme la gestion des stocks par exemple.
La méthode gloutonne ne permet pas à coup sûr de trouver une solution optimale au problème du sac à dos, mais elle est simple à mettre en oeuvre et donne un résultat en général satisfaisant. On parle de résultat approché dans ce cas.