Cours Génie algorithmique
cours 6: Algorithmes de Gloutons (Greedy)
Dr. Dhouha Maatar Razgallah
2019/2020
Outline
Introduction
Principe général
Exemple 1: Monnayeur
Schéma général
Exemple 2: Ordonnancement des tâches
1
Algorithme de Glouton Introduction
Un algorithme de Glouton est un algorithme qui résout des problèmes
d’optimisation (comme les algorithmes de programmation dynamique).
Mais leur méthode est complètement différente.
C’est un algorithme qui cherche à construire une solution pas à pas.
En prenant à chaque étape la solution qui semble la meilleure localement
En espérant obtenir une solution optimale globale
Il cherche à 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.
3
Algorithme de Glouton Principe général
2
Algorithme de Glouton : le monnayeur
Problème:
On dispose des pièces de monnaie correspondant aux valeurs E ={e1,…, en}
Pour chaque valeur ei, le nombre de pièces de monnaie (nbi) est non borné
Etant 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,10, 2, 5} et s=28, Quelle est la solution optimale?
Une solution S=(nb1, …, nbn) présente le nombre de pièces (nbi) pour chaque
valeur (ei ):
Elle est correcte si
Elle est optimale si est minimale
Algorithme de Glouton : le monnayeur
Algorithme de Glouton:
Approche gloutonne: Trier les valeurs de pièces de monnaie par ordre décroissant.
Pour chaque valeur de pièce, maximiser le nombre de pièces choisies.
1ère version:
Trier E en ordre décroissant
Pour i de 1 à n faire
S[i] ← s div E[i]
s ← s mod E[i]
Finpour
3
Algorithme de Glouton: Schéma général:
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 S.
On travaille sur ‘’solution partielle’’ et on doit disposer des modules suivants:
Init : qui initialise la solution de début
Select: qui choisit à chaque pas 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.
Ajout possible?: qui teste si un élément peut être ajouté à une solution
partielle. Dans certain cas c’est toujours vrai.
Ajout: qui permet d’ajouter un élément à une solution si c’est possible. 7
Algorithme de Glouton : Schéma général
Schéma général Algorithme de Glouton:
Trier (E)
Init (S)
Tant que (Non Complete (S)) faire
Select (x, E)
Si AjoutPossible (x) Alors
Ajout (S, x)
finsi
Fintantque
4
Algorithme de Glouton : le monnayeur
Algorithme de Glouton:
2 ème version:
Trier (E) // en ordre décroissant
Init (S) // Initialiser la solution à 0 (nbi = 0)
i←1
Tant que(i <= n)faire //la solution est complète après avoir parcouru tous les éléments de E
//Select retourne E(i)
//Ajoutpossible est toujours vrai
S[i] ← s div E[i] // ajouter la solution
s ← s mod E[i]
i ++
Fintantque
Algorithme de Glouton : le monnayeur
Complexité Algorithme de Glouton:
Trier (E)
Init (S)
i←1
Tant que(i <= n)faire
S[i] ← s div E[i]
s ← s mod E[i]
i ++
Fintantque
10
5
Algorithme de Glouton : Ordonnancement des tâches
Problème:
Soit E ={1,…, n} un ensemble de n tâches.
La tâche i commence à l’instant Di et finit à l’instant Fi.
Deux tâches i, j sont compatibles si elles ne se chevauchent pas Fi <= Dj.
But : trouver un ensemble maximal de tâches compatibles.
Exemple:
Algorithme Glouton:
Approche gloutonne: On considère les tâches dans un certain ordre (Trier les tâches
selon leurs date fin) . On retient chaque tâche à condition qu’elle soit compatible
avec les tâches retenues (sélectionner une tâche compatible par ordre croissant).
11
Algorithme de Glouton : Ordonnancement des tâches
Solution:
12
6
Algorithme de Glouton : Ordonnancement des tâches
Schéma Glouton:
Trier (E, D, F) // trier les tâches selon ordre croissant de la date fin
S ← {E[1]}; j ← 1 // initialiser la solution
i←2
Tant que(i <= n)faire // la solution est complète après avoir parcouru tous les
éléments de E
// la tâche E[i] est sélectionnée
Si D[i] >= F[j] alors // si la tâche E[i] compatible aves la tâche E[j]
S ← S ᴗ E[i] // ajouter la solution
j←i
finsi
i++
Fintantque
13
