Algorithmique

Cours 4 : Algorithmes gloutons

ROB3 – année 2017-2018

 Principe
● Diviser la résolution du problème en plusieurs étapes.
● A chaque étape, faire un choix localement optimal (choix
glouton), il ne sera ensuite pas remis en question dans la
résolution.
● Motivation : on espère que les choix localement optimaux
conduiront à une solution globalement optimale.

Pour certains problèmes cela marche, pour d'autres (la

plupart) cela ne marche pas.
Un premier exemple : les fractions
égyptiennes
Voici comment les Egyptiens écrivaient 1, 10 et 100 :

|=1 ⋂ = 10 = 100

Ils utilisaient uniquement des fractions comportant un 1 au

numérateur (fractions unitaires).

Exemple :

= 1/3 ⋂⋂⋂||| = 1/466

||| ⋂⋂⋂|||
 Fractions égyptiennes
Les fractions non unitaires sont décomposées en
fractions unitaires :
= 1/3+ 1/2

||| || = 2/6 + 3/6

= 5/6
= 1/4+ 1/10

|||| ⋂ = 5/20 + 2/20

= 7/20
 Formalisation
Soit r un nombre rationnel positif dans ]0,1[. Une représentation
en fraction égyptienne de r est une somme de fractions
unitaires distinctes qui est égale à r.

Théorème (Fibonacci 1202 ; Sylvester 1880)

Tout nombre rationnel positif dans ]0,1[ a une représentation en
fraction égyptienne.

Preuve.
Algorithme glouton !
 Algorithme glouton
Principe
Soustraire à la fraction donnée la plus grande
fraction unitaire possible, répéter l'opération avec
la nouvelle fraction, et ainsi de suite jusqu'à ce
que l'opération donne une fraction unitaire.
Exemple
51/105 = 1/3 + 16/105
= 1/3 + 1/7 + 1/105
 Terminaison
Lemme.
Soit p/q une fraction non unitaire dans ]0,1[. Soit 1/n la plus grande fraction ≤
p/q. Alors p/q – 1/n est une fraction r/s avec r<p.
Preuve.
p/q – 1/n = (np – q)/nq. Montrons que np – q < p.
Par l'absurde, supposons que np – q ≥ p.
En ajoutant q – p des deux côtés de l'inégalité, on obtient : np – p ≥ q.
Mais alors 1/(np – p) ≤ 1/q.
En multipliant des deux côtés par p, on obtient : p/(np – p) ≤ p/q.
Autrement dit : 1/(n – 1) ≤ p/q.
Comme p/q < 1, on en déduit n > 2. On a donc 1/(n-1) > 1/n.
Contradiction avec « 1/n la plus grande fraction ≤ p/q ».

En itérant le lemme jusqu'à ce que le numérateur soit égal à 1, on conclut que

l'algorithme glouton se termine en un nombre fini d'itérations (au plus p-1). La
terminaison de l'algorithme prouve la validité du théorème de Fibonacci-
Sylvester.
 Démoralisons le scribe...
Question.
Combien de termes peut comporter une fraction
égyptienne ?
Lemme.
Pour tout n≠0, 1/n = 1/(n+1) + 1/n(n+1)
Réponse.
En utilisant le lemme, on montre qu'une fraction
égyptienne peut comporter un nombre arbitrairement
grand de termes !
1 = ½ + 1/3 + 1/6
= ½ + 1/3 + 1/7 + 1/(6x7)
= ½ + 1/3 + 1/7 + 1/43 + 1/(42x43) = ...
 Décomposition optimale
Problème.
Etant donné un rationnel r, déterminer une représentation en
fraction égyptienne de r comportant un nombre minimum de
termes.
Question.
L'algorithme glouton retourne-t-il toujours une représentation
optimale ?
Réponse. Non ! Fournissons un contre-exemple.
Par l'algorithme glouton on trouve :
4/17 = 1/5 + 1/29 + 1/1233 + 1/3039345.
Mais il existe une meilleure décomposition :
4/17 = 1/5 + 1/30 + 1/510.
 Sélection d'intervalles
Application : réservation d'une salle.

Une salle municipale peut être réservée par

diverses associations. Chaque association indique
un intervalle durant lequel elle souhaite disposer
de la salle.

But : maximiser le nombre d'associations

satisfaites.
 Sélection d'intervalles
- L’intervalle
i commence en di et se termine en fi.
- Deux intervalles sont compatibles s’ils ne s’intersectent
pas.
- But : déterminer un sous-ensemble d’intervalles
mutuellement compatibles de taille maximale.

intervalles non compatibles

temps
 Principes gloutons
Algorithme générique : considérer les intervalles dans un
ordre spécifique. Prendre chaque intervalle dans cet ordre
s’il est compatible avec les intervalles déjà pris.

- L’intervalle le plus court d’abord : on considère les

intervalles par ordre de (fi - di) croissant.
- L’intervalle qui a le moins de conflits d’abord : pour
chaque intervalle i, soit ci le nombre d’intervalles avec
lesquels il est en conflit ; on considère les intervalles par
ordre de ci croissant.
- L’intervalle qui commence le plus tôt d’abord : on
considère les intervalles par ordre de di croissant.
- L’intervalle qui se termine le plus tôt d’abord : on
considère les intervalles par ordre de fi croissant.
 Principes gloutons
- L’intervalle le plus court d’abord : contre-exemple

- L’intervalle qui a le moins de conflits d’abord : contre-exemple

- L’intervalle qui commence le plus tôt d’abord : contre-exemple

 Celui qui se termine le plus tôt
d'abord
PlusPetiteDateDeFinDabord (n, d1 ,d2 , … , dn , f1 , f2 , … , fn )

Trier les intervalles par dates de fin t.q. f1 ≤ f2 ≤ … ≤ fn

IntervallesChoisis := ∅

Pour i allant de 1 à n
Si i est compatible avec IntervallesChoisis
IntervallesChoisis := IntervallesChoisis U {i}

Retourner IntervallesChoisis

Propriétés :
- On garde en mémoire l’intervalle k qui a été ajouté en dernier à IntervallesChoisis.
- L’intervalle j est compatible avec IntervallesChoisis ssi dj ≥ fk
- Du fait du tri, algorithme en O(n log n)

Cet algorithme retourne une solution optimale !

 Comment prouver qu'un algorithme
glouton est optimal ? (s'il l'est !)

Pour s'assurer qu'un algorithme glouton fournit une solution

optimale pour un problème, il faut montrer les propriétés
suivantes :
1. Propriété du choix glouton : il existe toujours une
solution optimale commençant par un choix glouton, c'est-
à-dire qu'un choix optimal local peut mener à une solution
optimale globale.
2. Propriété de sous-structure optimale : trouver une
solution optimale contenant le premier choix glouton se
réduit à trouver une solution optimale pour un sous-
problème de même nature.
 Propriété du choix glouton
Une façon de montrer cette propriété est de prendre une
solution optimale et de la transformer de manière à ce qu'elle
commence par un choix glouton, tout en restant optimale.

Soit i1,i2,...,ik les intervalles sélectionnés dans une solution

optimale.
Supposons que i1 n'est pas un choix glouton, autrement dit que
fi1>f1. Alors 1,i2,...,ik est également une solution réalisable
comportant k intervalles : elle est donc optimale et commence par
un choix glouton.

i1 i2 ... ik 1 i2 ... ik

1 1

fi1 fi1
Propriété de sous-structure optimale
Montrons qu'une solution optimale depuis la date 0, à
laquelle on ôte l'intervalle 1 (choix glouton), est une
solution optimale depuis la date f1.
Soit 1,i2,...,ik une solution optimale (contenant le premier
choix glouton 1).
Par l'absurde, supposons que i2,...,ik n'est pas optimale.
Soit j1,...,jp une solution optimale depuis f1, avec p>k-1.
Alors 1,j1,...,jp est réalisable avec p+1>k. Contradiction !

1 i2 ... ik 1 j1 ... jp-1 jp

j1 ... jp-1 jp j1 ... jp-1 jp

f1 f1
 Problème de sac à dos
● Plusieurs types :
- sac à dos en variables binaires
- sac à dos en variables fractionnaires

● L'algorithme glouton n'est pas optimal pour le

sac à dos en variables binaires

● L'algorithme glouton est optimal pour le sac à

dos en variables fractionnaires
 Définition du problème
● Un cambrioleur avec un sac à dos de
capacité W, et il peut dérober un
ensemble S de n objets
● Chaque objet i a un poids wi ∈ N et
rapporte vi ∈ N
● Problème : quel sous-ensemble d'objets
de S dérober pour maximiser le profit ?
 Sac à dos en variables binaires
● Les objets ne peuvent pas être divisés
– Un objet est sélectionné ou abandonné

 déterminer les xi dans {0,1} pour lesquels

 xivi est maximum

et  wixi  W

Si xi = 1, l'objet i est sélectionné

Si xi = 0, l'objet i est abandonné

 Le glouton n'est pas optimal

Objet 3 15 60€

Objet 2 25 +
10 50€
Objet 1 15
10 + 10 50€
5 5 30€

30€ 50€ 60€ W 80€ 110€

6€/kg 5€/kg 4€/kg

Choix glouton : Pas optimal

– Calculer le ratio €/kg
– Trier les objets selon ces valeurs
 Sac à dos en variables
fractionnaires
● Les objets peuvent être divisés
– On peut prendre une fraction d'un objet

 déterminer les xi dans [0,1] pour lesquels

 xivi est maximum

et  wixi  W

Si xi > 0, une fraction de l'objet i est sélectionnée

Si xi = 0, l'objet i est abandonné

 Le glouton est optimal

⅔
de 40€
Objet 3 15
+
Objet 2 25
10 50€
Objet 1 15
10 +
5 5 30€

30€ 50€ 60€ W 120€

6€/kg 5€/kg 4€/kg

Choix glouton : Optimal

– Calculer le ratio €/kg
– Trier les objets selon ces valeurs
– Prendre la plus grande fraction possible du dernier objet
sélectionné dans la liste
 Un autre exemple

 Objets : 1 2 3 4 5 6 7
 Profits : 5 8 3 2 7 9 4
 Poids : 7 8 4 10 4 6 4
 €/kg : 0.71 1 0.75 0.2 1.75 1.5 1
 Capacité du sac à dos : 22 kg
 Objet 5 (reste 18)

 Objet 6 (reste 12)

 Objet 2 (reste 4)

 Objet 7 (reste 0)
 Propriété du choix glouton
Une façon de montrer cette propriété est de prendre une solution optimale et de
la transformer de manière à ce qu'elle commence par un choix glouton, tout
en restant optimale.

Sans perte de généralité, on suppose que les objets sont indicés dans l'ordre des
ratios décroissants. Soit une solution optimale x avec x i1>0,...,xik>0 (i1<...<ik) et i1
> 1 (le choix glouton n'est donc pas inclus). Soit ŵ 1 = min {w1,W}. Considérons la
solution y obtenue à partir de x en retirant arbitrairement des fractions αi des objets
i1,...,ik du sac pour un poids total ŵ 1 afin de mettre une fraction ŵ1/w1 de l'objet 1 à
la place, autrement dit :
yi = 0 ∀i∉{1,i1,...,ik}
yi = xi-αi ∀i∈{i1,...,ik}
y1 = ŵ1/w1
avec αi≤xi ∀i∈{i1,...,ik} et ∑iαi = ŵ1. La différence ∑iyivi - ∑ixivi est égale à :
ik ik
v1 vi v1 vi
^ 1 −∑ αi
w ≥ w
^ 1 − max ∑α
w1 i=i wi 1
w1 i∈ {i ,... ,i } w i i=i i
1 k 1

v1 vi v1 vi
= w
^1
( − max
w 1 i∈{i ,..., i } wi
1 k
)
≥ 0 car
w1
≥
wi
∀ i∈{i1 ,... ,i k }

La solution y est donc optimale et contient le choix glouton.

 Propriété de sous-structure optimale
Montrons qu'un sac optimal auquel on retire l'objet 1 (choix glouton)
est optimal pour le problème P' défini sur les objets 2,...,n et une
capacité W-ŵ1.

Soit une solution optimale x avec x1=ŵ1/w1.

Par l'absurde, supposons que la restriction de x aux objets 2,...,n n'est pas
optimale pour P'. Soit y une solution optimale pour P'.
Alors la solution z telle que z1=x1, zi=yi pour i≠1 satisfait la contrainte de
capacité du sac à dos, avec ∑izivi > ∑ixivi puisque :

∑i≥2yivi > ∑i≥2xivi

∑izivi = x1v1+∑i≥2yivi
et ∑ixivi = x1v1+∑i≥2xivi

Contradiction avec l'optimalité de x !

 Codage de Huffman
● Données : une chaîne de caractères
(= fichier)
● Problème : encoder le fichier en un
nombre minimum de bits
(= compresser le fichier)
● Codage habituel : chaîne de bits de David Albert Huffman

longueur fixe pour chaque caractère

● Codage de Huffman : chaîne de bits de
longueur variable pour chaque
caractère
 Codage de Huffman
Idée : utiliser des codes plus courts pour les caractères
les plus fréquents et plus longs pour les caractères les
moins fréquents.
caractère a b c d e f nombre
de bits
fréquence 45 13 12 16 9 5

longueur 000 001 010 011 100 101 300

fixe

longueur 0 101 100 111 1101 1100 224

variable
 Comment décoder ?
● Avec un code de longueur fixe, c'est facile : fixe variable
– on découpe en sous-chaînes de longueur 3 a 000 0
b 001 101
Exemple :
001011100000000 c 010 100
d 011 111
b d e a a e 100 1101

● Avec un code de longueur variable, il faut s'assurer que le

code d'un caractère ne soit pas le préfixe d'un autre !
→ un code est appelé code préfixe si il vérifie cette propriété
– On décode alors de façon non ambigüe
Exemple :
101111110100
b d e a a
Comment créer un code préfixe ?

Idée : considérer un arbre binaire, avec :

0 signifiant descendre à gauche,
1 signifiant descendre à droite.

0 1
A
0 1
B
0 1
C D
Comment créer un code préfixe ?
Considérer les chemins depuis la racine vers
les feuilles A, B, C, D :

A:0 0 1
B : 10 A
C : 110 0 1
D : 111 B
0 1
C D

C'est un code préfixe car chaque feuille a un

unique chemin qui y mène et ne se prolonge pas.
 Code préfixe optimal
Problème : étant donnée une chaîne de caractères sur un
alphabet A={a1,...,an}, avec des fréquences f(ai), déterminer un
code préfixe qui minimise le nombre total de bits, qui s'écrit :

où c(ai) est le code de ai, et L(c(ai)) le nombre de bits dans

c(ai).
Remarque : L(c(ai)) correspond à la profondeur de c(ai) dans
l'arbre de codage.

Un code préfixe optimal (codage de Huffman) peut être

déterminé à l'aide d'un algorithme glouton.
 Algorithme glouton
Idée : Si on fait en sorte que les caractères les plus fréquents
soient proches de la racine, alors ils auront un code plus
court.

Algorithme
1. Considérer tous les couples : <f(ai),ai>.
2. Choisir les deux plus petites fréquences f(ai) et f(aj), et leur
donner un même parent dont la fréquence est f(ai)+f(aj).
3. Itérer jusqu'à obtenir un arbre binaire unique.
 Exemple

nombre total de bits : B(T) = 45x1 + 12x3 + 13x3 + 5x4 + 9x4 + 16x3 = 224
 Propriété du choix glouton
Soit x et y les caractères de plus faibles fréquences. Montrons qu'il existe
toujours un arbre de codage optimal où x et y sont frères et de profondeur
maximale.

Soit T un arbre de codage optimal, avec a et b deux frères de profondeur

maximale. Sans perte de généralité, on suppose f(a) ≤ f(b) et f(x) ≤ f(y).

On a : f(a) ≤ f(x) et f(b) ≤ f(y).

Soit T' l'arbre obtenu en échangeant a et x.

On a : B(T') = B(T) – f(a)d(a) + f(a)d(x) – f(x)d(x) + f(x)d(a)
= B(T) – (f(a) – f(x))(d(a) – d(x)) ≤ B(T)
car f(a) – f(x) ≥ 0 et d(a) – d(x) ≥ 0. Donc T' est optimal.
De même, en échangeant b et y dans T',
on obtient un arbre de codage T'' optimal.
Propriété de sous-structure optimale
Trouver un arbre optimal pour le problème P

revient à trouver un arbre optimal pour le

problème P' (obtenu après la fusion des arbres
de plus petits poids)

Il suffit de montrer qu'à tout arbre optimal pour P'

correspond un arbre optimal pour P.
Propriété de sous-structure optimale
● Soit c et d les caractères de plus petite fréquence dans P
● Soit T un arbre de codage optimal pour P
● Soit T' l'arborescence dérivée de T en substituant la feuille z au nœud
interne de fils c et d, avec f(z) = f(c) + f(d)

T optimal ⇒ T' optimal

Par l'absurde, supposons que T' n'est pas optimal, autrement dit :
∃ T'' pour P' tel que B(T'') < B(T').
Soit T''' l'arbre pour P obtenu à partie de T'' en substituant à la feuille z un nœud interne
avec deux fils c et d. On a : B(T''') = B(T'') + f(c) + f(d).
Or on a également : B(T) = B(T') + f(c) + f(d).
Par conséquent B(T'') < B(T') ⇒ B(T''') < B(T). Contradiction avec l'optimalité de T.