1Dé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.

2Exemple : 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 :
  1. Prendre la plus grande pièce possible : $2\text{€}$. Reste $1.70\text{€}$.
  2. Prendre la plus grande pièce possible : $1\text{€}$. Reste $0.70\text{€}$.
  3. Prendre la plus grande pièce possible : $0.50\text{€}$. Reste $0.20\text{€}$.
  4. 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 !")

3Zoom 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.

4Exercices 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
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)
Exercice 3 : Coloration de graphe

On veut colorier les sommets d'un graphe de sorte que deux sommets adjacents n'aient pas la même couleur, en minimisant le nombre de couleurs.

def coloration_gloutonne(graphe, sommets): # graphe[u] contient la liste des voisins de u couleurs_attribuees = {} for u in sommets: voisins_couleurs = {couleurs_attribuees[v] for v in graphe[u] if v in } couleur = 0 while couleur in : couleur += = couleur return # Jeu de tests g = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']} assert coloration_gloutonne(g, ['A', 'B', 'C']) == 2
Exercice 4 : Planification de tâches (Deadline 1)

On a des tâches qui durent toutes 1 heure. Chaque tâche a un profit. On veut maximiser le profit total en choisissant les meilleures tâches (une seule par créneau).

def max_profit_simple(taches): # taches est une liste de profits : [10, 50, 20, 40] # On veut choisir les tâches les plus rentables d'abord taches_triees = sorted(taches, ) profit_total = 0 nombre_max = # supposons 3 créneaux for i in range(): if i < len(): profit_total += return profit_total # Jeu de tests assert max_profit_simple([10, 50, 20, 40]) == 110 # 50 + 40 + 20
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)