Ecole Supérieure d’Economie Numérique
Algorithme Glouton (Greedy Algorithm)
Dr.Chiheb-Eddine Ben N’Cir
2015 − 2016
Outline
1 Algorithme Glouton
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
2 / 10
Algorithme Glouton: Principe
Algorithme Glouton
Construire au fur et à mesure une solution en faisant les choix qui paraissent
optimaux localement
Dans certains cas, cela donnera finalement la meilleure solution: on parlera
d’algorithmes gloutons exacts.
Dans d’autres, non, on parlera d’heuristiques gloutonnes.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
3
Publicité
3 / 10
Problème
Algorithme Glouton
On dispose des pièces de monnaie correspondant aux valeurs {a0, a1, ..., an−1}
avec 1 = a0 < a2 < ... < an−1.
Pour chaque valeur le nombre de pièces est non borné. Etant donnée une
quantité c entière, on veut trouver une façon de "rendre" la somme c avec un
nombre de pièces minimum.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
4
4 / 10
Solution 1
Algorithme Glouton
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
5
5 / 10
Solution 2
Algorithme Glouton
Chiheb-Eddine Ben N’Cir (ESEN)
Publicité
Algorithmique Avancée:
2015
6
6 / 10
Gestion des films
Algorithme Glouton
Un cinéma possède s salles de cinéma. Chaque semaine, le cinéma propose une
liste de films à voir. Chaque film correspond à une date de début et une date de fin
(intervalle de temps précis) qui sera diffusé dans la salle si. Les films n’ont pas tous la
même durée.
Un amateur de film (libre toute la journée) veut voir le maximum de films pendant cette
journée (il peut voir un même film plusieurs fois). Ecrire un algorithme qui permet de
résoudre le problème en utilisant le principe Glouton.
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
7
7 / 10
Modélisation du Problème
Algorithme Glouton
A = {a1, a2, .., an} =⇒ Tableau de n Films qui seront diffusés pendant une journée
chaque film ai est caractérisé par di, fi et numSi avec:
di date début du film ai,
Publicité
fi date fin du film ai,
numSi numéro de la salle qui diffuse le film ai
Film ai et aj sont compatibles si dj >= fi ou di >= fj
Problème: le plus grand nombre de films
choisir le plus grand nombre de films compatibles à voir
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
8
8 / 10
Algorithme Glouton
public Film choixFilm(Film [] A)
{
Film [] M; // M contient les films à voir pour maximiser le nombre
de film à regarder
trier(A); // trier le tableau de film selon la date de fin fi
M[0]=A[0];
int nbfilm=1;
int i=1;
While(i<A.length) {
if A[i].d < M[nbfilm-1].f
{
M[nbfilm]=A[i];
Publicité
nbfilm++;
}
i++
}
return M;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
9
9 / 10
Cadre générale d’un algorithme glouton
Algorithme Glouton
Pour mettre au point un algorithme glouton, il faut donc:
Trouver un critère objectif
Trouver un critère de sélection qui parait optimal: souvent facile
L’implémenter: en général facile et efficace!
Chiheb-Eddine Ben N’Cir (ESEN)
Algorithmique Avancée:
2015
10
10 / 10