Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Algorithmes gloutons

Au programme de la classe de première

Contenus Capacités attendues Commentaires
Algorithmes gloutons Résoudre un problème grâce à un algorithme glouton. Exemples : problèmes du sac à dos ou du rendu de monnaie. Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale.

Documents

Sous-sections de Algorithmes gloutons

Physique, Chimie et Informatique > Terminales Spé. NSI > Algorithmes gloutons

Le rendu de monnaie

Un client achète un objet qui coûte 53 euros. Il paye avec un billet de 200 euros. Il faut donc lui rendre 147 euros, par exemple un billet de 100, deux billets de 20, un billet de 5 et une pièce de 2.

Pour minimiser le nombre de pièces (on confond dans ce document les pièces et les billets) à rendre, on peut choisir la stratégie suivante :

  • On commence par rendre la pièce de plus grande valeur possible ;
  • On déduit cette valeur de la somme (encore) à rendre ;
  • On recommence, jusqu’à obtenir une somme nulle.

En procédant ainsi, on se rend compte que l’on résout le problème étape par étape et qu’un choix optimal est fait à chaque étape (la pièce de plus grande valeur). Cette stratégie entre donc bien dans la catégorie des algorithmes gloutons.

  1. Préparer la partie de code suivante :
if __name__ == "__main__":
    # valeurs des pièces
    pieces = [1, 2, 5, 10, 20, 50, 100]

    prix = int(input("Quel est le prix ? "))
    client = int(input("Combien le client donne-t-il ? "))

    a_rendre = somme_a_rendre(prix, client)
    comment = pieces_a_rendre(a_rendre, pieces)

    reponse = [f"{comment[i]} piece(s) de {pieces[i]}" for i in range(len(pieces))]
    print(f"Je dois rendre : {a_rendre}")
    print(f"Je donne donc : {reponse}")
  1. Définir la fonction somme_a_rendre dont la spécification est :
def somme_a_rendre(prix: int, client: int) -> int:
    """
    Détermine la somme à rendre à partir du prix et du montant donné par
    le client.
    """
  1. Définir la fonction pieces_a_rendre dont la spécification est :
def pieces_a_rendre(somme: int, pieces: list[int]) -> list[int]:
    """
    Détermine les pièces (et leur nombre) à choisir pour rendre la somme
    passée en argument.
    Utilise la division euclidienne et le modulo de façon à pouvoir
    traiter tous les cas.
    """
  1. Tester le programme.
24 janv. 2021
Physique, Chimie et Informatique > Terminales Spé. NSI > Algorithmes gloutons

Le problème du sac à dos

Introduction

Dans ce document, on s'intéresse à une classe de problèmes d'optimisation connus sous le nom général de « problème du sac à dos ». On peut définir ce problème de la manière suivante : *« durant un cambriolage un voleur possède un sac dont la capacité (en poids par exemple) est limitée. Il se trouve face à un ensemble d'objets qu'il veut dérober. Chacun de ces objets est caractérisé par sa valeur et son poids. Le voleur souhaite optimiser la valeur totale des objets qu'il dérobe tout en ne dépassant pas le poids maximal supporté par son sac ».*

Ce problème est une abstraction pour un grand nombre d’autres problèmes d’optimisation. Il a été utilisé en cryptographie comme base pour différents schémas de chiffrement1. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs. ^1, il est utilisé lors du chargement des bateaux ou d’avions, lors de la découpe de matériaux (minimisation des coupes « chutes » lors de la découpe), etc.

Problème étudié

On considère un sac à dos de masse maximale m=40 kgm = \pu{40 kg} dans lequel on souhaite ranger les objets dont les caractéristiques sont données ci-dessous :

Objet A B C D E F
Masse 13 12 8 10 14 18
Valeur 700 500 200 300 600 800

Quels objets faut-il sélectionner de façon à ce que la valeur totale, dans le sac à dos, soit maximale ?

Méthode de résolution approchée : stratégie gloutonne

Info
  1. Rappeler ce qu’est une stratégie gloutonne.

    Réponse
    À retenir

    Les algorithmes gloutons forment une catégorie d’algorithmes permettant de parvenir à une solution pour un problème d’optimisation qui vise à maximiser/minimiser une quantité (plus court chemin (GPS), plus petite durée d’exécution, meilleure organisation d’un emploi du temps, etc.)

    Le principe d’un algorithme glouton est le suivant :

    • Résoudre un problème étape par étape ;
    • À chaque étape, faire le choix optimal de moindre coût (de meilleur gain).

    Le choix effectué à chaque étape n’est jamais remis en cause, ce qui fait que cette stratégie permet d’aboutir rapidement à une solution au problème de départ. C’est en ce sens que l’adjectif greedy (glouton/avare) caractérise cet algorithme : il se termine rapidement (glouton) sans fournir beaucoup d’efforts (avare).

  2. Dans la partie principale du programme, définir la liste objets dont les membres sont des dictionnaires représentant les différents objets du problème.
    Chacun de ces dictionnaires doit posséder les clés nom, masse, valeur associées aux valeurs.

    Solution
    if __name__ == "__main__":
        objets = [
            {"nom": "A", "masse": 13, "valeur": 700},
            {"nom": "B", "masse": 12, "valeur": 500},
            {"nom": "C", "masse": 8, "valeur": 200},
            {"nom": "D", "masse": 10, "valeur": 300},
            {"nom": "E", "masse": 14, "valeur": 600},
            {"nom": "F", "masse": 18, "valeur": 800},
        ]

  3. Définir la variable masse_max et lui affecter la valeur 40.

    Solution
    masse_max = 40

Le principe de la stratégie gloutonne consiste à ajouter en priorité les objets « les plus efficaces ». « Plus efficace » ne signifie pas « plus grande valeur » mais « plus grande valeur comparativement à la masse ».

Avant d’appliquer l’algorithme glouton, il est nécessaire de trier la liste objets. Définir la fonction suivante :

def tri_objets(objets: list[dict]) -> list[dict]:
    """
    Trie la liste de dictionnaires selon les rapports valeur/masse.
    """

    def recupere_rapports(objet):
        return objet["valeur"] / objet["masse"]

    objets_tries = sorted(objets, key=recupere_rapports)

    return objets_tries
  1. Quel concept propre à la programmation fonctionnelle la fonction sorted met-elle en œuvre ?

    Solution

    Une fonction en Python peut être passée comme argument à une autre fonction.

  2. Décrire précisément la structure et le comportement de la fonction tri_objets.

  3. Affecter, dans la fonction main, le résultat de l’appel de la fonction tri_objets à la variable objets.
    Afficher à l’écran la liste triée.

    Solution
    objets = tri_objets(objets)
    print(f"Objets utilisables : {objets}", end="\n")

Remarque.
Ne pas oublier d’appeler la fonction main.
  1. Définir la fonction construction_sac_a_dos dont la spécification est :
def constrution_sac_a_dos(
    objets_tries: list[dict], masse_max: float
) -> tuple[list[str], int, int]:
    """
    Construction du sac à dos à partir d'une stratégie gloutonne.
    HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
    valeurs/masses.

    Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés,
    de la valeur du sac à dos et de la masse du sac à dos.
    """
Solution
def constrution_sac_a_dos(
    objets_tries: list[dict], masse_max: float
) -> tuple[list[str], int, int]:
    """
    Construction du sac à dos à partir d'une stratégie gloultonne.
    HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
    valeurs/masses.

    Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés,
    de la valeur du sac à dos et de la masse du sac à dos.
    """
    masse_sac = 0
    valeur = 0
    liste_objets = []

    i = len(objets_tries) - 1  # Compteur
    while i >= 0:
        objet = objets_tries[i]  # objet est un dictionnaire
        if (masse_sac + objet["masse"]) <= masse_max:
            valeur += objet["valeur"]
            masse_sac += objet["masse"]
            liste_objets.append(objet["nom"])

        i -= 1  # Décrémentation du compteur

    return (liste_objets, valeur, masse_sac)
  1. Affecter, dans la partie principale du programme, le tuple retourné par la fonction construction_sac_a_dos aux variables sac_a_dos,valeur et masse_sac.

    Solution
    sac_a_dos, valeur, masse_sac = constrution_sac_a_dos(objets, masse_max)

  2. Afficher le résultat :

print("Stratégie gloutonne")
print("-------------------")
print(f"Constitution du sac à dos : {sac_a_dos}")
print(f"Masse du sac à dos : {masse_sac}")
print(f"Valeur du sac à dos : {valeur}")
print()

Extension : Méthode de résolution exacte

Si on ne prend pas en compte, dans un premier temps, les contraintes, il est possible d’établir la liste des combinaisons possibles des objets à l’aide d’un arbre d’exploration binaire.

Par exemple, voici ce à quoi cet arbre ressemble lorsqu’on prend en compte les trois premiers objets :

graph TD
V("" ) --- A
V --- V1((" "))
A --- C(("A,B"))
C --- D(("A,B,C"))
C --- E(("A,B"))
A --- F(("A"))
F --- G(("A,C"))
F --- H(("A"))
V1 --- I(("B"))
I --- J(("B,C"))
I --- K(("B"))
V1 --- V2((" "))
V2 --- L(("C"))
V2 --- M((" "))

Les combinaisons s’obtiennent en parcourant l’arbre du sommet jusqu’à chaque extrémité : on obtient alors un vecteur dont on peut calculer la poids et la valeur. Il suffit alors de retenir celui dont la masse est inférieure à la masse maximale et dont la valeur est alors maximale.

  1. Au niveau de chaque nœud à quoi correspond le chemin « gauche » : objet retenu ou objet non retenu ?

    Réponse

    Objet retenu.

  2. Compléter l’arbre avec l’objet D.

  3. Si on implémente un algorithme mettant en œuvre la technique présentée ici, on trouve comme solution [A,C,F][A,C,F]. Vérifier que cette solution est meilleure que celle donnée par l’algorithme glouton.
    Pourquoi cette méthode n’est cependant pas utilisable la plupart du temps ? Quel est le nombre de combinaisons possibles ?

    Réponse

    Le nombre de combinaisons est 2n2^n où nn est le nombre d’objets. Cette croissance exponentielle rend l’algorithme exact beaucoup trop lent.

  4. Écrire le code de la fonction masse_sac dont la spécification est :

def masse_sac(objets: list[dict[str, str]], liste_obj: list[int]) -> int:
    """
    Calcule la masse du sac pour la liste d'objets retenus liste_obj.
    """
  1. Écrire le code de la fonction calcul_valeur_sac dont la spécification est :
def calcul_valeur_sac(objets: list[dict[str, str]], liste_obj: list[int]) -> int:
    """
    Calcule la masse du sac pour la liste d'objets retenus liste_obj.
    """
  1. Écrire le code suivant :
def recherche_recursive(
    objets: list[dict[str, str]], masse_max: isinstance, list_obj: list[int], i: int
) -> list[int]:
    """
    Détermine le chemin de l'arbre de décision correspondant à la valeur optimale
    pour une masse du sac déterminée.
    """
    if i == len(objets):
        return list_obj[:]

    val1 = -1  # Initialisation à une valeur impossible du poids
    if objets[i]["masse"] <= masse_max - masse_sac(
        objets, list_obj
    ):  # Ajoute objet si m_sac - m_inter > 0
        list_obj[i] = 1
        sol1 = recherche_recursive(objets, masse_max, list_obj, i + 1)
        val1 = calcul_valeur_sac(objets, sol1)

    list_obj[i] = 0  # On n'ajoute pas l'objet
    sol2 = recherche_recursive(objets, masse_max, list_obj, i + 1)
    val2 = calcul_valeur_sac(objets, sol2)

    if val1 > val2:
        return sol1[:]
    else:
        return sol2[:]
Examiner cette fonction