1 Définition
Un algorithme glouton (greedy algorithm en anglais) est une méthode de résolution de problèmes d'optimisation.
Le principe est simple : à chaque étape, on fait le choix qui semble le meilleur sur le moment , sans jamais remettre en question les décisions passées.
Propriétés fondamentales :
Choix local : On prend le meilleur élément disponible immédiatement.
Pas de retour arrière : Une fois un choix effectué, on ne revient pas dessus.
Optimisation : On cherche à maximiser ou minimiser une valeur (profit, poids, distance, etc.).
Attention : un algorithme glouton produit une solution admissible , mais pas forcément optimale . Il est souvent efficace en temps de calcul, mais peut passer à côté de la meilleure solution globale.
2 Exemple : Le rendu de monnaie
Considérons un système de pièces : $\{2\text{€}, 1\text{€}, 0.50\text{€}, 0.20\text{€}, 0.10\text{€}\}$. Nous voulons rendre $3.70\text{€}$ avec le moins de pièces possible.
Stratégie gloutonne :
Prendre la plus grande pièce possible : $2\text{€}$. Reste $1.70\text{€}$.
Prendre la plus grande pièce possible : $1\text{€}$. Reste $0.70\text{€}$.
Prendre la plus grande pièce possible : $0.50\text{€}$. Reste $0.20\text{€}$.
Prendre la plus grande pièce possible : $0.20\text{€}$. Reste $0\text{€}$.
Total : 4 pièces. Dans ce cas particulier (système canonique), l'algorithme glouton donne la solution optimale.
def rendu_monnaie(somme, systeme):
pieces_rendues = []
i = 0
while somme > 0:
if systeme[i] <= somme:
pieces_rendues.append(systeme[i])
somme = round(somme - systeme[i], 2)
else:
i += 1
return pieces_rendues
# Tests avec assertions
assert rendu_monnaie(3.70, [2, 1, 0.5, 0.2, 0.1]) == [2, 1, 0.5, 0.2]
assert rendu_monnaie(0.80, [2, 1, 0.5, 0.2, 0.1]) == [0.5, 0.2, 0.1]
assert len(rendu_monnaie(10, [5, 2, 1])) == 2
print("Tests réussis !")
3 Zoom sur la fonction sorted()
De nombreux algorithmes gloutons nécessitent un tri préalable pour effectuer le "meilleur choix local". En Python, on utilise souvent sorted() avec l'argument key.
Exemple : Trier des dictionnaires
Imaginez une liste de fruits avec leur prix :
fruits = [{"nom": "pomme", "prix": 2}, {"nom": "ananas", "prix": 5}]
Pour trier par prix décroissant :
sorted(fruits, key=lambda x: x["prix"], reverse=True)
Le paramètre key prend une fonction (souvent une lambda) qui définit le critère de comparaison.
4 Exercices d'application
Complétez les lignes de code pour chaque algorithme glouton présenté ci-dessous.
Exercice 1 : Le problème du sac à dos (version continue)
On veut remplir un sac de capacité W avec des objets ayant un poids et une valeur. On choisit les objets ayant le meilleur rapport valeur/poids.
def sac_a_dos(objets, W):
# objets est une liste de dict [{'nom': 'A', 'v': 10, 'p': 2}, ...]
# On trie les objets par rapport v/p décroissant
objets_tries = sorted(objets, key=lambda x: , reverse= )
poids_total = 0
valeur_totale = 0
for obj in objets_tries:
if poids_total + obj['p'] <= :
poids_total += obj['p']
valeur_totale +=
else:
# On pourrait prendre une fraction de l'objet ici
return valeur_totale
# Jeu de tests
objets_test = [{'v': 10, 'p': 2}, {'v': 20, 'p': 5}]
assert sac_a_dos(objets_test, 10) == 30
assert sac_a_dos(objets_test, 3) == 10
Vérifier
Exercice 2 : Sélection d'activités
On dispose d'une salle et de plusieurs activités avec un début d et une fin f. On veut réaliser le maximum d'activités.
def selection_activites(S):
# S est une liste de tuples (debut, fin)
# On trie les activités par heure de FIN croissante
S_tries = sorted(S, key=lambda x: )
selection = [ ]
derniere_fin = S_tries[0][1]
for i in range(1, len(S_tries)):
if S_tries[i][0] >= :
selection.append( )
derniere_fin =
return
# Jeu de tests
activites = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
assert selection_activites(activites) == 3 # (1,4), (5,7), (8,9)
Vérifier
Exercice 5 : Remplissage de camions (Bin Packing simplifié)
On veut transporter des paquets pesant chacun un certain poids. Chaque camion a une capacite_max. On remplit le camion actuel autant que possible avant d'en prendre un nouveau.
Stratégie gloutonne :
On parcourt la liste des paquets. Si le paquet rentre dans le camion actuel, on l'ajoute. Sinon, on utilise un nouveau camion.
def compter_camions(paquets, capacite_max):
# paquets = [2, 5, 4, 7, 1] (poids de chaque paquet)
nombre_camions = # On commence avec un camion
poids_actuel = 0
for p in :
if poids_actuel + p <= :
poids_actuel +=
else:
nombre_camions += 1
poids_actuel =
return nombre_camions
# Jeu de tests
assert compter_camions([5, 5, 5], 10) == 2
assert compter_camions([2, 5, 4, 1], 10) == 2 # (2+5), (4+1)
Vérifier