Aller au contenu principal
Objectifs
  1. Modéliser un problème d'optimisation sous forme de sous-problèmes ;
  2. Identifier la redondance des calculs dans une approche récursive naïve ;
  3. Mettre en place la mémoïsation pour obtenir un algorithme dynamique efficace ;
  4. Comparer la complexité avant et après optimisation.
TP

Les questions se répondent sur papier.
Le TP se fait sur Python.

TP3 — Le problème des découpes de planches

Contexte

La scierie Borges Jaumont, dans les Vosges, cherche à optimiser le prix de vente de ses planches.

À partir d'une planche de longueur donnée, l'entreprise peut la découper en plusieurs morceaux de longueurs entières. Chaque longueur a un prix de vente fixe, donné dans le tableau ci-dessous :

Longueur012345678910
Prix (€)01589101717202430

Objectif : déterminer comment découper une planche pour maximiser le revenu total.

Par exemple, une planche de longueur 4 vaut 9 € vendue entière, mais si on la découpe en deux morceaux de longueur 2, on obtient 5 + 5 = 10 €.

Exploration manuelle​

✏️Exercices
  1. 1

    En listant toutes les façons de découper une planche de longueur 3, compléter le tableau suivant :

    DécoupeCalcul du prixPrix total
    3p[3]8 €
    2 + 1p[2] + p[1]...
    1 + 1 + 1......
  2. 2

    Faire de même pour une planche de longueur 4. Combien de découpes différentes existe-t-il ?

  3. 3

    Quelle est la découpe optimale pour une planche de longueur 4 ? Justifier.

  4. 4

    En observant vos résultats, expliquer pourquoi ce problème peut se décomposer en sous-problèmes : comment le prix optimal d'une planche de longueur n dépend-il des prix optimaux de planches plus courtes ?

Approche récursive naïve​

✏️Exercices
  1. 1

    On note coupe(n) la fonction permettant d'obtenir le prix maximal pour une planche de longueur n. Quel est le cas d'arrêt de cette fonction récursive ?

  2. 2

    Si on fait une première coupe de longueur i dans une planche de longueur n, on obtient un morceau de longueur i et un reste de longueur n - i. Exprimer coupe(n) en fonction de coupe(n-i) et p[i].

  3. 3

    Dessiner un arbre d'appels récursifs pour coupe(4).

À observer

Repérer dans cet arbre les sous-problèmes qui sont calculés plusieurs fois.
C'est le cœur du problème de l'approche naïve.

  1. 4

    Compléter la fonction récursive coupe(n, p) ci-dessous :

    p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    def coupe(n: int, p: list)->int:
    if ... :
        return ...
    else:
        resultat = ...
        for i in range(..., ...) :
            resultat = max( ... , ... + ... )
        return ...
  2. 5

    Tester votre fonction avec coupe(4, p). Retrouve-t-on le résultat de la partie 1 ?

  3. 6

    Un employé exécute coupe(11, p) et obtient l'erreur : IndexError: list index out of range. D'où vient-elle ? Corriger le problème.

  4. 7

    Ce même employé tente coupe(30, p) et attend plus d'une heure. En vous appuyant sur l'arbre de la question 3, expliquer pourquoi cette approche est inefficace.

Approche dynamique par mémoïsation​

Principe de la mémoïsation

L'idée est simple : on ne calcule jamais deux fois la même chose.
Chaque fois qu'on calcule coupe(n), on stocke le résultat dans une liste mem.
Avant de calculer, on vérifie d'abord si le résultat est déjà connu.

✏️Exercices
  1. 1

    On initialise la mémoire grâce à l'instruction : mem = [0] * (n + 1). Que fait-elle ?

  2. 2

    Expliquer pourquoi la valeur 0 pourrait poser problème. Quelle valeur pourrait-on donner pour indiquer qu'une valeur n'a pas encore été calculée ?

  3. 3

    Schématiser le remplissage de mem pour coupe(4) en indiquant dans quel ordre les cases sont calculées et ce qu'elles contiennent à la fin.

    mem[0]mem[1]mem[2]mem[3]mem[4]
    0????
  4. 4

    Recopier et compléter le programme suivant permettant de résoudre le problème de découpe de planche en utilisant la mémoïsation :

    def planche_memo(n: int, p: list) -> int:
        """
        Crée la mémoire et retourne le prix optimal d'une planche de longueur n.
        """
        mem = ...  # Initialisation : -1 signifie "non calculé"
        return coupe_dyna(..., ..., ...)

    def coupe_dyna(n: int, p: list, mem: list) -> int:
        """
        Retourne le meilleur prix pour une planche de longueur n,
        en utilisant la mémoïsation.
        """
        if n == 0:
            return ...

        elif mem[n] != ...:  # Valeur déjà calculée ?
            return ...

        else:
            resultat = ...
            for i in range(..., ...):
                if i < len(p):
                    resultat = max(..., ...)

            mem[n] = ...
            return ...
  5. 5

    Tester planche_memo(30, p). Comparer le temps d'exécution avec la version naïve.

  6. 6

    Quel est l'ordre de grandeur de la complexité de cet algorithme ? La comparer avec la version naïve.

Pour aller plus loin (facultatif)​

✏️Exercices
  1. 18

    Modifier coupe_dyna pour qu'elle retourne non seulement le prix optimal, mais aussi la liste des longueurs correspondant à la découpe optimale.

  2. 19

    Tester votre fonction pour n = 4, 8, 10 et vérifier que les prix correspondent bien à vos calculs de la partie 1.

  3. 20

    Est-il possible que plusieurs découpes donnent le même prix optimal ? Donner un exemple.