Chapitre 16 : Algorithmes gloutons.

Introduction:

L'idée d'un algorithme glouton est simple : à chaque étape, il choisit la solution qui semble la meilleure sur le moment, sans regarder les conséquences futures. Il avance en prenant les décisions les plus optimales localement, en espérant que cela mènera à une solution optimale globale.

Mais cela pose une question : est-ce que ce qui paraît le meilleur choix à court terme est toujours le bon choix à long terme ? Si une décision immédiate semble bonne, peut-elle nous conduire vers un résultat sous-optimal par la suite ?

1. Les Algorithmes Gloutons

Les algorithmes gloutons sont une approche de résolution de problèmes qui consiste à faire des choix localement optimaux à chaque étape, dans l'espoir que ces choix mèneront à une solution globale optimale.

Les algorithmes gloutons fonctionnent en suivant un schéma simple :
1. À chaque étape, choisissez l'option qui semble la meilleure à ce stade, sans considérer les conséquences futures.
2. Effectuez ce choix et mettez à jour l'état du problème en conséquence.
3. Répétez les étapes 1 et 2 jusqu'à ce qu'une solution globale soit obtenue.
Voici quelques exemples d'algorithmes gloutons :
- L'algorithme du rendu de monnaie : Choisissez toujours la plus grande pièce de monnaie possible pour rendre la monnaie.
- L'algorithme de l'ordonnancement des tâches : Choisissez la tâche avec la durée la plus courte en premier.
- L'algorithme du sac à dos fractionnaire : Choisissez d'abord les objets qui ont la plus grande valeur par unité de poids.
Les algorithmes gloutons sont simples à mettre en œuvre et peuvent souvent donner des solutions acceptables rapidement. Cependant, ils ne garantissent pas toujours la meilleure solution globale et peuvent conduire à des solutions sous-optimales.

2. Problème du rendu de monnaie :

Le problème du rendu de monnaie est un problème d'algorithmique. Il s'énonce de la façon suivante : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ?

Par exemple, la meilleure façon de rendre 7 euros est de rendre un billet de cinq et une pièce de deux, même si d'autres façons existent (rendre 7 pièces de un euro, par exemple). On rencontre des problèmes similaires dans l'utilisation des boites à poids.

Ce problème est NP-complet dans le cas général, c'est-à-dire difficile à résoudre. Cependant pour certains systèmes de monnaie dits canoniques, l'algorithme glouton est optimal, c'est-à-dire qu'il suffit de rendre systématiquement la pièce ou le billet de valeur maximale — ce tant qu'il reste quelque chose à rendre.

Lien wikipedia

3. Exercice :

A faire dans le cahier.

Imaginons que dans un distributeur, il manque certaines pièces ou billets. Par exemple, il n'y a plus de billets de 5 euros.

Donner un exemple où un algorithme de rendu de monnaie de type gloutons va se tromper et ne pas trouver la solution optimale.

4. Exercice : (sujet 46 - 2025)

On considère dans cet exercice un algorithme glouton pour le rendu de monnaie. Pour rendre une somme en monnaie, on utilise à chaque fois la plus grosse pièce possible et ainsi de suite jusqu’à ce que la somme restante à rendre soit nulle.

Les pièces de monnaie utilisées sont :

pieces = [1, 2, 5, 10, 20, 50, 100, 200]

On souhaite écrire une fonction rendu_monnaie qui prend en paramètres :

un entier somme_due représentant la somme à payer ;
un entier somme_versee représentant la somme versée qui est supérieure ou égale à somme_due;
et qui renvoie un tableau de type list contenant les pièces qui composent le rendu de la monnaie restante, c’est-à-dire de somme_versee - somme_due.

Ainsi, l’instruction rendu_monnaie(452, 500) renvoie le tableau [20, 20, 5, 2, 1].

Compléter ce code et le tester.

Exemples :

>>> rendu_monnaie(700, 700)
[]
>>> rendu_monnaie(102, 500)
[200, 100, 50, 20, 20, 5, 2, 1]

# Pièces disponibles (en centimes d'euro) pieces = [1, 2, 5, 10, 20, 50, 100, 200] def rendu_monnaie(somme_due, somme_versee): '''Renvoie la liste des pièces à rendre pour rendre la monnaie lorsqu'on doit rendre somme_versee - somme_due''' rendu = ... a_rendre = ... i = len(pieces) - 1 while a_rendre > ...: while pieces[i] > a_rendre: i = i - 1 rendu.append(...) a_rendre = ... return rendu print(rendu_monnaie(452, 500))

Tests :

Affichage :

Console:

>>>

5. Exercice : Les boites (sujet 33 - 2025)

On dispose d’un ensemble d’objets dont on connaît, pour chacun, la masse. On souhaite ranger l’ensemble de ces objets dans des boites identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacité \(c\) de la boîte. On souhaite utiliser le moins de boîtes possibles pour ranger cet ensemble d’objets.

Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.

Par exemple, pour ranger dans des boîtes de capacité \(c = 5\) un ensemble de trois objets dont les masses sont représentées en Python par la liste [1, 5, 2] on procède de la façon suivante :

Le premier objet, de masse 1, va dans une première boite.
Le deuxième objet, de masse 5, ne peut pas aller dans la même boite que le premier objet car cela dépasserait la capacité de la boite. On place donc cet objet dans une deuxième boîte.
Le troisième objet, de masse 2, va dans la première boîte.

On a donc utilisé deux boîtes de capacité \(c = 5\) pour ranger les 3 objets.

Compléter la fonction Python empaqueter(liste_masses, c) suivante pour qu’elle renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble d’objets dont les masses sont contenues dans la liste liste_masses. On supposera que toutes les masses sont inférieures ou égales à c.

Exemples :

>>> empaqueter([1, 2, 3, 4, 5], 10)
2
>>> empaqueter([1, 2, 3, 4, 5], 5)
4
>>> empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11)
5

def empaqueter(liste_masses, c): """Renvoie le nombre minimal de boîtes nécessaires pour empaqueter les objets de la liste liste_masses, sachant que chaque boîte peut contenir au maximum c kilogrammes""" n = len(liste_masses) nb_boites = 0 boites = [0 for _ in range(n)] for masse in ...: i = 0 while i < nb_boites and boites[i] + ... > c: i = i + 1 if i == nb_boites: ... boites[i] = ... return ... liste = [1, 2, 3, 4, 5] contenance = 5 print(f"Il est nécessaire d'utiliser {empaqueter(liste, contenance)} boites.")

Tests :

Affichage :

Console:

>>>

6. Exercice : Algorithme glouton - Planning de salles

Un lycée doit organiser des activités dans une seule salle.

Chaque activité a une heure de début et une heure de fin (en minutes).

Deux activités sont compatibles si la première se termine avant ou au moment où la deuxième commence.

On veut choisir le plus grand nombre d activités possibles sans chevauchement.

On utilisera un algorithme glouton : à chaque étape, on choisit l'activité qui se termine le plus tôt parmi celles qui sont encore possibles.

Exemple :

activites = [
    ("A", 480, 540),  # 08:00 -> 09:00
    ("B", 525, 600),  # 08:45 -> 10:00
    ("C", 540, 570),  # 09:00 -> 09:30
]
# Une solution possible : ["A", "C"]

def selection_activites_glouton(activites: list) -> list: """ Selectionne un maximum d activites compatibles (sans chevauchement). Parametre : - activites : list de tuples (nom: str, debut: int, fin: int) * debut et fin sont en minutes depuis 0h00 * on suppose debut < fin Methode gloutonne attendue : 1) trier les activites par heure de fin croissante (fin la plus petite d abord) 2) prendre la premiere activite possible 3) puis parcourir les activites suivantes et choisir une activite si son debut est >= fin de la derniere activite choisie Retour : - list[str] : la liste des noms des activites selectionnees, dans l ordre choisi """ ... # Donnees de test activites_lycee = [ ("Maths", 8*60, 9*60), ("Francais", 8*60+30, 9*60+15), ("NSI", 9*60, 10*60), ("EPS", 9*60+30, 10*60), ("Anglais", 10*60, 10*60+45), ("Histoire", 10*60+30, 11*60+30), ("Physique", 11*60, 12*60), ("Chimie", 11*60+45, 12*60+15), ("SVT", 12*60, 12*60+30), ("Musique", 12*60+30, 13*60), ("Art", 13*60, 14*60), ("Theatre", 13*60+15, 14*60+30), ("Latin", 14*60+30, 15*60), ("Philo", 14*60+45, 16*60) ] planning = selection_activites_glouton(activites_lycee) print("Planning choisi :", planning) # Petit affichage lisible def hhmm(m: int) -> str: h = m // 60 mn = m % 60 return f"{h:02d}:{mn:02d}" # On reconstruit les intervalles des activites choisies pour visualiser dico = {nom: (debut, fin) for (nom, debut, fin) in activites_lycee} for nom in planning: debut, fin = dico[nom] print(f"{nom} : {hhmm(debut)} -> {hhmm(fin)}")

Tests :

Affichage :

Console:

>>>

7. Exercice : Algorithme glouton - Couvrir une route avec des capteurs

Une commune veut surveiller une route rectiligne de longueur L kilomètres, du point 0 au point L.

On peut placer un capteur à certaines positions. Un capteur placé en x couvre un intervalle :

de x - r à x + r,
où r est le rayon de couverture.

Objectif : choisir le minimum de capteurs pour couvrir entièrement la route [0, L].

Idée gloutonne :

On regarde le premier point non couvert de la route. Au début, c'est couvert = 0.
Parmi tous les capteurs dont l'intervalle commence avant ou au point couvert (donc debut <= couvert), on choisit celui qui va le plus loin vers la droite (plus grande valeur de fin).
On ajoute ce capteur à la solution, puis on met à jour couvert : il devient la nouvelle fin couverte.
On recommence jusqu à avoir couvert >= L.
Si à une étape aucun intervalle ne peut couvrir le point couvert, alors c'est impossible et on renvoie [].

Remarque : pour simplifier, on travaille directement avec les intervalles (debut, fin) calculés à partir des positions.

Exemple :

L = 10, r = 2, positions = [1, 4, 8]
intervalles = [(-1,3), (2,6), (6,10)]
# On peut couvrir toute la route avec 3 capteurs.

def construire_intervalles(positions: list, r: float) -> list: """ Transforme une liste de positions en une liste d intervalles (debut, fin). Parametres : - positions : list[float] - r : float Retour : - list[tuple[float,float]] : [(x-r, x+r), ...] """ return [(x - r, x + r) for x in positions] def couverture_glouton(L: float, positions: list, r: float) -> list: """ Selectionne un minimum de capteurs pour couvrir [0, L] avec un algorithme glouton. Parametres : - L : float - positions : list[float] - r : float Retour : - list[tuple[float,float]] : intervalles choisis dans l ordre - [] si impossible Methode (a suivre) : 1) Construire les intervalles (x-r, x+r) 2) Trier les intervalles par debut croissant, puis fin decroissante 3) couvert = 0 4) Tant que couvert < L : - parmi les intervalles dont debut <= couvert, choisir celui avec la plus grande fin - si on n en trouve aucun : return [] - ajouter l intervalle choisi - couvert = fin de l intervalle choisi """ intervalles = construire_intervalles(positions, r) # On trie les intervalles par début croissant et en cas d'égalité, par fin décroissante intervalles = sorted(intervalles, key=lambda t: (t[0], -t[1])) choix = [] couvert = 0 i = 0 n = len(intervalles) while couvert < L: # On cherche le meilleur intervalle qui commence avant (ou au) point couvert meilleur_fin = couvert meilleur_intervalle = None while i < n and intervalles[i][0] <= couvert: debut, fin = intervalles[i] if fin > meilleur_fin: meilleur_fin = ... meilleur_intervalle = ... i = i + 1 # Si on n a pas pu avancer, c est impossible if meilleur_intervalle is None: return ... choix.append(meilleur_intervalle) couvert = ... return choix # Donnees d essai L = 30 r = 6 positions = [2, 7, 11, 16, 21, 26, 29] print(f"L={L}, r={r}, positions={positions}") print("Intervalles :", sorted(construire_intervalles(positions, r))) choix = couverture_glouton(L, positions, r) print("Choix glouton :", choix) if choix != []: print("Nombre capteurs :", len(choix)) print("Premier debut :", choix[0][0]) print("Derniere fin :", choix[-1][1])

Tests :

Affichage :

Console:

>>>

8. Exercice : Algorithme glouton - Approvisionnement (packs uniques)

Un club de robotique prépare une compétition et doit acheter des packs de vis.

Le club doit obtenir au moins N vis. Il existe plusieurs packs disponibles, mais chaque pack ne peut être acheté qu'une seule fois.

Objectif : obtenir au moins N vis avec une stratégie gloutonne.

Stratégie gloutonne imposée :

Pour chaque pack (quantite, prix), on calcule le prix par vis : prix / quantite.
On trie les packs par prix par vis croissant (le meilleur en premier).
On parcourt les packs dans cet ordre et on décide de prendre le pack (1 fois) si cela aide à atteindre l'objectif.
On s arrête dès que l'on a au moins N vis.
Si on a parcouru tous les packs et que le total est encore strictement inférieur à N, alors c'est impossible et on renvoie [].

Exemple :

packs = [(50, 6.0), (20, 3.0), (10, 1.7)]  # (quantite, prix)
N = 70
# On peut prendre chaque pack au plus une fois.
# Le glouton prend d abord le meilleur prix/vis, puis continue.

def prix_par_vis(tup: tuple) -> float: """ Calcule le prix par vis d un pack. Parametre : - tup : tuple (quantite, prix) * quantite est un entier strictement positif * prix est un float strictement positif Retour : - float : prix / quantite Exemple : - prix_par_vis((40, 4.0)) renvoie 0.1 """ return ... def achat_glouton_packs_uniques(packs: list, N: int) -> list: """ Achete des packs de vis avec une strategie gloutonne (packs achetables au plus 1 fois). Parametres : - packs : list[tuple[int, float]] * chaque pack est (quantite, prix) * quantite > 0, prix > 0 * on ne peut acheter chaque pack qu une seule fois (0 ou 1) - N : int, nombre de vis souhaite (N >= 0) Strategie gloutonne imposee : 1) trier les packs par (prix/quantite) croissant, puis par quantite decroissante (pour etre deterministe) 2) total = 0 3) parcourir les packs dans cet ordre : - si total < N : prendre le pack (1 fois) et ajouter sa quantite a total - sinon : arreter 4) si total < N a la fin : renvoyer [] (impossible) sinon : renvoyer la liste des packs pris Retour : - list[tuple[int,float]] : la liste des packs pris (quantite, prix) dans l ordre du tri - [] si impossible - si N == 0 : renvoyer [] """ if N == 0: return ... packs.sort(key=lambda t: (prix_par_vis(t), -t[0])) ... def total_vis_packs(pris: list) -> int: """ Calcule le total de vis achetees a partir d une liste de packs (quantite, prix). """ s = 0 for (q, prix) in pris: s += q return s def cout_total_packs(pris: list) -> float: """ Calcule le cout total a partir d une liste de packs (quantite, prix). """ c = 0.0 for (q, prix) in pris: c += prix return c packs1 = [(50, 6.0), (20, 3.0), (10, 1.7), (5, 1.0)] N1 = 70 pris1 = achat_glouton_packs_uniques(packs1, N1) print("Pris 1 :", pris1) print("Total vis :", total_vis_packs(pris1)) print("Cout total :", cout_total_packs(pris1)) packs2 = [(12, 4.8), (30, 10.2), (8, 3.6)] N2 = 55 pris2 = achat_glouton_packs_uniques(packs2, N2) print("Pris 2 :", pris2) print("Total vis :", total_vis_packs(pris2)) print("Cout total :", cout_total_packs(pris2)) packs3 = [(40, 10.0), (30, 9.0), (25, 7.5)] N3 = 100 pris3 = achat_glouton_packs_uniques(packs3, N3) print("Pris 3 :", pris3) print("Total vis :", total_vis_packs(pris3)) print("Cout total :", cout_total_packs(pris3))

Tests :

Affichage :

Console:

>>>