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