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.
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.
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 :
- Caractérisation de la structure d’une solution optimale.
- Définition récursive de la valeur de la solution optimale.
- Calcul ascendant de la solution.
- 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.
Exemple: le change de monnaie
Nous souhaitons faire le change sur 67£. Pour cela nous voulons utiliser le minimum de pièces de type: 1, 5, 10, 25.
Ici il est facile de deviner la solution optimale 67=2*25+10+5+2*1. En choisissant toujours la pièce de plus grande valeur possible, nous obtenons une solution (par algorithme glouton).
Le problème s’écrit de manière suivant: Soit D={ d1,..,dk} un nombre fini de valeur de pièce. On suppose que chaque di est un entier et que l’ensemble soit trié par valeur croissante. Chaque valeur de pièce est disponible en illimité. Le problème est de faire le change sur une valeur de n£ avec un nombre minimal de pièce, si dk =1 alors il existe toujours une solution.
La méthode gloutonne ne donne pas toujours de solution optimale. Par exemple, D={25,10,1} et n=30. La méthode optimale donnera la solution suivante: 25+5*1, qui est moins bonne que 3*10.
Etape 1: Caractériser la sous-structure optimale. Définissons C[j] comme la solution optimale pour la somme j£. Nous pouvons ainsi enlever une pièce et ainsi trouver une solution optimale pour C[j]=1+C[j-di].
Etape 2: Valeur de la solution optimale. Nous pouvons définir récursivement la solution optimale à partir de la sous-structure.
Etape 3: Algorithme.
Coin-Changing(n,d,k)
C[0]=0;
For j from 1 to n
C[j]=inf;
For i from 1 to k
If j>=di and C[j-di]<C[j] then
C[j]=1+C[j-di]
Denom[j]=di
Return C
On utilise un tableau supplémentaire appeler Denom, tel que Denom[j] représente la pièce utiliser pour obtenir une solution optimale pour une somme j£. Si on remonte Denom de la valeur de la pièce jusqu’à atteindre j=1, alors nous connaissons la selection de pièce qui a été faite. Prenons l’exemple avec les pièces suivantes: 1, 5, 10, 25:
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| C[j] | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | 2 |
| Denom[j] | 0 | 1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 1 | 10 | 1 | 1 | 1 | 1 | 5 |
A partir d’une somme n£, nous pouvons trouver toutes les combinaisons de pièce permettant de faire le change. Prenons les mêmes valeurs de pièce : 1, 5, 10, 25. Par exemple, pour N=4, D={1,2,3} il y a quatre solutions : {1,1,1,1}, {1,1,2}, {2,2} et {1,3}.
Etape 1: Sous-structure optimale, C(N,m) peut être partitionner un deux ensembles:
- Les solutions ne contenant aucune pièce dm
- les solutions contenant au moins une pièce dm
Si une solution ne contient pas de pièce dm, alors nous pouvons résoudre le sous-problème de N avec D={d1, ..,dm-1}, soit les solutions de C(N,m-1).
Si une solution contient dm, alors nous allons enlever une pièce dm, il faut donc résoudre le sous-problème N- dm , avec D={d1, ..,dm}. Soit résoudre le problème suivant C(N- dm, m).
Etape 2: La règle est la suivante: C(N-m)=+ C(N- dm, m) avec les conditions de base:
- C(N,m)=1, N=0
- C(N,m)=0, N<0
- C(N,m)=0, N>=1, m<=0
Etape 3: Les solutions de l’algorithmes sont reporté dans un tableau de la forme
| n/d | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 4 |
| 10 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
| 25 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
FR 
EN 
ES