A L G O R IT H M E S G L O U T O N S

Lycée Omar Ibn Abdelaziz

MP
2025/2026
PLAN DU CHAPITRE V

❑ Introduction

❑ Schéma Général

❑ Preuve d’Optimalité

❑ Exemples

2
 INTRODUCTION
P R O B L È M E D ’ OPTIMISATION
❖ On est souvent dans le cadre des problèmes
d'optimisation:
➢ E: un ensemble fini d'éléments.
➢ S: une solution est construite à partir des éléments de E . Par
exemple: une partie de E , un multi-ensemble d'éléments de E , une
suite fini de E ou une permutation de E qui satisfait une certaine
contrainte.

➢ A chaque solution S est associée une fonction objectif F(S).

➢ Le but est de chercher une solution qui optimise (minimise ou

3
maximise) cette fonction objectif .
 INTRODUCTION
PRINCIPE GÉNÉRAL
❖ Pour un problème d’optimisation, un algorithme glouton
est un algorithme qui cherche à construire une
solution pas à pas

➢ sans jamais revenir sur ses décisions,

➢ en prenant à chaque étape la solution qui
semble la meilleure localement,

➢ en espérant obtenir une solution optimale.

4
 E X E M P L E 1: L E M O N N A Y E U R

❖ On dispose des pièces de monnaie correspondant aux

valeurs E = {e1, ..., e n }.

❖ Pour chaque valeur e i , le nombre de pièces (nbi) est non

borné.
❖ Étant donnée une somme « s » entière, on veut trouver
une façon de rendre la somme « s » avec un nombre de
pièces minimum.

❖ Prendre E ={1, 2, 5 , 10}, s = 28, Quelle est la

solution optimale? 6
 E X E M P L E 1: L E M O N N A Y E U R

❖ Une solution S = (nb 1 , ...., nb n ) présente le nombre de

pièces (nbi) pour chaque valeur (ei):

➢ Elle est correcte si

➢ Elle est optimale si est minimal.

❖ Algorithme glouton: Trier les valeurs de pièces par

ordre décroissant. Pour chaque valeur de pièce,
maximiser le nombre de pièces choisies.
7
 SCHÉMA GÉNÉRAL
❖ Il est basé sur un critère local de sélection des
éléments de E pour construire une solution optimale. En
fait, on travaille sur l'objet « solution partielle » et on
doit disposer des modules suivant:
9
 SCHÉMA GÉNÉRAL
➢ Init qui initialise la solution de début
➢ Select qui choisit le meilleur élément restant selon le critère
glouton: Souvent, on trie tout simplement la liste des éléments
selon le critère glouton au départ et on balaye ensuite cette liste
dans l'ordre.

➢ Complete? qui teste si une solution partielle est une solution

(complète).

➢ AjoutPossible? qui teste si un élément peut être ajouté à une

solution partielle. Dans certains cas, c'est toujours vrai!

➢ Ajout qui permet d'ajouter un élément à une solution si c'est

10
possible.
 SCHÉMA GÉNÉRAL

❖ L’algorithme Glouton est alors:

Trier (E) - Init (S)

- Select(x, E)
………(1) - Complete(S)
- AjoutPossible(x)
Tant que Non ……….(2) faire - Ajout(S, x)

………..(3)

S i ……….(4) alors ……….(5)

11
FTQ
 SCHÉMA GÉNÉRAL

❖ L’algorithme Glouton est alors:

Trier (E)

Init (S)

Tant que Non Complete(S) faire

Select(x, E)

S i AjoutPossible(x) alors Ajout(S, x)

12
FTQ
 SCHÉMA GÉNÉRAL
REMARQUES

➢ Dans certains cas, le schéma général est encore plus

simple! Comme dans le cas de M O N N AY E U R .

➢ Dans d'autres cas, les solutions sont un peu plus

compliquées ... et on a besoin d'un schéma un peu plus

sophistiqué...
16
 PREUVE D ’O P T I M A L I T É

❖ U n algorithme glouton produit des solutions optimales si

les propriétés suivantes sont vérifiées :

1. Propriété du choix glouton : Il existe toujours une

solution optimale qui contient un premier choix glouton
✓ En général on montre que toute solution optimale contient ou
débute par le premier choix glouton.

17
 PREUVE D ’O P T I M A L I T É

2. Propriété de sous-structure optimale : toute solution

optimale contient une sous-structure optimale
✓ Soit S une solution optimale du problème P contenant le choix C et
le S’ = S\{C} alors S’ est une solution optimale du sous problème
P C résultant du choix C dans le problème P

18
 PREUVE D ’O P T I M A L I T É

❖ Pour monter que l’algorithme glouton rend toujours une

solution optimale, il faut montrer que les deux

propriétés ( choix glouton et sous-structure

optimale) sont vérifiées.

❖ Pour montrer que l’algorithme glouton ne rend pas

toujours une solution optimale, il suffit de trouver un

contre-exemple.
19
 E X E M P L E 1: L E M O N N A Y E U R

❖ E = {8, 4, 2}:
➢ S est pair et S >1
Solution optimale existe si …………………………

➢ Algorithme G louton donne la solution optimale si elle

existe

❖ E = {5, 2}:
➢ S4
Solution optimale existe si ……….

➢
(S=6)
Algorithme Glouton ne la trouve pas toujours :…..…..

❖ E = {5, 4, 1}:
➢ existe toujours
Solution optimale ………..
23
22
➢ Algorithme Glouton trouve toujours la solution mais elle
(S=8)
n’est pas toujours optimale …………
 E X E M P L E 1: L E M O N N A Y E U R
P R E U V E D ’ OPTIMALITÉ

❖ Conclusion: Caractériser les jeux de pièces pour lesquels

l’algorithme glouton est optimal est un problème

ouvert. Il est facile de trouver des catégories qui

marchent (par exemple des pièces E ={1,B,B 2 ,B 3 } pour B ≥

2) mais le cas général résiste !

24
 E X E M P L E 2: O R D O N N A N C E M E N T D E S T Â C H E S

❖ Soit E = {1,..., n} un ensemble de n tâches.

❖ La tâche i commence à l’instant Di et finit à l’instant Fi.

❖ D eux tâches i et j sont compatibles si elles ne se

chevauchent pas (Dj  Fi) .

❖ B ut 1 : trouver un ensemble maximal de tâches

compatibles.

25
 E X E M P L E 2: O R D O N N A N C E M E N T D E S T Â C H E S

E 1 2 3 4 5 6 7 8 9
D 1 2 4 1 5 8 9 13 11
F 8 5 7 3 9 11 10 16 14

❖ Algorithme glouton:
Trier les tâches selon leur date fin
…………………………………………………………………….. et
sélectionner une tâche compatible
……………………………………………………………………..
par ordre croissant.
……………………………………………………………………..

26
E X E M P L E 2: O R D O N N A N C E M E N T D E S T Â C H E S

E 1 2 3 4 5 6 7 8 9
D 1 2 4 1 5 8 9 13 11
F 8 5 7 3 9 11 10 16 14

1. Trier les tâches selon leur date fin

E 4 2 3 1 5 7 6 9 8
D 1 2 4 1 5 9 8 11 13
F 3 5 7 8 9 10 11 14 16

2. Sélectionner les tâches compatibles par ordre croissant

E 4 2 3 1 5 7 6 9 8
D 1 2 4 1 5 9 8 11 13
F 3 5 7 8 9 10 11 14 16 27

Solution: Tâches 4, 3, 7, 9
 E X E M P L E 4: P R O B L È M E D E S A C À D O S E N T I E R

❖ Soit E = {1,..., n} un ensemble de n objets.

❖ Chaque objet i a un poids Pi et une valeur Vi. Il peut

être pris en entier et au plus une fois, i.e. 𝑵𝒃𝒊 ∈ {𝟎,

𝟏}.

❖ Soit un sac à dos de contenance maximale P max

❖ But : Maximiser la valeur totale des objets mis

dans le sac à dos 32

 E X E M P L E 4: P R O B L È M E D E S A C À D O S E N T I E R

❖ Algorithme Glouton: trier les objets selon un critère

donné et sélectionner un objet jusqu’à atteindre la
capacité maximale de sac à dos.

❖ Choix gloutons possibles

➢ choisir l’objet de plus grande valeur

➢ choisir l’objet le plus léger

➢ choisir l’objet dont le rapport valeur/poids est

maximal.
❖ Montrer que ces choix ne donnent pas de solution
33
optimale dans le cas où l’objet est pris en entier.
E X E M P L E 4: P R O B L È M E D E S A C À D O S E N T I E R

E 1 2 3
P 10 20 30
V 30 100 120
V/P 3 5 4

P max = 50 P max = 40 P max = 30

(220) (150) (130)
L’objet le plus N on (130) N on (130) Oui (130)
léger
L’objet de plus Oui (220) Oui (150) Non(120)
grande valeur
L’objet dont le 42
Oui (220) N on (130) Oui (130)
rapport V/P est
34
maximal
E X E M P L E 5: P R O B L È M E DE SAC À DOS FRACTIONNÉ

❖ Soit E = {1,..., n} un ensemble de n objets.

❖ Chaque objet i a un poids Pi et une valeur Vi. Il peut

être fractionné i.e. Nbi  [0, 1].

❖ Soit un sac à dos de contenance maximale P max

❖ B ut : M a ximiser la valeur totale des objets mis

dans le sac à dos

35
E X E M P L E 5: P R O B L È M E D E S A C À D O S F R A C T I O N N É

❖ Une solution S = (nb 1 , ...., nb n ) présente le nombre de

l’objet i (nbi  [0, 1])

❖ Algorithme glouton:

Trier les objets par ordre décroissant de leur rapport Vi/Pi.

Pour chaque objet, maximiser le nombre nbi  [0, 1] jusqu’à

atteindre la capacité maximale de l’objet.

37
E X E M P L E 5: P R O B L È M E D E S A C À D O S F R A C T I O N N É

E 1 2 3
P 10 20 30
V 30 100 120
V/P 3 5 4

P max = 50 P max = 40 P max = 30

(220) (180) (140)
L’objet le plus Non (170)
Non (210) Non (130)
léger
L’objet de plus Ou i (220) Non (170) Non (120)
grande valeur
L’objet dont le 45
Ou i (220) Ou i (180) Ou i (140)
rapport V/P
36
est maximal