25 - Programmation dynamique

⏪

⏬

⏩

1 - Limite

2 - Programmation dynamique

3 - découpe

4 - Mémoïsation

Nous avons déjà rencontré plusieurs façons de résoudre un problème.

Résolution par force brute : on y va franchement, on calcule tout, quitte à calculer les choses plusieurs fois. Calculer, calculer, calculer...

La force brute : image tirée du film HULK

Résolution par la stratégie gloutonne : on résoud le problème en ne s'intéressant qu'à un problème local immédiat. Cette sous-réponse reste définitive et va mener à un autre sous-problème et vers UNE solution finale, pas nécessairement la meilleure solution. Choisir et réduire, choisir et réduire, choisir et réduire, ...

La stratégie gloutonne : Mr Glouton préfère la malbouffe salée, puis la malbouffe sucrée et les crudités si vraiment il n'a pas le choix

Résolution par la stratégie Diviser pour Règner : on résoud le problème en le découpant en plusieurs sous-problèmes plus petits. On résoud chaque sous-problème puis on combine les résultats pour répondre à la question. Diviser - Régner - Combiner.

Imaginons qu'on veuille faire tourner Tux, la mascote de Linux :

On peut calculer les positions des pixels en faisant un peu de mathématiques, ou on peut utiliser la méthode diviser pour régner. Regardez le résultat :

On divise Tux en quatre zones et on les décale simplement dans le sens horaire :

Tux Illustration de la méthode diviser pour régner

On divise à nouveau chacune des 4 zones en 16 sous-zones. Et dans chaque zone, on décale les sous-zones dans le sens horaire :

Tux Illustration de la méthode diviser pour régner

On divise à nouveau chacune des 16 sous-zones en 4, soit 64 sous-sous-zones. Et dans chaque sous-zone, on décale les sous-sous-zones dans le sens horaire :

Tux Illustration de la méthode diviser pour régner

Et on continue :

Tux Illustration de la méthode diviser pour régner

Et on continue :

Tux Illustration de la méthode diviser pour régner

Et on continue :

Tux Illustration de la méthode diviser pour régner

Et encore et encore jusqu'à arriver à des sous-zones qui sont constituées uniquement de ... 1 pixel. Du coup, pas besoin de faire de rotation...

Et on continue :

Tux Illustration de la méthode diviser pour régner

Nouvelle stratégie aujourd'hui : la programmation dynamique. En image, ça donnera ceci :

Et en fin d'activité, vous comprendrez mieux comment je compte me reconvertir dans la production de planches de bois :

Logiciel nécessaire pour l'activité : -

Prérequis : au moins une autre stratégie de résolution : gloutonne ou diviser pour régner

Evaluation ✎ :

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - Limite des techniques vues jusqu'à présent

Imaginons que vous vouliez savoir s'il faut rester dans une file d'attente pour acheter une place de concert, ou si ce n'est plus la peine.

Seule manière de savoir : lire l'attitude des deux personnes juste devant vous.

Il faudra associer une valeur à l'incertitude des personnes d'obtenir une place pour ce concert.

0, c'est la certitude d'avoir une place : on est au gichet et on paye.
1 pourrait correspondre au fait de voir la personne qui vient de s'acheter la place.
ect... Plus cette valeur est grande, plus l'incertitude grandit.

Définissons une fonction nommée f() qui fonctionnerait de cette façon :

f(0) = 0 pour la personne d'indice 0 dans la file. Elle sait qu'elle va avoir sa place.
f(1) = 1 pour la personne d'indice 1 juste derrière dans la file

La file d'attente de Fibbonaci

Pour modéliser l'attitude des suivants, partons sur le fait qu'on additionne les incertitudes des deux personnes devant nous :

f(2) = f(1) + f(0)
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
f(5) = f(4) + f(3)
...

Cela se résume par formule suivante :

f(n) = f(n - 1) + f(n - 2)

01° Calculer f(5) en justifiant vos calculs.

02° Compléter la fonction Python f() dont le prototype est fourni pour qu'elle renvoie la bonne valeur d'incertitude d'achat du billet en fonction de la position n de la personne dans la file d'attente.

On impose la récursivité : il faut commencer par se demander quels sont les cas de base, puis de demander comment travailler s'il ne s'agit pas d'un cas de base.

def f(n:int) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci
 
    :: param n(int) :: entier, supérieur ou égal à 0
    :: return (int) :: la valeur de f(n)
    :: exemple ..
    >>> f(6)
    8
 
    """
    assert n >= 0
 
    pass
 
def test_fibonacci():
    assert f(0) == 0
    assert f(1) == 1
    assert f(2) == 1
    assert f(3) == 2
    assert f(4) == 3
    assert f(5) == 5
    assert f(6) == 8

Correction ?

...CORRECTION...

def f(n:int) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci
 
    :: param n(int) :: entier, supérieur ou égal à 0
    :: return (int) :: la valeur de f(n)
    :: exemple ..
    >>> f(6)
    8
 
    """
    assert n >= 0
 
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n-1) + f(n-2)
 
def test_fibonacci():
    assert f(0) == 0
    assert f(1) == 1
    assert f(2) == 1
    assert f(3) == 2
    assert f(4) == 3
    assert f(5) == 5
    assert f(6) == 8

03° Lancer les appels suivants pour voir l'évolution du temps de réponse :


>>> f(5)
5
 
>>> f(10)
55
 
>>> f(20)
6765
 
>>> f(30)
832040
 
>>> f(40)
102334155

Rapide ou pas ?

Regardons maintenant pourquoi cela devient rapidement si long avant que votre fonction ne réponde.

L'arbre d'appel de f(5)

04° Combien d'appels à la fonction f() va-t-on faire pour calculer f(2) ? Combien d'appels pour calculer f(3) ? Combien d'appels pour calculer f(4) ? Combien d'appels pour calculer f(5) ?

Correction ?

...CORRECTION...

Il suffit de compter les noeuds.

L'appel f(2) engendre 3 appels au total.

L'appel f(3) engendre 5 appels au total.

L'appel f(4) engendre 9 appels au total.

L'appel f(5) engendre 15 appels au total.

L'arbre d'appel de f(5)

05° Si on nomme nb_appels(n) le nombre d'appels nécessaires pour calculer la fonction f(n), quelle formule récursive peut-on utiliser pour calculer ce nombre d'appels avec comme précondition n > 1 ?

nb_appels(n) = ...

Calculer alors ce nombre d'appels pour f(6), f(7) et f(8).

Correction ?

...CORRECTION...

Il faut se demander comment faire chaque appel de fonction peut faire le travail en utilisant les autres....

Chaque fonction calculant le nombre d'appels devra renvoyer :

return 1 + nb_appels(n - 1) + nb_appels(n - 2)

De façon plus mathématique, on peut écrire :

nb_appels(n) = 1 + nb_appels(n - 1) + nb_appels(n - 2)

f(6) provoque donc 1 + 15 + 9 appels, soit 25 appels car

f(5) provoque 15 appels et
f(4) provoque 9 appels.

f(7) provoque donc 1 + 25 + 15 appels, soit 41 appels car

f(5) provoque 25 appels et
f(4) provoque 15 appels.

f(8) provoque donc 1 + 41 + 25 appels, soit 67 appels car

f(7) provoque 41 appels et
f(6) provoque 25 appels.

Pour vous donner une idée des valeurs suivantes :

f(9) provoque donc 1 + 67 + 41 appels, soit 109 appels car

f(8) provoque 67 appels et
f(7) provoque 41 appels.

f(10) provoque donc 1 + 109 + 67 appels, soit 177 appels car

f(9) provoque 109 appels et
f(8) provoque 67 appels.

f(11) provoque donc 1 + 177 + 109 appels, soit 287 appels car

f(10) provoque 177 appels et
f(9) provoque 109 appels.

f(12) provoque donc 1 + 287 + 177 appels, soit 465 appels car

f(11) provoque 287 appels et
f(10) provoque 177 appels.

Comme vous pouvez le voir cela augmente dangereusement vite...

Si on désire faire compter automatiquement le nombre d'appels avant la résolution du problème posé, il va falloir modifier un peu le programme.

Nous allons rajouter un paramètre optionnel de type muable de façon à ce que c augmente de 1 à chaque fois qu'on lance un appel à f(). De cette façon, nous aurons bien le nombre total d'appels.

def f(n, c=None):
    """Renvoie la bonne valeur de la suite de Fibonacci
     
    :: param n(int)  :: entier, supérieur ou égal à 0
    :: return (int)  :: la valeur de f(n)
    .. note          :: le paramètre par défaut c va devenir un tableau-compteur
    :: exemple ..
    >>> f(6)
    8
     
    """
    assert n >= 0
     
    if c == None:    # si c'est le 1er appel
        c = [1]      # on crée un tableau mono-case contenant 1
    else:            # si on a déjà des appels
        c[0] = c[0] + 1  # on incrémente le compteur
     
    print("Appel n° ", c[0])
     
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n-1, c) + f(n-2, c)

06-A° Placer la nouvelle fonction en mémoire. L'évolution du nombre d'appels semble-t-elle linéaire ? Que risque-t-il de se passer lorsqu'on voudra lancer le calcul avec un paramètre de grande valeur ?


>>> f(5)
 1
 2
 ...
 15
5
 
>>> f(10)
 1
 2
 ...
 177
55
 
>>> f(20)
 1
 2
 ...
 21891
6765

06-B° Qu'est-ce qui ralentit fortement vraiment ce programme avec traces pour le moment ?

06-C (maison)° Une autre façon de créer ce compteur : utiliser une fonction auxiliaire, locale à la fonction f().

Expliquer comment fonctionne maintenant la fonction f() qui utilise la fonction auxiliaire aux().

def f(n):
    """Renvoie la bonne valeur de la suite de Fibonacci
 
    :: param n(int)  :: entier, supérieur ou égal à 0
    :: return (int)  :: la valeur de f(n)
    .. note          :: le paramètre par défaut c va devenir un tableau-compteur
    :: exemple ..
    >>> f(6)
    8
 
    """
 
    def aux(n:int, c:list):
        """Fonction auxiliaire recursive pour ce calcul"""
        c[0] = c[0] + 1  # on incrémente le compteur     
        print("Appel n° ", c[0])
 
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return aux(n-1, c) + aux(n-2, c)
 
    assert n >= 0
    c = [1]  # on crée un tableau mono-case contenant 1
    return aux(n, c)

CONCLUSION TEMPORAIRE

On vient de voir que la force brute ne fonctionne pas dès que l'argument envoyé dépasse environ 30.

On ne peut pas utiliser la stratégie gloutonne car il ne s'agit pas d'un problème d'optimisation : il n'y a qu'une seule bonne réponse et pas plusieurs solutions plus ou moins bonnes.

On ne peut pas non plus utiliser la stratégie diviser pour régner car en réduisant le problème f(n) en deux sous-problèmes f(n-1) et f(n-2), on n'obtient pas deux sous-problèmes indépendants l'un de l'autre : le résultat de f(n-1) dépend en partie de f(n-2) !

Nous allons donc voir comment résoudre cette nouvelle catégorie de problème en utilisant une nouvelle statégie : la stratégie de la programmation dynamique.

2 - Programmation dynamique

Pour réduire les calculs, nous allons rajouter de l'intelligence plutôt que de passer par force brute. C'est là qu'intervient la programmation dynamique :

Illustration de la programmation dynamique

Principe général :

On analyse le problème de la recherche des sous-solutions imbriquées les unes dans les autres et on se demande quels sont les sous-problèmes à résoudre avant les autres.

On met en mémoire chaque sous-solution dès qu'on l'obtient. De cette façon, une fois que f(3) aura été calculée une première fois, il suffira d'aller relire le résultat plutôt que de relancer le vrai calcul !

Sur notre exemple avec f(5), cela donnerait donc l'arbre d'appels suivant :

Illustration de la programmation dynamique

Pour rappel, sans stockage des résultats, nous avions l'arbre suivant par notre calcul naïf :

L'arbre d'appel de f(5)

07° Répondre aux questions suivantes en analysant l'arbre des appels :

Illustration de la programmation dynamique

Combien d'appels au total cette fois pour f(5) ?
Après l'appel initial à f(5), faut-il calculer f(4) ou plutôt f(2) ?
Que faut-il faire ensuite ?

Pour réaliser cela, nous allons donc devoir stocker les résultats des sous-problèmes intermédiaires dans une mémoire temporaire qu'on nomme mémoire-cache. On peut prendre n'importe quelle structure de données muable en Python.

Tableau via le type list : avantage de la rapidité si on peut facilement attribuer un numéro à chaque sous-problème.
Dictionnaire via le type dict sinon.

08° Traduire en Français les lignes 3 à 8. Répondre ensuite à ces deux questions :

Expliquer ce que va contenir le tableau-mémoire-cache m une fois arrivé en ligne 10.
Pourquoi avoir mis n+2 ligne 6 ? Réflechir à un appel qui pourrait provoquer un problème avec juste n+1.

def f(n:int) -> int:
    """Renvoie la bonne valeur f(n) de la suite de Fibonacci"""
    assert n >= 0
     
    # création de la mémoire-cache
    m = [None for _ in range(n+2)]
    m[0] = 0
    m[1] = 1
     
    # remplissage de la mémoire-cache
    ...

09° Compléter la fonction f() pour créer la planification des appels en mode ascendant (croissant) : on calcule et place dans la mémoire-cache m d'abord "f"(2) puis "f"(3)... jusqu'à obtenir celui qui vous intéresse.

def f(n:int) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci"""
    assert n >= 0
     
    # créatiion de la mémoire-cache
    m = [None for _ in range(n+2)]
    m[0] = 0
    m[1] = 1
     
    # remplissage de la mémoire-cache
    for k in range(..., ...):
        m[k] = m[...] + m[...]
     
    # reponse
    return ...

Correction ?

...CORRECTION...

def f(n:int) -> int:
    """Renvoie la bonne valeur f(n) de la suite de Fibonacci"""
    assert n >= 0
     
    # création de la mémoire-cache
    m = [None for _ in range(n+2)]
    m[0] = 0
    m[1] = 1
     
    # remplissage de la mémoire-cache
    for k in range(2, n+1):
        m[k] = m[k-1] + m[k-2]
     
    # reponse
    return m[n]

10° Utiliser maintenant notre fonction pour vérifier qu'on puisse bien calculer f(40) ou plus.


>>> f(40)
?
 
>>> f(100)
?
 
>>> f(1000)
?
 
>>> f(10000)
?

Rapide ou pas ?

Question : quel est le coût de cette fonction en fonction de n ?

11° Traduire en Français les lignes de votre fonction (ou de la correction fournie si vous avez bloqué).

Programmation dynamique

Vocabulaire

Le mot Programmer s'entend ici sous le sens Planifier, Prévoir. Il n'y aucun lien avec le mot "coder".

Domaine d'utilisation

La stratégie de la programmation dynamique est utilisée lorsqu'on veut résoudre un problème

dont les sous-problèmes sont interdépendants (par exemple f(9) et f(10) vont devoir faire intervenir f(5) tous les deux)
dont la solution d'un sous-problème doit être utilisée pour résoudre le problème plus global (par exemple la solution de f(9) est utilisée pour trouver la solution de f(10))

Principe

La stratégie de la programmation dynamique consiste à planifier l'ordre de résolution des différents résultats intermédiaires pour ne jamais refaire deux fois la même chose.

A chaque fois qu'une sous-solution est trouvée, on l'enregistre dans une mémoire-cache de façon à pouvoir utiliser à nouveau directement le résultat lors de la résolution d'un autre sous-problème.

On ne parle pas de mémorisation mais de mémoïsation car les résultats intermédiaires ne seront en mémoire que le temps du calcul.

def f(n:int) -> int:
    """Renvoie la bonne valeur f(n) de la suite de Fibonacci"""i
    assert n >= 0
     
    # création de la mémoire-cache
    m = [None for _ in range(n+2)]
    m[0] = 0
    m[1] = 1
     
    # remplissage de la mémoire-cache
    for k in range(2, n+1):
        m[k] = m[k-1] + m[k-2]
     
    # reponse
    return m[n]

Quelques éléments supplémentaires

Cette stratégie a été introduite par Bellman, dans les années 1950, pour résoudre des problème d’optimisation.

On parvient ainsi à réduire la complexité temporelle au détriment de la complexité en espace-mémoire : on utilise de la mémoire pour éviter de reproduire de nombreuses fois le même calcul.

Il faut réflechir !

Oui et parfois, c'est d'ailleurs assez compliqué de trouver l'ordre de résolution à planifier. Si on ne parvient pas à trouver une méthode qui fonctionne à chaque fois, pas de panique : nous verrons dans la dernière partie une technique basée uniquement sur la mémoïsation, sans planifier directement les calculs. On lance et on mémoïse au fil de l'eau.

3 - Problème de la découpe

Voici un nouveau problème où encore une fois l'informatique intervient dans un domaine qui semble bien éloigné de l'informatique.

Troncs d'arbre

Une scierie récupère des troncs d'arbre de 10 mètres et plus pour en faire des planches.

Voici le prix des planches entières en fonction de la longueur de la planche :

Longueur (m)	1	2	3	4	5	6	7	8	9	10
Prix	1	5	8	9	10	17	17	20	24	30

Exemple : voici les différents choix qui s'offrent à nous pour des planches de 4m :

On vend une planche d'exactement 1m et on voit comment vendre au mieux les 3m restants

9 avec 🏿 et 🏾🏾🏾
7 avec 🏿 et 🏾🏾+🏾
7 avec 🏿 et 🏾+🏾🏾
4 avec 🏿 et 🏾+🏾+🏾

2² possibilités de gérer cette découpe. Si on réflechit un peu, on peut voir que si on savait déjà comment gèrer au moins les 3m, nous n'aurions pas eu besoin de tester toutes les possibilités.

On vend une planche d'exactement 2m et on voit comment vendre au mieux les 2m restants

10 avec 🏿🏿 et 🏾🏾
7 avec 🏿🏿 et 🏾+🏾

2¹ possibilités de gérer cette découpe.

On vend une planche d'exactement 3m et on voit comment vendre au mieux le m restant

9 avec 🏿🏿🏿 et 🏾

2⁰ possibilité de gérer cette découpe.

On vend directement d'exactement 4m.

9 avec 🏿🏿🏿🏿

Ce n'est pas une découpe.

Comme on le comprend, tester toutes les possibilités deviendrait rapidement trop long.

On retrouve certaines formules vues notamment sur les arbres binaires :

Avec 4 m : on a 2² + 2¹ + 2⁰, soit 2³ - 1 possibilités.
Avec 5 m : on a 2³ + 2² + 2¹ + 2⁰, soit 2⁴ - 1 possibilités.
Avec 5 m : on a 2⁴ + 2³ + 2² + 2¹ + 2⁰, soit 2⁵ - 1 possibilités.
Avec 20 m : on a 2²⁰ - 1 possibilités (1 048 575).

Or, si on réflechit un peu, on voit qu'on peut faire beaucoup moins de calculs si on tente de vendre une planche de 20 m :

Vendre une planche de 1m associée à la meilleure vente pour 19m.
Vendre une planche de 2m associée à la meilleure vente pour 18m.
Vendre une planche de 3m associée à la meilleure vente pour 17m.
...
Vendre une planche de 19m associée à la meilleure vente pour 1m.
Vendre une planche de 20m directement.

12° Résolution du problème 2m : quelle est la meilleure découpe à faire pour des planches de 2 mètres pour parvenir à vendre en récupérant le plus d'argent ?

Longueur (m)	1	2	3	4	5	6	7	8	9	10
Prix	1	5	8	9	10	17	17	20	24	30

Couper 1m et vendre deux planches de 1 m
Vendre une planche de 2m

13° Résolution du problème 3m : quelle est la meilleure découpe à faire pour des planches de 3 mètres ?

Longueur (m)	1	2	3	4	5	6	7	8	9	10
Prix	1	5	8	9	10	17	17	20	24	30

Nous allons utiliser le résultat précédent.

Vendre une planche d'un mètre et faire au mieux pour les deux mètres restants (voir question 12)
Vendre une planche de 2m et faire au mieux pour le mètre restant
Vendre directement une planche de 3m

14° Quelle est la meilleure découpe à faire pour des planches de 4 mètres ?

Longueur (m)	1	2	3	4	5	6	7	8	9	10
Prix	1	5	8	9	10	17	17	20	24	30

Nous allons utiliser le résultat précédent.

Couper 1m et vendre la planche d'un mètre et faire au mieux pour les trois mètres restants
Couper 2m et vendre cette planche de 2m et faire au mieux pour les deux mètres restants (voir question 12)
Couper 3m et vendre cette planche de 3m et faire au mieux pour le mètre restant (voir question 13)
Ne pas couper la planche et vendre une planche de 4m

15° Compléter maintenant la fonction meilleure_vente() qui doit renvoyer le meilleur prix de ventes d'une planche de longueur initiale taille, et devra travailler à partir du tableau des prix fourni.

meilleure_vente(prix:list, taille:int) -> int

Cette fonction est basée sur la programmation dynamique : on va d'abord chercher à mémoïser le meilleur prix de vente pour une planche initialement de 2m, puis une planche de 3m puis une planche de 4m...

Le paramètre prix est le tableau des prix où l'indice de la case doit correspondre à la taille des planches. Notez bien que l'indice 0 DOIT contenir 0 : une planche de 0m rapporte nécessairement 0 euro.

Exemple :

Indice/Longueur	0	1	2	3	4	5	6	7	8	9	10
Prix	0	1	5	8	9	10	17	17	20	24	30

Le paramètre taille est un entier : il correspond à la taille de la planche (l'unité étant le mètre). Ce paramètre est donc également l'indice permettant de retrouver le prix d'une telle planche entière.

Si vous bloquez (ce qui est probable, ce problème n'est pas trivial), vous pouvez vous aider des quelques indications supplémentaires sous le programme.

# Déclaration des constantes
 
LES_PRIX = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
 
 
# Déclaration des fonctions
 
def meilleure_vente(prix, taille):
    """Renvoie le meilleur prix de vente pour une taille donnée
 
    :: param prix(list)  :: un tableau d'entiers correspond aux prix des planches
    :: param taille(int) :: la taille de la planche (unité m)
    :: return (int)      :: le meilleur prix de vente qu'on puisse obtenir
    .. précondition 1    :: prix est un tableau d'entiers
                            - où l'indice correspond à la taille de la planche
                            - de taille 2 minimum
    .. précondition 2    :: taille < len(prix)                        
    """
 
    assert len(prix) >= 2
    assert taille < len(prix)
 
    # Création du cache "meilleure vente"
    m = ...  # On copie prix pour considérer juste les planches entières au début
 
    # Meilleure vente pour une planche de 1m, puis 2m... jusqu'à taille
    for planche in range(1, ...):
 
        # 1 - meilleure vente associée à une planche pleine au départ
        vente_max = ...
        print(f"Recherche pour une planche de {planche}m initialement à {m[planche]}")
 
        # 2 - on cherche la meilleure vente avec découpe ou pas.
        for decoupe in range(1, planche):       # pour chaque découpe initiale possible
 
            prix_decoupe  = prix[...]        # prix pour une telle decoupe entière
            vente_reste = m[... - ...]  # meilleure vente avec le reste de la planche
            if (... + ...) > vente_max:
                vente_max = ... + ...
            print(f"{decoupe} + {planche-decoupe} rapporte {prix_decoupe + vente_reste}")
 
        # 3 - on mémoïse la vente optimale pour cette longueur maintenant qu'on l'a connaît
        ...
        print(f"Meilleur prix pour une planche de {planche}m : {m[planche]}\n")
 
    # Réponse finale : meilleur vente pour une planche de la taille voulue
    return ...
 
 
# Programme
 
print(meilleure_vente(LES_PRIX, 10))

Indications supplémentaires

Ligne 24 : il s'agit de copier par compréhension. Surtout pas de création d'alias qui ne ferait que donner un deuxième nom au même tableau.
Ligne 27 : on veut aller réellement jusqu'à la recherche d'une planche de valeur taille. Attention donc à la valeur finale...
Ligne 30 : il s'agit de dire qu'au départ, on considère que le meilleur prix consiste à ne pas découper la planche. On prend donc le prix d'une telle planche entière.
Ligne 36 : de la même façon, on prix juste le prix de cette découpe "entière", sans chercher à l'optimiser.
Ligne 37 : on cherche le prix de vente optimum pour le reste de la planche après découpe. La taille étant plus petite, notre programmation / planification des sous-problèmes nous permet de voir qu'on dispose déja de cette sous-solution dans la mémoire-cache !
Ligne 38 Classique sur les recherches de maximum. On se demande si le nouveau prix de vente est meilleur que l'ancien. On remplace le maximum au besoin.
Ligne 43 Nous venons de terminer la recherche de la meilleure vente pour cette planche. Reste à mémoïser la valeur dans le cache m.
Ligne 47 Il suffit de savoir où se trouve la réponse dans le cache m.

Correction ?

...CORRECTION...

# Déclaration des constantes
 
LES_PRIX = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
 
 
# Déclaration des fonctions
 
def meilleure_vente(prix, taille):
    """Renvoie le meilleur prix de vente pour une taille donnée
 
    :: param prix(list)  :: un tableau d'entiers correspond aux prix des planches
    :: param taille(int) :: la taille de la planche (unité m)
    :: return (int)      :: le meilleur prix de vente qu'on puisse obtenir
    .. précondition 1    :: prix est un tableau d'entiers
                            - où l'indice correspond à la taille de la planche
                            - de taille 2 minimum
    .. précondition 2    :: taille < len(prix)                        
    """
 
    assert len(prix) >= 2
    assert taille < len(prix)
 
    # Création du cache "meilleure vente"
    m = [valeur for valeur in prix]  # On copie prix pour considérer juste les planches entières au début
 
    # Meilleure vente pour une planche de 1m, puis 2m... jusqu'à taille
    for planche in range(1, taille+1):
 
        # 1 - meilleure vente associée à une planche pleine au départ
        vente_max = prix[planche]
        print(f"Recherche pour une planche de {planche}m initialement à {m[planche]}")
 
        # 2 - on cherche la meilleure vente avec découpe ou pas.
        for decoupe in range(1, planche):       # pour chaque découpe initiale possible
 
            prix_decoupe  = prix[decoupe]        # prix pour une telle decoupe entière
            vente_reste = m[planche - decoupe]  # meilleure vente avec le reste de la planche
            if (prix_decoupe + vente_reste) > vente_max:
                vente_max = prix_decoupe + vente_reste
            print(f"{decoupe} + {planche-decoupe} rapporte {prix_decoupe + vente_reste}")
 
        # 3 - on mémoïse la vente optimale pour cette longueur maintenant qu'on l'a connaît
        m[planche] = vente_max
        print(f"Meilleur prix pour une planche de {planche}m : {m[planche]}\n")
 
    # Réponse finale : meilleur vente pour une planche de la taille voulue
    return m[taille]
 
 
# Programme
 
print(meilleure_vente(LES_PRIX, 10))

16° Quelle est la meilleure découpe à faire pour des planches de 9 mètres ?

Correction ?

...CORRECTION...

Il suffit de lancer l'appel en fournissant 9 en argument et de regarder la valeur finale.


>>> meilleure_vente(LES_PRIX, 9)
Recherche pour une planche de 1m initialement à 1
Meilleur prix pour une planche de 1m : 1
 
Recherche pour une planche de 2m initialement à 5
1 + 1 rapporte 2
Meilleur prix pour une planche de 2m : 5
 
Recherche pour une planche de 3m initialement à 8
1 + 2 rapporte 6
2 + 1 rapporte 6
Meilleur prix pour une planche de 3m : 8
 
Recherche pour une planche de 4m initialement à 9
1 + 3 rapporte 9
2 + 2 rapporte 10
3 + 1 rapporte 9
Meilleur prix pour une planche de 4m : 10
 
Recherche pour une planche de 5m initialement à 10
1 + 4 rapporte 11
2 + 3 rapporte 13
3 + 2 rapporte 13
4 + 1 rapporte 10
Meilleur prix pour une planche de 5m : 13
 
Recherche pour une planche de 6m initialement à 17
1 + 5 rapporte 14
2 + 4 rapporte 15
3 + 3 rapporte 16
4 + 2 rapporte 14
5 + 1 rapporte 11
Meilleur prix pour une planche de 6m : 17
 
Recherche pour une planche de 7m initialement à 17
1 + 6 rapporte 18
2 + 5 rapporte 18
3 + 4 rapporte 18
4 + 3 rapporte 17
5 + 2 rapporte 15
6 + 1 rapporte 18
Meilleur prix pour une planche de 7m : 18
 
Recherche pour une planche de 8m initialement à 20
1 + 7 rapporte 19
2 + 6 rapporte 22
3 + 5 rapporte 21
4 + 4 rapporte 19
5 + 3 rapporte 18
6 + 2 rapporte 22
7 + 1 rapporte 18
Meilleur prix pour une planche de 8m : 22
 
Recherche pour une planche de 9m initialement à 24
1 + 8 rapporte 23
2 + 7 rapporte 23
3 + 6 rapporte 25
4 + 5 rapporte 22
5 + 4 rapporte 20
6 + 3 rapporte 25
7 + 2 rapporte 22
8 + 1 rapporte 21
Meilleur prix pour une planche de 9m : 25
 
25

Good Job. Un vrai bucheron !

Troncs d'arbre — Jacques the woodcutter, tiré du site Alpe d'Huez

4 - Mémoïsation sans trop de planification

Hors Programme

La mémoïsation directe des résultats n'est pas au programme de T-NSI. Mais c'est un prolongement naturelle de la programmation dynamique et cela peut faire un beau sujet pour l'épreuve du grand oral.

Comme vous venez de le voir, la programmation dynamique consiste à se demander comment traiter et mémoriser peu à peu les sous-problèmes.

Or, parfois, il n'est pas si facilement que cela de savoir dans quel sens travailler.

Sur certains problèmes, il est même possible que la façon de planifier les sous-problèmes dépends des données...

Dans ce cas, on peut utiliser simplement la mémoïsation sans l'aspect planification :

On se crée une structure de données permettant de stocker les résultats
Lorsqu'on veut résoudre un sous-problème

Si la solution a déjà été trouvée et mémoïsée : on va juste lire la réponse dans la mémoire
Si la solution n'existe pas encore : on la calcule puis on la mémoïse

Comme sur un bloc-note...

La programmation dynamique utilise souvent une approche impérative (à boucle de boucle), la mémoïsation directe utilise souvent plutôt une approche récursive.

Nous allons reprendre notre recheche d'incertitude dans la File d'attente avec notre suite de Fibonacci. On va rajouter un paramètre m possédant une valeur par défaut qui va contenir la mémoire qui va stocker au fur et à mesure les résultats obtenus.

La file d'attente de Fibbonaci

f(n) = f(n - 1) + f(n - 2)

Les deux cas de base sont toujours f(0) = 0 et f(1) = 1.

17° Utiliser le programme ci-dessous pour répondre aux questions ci-dessous.

A l'aide d'une traduction en Français des lignes 01 et 12 à 17, expliquer ce que va contenir le tableau-mémoire-cache m lors du premier appel.
Expliquer ensuite le reste du fonctionnement (L19-L23).
Conclure sur le nombre d'appels en réfléchissant sur le nombre de cas de base disponibles au fur et à mesure des calculs

L'exemple donné ligne 14 vous permettra de voir qu'on ne désire pas une traduction "mot à mot".

def f(n, m=None):
    """Renvoie la bonne valeur de la suite de Fibonacci
 
    :: param n(int)  :: entier, supérieur ou égal à 0
    :: return (int)  :: la valeur de f(x)
    .. remarque      :: le paramètre m par défaut m à None va devenir un tableau-mémoire
    :: exemple ..
    >>> f(6)
    8
 
    """
    assert n >= 0
 
    if m == None:  # si c'est le 1er appel, il va falloir créer la mémoire-cache
        m = [None for _ in range(n+2)]
        m[0] = 0
        m[1] = 1
 
    if m[x] != None:
        return m[x]
    else:
        m[x] = f(x-1, m) + f(x-2, m)
        return m[x]

18° Réaliser une version où le cache est un dictinnaire où les clés sont les n déjà calculés et les valeurs associées les réponses f(n).

Correction ?

...CORRECTION...

def f(n:int, m=None) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci"""
    assert n >= 0
 
    if m == None:  # si le dictionnaire m n'existe pas encore
        m = {}     # on crée un cache-dictionnaire vide
        m[0] = 0   # on y place le fait que f(0) vaut 0
        m[1] = 1   # on y place le fait que f(1) vaut 1
 
    if n in m.keys():  # si n est déjà une clé du dictionnaire-mémoire
        return m[n]    # on renvoie cette solution depuis le cache
    else:
        m[n] = f(n-1, m) + f(n-2, m)  # on calcule et stocke cette solution
        return m[n]                   # on renvoie cette solution depuis le cache

Mémoïsation directe

Principe

La stratégie de la mémoïsation consiste à mémoriser temporairement en RAM les différents résultats intermédiaires pour ne jamais refaire deux fois la même chose.

Ce terme de mémoïsation a été introduit par Donald Michie en 1968 dans ces travaux de résolution des problèmes d’optimisation.

On parvient donc à réduire la complexité temporelle au détriment de la complexité en espace-mémoire : on utilise la ressource mémoire pour remplacer une partie de la ressource calcul du processeur.

def f(x:int, m=None) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci"""
    assert x >= 0
 
    if m == None:  # si c'est le 1er appel
        m = [None for _ in range(n+2)]
        m[0] = 0
        m[1] = 1
 
    if m[x] != None:
        return m[x]
    else:
        m[x] = f(x-1, m) + f(x-2, m)
        return m[x]

Mémoïsation plus longue

Plutôt que de tout recalculer, on peut aussi éventuellement placer la mémoire-cache en variable globale. De cette façon, tant que le programme est en marche, on garde trace de tous les calculs précédents.

# mémoire-cache de 200 cases
m = [None for _ in range(200)]
m[0] = 0
m[1] = 1
 
def f(x:int) -> int:
    """Renvoie la bonne valeur de la suite de Fibonacci"""
    assert x >= 0
 
    if m[x] != None:
        return m[x]
    else:
        m[x] = f(x-1) + f(x-2)
        return m[x]

Deux défauts importants :

Si on travaille avec des tableaux statiques, cela oblige en plus de choisir une taille maximale pour la mémoire-cache.
A manier avec précaution si cette mémoire-cache peut prendre une taille arbitrairement grande (on travaille avec des tableaux dynamiques ou des dictionnaires) et donc saturer la RAM.

C'est pour cela qu'on utilise très rarement cette technique. Et il s'agit d'une variable globale, on a donc toujours les mises en garde habituelles à avoir en tête.

Mémorisation réelle ?

On pourrait se demander pourquoi mettre la mémoire des calculs précédents en RAM plutôt qu'en mémoire de masse dans un fichier pour ne pas avoir à refaire les calculs à chaque fois qu'on redémarre le processus.

La réponse est simple : à cause du temps d'accès à la mémoire de masse.

Finissons avec la version mémoïsée de la découpe d'arbres.

20° Répondre aux questions après avoir regardé la fonction meilleure_vente().

Dans la mémoire-cache m, quelle valeur encode le fait qu'on n'ai pas encore déterminé la meilleure vente possible pour une longueur donnée ?
Quels sont les deux seuls cas où on pourra définir un cas de base pour le moment ?
Pourquoi n'a-t-on pas eu besoin de faire cela avec la programmation dynamique ? (nous avions juste initialisé m comme une simple copie de prix).
meilleure_vente() est-elle une fonction récursive ?

# Importation
 
import math
 
 
# Déclaration des constantes
 
LES_PRIX = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
 
 
# Déclaration des fonctions
 
def meilleure_vente(prix:list, taille:int) -> int:
    """Renvoie au final le prix maximum qu'on peut obtenir à partir des prix"""
 
    assert len(prix) >= 2
    assert taille < len(prix)
 
    m = [-math.inf for _ in range(len(prix))]  # on initialise les cases à -∞
    m[0] = 0        # on sait qu'une planche de 0m rapporte 0
    m[1] = prix[1]  # on sait qu'une planche de 1m n'est pas découpable
 
    return meilleure_vente_rec(prix, taille, m)
 
 
def meilleure_vente_rec(prix:list, taille:int, m:list) -> int:
    """Renvoie le prix maximum d'une planche de cette taille"""
 
    if m[taille] != -math.inf: # que veut dire cette condition d'arrêt ?
        return m[taille]
 
    else:
        # 1 - on fixe le prix à - l'infini pour cette taille
        vente_max = -math.inf
 
        # 2 - on cherche la meilleur vente pour différentes découpes
        for decoupe in range(1, ...):
 
            prix_decoupe = ...  # prix pour une telle decoupe entière
            vente_reste = meilleure_vente_rec(...)  # appel récursif
            if (...) > vente_max:
                vente_max = ...
 
        # 3 - on mémoïse le prix max pour cette longueur de planche
        ...
 
        # 4 - on répond à l'appel
        return ...
 
 
# Programme
 
print(meilleure_vente(LES_PRIX, 10))

20° Finaliser la deuxième fonction (qui elle est récursive) pour que votre programme fonctionne correctement.

Correction ?

...CORRECTION...

# Importation
 
import math
 
 
# Déclaration des constantes
 
LES_PRIX = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
 
 
# Déclaration des fonctions
 
def meilleure_vente(prix:list, taille:int) -> int:
    """Renvoie au final le prix maximum qu'on peut obtenir à partir des prix"""
 
    assert len(prix) >= 2
    assert taille < len(prix)
 
    m = [-math.inf for _ in range(len(prix))]  # on initialise les cases à -∞
    m[0] = 0        # on sait qu'une planche de 0m rapporte 0
    m[1] = prix[1]  # on sait qu'une planche de 1m n'est pas découpable
 
    return meilleure_vente_rec(prix, taille, m)
 
 
def meilleure_vente_rec(prix:list, taille:int, m:list) -> int:
    """Renvoie le prix maximum d'une planche de cette taille"""
 
    if m[taille] != -math.inf: # que veut dire cette condition d'arrêt ?
        return m[taille]
 
    else:
        # 1 - on fixe le prix à - l'infini pour cette taille
        vente_max = -math.inf
 
        # 2 - on cherche la meilleur vente pour différentes découpes
        for decoupe in range(1, taille + 1):
 
            prix_decoupe = prix[decoupe]  # prix pour une telle decoupe entière
            vente_reste = meilleure_vente_rec(prix, taille - decoupe, m)
            if (prix_decoupe + vente_reste) > vente_max:
                vente_max = prix_decoupe + vente_reste
 
        # 3 - on mémoïse le prix max pour cette longueur de planche
        m[taille] = vente_max
 
        # 4 - on répond à l'appel
        return vente_max
 
 
# Programme
 
print(meilleure_vente(LES_PRIX, 10))

Activité publiée le 22 03 2021
Dernière modification : 22 03 2021
Auteur : ows. h.

⏪

⏫

⏩