Cours: Les algorithmes Gloutons

1
Chapitre IV :

Les algorithmes Gloutons

1. Introduction:
Les méthodes algorithmiques sont regroupés en famille, parmi lesquelles figure celle
des algorithmes dits gloutons.
Dans ce présent chapitre, nous allons dans un premier temps, définir ce qui
caractérise un algorithme glouton, puis nous implémenterons quelques algorithmes
gloutons pour résoudre différents problèmes d'optimisation.

2. Généralités
Un problème d’optimisation est un problème algorithmique dans lequel l’objectif est de
trouver la « meilleure » solution (selon un critère donné) parmi un ensemble de
solutions également valides mais potentiellement moins bonnes.
Le contexte d’un problème d’optimisation est donc :
 un très grand nombre de solutions (dans le cas contraire, il n’y aurait pas de
difficulté à trouver la meilleure),
 une fonction permettant d’évaluer la qualité de chaque solution,
 l’existence d’une solution optimale, ou suffisamment bonne.
De nombreuses techniques informatiques sont susceptibles d’apporter une solution
exacte ou approchée à ces problèmes.

Certaines de ces techniques, comme l’énumération exhaustive de toutes les solutions, ont
un coût machine qui les rend souvent peu pertinentes au regard de contraintes
extérieures imposées (temps de réponse de la solution imposé, moyens machines
limités). Quand il existe un très grand nombre de solutions il est tout
simplement impossible de les évaluer toutes.
Les techniques de programmation dynamique peuvent apporter une solution mais sont
parfois complexes à mettre en œuvre.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

Les algorithmes gloutons (greedy algorithms) constituent une alternative beaucoup

2
plus simple à programmer, mais dont le résultat n’est pas toujours optimal (sauf dans
certaines situations dites canoniques).

3. Définition d'un algorithme glouton

L’approche gloutonne consiste à construire une solution complète par une succession
de choix locaux donnant systématiquement la meilleure solution partielle. Ces
algorithmes déterminent une solution optimale à un problème donné en effectuant
successivement des choix locaux, jamais remis en cause. Au cours de la construction de
la solution, l’algorithme résout une partie du problème puis se focalise ensuite sur le
sous-problème restant à résoudre. Le principal avantage des algorithmes gloutons est
leur facilité de mise en œuvre. Nous présentons de telles situations dans la suite de ce
chapitre, en montrant les avantages mais aussi les limites de la technique.

4. Exemple introductif
Nous cherchons à écrire le plus grand nombre possible à partir d'un ensemble donné de
chiffres. Chaque chiffre ne peut être utilisé qu'une seule fois.
L'ensemble de chiffres dont nous disposons est 2, 9, 7, 4, 8, 1. Nous parvenons
rapidement à composer le nombre 987421. Ce nombre est effectivement le plus grand
nombre possible. Pour le former à partir de l'ensemble de chiffres dont nous disposons,
nous avons d'abord cherché le plus grand chiffre disponible qui était le 9.
Une fois le 9 utilisé pour composer le premier chiffre du nombre, nous avons cherché
parmi les chiffres restants le plus grand chiffre possible, qui était le 8, et ainsi de suite
jusqu'à épuisement des chiffres disponibles.
-> Nous avons appliqué un algorithme glouton pour former ce nombre.

5. Principe général d'un algorithme glouton

L'algorithme glouton choisit la solution optimale qui se présente à lui à chaque instant,
sans se préoccuper, ni du passé ni de l'avenir. Il répète cette même stratégie à chaque
étape jusqu'à avoir entièrement résolu le problème. Ainsi, un algorithme glouton est un
algorithme qui effectue à chaque instant le meilleur choix possible sur le moment, sans

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

retour en arrière ni anticipation des étapes suivantes, dans l'objectif d'atteindre au final
3
un résultat optimal.

6. Cas d'usage d'algorithmes gloutons

Les algorithmes gloutons sont généralement moins coûteux qu'une exploitation
systématique. Ils sont ainsi capables de produire rapidement des résultats qui s'avèrent,
dans de nombreux cas, suffisamment optimisés pour être acceptables.
Les algorithmes gloutons sont souvent employés pour résoudre des problèmes
d'optimisation. Exemples:
 Déterminer le plus court chemin dans un réseau;
 Optimiser la mise en cache des données;
 Compresser des données;
 Organiser au mieux le parcours d'un voyageur visitant un ensemble de villes;
 Organiser au mieux des planning d'activité ou d'occupation de salles;
 ..etc.

7. Exemples d'algorithmes gloutons

7.1. Rendu de monnaie
Ce problème consiste à rendre de la monnaie avec le moins de pièces possible. Un achat
dit en espèces se traduit par un échange de pièces et de billets. Supposons qu’un achat
induise un rendu de 57 dinars. Quelles pièces peuvent être rendues? La réponse, bien
qu’évidente, n’est pas unique. Cinq pièces de 10 dinars, 1 pièce de 5 dinars et 1 pièce de
2 dinars conviennent. Mais cinquante-sept pièces de 1 dinars conviennent également! Si
la question est de rendre la monnaie avec un minimum de pièces, le problème change de
nature. Toutefois, comment parvient-on à un tel résultat ? Quels choix doivent être faits
pour optimiser le nombre de pièces à rendre? C’est le problème du rendu de monnaie
dont la solution dépend du système de monnaie utilisé.

a) Solution naïve
La solution à laquelle on pense immédiatement est d'énumérer toutes les combinaisons
de pièces possibles, de sélectionner celles qui impliquent un minimum de pièces et de
choisir la meilleure.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

Cette solution, fonctionnera toujours mais est très loin d'être efficace.
4
En effet, si elle est simple dans certains cas, elle implique en général un nombre très
important de combinaisons différentes, ce qui nuit grandement à l'efficacité de cette
solution.

b) Solution gloutonne
Dans le système monétaire algérien, les pièces prennent les valeurs 1, 2, 5, 10, 20, 50,
100, 200 dinars. Rendre 72 dinars avec un minimum de pièces est un problème
d’optimisation. En pratique, sans s’en rendre compte généralement, tout individu met en
œuvre un algorithme glouton. Il choisit d’abord la plus grande valeur de monnaie, parmi
le système monétaire, contenue dans 72 dinars. En l’occurrence, une fois une pièce de 50
dinars. Pour la somme de 22 dinars restant à rendre, il choisit une pièce de 20 dinars,
puis une pièce de 2 dinars. Cette stratégie gagnante pour la somme de 72 dinars l’est-elle
pour n’importe quelle somme à rendre ? On peut montrer que la réponse est positive
pour le système monétaire algérien. Pour cette raison, un tel système de monnaie est
qualifié de canonique. D’autres systèmes ne sont pas canoniques. L’algorithme glouton
ne répond alors pas de manière optimale. Par exemple, avec le système {1, 3, 6, 12, 24,
30}, l’algorithme glouton répond en proposant le rendu 72 = 30 + 24 + 12 + 6, soit 4
pièces alors que la solution optimale est 72 = 3 × 24, soit 3 pièces.

c) Implémentation de la solution gloutonne:

L'implémentation de cette solution est relativement intuitive : On va récupérer les
données sous forme d'une liste (pour le système monétaire en vigueur) et d'un entier
(pour le rendu).

De là, tant que le rendu est supérieur à la pièce de plus haute valeur (située en première
position dans la liste) on retranchera la valeur de cette pièce au rendu et on ajoutera la
pièce dans une liste qui constituera la solution.
Si le rendu est inférieur à la pièce de plus haute valeur en cours, la fonction s'appellera
récursivement en ne considérant plus la pièce de plus haute valeur. C'est alors la
seconde pièce qui joue ce rôle, et ainsi de suite.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

L'algorithme glouton est donné dans ce qui suit:

5
Procédure Rendu_Monnaie (Système_monnaie: tableau[1..n] d'entiers;
somme_a_rendre: entier);
Var Valeur, Cpt: entier;
Début
Cpt←0;
TQ (somme_a_rendre>0) Faire
Valeur ← Système_monnaie [n];
Si (Valeur > somme_a_rendre) Alors
n←n-1;
Sinon
Ecrire ('la pièce à rendre est de ', Système_monnaie [n],'dinars');
somme_a_rendre← somme_a_rendre - Valeur;
Cpt←Cpt+1;
Fin;
Fin;
Ecrire ('Le nombre de pièces à rendre est:', Cpt);
Fin;

7.2. Le problème du sac à dos

Dans la recherche en informatique, le problème du sac à dos et ses dérivés sont encore
beaucoup étudiés. Il en existe de nombreuses variantes : sac à dos multi-dimensions
(plusieurs poids par objet), plusieurs fonctions objectif, etc. De nombreux algorithmes
exacts et approchés sont proposés pour ce type de problèmes.

L’énoncé de ce problème est simple : « Étant donné plusieurs objets possédant chacun
un poids et une valeur et étant donné un poids maximum pour le sac, quels objets faut-il
mettre dans le sac de manière à maximiser la valeur totale sans dépasser le poids
maximal autorisé pour le sac ? ».

Nous pouvons retrouver le problème du sac à dos dans de nombreux domaines :

 en cryptographie, où il fut à l’origine du premier algorithme de chiffrement

asymétrique en 1976 ;
 dans les systèmes financiers, où l’idée est la suivante : étant donné un certain
montant d’investissement dans des projets, quels projets choisir pour que le tout
rapporte le plus d’argent possible ;
 pour la découpe de matériaux, afin de minimiser les pertes dues aux chutes ;
 dans le chargement de cargaisons (avions, camions, bateaux…) ;
 ou encore, dès qu’il s’agit de préparer une valise ou un sac à dos pour une
randonnée.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

a) Formulation mathématique du problème:

6
Toute formulation commence par un énoncé des données. Dans notre cas, nous avons un
sac à dos de poids maximal W et n objets. Pour chaque objet i, nous avons un poids wi et
une valeur pi.

Pour quatre objets (n = 4) et un sac à dos d’un poids maximal de 30 kg (W = 30), nous
avons par exemple les données suivantes :

Objets 1 2 3 4
pi 7 4 3 3
wi 13 12 8 10

Ensuite, il nous faut définir les variables qui représentent en quelque sorte les actions ou
les décisions qui amèneront à trouver une solution. On définit la variable xi associée à un
objet i de la façon suivante : xi = 1 si l’objet i est mis dans le sac, et xi = 0 si l’objet i n’est
pas mis dans le sac.

Dans notre exemple, une solution réalisable est de mettre tous les objets dans le sac à
dos sauf le premier, nous avons donc : x1 = 0, x2 = 1, x3 = 1, et x4 = 1.

Puis il faut définir les contraintes du problème. Ici, il n’y en a qu’une : la somme des
poids de tous les objets dans le sac doit être inférieure ou égale au poids maximal du sac
à dos. Cela s’écrit :

x1.w1 + x2.w2 + x3.w3 + x4.w4 ≤ W

ou plus généralement pour n objets :

𝑛

∑ 𝑥𝑖 × 𝑤𝑖 ≤ 𝑊
𝑖=1

b) Solution naïve:
En apparence, la solution la plus simple dans le cas du sac à dos serait d'écrire un
algorithme qui teste toutes les combinaisons d'objets possibles et qui retient les
solutions qui offrent un gain maximum. Dans notre cas précis, avec seulement 4 objets,
cette solution pourrait être envisagée, mais avec un plus grand nombre d'objets, le
temps de calculs, même pour un ordinateur très puissant, deviendrait trop important.
En effet l'algorithme qui testerait toutes les combinaisons possibles aurait une
complexité en temps en O(an) avec a une constante et n les nombre d'objets. On parle
d'une complexité exponentielle. Les algorithmes à complexité exponentielle ne sont pas
efficaces pour résoudre des problèmes, le temps de calcul devient beaucoup trop
important quand n devient très grand.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

c) Solution gloutonne:
7
En apparence, la solution la plus simple dans le cas du sac à dos serait d'écrire un
algorithme qui teste toutes les combinaisons d'objets possibles et qui retient les
solutions qui offrent une valeur maximale. avec seulement 4 objets, cette solution
pourrait être envisagée, mais avec un plus grand nombre d'objets, le temps de calculs,
même pour un ordinateur très puissant, deviendrait trop important. En effet
l'algorithme qui testerait toutes les combinaisons possibles aurait une complexité en
temps en O(an) avec a une constante et n les nombre d'objets. On parle d'une complexité
exponentielle. Les algorithmes à complexité exponentielle ne sont pas efficaces pour
résoudre des problèmes, le temps de calcul devient beaucoup trop important quand n
devient très grand.

d) Implémentation:
La stratégie gloutonne a pour but de trouver une solution avec un bon compromis entre
la qualité de la solution et le temps de calcul. Pour le problème du sac à dos, voici un
exemple d’algorithme de ce type :

 DEBUT
 calculer la valeur (pi / wi) pour chaque objet i,
 trier tous les objets par ordre décroissant de cette valeur,
 sélectionner les objets un à un dans l’ordre du tri et ajouter l’objet sélectionné
dans le sac si le poids maximal reste respecté.
 FIN


Déroulons cet algorithme sur l'exemple ci-dessus:

 Premier étape:
Objets 1 2 3 4
pi 7 4 3 3
wi 13 12 8 10
pi / w i 0.54 0.33 0.37 0.30

 Deuxième étape: Apres le tri, l’ordre des objets est le suivant : 1, 3, 2, et 4.

Objets 1 3 2 4
pi 7 3 4 3
wi 13 8 12 10
pi / w i 0.54 0.37 0.33 0.30

 Troisième étape :
 Objet 1 : on le met dans le sac (qui est vide au départ).
 Objet 3 : on le met dans le sac car l’addition du poids de l’objet 1 et de l’objet 3
est inférieure à 30.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

 Objet 2 : on ne le met pas dans le sac car le poids total (33) dépasse le poids
maximal du sac. 8
 Objet 4 : on ne le met pas dans le sac pour la même raison que pour l’objet 2.

L'algorithme glouton est donné dans ce qui suit. Nous avons considéré à cet effet une
liste linéaire chainée dont chaque nœud désigne un objet (id_objet, Valeur, Poids,
Rapport).

Procédure sac_a_dos (Var P: liste; poids_max: entier);

Var Poids_total, Valeur_Max: entier;
L: liste;
Début
L←P;
Valeur_Max←0;
Poids_total←0;
TQ (L<>Nil) Faire
L^.valeur
L^.Rapport ← L^.poids ;
L ← L^.suivant;
Fin;
L←P;
Trier(L);//le tri se fera dans l'ordre décroissant en fonction de la valeur du rapport 𝑣𝑎𝑙𝑒𝑢𝑟
𝑝𝑜𝑖𝑑𝑠
de l'objet

TQ (L<>Nil) et (poids_max >0) Faire

Si (L^.poids≤ poids_max) Alors
poids_max ← poids_max - L^.poids;
Valeur_max ← Valeur_max - L^.Valeur;
Poids_total ← Poids_total + L^.Poids;
Ecrire ('l'objet', L^.id_objet,'est mis dans le sac');
L ← L^.suivant;
Fin;
Fin;
Ecrire ('La valeur des objets mis dans le sac est:', Valeur_Max,' avec un
poids=',Poids_total);
Fin;

Avec l'algorithme glouton ci-dessus, la solution trouvée est donc de mettre les objets 1 et
3 dans le sac, ce qui donne une valeur de 10. Cette solution n’est pas optimale,
puisqu’une solution avec une valeur totale de 11 existe (en choisissant les objets 1 et 2).
Néanmoins, cet algorithme reste rapide même si le nombre d’objets augmente
considérablement.

Cet algorithme est un algorithme glouton, car il ne remet jamais en cause une décision
prise auparavant. Ici, lorsque l’objet 2 ne peut pas entrer dans le sac, l’algorithme
n’essaie pas d’enlever l’objet 3 du sac pour y mettre l’objet 2 à sa place.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Les algorithmes Gloutons

7.3. Un problème d'organisation

9
Le problème est formulé comme suit: Des conférenciers sont invités à présenter leurs
exposés dans une salle. Mais leurs disponibilités ne leur permettent d’intervenir qu’à des
horaires bien définis. Le problème est de construire un planning d’occupation de la salle
avec le plus grand nombre de conférenciers. Désignons par n, entier naturel non nul, le
nombre de conférenciers. Chacun d’eux, identifié par une lettre C i , où i est un entier
compris entre 0 et n − 1, est associé à un intervalle temporel [d i , fi[ où di et fi désignent
respectivement l’heure de début et l’heure de fin de l’intervention.

On peut proposer la stratégie gloutonne suivante:

 Classer les intervalles par heures de fin croissantes.

 Choisir le conférencier associé au premier intervalle.
 Choisir parmi les intervalles suivants celui du conférencier dont l’intervalle est
compatible avec celui du premier conférencier.
 Recommencer ainsi avec les intervalles classés suivants jusqu’à ce qu’il n’y en ait
plus à traiter.

Conclusion:
Dans ce chapitre, nous avons décrit les principales caractéristiques des algorithmes
gloutons. Nous avons préciser que s'ils ne fournissent pas toujours la solutions optimale,
ils sont généralement capables de fournir rapidement des solutions satisfaisantes. Nous
avons ensuite implémenté deux algorithmes gloutons pour résoudre des problèmes
d'optimisation: nous avons d'abord traité le rendu de monnaie puis le problème du sac à
dos.

Il est à noter que si le choix est optimal localement à chaque étape, la solution trouvée
par un algorithme glouton n'est pas forcément optimale globalement. L'algorithme
glouton ne va pas toujours donner l'optimal mais a une complexité plus faible que la
programmation dynamique et permet généralement d'obtenir une solution correcte
pour des problèmes variés. Il est à noter que tous les problèmes n'admettent pas une
solution gloutonne.

Dr KHAMTACHE-KHOULALENE Nadjet