Programmation dynamique

La programmation dynamique est utilisé pour la résolution de nombreux problèmes provenant de la recherche opérationnelle, c’est pourquoi nous ne listerons pas les tutoriels liés à cette méthode.

Introduction

La Programmation Dynamique est une méthode exacte de résolution de problèmes
d’optimisation, due essentiellement à R. Bellman (1957).

Plus précisément, la programmation dynamique est un paradigme de conception d’algorithmes qu’on peut appliquer pour résoudre un problème s’il répond à l’optimalité de Bellman.

Définition. Optimalité de Bellman. Un problème possède la propriété de sous-structure optimale si une solution optimale contient la solution optimale des sous-problèmes.

progdyn

La programmation dynamique ressemble dans l’idée à la méthode diviser et régner. La différence significative entre ces deux méthodes est que la programmation dynamique permet aux sous-problèmes de se superposer. Autrement dit, un sous-problème peut être utilisé dans la solution de deux sous-problèmes différents. Tandis que l’approche diviser et régner crée des sous-problèmes séparés pouvant être résolus indépendamment l’un de l’autre.

La différence fondamentale entre ces deux méthodes est donc : les sous-problèmes dans la programmation dynamique peuvent être en interaction, alors dans la méthode diviser et régner, ils ne le sont pas.

Une seconde différence entre ces deux méthodes est, comme illustré par la figure ci-dessus, est que la méthode diviser et régner est récursive, la récursion prend le problème global pour le découper en problème élémentaire. La programmation dynamique est une méthode dont les calculs se font de bas en haut : on commence par résoudre les plus petits sous-problèmes. En combinant leur solution, on obtient les solutions des sous-problèmes de plus en plus grands.

Principe

Le paradigme se décompose en quatre problématiques :

  1. Caractérisation de la structure d’une solution optimale.
  2. Définition récursive de la valeur de la solution optimale.
  3. Calcul ascendant de la solution.
  4. Construction de la solution à partir du calcul ascendant.

On construit une table pour mémoriser les calculs déjà effectués : à chaque élément correspondra la solution d’un et d’un seul problème intermédiaire, et un pour la solution finale. Il faut donc qu’on puisse déterminer les sous-problèmes qui seront traités au cours du calcul.

Il existe deux approches pour remplir le tableau :

  • Itérative : On initialise les « cases » correspondant aux cas de base.
    On remplit ensuite la table selon un ordre bien précis à déterminer : on commence par les problèmes de « taille » la plus petite possible, on termine par la solution du problème principal : il faut qu’à chaque calcul, on n’utilise que les solutions déjà calculées.
  • Récursive : Même principe que l’approche itérative, cette méthode quant à elle ne calculera que le strict nécessaire pour atteindre l’objectif donné.

Exemple : produit de matrices

Soient n matrices M1, …, Mn, chaque matrice à un certain nombre mi de lignes et mi+1 colonnes, les entrées sont des nombres réels (problème linéaire). Nous cherchons à calculer M1*…*Mn de façon à minimiser le nombre d’opérations.

Notons cij le nombre d’opérations pour calculer Mi*…*Mj. On a alors cii=0 et ci(i+1)=m(i-1)*mi*m(i+1) opérations. Découpons ce sous-problème en calculant le meilleur cij avec Mi*…*Mk et M(k+1)*…*Mj. Alors : cij = min [cik + c(k+1)j + mi*m(k+1)*m(j+1)] avec k de i à j-1, le dernier terme revient à multiplier les résultats du produit de matrices de i à k avec celui de k+1 à j.

Nous avons donc le programme suivant :

  • cij = 0 si i = j;
  • ci(i+1)=m(i-1)*mi*m(i+1);
  • cij = min [cik + c(k+1)j + mi*m(k+1)*m(j+1)] sinon.

Le tableau du programme dynamique prend en entrée le nombre d’opérations effectuées en fonction des matrices choisies. Prenons l’exemple suivant :

i
1
2
3
4
5
6
7
mi
30
35
15
5
10
20
25

Le tableau initial est le suivant :

cij
1
2
3
4
5
6
1
0
2
0
3
0
4
0
5
0
6
0

Puis nous pouvons calculer cij avec deux matrices (sans principe de sous-structure) :

cij
1
2
3
4
5
6
1
0
15750
2
0 2625
3
0 750
4
0 1000
5
0 5000
6
0

Le reste du tableau se remplit diagonale par diagonale suivant la règle décrite plus haut :

cij
1
2
3
4
5
6
1
0
15750
7875 9375 11875 15125
2
0 2625 4375 7125 10500
3
0 750 2500 5375
4
0 1000 3500
5
0 5000
6
0

Le résultat est obtenu pour i=1 et j=6, soit la case en haut à droite du tableau. Le coût minimal est donc de 15125 opérations. Une nouvelle question se pose alors : comment a-t-on procédé pour avoir un nombre de calcul minimal ?

Lorsque nous calculons le coût minimal pour chaque case, nous effectuons un choix parmi deux configurations. Par exemple pour calculer c13, nous prenons le minimum entre c12*M3 et M1*c23. Il suffit de noter le choix effectué afin de connaitre l’ordre de calcul du produit matriciel.

Kij
1
2
3
4
5
6
1
1 3 3 3
2
3 3 3
3
3 3
4
5
5
6

Le tableau se lit ainsi : pour calculer Mi*Mj, on pose k = Kij donné par le tableau puis on calcule Mi*…*Mk et M(k+1)*…*Mj que l’on multiplie ensuite entre elles.

Dans notre exemple, pour calculer c16, nous calculons c13*c46; pour calculer c13, nous calculons M1*c23; pour calculer c46  nous calculons c45*M6.

La plupart des algorithme basés sur la programmation dynamique retienne en mémoire le choix effectué pour chaque calcul. Bien souvent le résultat n’est pas important, le parcours pour l’atteindre l’est.

Publicités