Algorithmes gloutons
Les algorithmes gloutons permettent de répondre à des problèmes d'optimisation. Ces problèmes nécessitent de trouver la meilleure solution possible, parmi les solutions existantes.
Définition : Problème d'optimisation
Il s'agit d'un problème défini tel que :
on considère un problème ayant un très grand nombre de solutions possibles ;
on dispose d'une fonction permettant d'évaluer la qualité d'une solution ;
on cherche une bonne solution, voire la meilleure.
Définition : Algorithme glouton
Les algorithmes gloutons s'appliquent aux problèmes d'optimisation, notamment ceux dont :
la recherche d'une solution est une succession de choix qui produisent petit à petit une solution partielle ;
on dispose d'une fonction permettant d'évaluer la qualité des solutions partielles, qui soit cohérente avec l'évaluation de la solution complète.
Un algorithme glouton est donc un algorithme qui va construire une solution complète grâce à une succession de choix qui donneront la meilleure solution partielle.
Exemple : Résolution approchée du problème du voyageur de commerce
L'approche gloutonne de notre problème du voyageur de commerce consiste à réaliser le trajet étape par étape, en choisissant toujours la ville la plus proche, et ce jusqu'à épuisement de la liste des villes.
La solution partielle est une séquence de villes, du début de la solution finale.
La qualité de la solution partielle est la distance totale parcourue.
Attention : Solution rapide mais pas optimale
Il ne faut pas oublier que la rapidité d'exécution de cet algorithme ne nous permet pas d'obtenir un algorithme fiable ! Le résultat ne sera pas optimal, mais pourra être toutefois proche du résultat optimal.