Algorithmes Gloutons.

Présentation.

Les algorithmes gloutons permettent de donner des approximations (parfois exactes d'ailleurs) à des problèmes d'optimisations, c'est à dire qu'on a à la base un problème qui admet un grand nombres de possibilités et une fonction mathématique f qui associe à chaque possibilité un nombre. On essaye de trouver la ou les possibilités qui vont donner la plus grande ou la plus petite image.

Pour développer un algorithme glouton il faut réussir :

• Construire une possibilité de façon progressive, étape par étape, et pour chaque étape avoir des choix différents.
• Avoir une fonction mathématique g qui a un des choix précédents associe une valeur.

L'algorithme glouton consiste à choisir pour chaque étape le choix qui minimise ou maximise la fonction g.

On peut voir l'algorithme glouton comme un algorithme myope, on voit le mieux à court terme sans se poser la question sur le long terme.

Des exemples de problèmes.

Le problème du voyageur de commerce.

Un voyageur doit passer une fois dans chaque ville, comment doit il choisir son trajet pour minimiser la distance ?

Exemple

Voici le résultat obtenu en utilisant l'algorithme glouton :

On voit que l'algorithme glouton ne donne pas la meilleure réponse, cependant il a donné une possibilité pas trop mauvaise de façon très rapide.

Solution exacte avec un algo génétique "maison".

Un algo génétique avec plein de villes.

La complexité des bons algorithmes de résolution exacte est d'ordre exponentielle, ils sont très lents si le nombre de villes à visiter est un peu grand (n>15). Par contre on dispose de nombreux algorithmes qui donnent des bonnes solutions mais sans garantir d'avoir les meilleurs.

Le problème du sac à sac à dos

Le problème est simple, on dispose d'un sac et un nombre n d'objets, le sac a une masse maximale chaque objet a une masse déterminée et une valeur donnée. Quels objets faut il placer dans le sac sans dépasser la masse maximale donnée pour que la somme des valeurs soit maximale ?

Le problème semble simple mais il ne l'est pas tant que ça, et la méthode naïve (on tente toutes les possibilités) est exponentielle (Le nombre de parties d'un ensemble de n objets est de 2ⁿ). C'est moins pire que la méthode naïve du voyageur du commerce mais la complexité est largement supérieur à une complexité polynomiale. Pratiquement pour 10 sacs la réponse en force brute est presque immédiate mais à partir de 30 le temps commence à être important.

Pour trouver une possibilité, on peut utiliser un algorithme glouton. La fonction f à maximiser est la somme des valeurs des objets dans le sac, maintenant pour la fonction g on a le choix :

• g représente le poids de l'objet et on essaye de mettre les plus légers en premier.
• g représente la valeur des objets et on essaye de mettre les plus chers en premier.
• g représente le rapport valeur/poids et on essaye de mettre les meilleurs rapport en premier.

Malheureusement ces méthodes de type glouton ne permettent pas de garantir la meilleur réponse (mais elles peuvent la donner).

Le problème du rendu de monnaie.

Là aussi l’énoncé est très simple : Comment doit on rendre la monnaie pour minimiser le nombre de pièces rendues.

Ici un algorithme glouton marche parfaitement (dans notre système monétaire). La fonction à minimiser est le nombre de pièces à rendre, et g représente la valeur de la pièce et on rajoute la plus grande valeur qui reste inférieure à la somme encore à rendre.

La solution est dans notre système monétaire la meilleur possible, mais avec d'autres systèmes elle ne l'est plus.

Le problème des spectacles

Pour un spectacle, un organisateur se retrouve avec de nombreux créneaux possibles de spectacles, il doit choisir les spectacles pour en avoir le plus possible.

La aussi la méthode gloutonne marche à condition de choisir pour g la fonction qui donne la durée de fin des spectacles, et de choisir pour chaque étape le minimum de g pour les spectacles encore possibles.

Du code.

Rendu de monnaie.

Voici par exemple une façon d'implémenter le problème du rendu de monnaie :

Voyageur de commerce

Voici par exemple une façon d'implémenter le problème du voyageur :

Exercice

Q.C.M.

On donne le tableau des distance entre villes suivants :

On considére les objets suivants, on veut en mettre dans un sac à dos qui peut au maximum porter 14 kg.