L’algorithme Glouton

Mehdi Mekkaoui

CPGE Salé
Lycee Salman Al Farissi
[email protected]

5 décembre 2024
 Introduction
Résolution problèmes glouton
Applications

1 Introduction

2 Résolution problèmes glouton

3 Applications
 Introduction
Résolution problèmes glouton
Applications

Un problème d’optimisation (PO) est un problème où on cherche à

déterminer un résultat optimal,c’est à dire maximum ou minimum. Dans
un PO, on cherche à déterminer quand une certaine quantité (distance,
temps, hauteur, longueur...etc) qui en relation avec d’autres quantité
attend un maximum ou un minimum selon les valeurs des autres
quantités.

Considérons le problème de trouver deux nombres x et y tels que x +

2y = 10 et leur produit est maximum.
Si x et y sont les deux nombres, on cherche optimiser leur produit xy.
Comme x et y doivent satisfaire la contrainte x + 2y = 10, on doit
avoir que : y = 10−x
2
Avec cette contrainte, on peut exprimer le produit xy uniquement en
2
fonction de x : P(x) = xy = x 10−x
2 = 10x−x
2
pour optimiser P(x) , on cherche les valeurs critiques :
P’(x)= 10−2x
2 =5−x
 Introduction
Résolution problèmes glouton
Applications

Donc pour la valeur critique P’(x) = 0 on a x = 5

On utilise le test de la dérivée seconde pour déterminer si on a un
minimum ou un maximum en x = 5.
on dérive a nouveau , on a P"(x) = -1 d’où :

P”(x) = −1 < 0

donc le produit est donc maximum en x= 5

les deux nombres a cherchés sont :
10 − 5 5
x = 5 et y= =
2 2
 Introduction
Résolution problèmes glouton
Applications

Approche glouton

De nombreuses approches de programmation sont conçues pour

trouver une solution exacte ou approchée à un ensemble de
problèmes d’optimisation.
Certaines de ces approches, comme la force brute (l’énumération
exhaustive de toutes les solutions), ont une complexité qui les rend
souvent peu pertinentes compte tenu des contraintes extérieures
imposées, telles que le temps de réponse de la solution imposé et les
ressources machines limitées.
Les algorithmes gloutons constituent une méthode possible de
résolution pour les problèmes qui imposent ce genre de
contraintes.
 Introduction
Résolution problèmes glouton
Applications

l’exécution d’un algorithme glouton nécessite généralement de

faire une série d’étapes appelée pré-traitement
Un algorithme glouton (greedy en anglais) fait toujours le choix qui
lui semble le meilleur sur le moment. (appelle choix glouton)
Il fait un choix localement optimal (le choix glouton) dans l’espoir
que ce choix mènera à une solution globalement optimale.
 Introduction
Résolution problèmes glouton
Applications

Exemple :Rendu de Monnaie

1 Pour maximiser la somme que vous prenez, vous commencerez

évidemment avec la pile de 20$.
2 Ensuite, si vous parvenez à terminer cette pile en moins d’une
minute, vous passerez ensuite à la pile de 10$ (et non à celle de 5$).
3 finalement, vous passerez à la pile de 5$
 Introduction
Résolution problèmes glouton
Applications

Introduction
Dans ce chapitre nous essayons de voir quelques problèmes
d’optimisation qui peuvent résolu par une approche glouton

Remarque
Les algorithmes gloutons n’aboutissent pas toujours à des solutions
optimales, mais ils y arrivent dans de nombreux cas.
 Introduction
Résolution problèmes glouton
Applications

le choix glouton
permet de trouver une solution globale optimale à partir d’un choix au
départ local optimal.
Il faut démontrer que le choix glouton engendre une solution
optimale au problème global.
un algorithme glouton peut exploiter une sous-structure optimale
pour résoudre efficacement un problème particulier.

La sous structure optimale signifie que la solution optimale pour un

problème peut être construite à partir des solutions optimales de ses
sous-problèmes. (notion liée à la programmation dynamique).
 Introduction
Résolution problèmes glouton
Applications

Problème du sac à dos

Un voleur dévalisant un magasin trouve n objets le ième objet vaut vi

euros et pèse wi kilo, vi et wi sont des entiers. Il cherche à maximiser la
valeur totale d’objets qu’il peut mettre dans son sac à dos, sous une
contrainte de poids maximal W

Objectif : Déterminer quels sont les objets à inclure dans le sac à

dos de manière à maximiser la valeur totale des objets tout en
respectant la contrainte de poids.
Deux variantes : fractionnaire (des fractions d’un objet) ou TOR
(Tout ou rien).
 Introduction
Résolution problèmes glouton
Applications

Algorithme : Sac à dos fractionnaire

Entrées : n objets, pour chaque objet i, deux valeurs wi ≥ 0 son

poids et vi sa valeur, une constante W ≥ 0.
Pn
Calcul : Maximiser la somme des valeurs i=1 xi vi où xi est un
indicateur binaire indiquant si l’objet i est inclus dans le sac à dos (1
si
Pinclus, fraction sinon), tout en respectant la contrainte
n
i=1 i i ≤ W .
x w
Sorties : Des valeurs x1 , x2 , . . . , xn dans [0, 1].
 Introduction
Résolution problèmes glouton
Applications

Exemple :
Supposons on a :
Un sac à dos de capacité W = 50Kg
Quatre objets : o1 , o2 , o3 et o4 .
 Introduction
Résolution problèmes glouton
Applications

Exemple :
Supposons on a :
Un sac à dos de capacité W = 50Kg
Quatre objets : o1 , o2 , o3 et o4 .

On calcule la valeur par kilo ( valeur

poids ) de chaque objet.
On prend la fraction le plus possible de l’objet ayant la plus grande
valeur par kilo, et ainsi de suite, jusqu’à ce que le sac à dos soit plein.
En triant les objets en fonction de leur valeur par kilo, on aura un
algorithme en O(nlog(n)).
 Introduction
Résolution problèmes glouton
Applications
 Introduction
Résolution problèmes glouton
Applications
 Introduction
Résolution problèmes glouton
Applications

l’algorithme ne donne pas toujours une solution optimale , a savoir

l’exemple précédant on a eu une solution optimale , cependant l’exemple
suivant ne donne pas
 Introduction
Résolution problèmes glouton
Applications

l’algorithme ne donne pas la solution optimale : o3 et o2.

 Introduction
Résolution problèmes glouton
Applications

Rendu de Monnaie
Considérons le problème consistant à rendre la monnaie avec le moins de
pièces possibles.

Un commerçant applique une stratégie gloutonne consistant à rendre

toujours la plus grosse pièce de valeur au plus ce qu’il reste à rendre.
Cette méthode semble plus efficace car à chaque étape il effectue le choix
optimal qui conduit à minimiser ce qu’il reste à rendre.

Objectif : On cherche la combinaison optimale de pièces pour atteindre

la somme demandée tout en minimisant le nombre total des pièces
utilisées.
 Introduction
Résolution problèmes glouton
Applications

Algorithme : Rendu de monnaie

Entrées : Un système de pièces S = {c1 , c2 , ..., cn } et un entier

positif t qui représente la somme de monnaie à rendre. Pour chaque
ci ∈ S On a ci > 0. On suppose que c1 = 1 afin de rendre tout type
de somme.
Calcul : Déterminer
Pn un n-uplet d’entiersPpositifs (x1 , x2 , ..., xn ) qui
n
minimise : i=1 xi sous la contrainte : i=1 xi ci = t . xi présente le
nombre de pièces ci à utiliser.
Sorties : Le n-uplet (x1 , x2 , ..., xn ) qui minimise le nombre de pièces
à rendre.

Au niveau du programme Python inclus dans le cours, la sortie indique les

pièces utilisées.
 Introduction
Résolution problèmes glouton
Applications

Supposons que ce commerçant X dispose des pièces suivantes : 1, 2,

4 et 5, et qu’il doit rendre la monnaie pour 8 pièces.
La stratégie gloutonne donne trois pièces : 5 + 2 + 1.
La solution optimale vaut deux pièces : 4 + 4
 Introduction
Résolution problèmes glouton
Applications
 Introduction
Résolution problèmes glouton
Applications

Complexité : O(nlog(n)).
 Introduction
Résolution problèmes glouton
Applications

Problème : choix d’activités

Ce problème concerne l’ordonnancement de plusieurs activités qui

partagent l’utilisation exclusive d’une ressource commune. L’objectif
étant de sélectionner un ensemble de taille maximale d’activités
mutuellement compatibles.

Considérons A = {a1 , ..., an } l’ensemble d’activités.

Chaque activité ai à lieu pendant l’intervalle de temps [di , fi [.
Les activités ai et aj sont compatibles si les intervalles [di , fi [ et
[dj , fj [ ne se super-posent pas (si di ≥ fj ou dj ≥ fi ).
Stratégies : par durée, par date de début, par date de fin, ... etc.
Une stratégie gloutonne consiste à choisir l’activité qui se termine le
plus tôt parmi les activités choisies.
 Introduction
Résolution problèmes glouton
Applications

Algorithme : choix d’activités

Cela permet de libérer les ressources aussi rapidement que possible,

ce qui augmente les chances de pouvoir sélectionner plus d’activités
par la suite.

Trier les activités par date de fin.

Choisir la première activité.
Sélectionner une nouvelle activité compatible avec la dernière
activité choisie(*).
Tant que l’ensemble des activités n’est pas vide, répéter l’étape (*).
 Introduction
Résolution problèmes glouton
Applications

Exemple
 Introduction
Résolution problèmes glouton
Applications

Complexité : O(nlog(n)).
Cette algorithme glouton donne toujours une solution optimale