Table des matières
Algorithme Glouton
Un algorithme glouton greedy algorithm désigne une stratégie consistant à faire à chaque étape le choix permettant de gagner le plus sans se soucier du gain total final.
Il s'agit d'un algorithme d'optimisation c'est à dire qu'il consiste à chercher à atteindre un maximum, ou un minimum, en respectant une contrainte.
Dans nos exemples, on travaille sur des problèmes de petite taille. Sur ces petits problèmes on peut trouver une solution en testant bêtement tous les cas possibles, la puissance de calcul de la machine nous le permet. Un algorithme comme l'algorithme glouton n'a d'intérêt que dans les cas plus gros où il faut trouver une solution sans faire trop de calcul, sans tout tester.
Exemple : un voyageur de commerce
Un voyageur de commerce va de ville en ville pour proposer des ventes. Il souhaite bien sûr maximiser ses gains mais la distance qu'il peut parcourir est limitée.
Représentons cette situation par un graphe :
- Les ronds sont les villes,
- dans chaque rond, la valeur représente le gain espéré dans cette ville,
- les arcs (traits) entre les villes sont les chemins possibles,
- les valeurs sur les arcs sont des distances.
- Le voyageur commence en A.
Le voyageur de commerce cherche donc un itinéraire, qui lui permettra de faire le gains de vente. Mais la distance maximale qu'il peut parcourir est de 15. On décide également qu'il ne peut pas passer deux fois par une même ville.
On a bien une quantité à maximiser et une contrainte (un ensemble de contraintes).
Pour l'exemple, nous nous concentrons sur ce problème qui ne contient que 8 villes. Il n'est pas impossible, pour une machine, d'essayer tous les chemins possibles et de trouver le meilleur.
Vous devez comprendre que ce n'est qu'un exemple : l'outil informatique deviendra intéressant pour un gros problème avec 100, 1 000, 10 000 villes… Et alors il sera impossible d'essayer tous les chemins.
L'algorithme glouton
Il va consister, à chaque étape, à rechercher le gain maximal dans cette étape, sans se soucier des conséquences.
- Depuis A, l'étape suivante la plus profitable vaut 16. C'est loin mais le voyageur ne s'en soucie pas, il y va car c'est le meilleur gain disponible.
- Depuis la ville rapportant 16, le mieux est d'atteindre celle rapportant 11,
- ensuite celle rapportant 9 (on ne peut pas atteindre le 15 de puis 11)
- ensuite 15,
- enfin 3 car 7 est trop loin (distance totale maximale de 15)
Ce chemin a bien une longueur de 15, il respecte la contrainte, et il totalise un gain de 54.
Paramétrage possible
Dans cet exemple, le voyageur doit maximiser son gain total. Il paraît donc naturel de chercher, à chaque étape, la ville donnant le plus grand gain parmi celles accessibles.
On peut essayer d'autres approches, tout en restant dans le cadre de l'algorithme glouton : L'algorithme glouton consiste seulement à renoncer à une vision globale du problème. On se fixe un critère simple localement. Dans notre exemple, on aurait pu décider qu'à chaque étape on choisissait la prochaine ville la plus proche.
Parfois plusieurs villes sont à la même distance, on choisit alors la ville au meilleur gain. Je rappelle qu'on ne peut pas passer deux fois par la même ville.
Cela donne le trajet suivant :
Le gain total est ici de 66. À la dernière étape, on n'a parcouru 12. On a encore le droit de parcourir 3 mais la seule ville disponible est à une distance de 4. C'est ce genre d'effet de seuil qui rend le problème difficile.
Dans ce cas ce critère donne de meilleurs résultats. Mais il est difficile – sinon impossible – d'anticiper quel critère donnera les meilleurs résultats et cela dépend grandement du problème.
Pas optimal
Quelque soit le critère, l'algorithme glouton ne garantit pas de trouver la meilleure solution. L'algorithme glouton permet de trouver une bonne solution rapidement même pour un très gros problème.
Encore une fois, le problème étudié ici est petit et on peut chercher un optimum de façon exhaustive (essayer tous les chemins) mais dans un gros problème (par exemple 200 villes) il sera impossible de tester tous les chemins et il faut donc une stratégie efficace permettant d'obtenir un bon résultat sans avoir à tout tester.
L'algorithme glouton a l'avantage d'être très rapide et simple. Mais il ne garantit pas de trouver la meilleure solution.
Par exemple, dans notre problème, ce chemin est meilleur que ceux trouvés par l'algorithme glouton.
Gain total de 71 avec ce chemin.
Cas classiques
Deux problèmes classiques sont souvent étudiés dans le cadre de l'algorithme glouton :
- Le problème du rendu de monnaie (dans les projets)