Objectif
résoudre un problème grâce à un algorithme glouton :
Exemples traités :
- Problème du rendu de monnaie.
- Problème du sac à dos.
Définition
Un algorithme est qualifié de glouton si le problème qu’il essaie de résoudre est décomposé en une succession de problèmes identiques pour lesquels l’algorithme va chercher une solution optimale.
La question (presque philosophique) est : Lorsqu’on fait à chaque étape le meilleur choix possible, est-ce que la solution finale à laquelle on arrive est la meilleure possible ?
Formulé autrement : Est-ce que faire le meilleur choix à chaque étape nous assure le meilleur choix global ?
Exemple d'algorithme glouton
Un plus court chemin ?
- Vous partez du point O.
- Vous devez avoir atteint le plus rapidement possible tous les points A, B, C, D, E, F.
- L’ordre de parcours des points n’est pas important.
La philosophie de l’algorithme glouton implique qu’à chaque étape, vous allez vous diriger vers le point le plus proche.
Quel est alors le parcours final avec l’algorithme glouton ? A ou B
Solution A
Solution B
Ce chemin est-il optimal ?
Pourquoi ?
Remplir un rectangle avec des carrés
(d’après S.Tummarello et E.Buonocore)
On considère un rectangle de dimension 11 sur 13 (figure 0). On veut remplir ce rectangle avec le minimum de carrés.
En utilisant l’algorithme glouton pour remplir le rectangle avec des carrés
Clic pour la solution
Question : Est-ce qu’un algorithme glouton va toujours passer à côté de la solution optimale ?
Non ! Il arrive aussi qu’il donne la solution optimale. Changeons le rectangle initial en un rectangle de 10 sur 15 :
Conclusion
Un algorithme glouton est une méthode rapide et souvent efficace, mais qui ne garantit pas l’optimalité de la solution trouvée.
La succession de meilleurs choix LOCAUX va nous amener à une bonne solution GLOBALE, mais ne nous garantit pas d’arriver à la solution optimale.