Programmation dynamique

Hicham EL YAHYAOUY

CPGE Tanger
Lycee Moulay EL-Hassan
[email protected]
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plan

1 Introduction

2 Principe générale

3 Problème : Plus longue sous-chaîne commune (LCS)

4 Programmation Dynamique Vs Glouton vs Diviser pour régner

Programmation dynamique 1 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Introduction

C’est une des plus vieilles techniques pour produire des algorithmes exacts, plus efficaces que
l’énumération exhaustive.
Principe (Bellman, 1949)
Composer une solution optimale du problème en combinant les solutions (optimales) de ses
sous-problèmes.
Décomposer le problème en des sous-problèmes plus petits ;
Calculer les solutions optimales de tous ces sous-problèmes et les garder en mémoire.
Calculer la solution optimale à partir des solutions optimales des sous-problèmes.

Programmation dynamique 2 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Introduction

Le problème est que dans certaines situations, les sous-problèmes ne sont pas indépendants. On
peut alors retrouver un même sous-problème dans des appels récursifs différents.
Et donc être amené à le résoudre plusieurs fois car dans cette approche dès qu’un sous-problème est
rencontré il est résolu.

Programmation dynamique 3 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Introduction

Le problème est que dans certaines situations, les sous-problèmes ne sont pas indépendants. On
peut alors retrouver un même sous-problème dans des appels récursifs différents.
Et donc être amené à le résoudre plusieurs fois car dans cette approche dès qu’un sous-problème est
rencontré il est résolu.
Exemple : Rappelons la formule de récurrence définissant la suite de Fibonacci :

 0 si n = 0
un = 1 si n = 1
un−1 + un−2 si n ≥ 2


Programmation dynamique 3 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Introduction
pour n=5 :

Programmation dynamique 4 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Introduction
pour n=5 :

Programmation dynamique 5 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Principe générale

Remarque 1
On peut alors constater que plusieurs appels sont réalisés avec une même valeur du paramètre. On fait
par exemple ici 5 appels à la fonction avec un paramètre égal à 2.

Programmation dynamique 6 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Principe générale

Remarque 1
On peut alors constater que plusieurs appels sont réalisés avec une même valeur du paramètre. On fait
par exemple ici 5 appels à la fonction avec un paramètre égal à 2.
On réalise ainsi un grand nombre d’opérations inutiles car redondantes. Celles-ci sont très coûteuses et
expliquent la complexité exponentielle de cet algorithme.

Programmation dynamique 6 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Principe générale

Remarque 1
On peut alors constater que plusieurs appels sont réalisés avec une même valeur du paramètre. On fait
par exemple ici 5 appels à la fonction avec un paramètre égal à 2.
On réalise ainsi un grand nombre d’opérations inutiles car redondantes. Celles-ci sont très coûteuses et
expliquent la complexité exponentielle de cet algorithme.

Solution : Pour éviter ces appels récursifs redondants et coûteux, il suffit d’avoir une idée
relativement simple :
On mémorise les résultats des sous-problèmes affin de ne pas les recalculer plusieurs fois.
Cela n’est bien sûr possible que si les sous-problèmes sont dépendants.
Cela signifie donc que ces sous-problèmes ont des sous-sous-problèmes communs.

Programmation dynamique 6 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Deux types de solutions "dynamiques"

Pour ce faire, et donc éviter de recalculer plusieurs fois les solutions des mêmes sous-problèmes, on
va mémoriser ces solutions dans une sorte de mémoire cache (liste ou dictionnaire).
Cette technique porte le nom de programmation dynamique, et sa mise en pratique peut prendre
deux formes :
Une forme récursive "Top down" dite de mémoïsation :
On utilise directement la formule de récurrence.
Lors d’un appel récursif, avant d’effectuer un calcul on regarde dans le tableau de mémoire cache si ce
travail n’a pas déjà été effectué.

Programmation dynamique 7 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Deux types de solutions "dynamiques"

Pour ce faire, et donc éviter de recalculer plusieurs fois les solutions des mêmes sous-problèmes, on
va mémoriser ces solutions dans une sorte de mémoire cache (liste ou dictionnaire).
Cette technique porte le nom de programmation dynamique, et sa mise en pratique peut prendre
deux formes :
Une forme récursive "Top down" dite de mémoïsation :
On utilise directement la formule de récurrence.
Lors d’un appel récursif, avant d’effectuer un calcul on regarde dans le tableau de mémoire cache si ce
travail n’a pas déjà été effectué.
Une forme itérative "Bottom Up" :
On résout d’abord les sous problèmes de la plus "petite taille", puis ceux de la taille "d’au dessus", etc.
Au fur et à mesure on stocke les résultats obtenus dans le tableau de mémoire cache.
On continue jusqu’à la taille voulue.

Programmation dynamique 7 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Solution Top Down

Notre mémoire cache sera ici une liste unidimensionnelle. Rappelons que son rôle va être de
mémoriser les résultats des sous-problèmes de tailles inférieures à celui du problème à résoudre.
Pour la suite de Fibonacci, si l’on veut calculer le terme d’indice n, il nous faudra ainsi mémoriser les
termes d’indices 0, 1, ..., n − 1. Cette liste aura donc n + 1 éléments.
Voici la fonction déclarant cette liste, nommée track, et réalisant le premier appel de la fonction
récursive qui effectuera le calcul :

1 def Fibo_DPTD ( n ) :
2 track = [ None ]*( n +1)
3 return Fibo_rec_DPTD (n , track )
 

Programmation dynamique 8 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Solution Top Down

A suivre à présent la fonction récursive en elle-même :


1 def Fibo_rec_DPTD (n , track ) :
2 if n ==0 or n ==1:
3 track [ n ]= n
4 return n
5 elif track [ n ] not None :
6 return track [ n ]
7 else :
8 track [ n ]= Fibo_rec_DPTD ( n - 1 , track ) + Fibo_rec_DPTD ( n - 2 , track )
9 return track [ n ]
 

Programmation dynamique 9 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Solution Top Down

A suivre à présent la fonction récursive en elle-même :


1 def Fibo_rec_DPTD (n , track ) :
2 if n ==0 or n ==1:
3 track [ n ]= n
4 return n
5 elif track [ n ] not None :
6 return track [ n ]
7 else :
8 track [ n ]= Fibo_rec_DPTD ( n - 1 , track ) + Fibo_rec_DPTD ( n - 2 , track )
9 return track [ n ]
 
Il s’agit quasiment de la même fonction récursive. La seule différence réside dans la condition
”elif track[n] ! = None”. Elle permet de vérifier dans la mémoire cache si le terme en question de la
suite à déjà été calculé ou non. Si oui on le retourne et la fonction prend fin, sinon on le calcule
récursivement, on stocke sa valeur dans la mémoire cache et on la retourne.
La complexité de cette fonction n’est plus exponentielle comme dans sa première version mais
linéaire.

Programmation dynamique 9 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Solution Top Down

Cette complexité s’estime également en étudiant l’arbre des appels récursifs :

Programmation dynamique 10 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Solution Buttom up

Puisqu’elle a le même rôle, il est logique que la mémoire cache soit comme dans le cas Top Down
une liste à n + 1 éléments. La différence est que cette liste ne vas plus se remplir récursivement, en
partant de la valeur n et en décrémentant jusqu’à 0 ou 1, mais itérativement, en partant cette fois de
0 et 1 et en incrémentant jusqu’à n.
Voici la fonction correspondante :

1 def Fibo_DPBU ( n ) :
2 track = [0]*( n +1)
3 track [1] = 1
4 for i in range (2 , n +1) :
5 track [ i ] = track [ i - 1] + track [ i - 2]
6 return track [ n ]
 

Programmation dynamique 11 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Bottom-up vs Top-down

Si le problème initial nécessite la résolution de tous les sous-problèmes, la tabulation est

généralement plus performante que la mémoïsation par un facteur constant.
Si seulement certains des sous-problèmes doivent être résolus pour que le problème initial soit
résolu, la mémoïsation est préférable

Programmation dynamique 12 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Étapes de la programmation dynamique

Caractériser la structure d’une solution optimale.

Définir la valeur de la solution optimale de manière récursive.
Calculer les valeurs de la solution optimale soit de manière descendante (Top-down) avec mise
en cache, soit de manière ascendante (Bottom-up) dans un tableau.
Construire une solution optimale à partir des valeurs calculées.

Programmation dynamique 13 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Problème :
Étant donné deux chaînes de caractères (séquences) x et y, trouver la plus longue sous-séquence
commune (LCS) et afficher sa longueur.
Une sous-séquence est une séquence qui apparaît dans le même ordre relatif, mais pas nécessairement
contigue.

Programmation dynamique 14 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Problème :
Étant donné deux chaînes de caractères (séquences) x et y, trouver la plus longue sous-séquence
commune (LCS) et afficher sa longueur.
Une sous-séquence est une séquence qui apparaît dans le même ordre relatif, mais pas nécessairement
contigue.
Exemple :
x=ABCBDAB
y=BDCABC
"BCAB" est la LCS trouvée dans les deux séquences, la réponse est donc 4.

Programmation dynamique 14 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Caractériser la structure d’une solution optimale :

Soit Dij la longeur du LCS de x1..i et y1..j .

cas de base :
Di0 = D0j = 0
Si xi = yj , ils contribuent tous les deux au LCS, donc

Dij = Di−1,j−1 + 1

Sinon, xi ou yj ne contribuent pas au LCS, donc un peut être supprimé :

Dij = max(Di−1,j , Di,j−1 )

Programmation dynamique 15 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Solution récursive :


1 def lcs (X , Y , m , n ) :
2 if m == 0 or n == 0:
3 return 0
4 elif X [ m - 1] == Y [ n - 1]:
5 return 1 + lcs (X , Y , m - 1 , n - 1)
6 else :
7 return max ( lcs (X , Y , m , n - 1) , lcs (X , Y , m - 1 , n ) )
 

Programmation dynamique 16 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Solution Top-down : (track est une liste )

1 def lcs_PDTD (X , Y ) :
2 m , n = len ( X ) , len ( Y )
3 track = [[ None ]*( n +1) for _ in range ( m +1) ]
4 return lcs_rec_PDTD (X , Y ,m ,n , track )
5
6 def lcs_rec_PDTD (X , Y ,m ,n , track ) :
7 if ( m == 0 or n == 0) :
8 return 0
9 if track [ m ][ n ] != None :
10 return track [ m ][ n ]
11
12 if X [ m - 1] == Y [ n - 1]:
13 track [ m ][ n ] = 1 + lcs_rec_PDTD (X , Y , m - 1 , n - 1 , track )
14 return track [ m ][ n ]
15
16 track [ m ][ n ] = max ( lcs_rec_PDTD (X , Y , m , n - 1 , track ) , lcs_rec_PDTD (X , Y ,
m - 1 , n , track ) )
17 return track [ m ][ n ]
 

Programmation dynamique 17 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Solution Top-down : (track est un dictionnaire )

1 def lcs_PDTD (X , Y ) :
2 m , n = len ( X ) , len ( Y )
3 track ={}
4 return lcs_rec_PDTD (X , Y ,m ,n , track )
5
6 def lcs_rec_PDTD (X , Y , m , n , track ) :
7 if ( m == 0 or n == 0) :
8 return 0
9
10 if (m , n ) in track :
11 return track [( m , n ) ]
12
13 if X [ m - 1] == Y [ n - 1]:
14 track [( m , n ) ] = 1 + lcs_rec_PDTD (X , Y , m - 1 , n - 1 , track )
15 return track [( m , n ) ]
16
17 track [( m , n ) ] = max ( lcs_rec_PDTD (X , Y , m , n - 1 , track ) , lcs_rec_PDTD (X , Y ,
m - 1 , n , track ) )
18 return track [( m , n ) ]
 
Programmation dynamique 18 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Solution Buttom-up : (track est une liste )


1 def lcs_PDBU ( X , Y ) :
2 m = len ( X )
3 n = len ( Y )
4 L = [[ None ]*( n +1) for i in range ( m +1) ]
5 for i in range ( m +1) :
6 for j in range ( n +1) :
7 if i == 0 or j == 0 :
8 L [ i ][ j ] = 0
9 elif X [ i - 1] == Y [ j - 1]:
10 L [ i ][ j ] = L [ i - 1][ j - 1]+1
11 else :
12 L [ i ][ j ] = max ( L [ i - 1][ j ] , L [ i ][ j - 1])
13 return L [ m ][ n ]
 

Programmation dynamique 19 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Plus longue sous-chaîne (Sous-séquence) commune (LCS)

Solution Top-down : (track est un dictionnaire )


1 def lcs_PDBU ( X , Y ) :
2 m = len ( X )
3 n = len ( Y )
4 L ={}
5 for i in range ( m +1) :
6 for j in range ( n +1) :
7 if i == 0 or j == 0 :
8 L [( i , j ) ] = 0
9 elif X [ i - 1] == Y [ j - 1]:
10 L [( i , j ) ] = L [( i - 1 , j - 1) ]+1
11 else :
12 L [( i , j ) ] = max ( L [( i - 1 , j ) ] , L [( i , j - 1) ])
13 return L [( m , n ) ]
 

Programmation dynamique 20 / 21
Introduction Principe générale Problème : Plus longue sous-chaîne commune (LCS) Programmation Dynamique Vs Glouton vs Diviser pour régner

Programmation Dynamique Vs Glouton vs Diviser pour régner

Programmation dynamique 21 / 21