next up previous


Exemples de programmation dynamique

G. Tremblay

Automne 1998

Calcul des nombres de fibonacci

Intuition (descendante) de la programmation dynamique:

Version récursive simple 


PROCEDURE fib( n: nat ): nat
DEBUT
      SI n = 0 || n = 1 ALORS
            RETOURNER 1
      SINON
            RETOURNER fib(n-1) + fib(n-2)
FIN

Complexité: O(2n)

Solution avec mémoisation (programmation dynamique descendante) 


PROCEDURE fib( n: nat ): nat
DEBUT
      dict <- new Dictionary()
      dict.insertItem( 0, 1 )
      dict.insertItem( 1, 1 )
      RETOURNER fib'( n, dict )
FIN


PROCEDURE fib'( n: nat, dict: Dictionary ): nat
DEBUT
      r <- dict.findElement( n )
      SI r != NO_SUCH_KEY ALORS
            // L'appel fib(n) a d'ej`a 'et'e calcul'e
            RETOURNER r
      FIN

      // Premier appel `a fib(n)
      r1 <- fib'( n-1, dict )   // dict peut ^etre modifi'e
      r2 <- fib'( n-2, dict )   // idem
      r  <- r1 + r2
      dict.insertItem( n, r )
      RETOURNER r
FIN
Complexité (temps): $O(n) * O(\rm temps\ \mbox{\tt findElement}\ \rm et/ou\ \mbox{\tt insertItem})$

Méthode de programmation dynamique plus classique

Intuition

=
Méthode ascendante
=
On construit, de façon ascendante (donc des problèmes simples vers les problèmes complexes), une table des solutions intermediaires 

PROCEDURE fib( n: nat ): nat
DEBUT
      a <- new nat[n+1]   // Table pour les solutions interm'ediaires
      a[0] <- 1           // Initialisation pour les probl`emes de base
      a[1] <- 1           // Idem.
      POUR i <- 2 A n FAIRE
        // Construction ascendante de la table
            a[i] <- a[i-1] + a[i-2]
      FIN
      RETOURNER a[n]
FIN
Complexité (temps): O(n)

Multiplication de matrices

Version diviser-pour-régner (pure)

L'algorithme qui suit est une version récursive utilisant la méthode diviser-pour-régner pour le problème du minimisation du nombre d'opérations pour la multiplication d'une chaîne de matrices (cf. section 12.3.1 du manuel).

Pour résoudre le problème de trouver le nombre optimal de multiplications requises pour multiplier les matrices A0, ..., An-1, on va calculer, pour tous les k possibles entre et n-1, le nombre optimal de multiplications pour faire le produit $A_0..A_k \times A_{k+1}..A_{n-1}$. On choisira ensuite le k qui minimise le nombre total de multiplications (= applications répétées de la stratégie diviser-pour-régner puis recherche de la solution minimale parmi les diverses solutions obtenues). 


PROCEDURE MatrixChain( d: sequence{nat} ): nat
ARGUMENTS
       Les matrices `a multiplier sont A0, ..., An-1 (non requises)
      La taille de la matrice Ai est donn'ee par d$_i
\times $di+1
PRE
       d = d0, d1, ..., dn-1, dn
DEBUT
     n <- length(d)-1
     RETOURNER MatrixChain'( d, 0, n-1 )
FIN


PROCEDURE MatrixChain'( d: sequence{nat}, i, j: nat ): nat
PRE
      i < j  &&  j+1 < length(d)
DEBUT
      minMulij <-  +INFINITY  // On va chercher le nombre minimum requis d'ops
      POUR k <- i A j-1 FAIRE
            // Diviser: on d'ecompose en 2 sous-probl`emes qu'on r'esout r'ecursivement
            nbMulik <- MatrixChain'( d, i, k )    // Sous-probl`eme r'ecursif
            nbMulkj <- MatrixChain'( d, k+1, j )  // Autre sous-probl`eme r'ecursif

            // Combinaison: on connait le nombre de multiplications requises pour les
            // deux sous-probl`emes. On les combine (avec +) et on ajoute
            // le nombre d'op'erations requises pour multiplier
            // les deux matrices qui r'esultent de cette d'ecomposition
            nbMulikj <- nbMulik + nbMulkj + d[i] * d[k+1] * d[j+1]

            // On v'erifie si ce nouveau r'esultat est le minimum
            SI nbMulikj < minMulij ALORS
                  minMulij <- nbMulikj
            FIN
      FIN

      // On a fait la division-combinaison pour tous les k possibles
      // et on a trouve le minimum: on retourne ce minimum comme resultat global
      RETOURNER minMulij 
FIN

Exemple

Supposons qu'on désire multiplier les matrices A0, A1, A2, A3, A4. Avec la méthode diviser-pour-régner na"ive indiquée plus haut, les appels récursifs à MatrixChain' seraient ceux indiqués à la figure 1. On voit clairement que certains de ces appels vont inévitablement se répéter (comme fibonacci), rendant l'algorithme inefficace.

Note: Le nombre de ``>'' devant une expression ``k = ?'' indique le niveau de la récursion. Les appels MC' sous une telle expression sont ceux (les deux appels) faits pour cette valeur de k donnee.


  
Figure 1: Exemple d'exécution pour MC'
\begin{figure} {\small \begin{verbatim} MC'( 0, 4 ) \gt k = 0 MC'(0, 0) MC'(1... ...C'(3, 4) ... \gt k = 3 MC'(0, 3) ... MC'(4, 4) ...\end{verbatim}}\end{figure}

Version récursive avec mémorisation

L'algorithme qui suit est une version récursive descendante avec mémorisation pour la solution avec programmation dynamique au problème du minimisation du nombre d'opérations pour la multiplication d'une chaîne de matrices (cf. section 12.3.1 du livre). 


PROCEDURE MatrixChain( d: sequence{nat} ): nat
ARGUMENTS
     Les matrices `a multiplier sont A0, ..., An-1
     La taille de la matrice Ai est d$_i
\times $ di+1
PRE
       d = d0, d1, ..., dn-1, dn
DEBUT
      n <- length(d)-1
      dict <- new Dictionary()
      POUR i <- 0 A n-1 FAIRE
            // On 'etablit les cas de base de la r'ecursion
            dict.insertItem( (i, i), 0 )
      FIN
      RETOURNER MatrixChain'( d, 0, n-1, dict )
FIN


PROCEDURE MatrixChain'(
     d: sequence{nat},
     i, j: nat,
     dict: Dictionary
     ): nat
DEBUT
      r <- dict.findElement( (i, j) )
      SI r != NO_SUCH_KEY ALORS
             RETOURNER r
      FIN
      // ASSERT: i < j
      minMulij <-  +INFINITY
      POUR k <- i A j-1 FAIRE
            nbMulik <- MatrixChain'( d, i, k, dict )
            nbMulkj <- MatrixChain'( d, k+1, j, dict )
            nbMulikj <- nbMulik + nbMulkj + d[i] * d[k+1] * d[j+1]
            SI nbMulikj < minMulij ALORS
                  minMulij <- nbMulikj
            FIN
      FIN
      dict.insertItem( (i, j), minMulij )
      RETOURNER minMulij 
FIN

Le problème de sac à dos à valeurs entières

Le problème du sac à dos est de maximiser le ``bénéfice'' pouvant être obtenu en remplissant un sac avec des items. À chaque item est associé un bénéfice (nombre réel) et un poids (une quantité entière). On doit remplir le sac à dos pour maximiser le bénéfice, mais sans dépasser un certain poids (= poids pouvant être conservé au maximum par le sac).

Dans le problème fractionnaire, on peut prendre une partie d'un item. Dans ce cas, on peut utiliser un algorithme vorace. On a vu en classe un exemple où l'approche vorace ne conduit PAS à un résultat optimal dans le cas où on doit prendre tout un item ou rien du tout (pas de fraction d'un item, d'où le nom "0-1": 0 = rien, 1 = tout).

Pour le problème 0-1, on doit donc utiliser une approche différente. Soit W le poids maximum pouvant être contenu par le sac. Soit n le nombre total d'items (on suppose que les items,, et les poids et bénéfices associés, sont numérotés 1, 2, ..., n).

La stratégie pour obtenir la solution maximale est de résoudre les sous-problèmes suivants:

Si on peut résoudre tous ces sous-problèmes, alors la solution optimale au problème initiale sera B[n, W]. Notons que ceci signifie qu'il faut, pour un poids W donné, calculer toutes les possibilités pour w = 1, 2, 3, ..., W!

De facon récursive descendante, diviser-pour-régner (non efficace!), on peut résoudre ce problème (grosso modo) comme suit (ici, on retourne simplement le bénéfice total resultant): 


PROCEDURE BeneficeSac( W: nat, poids: sequence{nat}, benefs: sequence{real} ): real
PRE
     length(poids) = length(benefs) = n
DEBUT
    RETOURNER BS'( n, W, poids, benefs )
FIN


PROCEDURE BS'(
     k: nat,
     w: nat,
     poids: sequence{nat},
     benefs: sequence{real}
     ): real
// Pour simplifier et refl'eter ce qui est dans le livre, on suppose 
// que les s'equences sont index'ees `a partir de 1 plutot que 0.
DEBUT
        SI w = 0 ALORS
              RETOURNER 0.0
        FIN
 
        SI poids[k] > w ALORS
              // Pour trouver la solution optimale pour un poids de w avec les
              // items 1 `a k, on ne doit pas  inclure l'item k pour un poids
              // restant w car son poids depasse w
              RETOURNER BS'( k-1, w, poids, benefs )
        SINON
              // ASSERT: poids[k] <= w
              // On peut donc inclure l'item k ... SI le b'en'efice en vaut la peine
              // On examine deux sous-probl`emes et on choisit celui qui
              // apporte le meilleur b'en'efice (inclure ou  pas l'item k)

              // 1: On n'inclut pas l'item k: w restant ne change donc pas
              b1 <- BS'(k-1, w, poids, benefs)

              // 2: On inclut l'item k: le poids restant est donc diminue
              b2 <- BS'(k-1, w - poids[k], poids, benefs) + benefs[k]
              RETOURNER max{b1, b2}
        FIN
FIN

About this document ...

Exemples de programmation dynamique

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split +0 -auto_navigation prog-dynamique.tex.

The translation was initiated by Tremblay Guy on 10/1/1999

next up previous
Tremblay Guy
10/1/1999