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 13 - 2023)

La fonction rendu_monnaie prend en paramètres deux nombres entiers positifs somme_due et somme_versee. Elle procède au rendu de la monnaie de la différence somme_versee – somme_due pour des achats effectués avec le système monétaire de la zone Euro. On utilise pour cela un algorithme glouton qui commence par rendre le maximum de pièces ou billets de plus grandes valeurs et ainsi de suite. Par la suite, on assimilera les billets à des pièces.

La fonction rendu_monnaie renvoie un tableau de type list contenant les pièces qui composent le rendu.

Toutes les sommes sont exprimées en euros. Les valeurs possibles pour les pièces sont donc contenues dans le tableau pieces = [1, 2, 5, 10, 20, 50, 100, 200].

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

En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.

Le code de la fonction rendu_monnaie est à compléter :

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

def rendu_monnaie(somme_due, somme_versee):

    rendu = ...
    a_rendre = ...
    i = len(pieces) - 1
    while ... :
        if pieces[i] <= a_rendre :
            rendu.append(...)
            a_rendre = ...
        else :
            i = ...
    return rendu

Exemples :

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

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.

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

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