Algo Prog Dynamique

Identification

Infoforall

23 - Programmation dynamique


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

Il y a d'abord la façon de programmer : la programmation itérative ou la programmation récursive.

Mais, en cours que cela, il y a l'approche générale de résolution. Nous avons déjà vu :

  • Résolution par force brute : on y va franchement, on calcule tout, quitte à calculer les choses plusieurs fois, voire à calculer des choses qui ne servent en rien à trouver la solution.
  • Illustration de la force brute avec Hulk contre un Tank
    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 optimale mais correcte.
  • Illustration de la méthode gloutonne
    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 le découpant un ensemble de problèmes plus petit. On résoud chaque sous-problème puis on combine les résultats pour répondre à la question.
  • Imaginons qu'on veuille faire tourner Tux, la mascote de Linux :

    Tux

    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és 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 :

Illustration de la programmation dynamique

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

1 - Principe de la programmation dynamique

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'attitude des personnes. 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. Plus cette valeur est grande, plus l'incertitude grandit. Définissons une fonction nommée fib qui fonctionnerait de cette façon :

  1.  fib(0) = 0  pour la personne d'indice 0 dans la file. Elle sait qu'elle va passer
  2.  fib(1) = 1  pour la personne 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 :

  •  fib(2) = fib(1) + fib(0
  •  fib(3) = fib(2) + fib(1
  •  fib(4) = fib(3) + fib(2
  •  fib(4) = fib(3) + fib(2

Cela se résume par formule suivante :

 fib(x) = fib(x-1) + fib(x-2

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

Regardons maintenant comment un programme pourrait faire pour trouver le même résultat, de façon naïve et par force brute.

L'arbre d'appel de f(5)

02° Combien d'appels à f(3) va-t-on faire ? Combien d'appels à f(2) va-t-on faire ?

...CORRECTION...

Il faudrait faire le calcul de f(3) deux fois et le calcul de f(2) trois fois.

L'arbre d'appel de f(5)

03° Comment va évoluer le nombre d'appels à f(3) si on recherche à la base une fonction avec un argument encore plus grand ?

...CORRECTION...

Il faudrait faire le calcul de f(3) deux fois et le calcul de f(2) trois fois.

L'arbre d'appel de f(5)

04° Fournir le code d'une fonction python dont voici le prototype qui renvoie la bonne valeur. On travaillera par récursivité.

1 2 3 4 5 6 7 8 9 10 11 12 13
def fib(x): '''Renvoie la bonne valeur de la série de Fibonacci :: param x(int) :: entier, supérieur ou égal à 0 :: return (int) :: la valeur de fib(x) :: exemple .. >>> fib(6) 8 ''' assert x >= 0 pass

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def fib(x): '''Renvoie la bonne valeur de la série de Fibonacci :: param x(int) :: entier, supérieur ou égal à 0 :: return (int) :: la valeur de fib(x) :: exemple .. >>> fib(6) 8 ''' assert x >= 0 if x == 0: return 0 elif x == 1: return 1 else: return fib(x-1) + fib(x-2) def test_fib(): assert fib(0) == 0 assert fib(1) == 1 assert fib(2) == 1 assert fib(3) == 2 assert fib(4) == 3 assert fib(5) == 5 assert fib(6) == 8

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

>>> fib(5) 5 >>> fib(10) 55 >>> fib(20) 6765 >>> fib(40) 102334155

Rapide ou pas ?

Si on désire compter le nombre d'appels pour résoudre le problème, il va falloir modifier un peu le programme : nous allons rajouter un paramètre de type mutable de façon à ce que n'importe quel appel puisse augmenter la valeur contenue de 1. De cette façon, nous aurons bien un compteur d'appels.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
def fib(x, c=None): '''Renvoie la bonne valeur de la série de Fibonacci :: param x(int) :: entier, supérieur ou égal à 0 :: return (int) :: la valeur de fib(x) .. note :: le paramètre par défaut c va devenir un tableau-compteur :: exemple .. >>> fib(6) 8 ''' assert x >= 0 if c == None: c = [0] c[0] = c[0] + 1 print(c[0]) if x == 0: return 0 elif x == 1: return 1 else: return fib(x-1, c) + fib(x-2, c)

06° 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 ?

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

C'est là qu'intervient la programmation dynamique :

Illustration de la programmation dynamique

Nous allons mettre en mémoire les résultats obtenus pour nos différents calculs : de cette façon, une fois que fib(3) aura été calculée par exemple, nous placerons le résultat en mémoire et nous n'aurons plus qu'à aller chercher le résulat en mémoire plutôt que de relancer tout le processus de calcul !

Sur notre exemple avec fib(5), cela donnerait donc les appels suivants :

Illustration de la programmation dynamique

07° Combien d'appels au total ?

08° L'arbre traduisant les appels successifs va-t-il être lu en préfixe, infixe ou suffixe/postfixe ?

Et voici la fonction correspondante : on a un paramètre m possédant une valeur par défaut qui va contenir le tableau-mémoire qui va stocker au fur et à mesure les résultats obtenus.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def fib(x, m=None): '''Renvoie la bonne valeur de la série de Fibonacci :: param x(int) :: entier, supérieur ou égal à 0 :: return (int) :: la valeur de fib(x) .. note :: le paramètre par défaut m va devenir un tableau-mémoire :: exemple .. >>> fib(6) 8 ''' assert x >= 0 if m == None: # on crée le tableau-mémoire m = [None for i in range(x+1)] m[0] = 0 m[1] = 1 if m[x] != None: return m[x] else: m[x] = fib(x-1, m) + fib(x-2, m) return m[x]

09° Expliquer le fonctionnement de cette fonction et comment elle parvient à mémoriser les valeurs déjà calculées.

Vocabulaire : Mémoïsation

Le terme utilisé pour cette mise en mémoire temporaire des résultats est mémoïsation, comme dans le fait de faire un mémo.

On ne parle pas vraiment de mémorisation car ces valeurs ne seront plus disponibles après que le premier appel réponde. On dit que les résultats sont mis dans une mémoire-cache temporaire.

10° Tracer l'arbre des appels pour fib(6) en tenant compte de la mémoïsation des résultats.

Déterminer le nombre d'appels nécessaires au total.

Regardons le nombre d'appels successifs en rajoutant à nouveau notre paramètre-tableau par défaut c servant de compteur d'appels.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
def fib(x, m=None, c=None): '''Renvoie la bonne valeur de la série de Fibonacci :: param x(int) :: entier, supérieur ou égal à 0 :: return (int) :: la valeur de fib(x) .. note :: le paramètre par défaut m va devenir un tableau-mémoire .. note :: le paramètre par défaut c va devenir un tableau-compteur :: exemple .. >>> fib(6) 8 ''' assert x >= 0 if m == None: # on crée le tableau-mémoire m = [None for i in range(x+1)] m[0] = 0 m[1] = 1 if c == None: # on crée le tableau-compteur c = [0] c[0] = c[0] + 1 print(c[0]) if m[x] != None: return m[x] else: m[x] = fib(x-1, m, c) + fib(x-2, m, c) return m[x]

11° L'évolution du nombre d'appels semble-t-elle linéaire maintenant ?

>>> fib(5) 1 2 ... 9 5 >>> fib(10) 1 2 ... 19 55 >>> fib(20) 1 2 ... 39 6765 >>> fib(40) 1 2 ... 79 102334155

Quelle formule donnant le nombre d'appels n en fonction de x semble se dégager ?

12° On voit donc qu'on parvient nettement à réduire la complexité en temps. Comme rien n'est magique, quel est le défaut ? Que pourriez-vous dire de la complexité en espace-mémoire ?

Programmation dynamique

Principe

La stratégie de la programmation dynamique consiste à planifier-programmer l'enregistrement des différents résultats intermédiaires de calculs de façon à ne jamais refaire deux fois la même chose.

Le mot programmation ne doit donc pas être vu comme le fait de "coder" mais comme le fait de planifier cet enregistrement.

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

On notera encore une fois qu'on utilise le mot mémoïsation car la mémorisation des résultats intermédiaires n'est que temporaire : il s'agit d'un compromis temps-méoire.

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

Il existe une différence fondamentale entre programmation dynamique et diviser pour régner : lors du diviser pour régner, les résolutions des différents sous-problèmes sont faites de façon indépendantes. La programmation dynamique est, elle, particulièrement efficace lorsque les sous-problèmes se recoupent : toutes les étapes de résolution sont potentiellement dépendantes d'un calcul fait précédemmemnt lors de la résolution d'une autre partie du problème.

Conditions d'utilisation

Quand peut-on utiliser cette méthode ? Lorsque la solution optimale d'un sous-problème fait bien partie de la solution globale.

Ici, cela n'apparaît pas clairement car avec la série de Fibonacci, il s'agit simplement de faire un calcul. Mais nous allons voir un deuxième problème où il s'agira effectivement d'optimer un résultat, sans passer par la force brute, trop longue et couteuse en ressources.

2 - Méthode ascendante ou descendante

Dans la résolution précédente, on lance f(5) et on se rend compte qu'on a besoin de f(4). Du coup, on calcule f(3)...

Il s'agit de la méthode descendante : on calcule au fil des besoins et on mémoïse les résultats pour la suite.

On se rend néanmoins bien compte que nous aurions pu planifier le tout dans l'autre sens : commencer par calculer f(2), de façon à calculer f(3) puis f(4) et enfin f(5).

Il s'agit de la méthode ascendante : on commence par s'occuper des problèmes les plus petits. Lorsqu'on atteint un problème de plus grande taille, nous avons déjà résolu tous les sous-problèmes de plus petite taille.

En fonction du problème, vous pouvez utiliser l'une ou l'autre. De bas en haut ou de haut en bas. Sauf cas particulier, elles donnent des résultats similaires.

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 moyen des planches qu'elle peut vendre actuellement en fonction de la longueur de la planche :

Longueur (m) 1234 5678 910
Prix 1589 10171720 2430

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

14° Quelle est la meilleure découpe à faire pour des planches de 3 mètres ? Utilisez le résultat de la question précédente pour connaître la découpe optimale pour moins de 3 mètres.

15° Quelle est la meilleure découpe à faire pour des planches de 4 mètres ? Utilisez les résultats des questions précédentes pour connaître la découpe optimale pour moins de 4 mètres.

16° Quelle est la meilleure découpe à faire pour des planches de 5 mètres ? Utilisez les résultats des questions précédentes pour connaître la découpe optimale pour moins de 5 mètres.

17° Quelle est la meilleure découpe à faire pour des planches de 6 mètres ? Utilisez les résultats des questions précédentes pour connaître la découpe optimale pour moins de 6 mètres.

18° Quelle est la meilleure découpe à faire pour des planches de 7 mètres ? Utilisez les résultats des questions précédentes pour connaître la découpe optimale pour moins de 7 mètres.

19° Expliquer comment fonctionne l'appel decoupe_optimale(prix, 7)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
import math prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] def decoupe_optimale(p, lg_max): '''Renvoie au final le prix maximum qu'on peut obtenir à partir des prix p''' m = [-math.inf for i in range(len(p))] m[0] = 0 m[1] = p[1] return dr(lg_max, p, m) def dr(lg, p, m): '''Renvoie le prix maximum d'une planche de longueur lg''' # dr pour découpe récursive if m[lg] != -math.inf: # condition d'arrêt return m[lg] else: # 1 - on fixe le prix à - l'infini pour cette lg prix_max = -math.inf # 2 - on cherche le prix pour les différentes découpes for i in range(1, lg+1): # prix_max = max(prix_max, p[i] + dr(lg-i, p, m)) # 3 - on mémoïse le prix max pour cette longueur de planche m[lg] = prix_max # 4 - on répond à l'appel return prix_max

20° Fournir une version descendante.

Good Job. Un vrai bucheron !

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

4 - FAQ

Rien pour le moment

Retenons donc qu'en fonction des problèmes, on peut utiliser :

  • la stratégie Diviser pour régner : lorsqu'on peut résoudre le problème en résolvant et combinant des sous-problèmes
  • la stratégie Glutonne : lorsqu'on se rend compte que la recherche de la solution exacte n'est pas possible et qu'on veut simplement une solution "correcte", pas nécessairement LA meilleure.
  • la stratégie de la programmation dynamique : lorsqu'on se rend compte que la résolution nécessite de résoudre de multiples fois les mêmes sous-problèmes.

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