Cours Stage - Algorithmes gloutons

Algorithmes gloutons

Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Fiche de cours

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 d

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.