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.
Méthode : Fonctionnement de l'Algorithme glouton
L'algorithme glouton peut être décomposé en plusieurs étapes :
Un pré calcul sur les données.
Par exemple dans le cas du problème des gymnases, un tri par ordre croissant de la date de fin des activités.
La construction étape par étape de la solution globale.
À chaque étape, on fait un choix localement (au moment de l'étape) optimal.
Par exemple dans le cas du problème des gymnases, on choisit l'activité possible qui finit le plus tôt.
On recompose la solution globale.
Attention : Solution rapide mais pas toujours optimale
Il ne faut pas oublier que la rapidité d'exécution de cet algorithme ne nous permet pas toujours d'obtenir un algorithme fiable !
Dans le cas du problème des gymnases, on obtient toujours une solution optimale. Mais dans certains cas, par exemple de le problème générale d'ordonancement, l'algorithme glouton n'offre qu'un résultat approché du résultat optimal.