Programmation dynamique.

Rendu de monnaie.

L'an dernier nous avons vu le problème du rendu de monnaie et nous l'avons résolue dans des cas particuliers en utilisant la méthode gloutonne. Malheureusement dans le cas général, la méthode ne marche pas. Par exemple si on ne possède que des pièces de 1 de 4 et de 5 et on veut avoir 8 la méthode gloutonne donne quatre pièces (5-1-1-1) alors que la solution optimale est 2 (4-4).

Pour n entier, soit M_n un ensemble de pièces réalisant une solution au problème du rendu de monnaie de n avec les pièces 1, 4 et 5 (par exemple), alors :

Si M_n possède une pièce de valeur 1 alors M_n\{1} est solution de M_n-1.
Si M_n possède une pièce de valeur 4 alors M_n\{4} est solution de M_n-4.
Si M_n possède une pièce de valeur 5 alors M_n\{5} est solution de M_n-5.

Nous sommes forcément dans un des cas suivants, donc on peut se ramener à chercher M_n-1, M_n-4 et M_n-5 puis à choisir l'ensemble le plus petit puis ajouter un pièce pour trouver M_n.

Cela ressemble assez à la méthode diviser pour régner (sauf que pour diviser pour reigner sépare le problème à des sous problèmes indépendants.) et on peut avoir conclure par une version récursive de la façon suivante :

Il y a un gros problème dans la version précédente, la récursivité multiplie les calculs.

Le principe de la programmation dynamique est de mémoriser les solutions précédentes pour éviter cette répétition.

Il existe deux méthodes pour programmer de façon dynamique.

Première méthode : memoïsation

La première méthode est simple à mettre en place, on part de la programmation récursive et on ajoute un dictionnaire qui enregistre les résultats déjà calculé, ensuite on regarde si la solution 'existe pas déjà.

Deuxième méthode : construction progressive

Une autre façon de programmer de manière dynamique est de partir du début et progressivement arriver à la solution, on va donc dans le sens inverse des précédents !

Remarques

Cette façon de programmer est certes plus compliquée mais offre un avantage de taille : sa taille (justement), en effet si on cherche à connaître le meilleur rendu pour une valeur 12 avec les pièces 1, 4 et 5 (par exemple) alors il revient à connaître des étapes précédentes les cas 7, 8 et 11. Comme dans les cas futurs on peut avoir besoin de 9 donc il faut le conserver mais par contre on n'a plus besoin de conserver le cas 6, on peut le supprimer de la mémoire au bout d'un moment.

Remarques

On peut aussi conserver la distribution idéale mais c'est un peu plus compliqué à programmer :

Exercices

LA célèbre suite de Fibonacci est définie par u₀ = u₀ = 1 et la relation de récurrence u_n+2 = u_n+1 + u_n.
- Faire un algorithme récursif qui trouve u_n.
- Faire un algorithme dynamique avec memoïsation qui trouve u_n.
- Faire un algorithme dynamique sans memoïsation qui trouve u_n.
Le non moins célèbre triangle de Pascal permet de déterminer le nombre de façons de choisir k objets parmi n.
- Compléter la derniére ligne du triangle.
- Le nombre qui est dans la case n en ligne et k en colonne est noté \(C_{k}^{n}\). Trouver la relation entre \(C_{k}^{n}\), \(C_{k}^{n-1}\) et \(C_{k-1}^{n-1}\).
- Faire une version récursive de permettant de calculer \(C_{k}^{n}\), testez ces limites.
- Faire une version dynamique de permettant de calculer \(C_{k}^{n}\).
En UTF8 les caractères sont stockés sur 1 à 4 octets, on se pose la question du nombre de combinaison de caractères que l'on peut stocker sur n octets (c'est plus un problème de dénombrement que d'optimisation). Par exemple pour n = 4, les possibilités de stockage sont :
- (1,1,1,1) 4 caractères de 1 octect.
- (1,1,2) 2 caractères de 1 octet plus un de deux.
- (1,2,1)
- (2,1,1
- (2,2)
- (1,3)
- (3,1)
- (4)
- Trouver toutes les combinaisons de taille de caractères tenant dans 5 octects.
- Si on note u_n ce nombre, établir une relation de récurrence sur u_n avec n >= 4.
- Faire un algorithme récursif qui résout le problème.
- Faire un algorithme dynamique avec memoïsation qui résout le problème.
- Faire un algorithme dynamique sans memoïsation qui résout le problème.
On considère une matrice m×n de nombres entiers, on part du haut à gauche (case (0,0)) et on souhaite rejoindre la case en bas à droite (case (n-1,m-1)) en se permettant que les déplacement vers la droite ou vers le bas. On additionne toutes les cases du chemin et on cherche à avoir la somme maximale.

n = 3

m = 4

4 1 1 3

2 0 2 1

3 1 5 1

Essayer de faire le maximum :
- Si on désigne par S(ligne,colonne) le maximum du total possible d'un chemin commencant en (0,0) et terminant en (ligne, colonne) donner une relation de récurrence entre S(ligne,colonne), S(ligne-1,colonne) et S(ligne,colonne-1).
- Programmer une version récursive (on donnera une matrice de taille libre en paramètre).
- Programmer une version dynamique avec memoïsation.
- Programmer une version dynamique sans utiliser la memoïsation en économisant la mémoire.
- Indiquer le chemin a prendre pour avoir le maximum (par exemple en le mettant dans une liste.
L'exercice précédent admet des variantes utiles, par exemple si on souhaite transformer le plus rapidement un mot1 en un mot2 en utilisant trois opérations : la substitution, la suppression et l'insertion, on construit une matrice comme dans l'exemple dessous. Puis on essaye de se déplacer de la case en haut à gauche à la case en bas à droite, avec pour mouvement un déplacement de un vers la droite (coût 1 point), un vers le bas (coût 1 point), un de diagonale bas droite (gratuit si la case est bleu, 1 point sinon).
mot1 = mot2 =

n\k	0	1	2	3	4	5
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6