Algorithmes gloutons

Algorithmes gloutons

Algorithmes gloutons

On souhaite optimiser une situation. Il s’agit ainsi de minimiser ou maximiser une fonction, en satisfaisant des conditions que l’on appelle contraintes. 

La première idée consiste à traiter tous les cas possibles. Si il y a peu de cas, cette solution est envisageable. Mais dans la plupart des cas, il n’est pas possible de retenir cette solution qui nécessite trop de temps pour aboutir au résultat. 

Le meilleur de tous les choix possibles est globalement optimal. On peut alors se rappeler de la notion des extrama globaux d’une fonction. 
L’algorithme glouton, à chaque étape, fait le meilleur choix parmi un ensemble restreint de choix. Il fait donc un choix localement optimal, c’est à dire optimal sur l’ensemble restreint. 
On se demande alors si en effectuant une série de choix localement optimaux, il est possible d’aboutir au choix globalement optimal. Il s’avère que cette démarche fonctionne dans certains cas.

On propose, afin de mieux comprendre, d’illustrer cette notion par un exemple emblématique : le problème du sac à dos.
On dispose ainsi de $n$ objets $o_1, … o_n$. Chaque objet $o_i$ a une valeur $v_i$ et un poids $p_i$.

On essaie alors d’emporter dans son sac à dos la plus grande valeur d’objets sans dépasser une masse $P$.

Il faut donc sélectionner les bons objets tels que la somme des valeurs $v_i$ soit maximale en respectant la contrainte qui stipule que la somme des masses $p_i$ des objets doit être inférieure à $P$.  

Ce problème d’optimisation peut se résoudre très efficacement à l’aide d’un algorithme.