Algorithme Glouton (Greedy Algorithm)

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)

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,

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];

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