Introduction à la programmation dynamique

Introduction du cours

La « programmation dynamique » est un paradigme de programmation, c'est-à-dire une façon particulière d'appréhender un problème algorithmique donné.

C'est une méthode utile pour obtenir une solution exacte à un problème algorithmique, là où une solution « classique » se trouve être trop complexe, c'est-à-dire trop peu efficace. On parle alors d'optimisation combinatoire.

L'efficacité de cette méthode repose sur le principe d'optimalité énoncé par le mathématicien Richard Bellman : « toute politique optimale est composée de sous-politiques optimales ».

Cette méthode paraît souvent inaccessible au débutant (d'ailleurs, si vous n'avez rien compris à ce qui précède, ne craignez rien : c'est parfaitement normal :p ), aussi je vous propose de la découvrir avec moi sur quelques problèmes concrets.

Un exemple simple

Pour commencer, nous allons prendre un problème tiré d'ici :

Voici une pyramide de nombres. En partant du sommet, et en se dirigeant vers le bas à chaque étape, on doit réussir à maximiser le total des nombres traversés. Sur l'image d'exemple, ce maximum est 23 (le chemin est indiqué en rouge).

Quelle est la meilleure méthode pour trouver un tel chemin ?

Si l'on teste tous les chemins possibles, ça devient impraticable dès que la pyramide est un peu grande. En effet, pour une pyramide de hauteur N, il y a 2N-1 chemins possibles. Nous allons donc très vite nous retrouver bloqués...

Mais heureusement, il existe une manière de procéder infiniment meilleure (et très intuitive, dans notre cas) :) :

Chaque case de notre pyramide (sauf le sommet) possède un ou deux parents (parent = case du dessus permettant d'y parvenir). Les cases situées sur les arêtes (= cotés) n'ont qu'un parent, et les autres en ont deux, l'un à gauche et l'autre droite. A partir de là, et sachant que l'on parcourt la pyramide de haut en bas, il suffit de déterminer pour chaque case de la pyramide quel est le maximum possible, et nous trouvons alors facilement la réponse.

Analysons ensemble le tableau :

LIGNE 1 (sommet) :    - CASE 1 (3) : max = 3 (seule valeur possible) LIGNE 2   - CASE 1 (7) : max = 7 + 3 = 10   - CASE 2 (4) : max = 4 + 3 = 7 LIGNE 3   - CASE 1 (2) : max = 10 + 2 = 12   - CASE 2 (4) : max = MAX(10+4, 7+4) = 10 + 4 = 14   - CASE 3 (6) : max = 6 + 7 = 13 LIGNE 4 :   - CASE 1 (8) : max = 12 + 8 = 20   - CASE 2 (5) : max = MAX(12+5, 14+5) = 14 + 5 = 19   - CASE 3 (9) : max = MAX(14+9, 13+9) = 14 + 9 = 23   - CASE 4 (3) : max = 13 + 3 = 16

Il suffit maintenant de chercher le maximum pour la ligne 4, et le tour est joué ! ;)

Cette approche en informatique est appelée « programmation dynamique ». Elle se révèle extrêmement efficace pour résoudre certains problèmes courants (souvent des problèmes de combinatoire). Nous allons maintenant voir comment résoudre certains problèmes intéressants grâce à la programmation dynamique.

Problème de partition de nombresProblème

Le problème est le suivant : on dispose d'un grand sac de monnaie (de billets, ou de ce que vous voulez). L'objectif est de diviser le sac en deux sacs plus petits contenant les sommes les plus rapprochées possibles.

L'approche la plus « simple » serait d'essayer toutes les combinaisons et d'en retenir la meilleure. Néanmoins, après un petit calcul, on s'aperçoit que cela n'est pas très réaliste. En effet, supposons que nous avons 100 pièces, il existe alors 2100 combinaisons possibles. Il faut donc obligatoirement trouver une meilleure solution.

Méthode

C'est là qu'intervient le concept de programmation dynamique. Pour connaître toutes les combinaisons possibles, il existe un autre moyen : traiter le problème « à l'envers ».

Prenons un cas concret.
Dans un sac de pièces, nous avons :

PIÈCES : 5, 9, 3, 8, 2, 5

Nous allons rechercher une sous-liste de pièces optimale dont la somme se rapprochera le plus possible de la moitié de la somme de toutes les pièces. Raisonnons :

1. Avec la première pièce, quel est l'assemblage possible ?
2. Et avec les deux premières pièces, quels sont les assemblages possibles ? Quelle est la meilleure solution ?
3. Et ainsi de suite jusqu'à n pièces...

ÉTAPE 1. avec 5 :  - COMBINAISONS CONNUES : néant.  - PIÈCE À ÉVALUER : 5.  - NOUVELLES COMBINAISONS : 5. ÉTAPE 2. avec 5 et 9 :  - COMBINAISONS CONNUES : 5.  - PIÈCE À ÉVALUER : 9.  - NOUVELLES COMBINAISONS : 9,  14 (9+5). ÉTAPE 3. avec 5, 9 et 3 :  - COMBINAISONS CONNUES : 5, 9, 14.  - PIÈCE À ÉVALUER : 3.  - NOUVELLES COMBINAISONS : 3,  8 (3+5), 12 (3+9)... ÉTAPE 4. avec 5, 9, 3 et 8 :  - COMBINAISONS CONNUES : 3, 5, 8, 9, 12, 14.  - PIÈCE À ÉVALUER : 8.  - NOUVELLES COMBINAISONS : 11 (3+8),  13 (5+8), 16 (8+8)... On a trouvé 16, alors on s'arrête !

En pratique, on peut connaître les assemblages possibles avec deux pièces à partir des assemblages possibles avec une pièce, et ainsi de suite. C'est ce que l'on appelle une relation de récurrence : la solution du problème sur n instances est récurrente à la solution du problème sur n-1 instances.

On constate que, pour travailler, le programme a besoin de connaître les données déjà trouvées. C'est le fondement même de la programmation dynamique : on élimine les recalculs en mémorisant ce qui a déjà été calculé.

C'est ce qui fait l'efficacité de cette méthode, mais c'est aussi son point faible : la programmation dynamique requiert de la mémoire et ne sera pas toujours envisageable à cause de cela.

Et concrètement, on fait comment ?

Mise en oeuvre

Passons maintenant à l'implémentation de tout cela.

Nous allons devoir créer une matrice booléenne M de dimensions nombrePieces * (miSommeGlobale+1), que nous appellerons M[i][j].

Dans le cas où sommeGlobale est paire, miSommeGlobale vaut sommeGlobale/2. Dans le cas inverse, on prendra (sommeGlobale-1)/2.

DEFINIT sommePieces, miSommeGlobale sommePieces = somme(listePieces) SI sommePieces EST PAIRE    miSommeGlobale = sommePieces/2 SINON    miSommeGlobale = (sommePieces-1)/2 DEFINIT M[nombrePieces][miSommeGlobale+1]

Puis on remplit la première ligne comme ceci :

M[0][0] = VRAI POUR j=1 TANT QUE j < miSommeGlobale    SI piece[0] EGALE j        M[0][j] = VRAI    SINON        M[0][j] = FAUX    incrémente j

Ce qui nous donne :

i\j

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

1re pièce

V

F

F

F

F

V

F

F

F

F

F

F

F

F

F

F

F

Cette ligne représente les combinaisons possibles avec la première pièce.
On peut avoir soit 0 avec zéro pièces, soit 5 avec une pièce.

Ensuite, nous allons remplir les autres lignes du tableau (ligne par ligne) en suivant la condition suivante :

M[i][j] EST VRAI SI    - M[i-1][j] EST VRAI    OU    - piece[i] <= j ET M[i-1][j-piece[i]] EST VRAI

Ce qui nous donne bien :

i\j

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

1re pièce

V

F

F

F

F

V

F

F

F

F

F

F

F

F

F

F

F

2 premières pièces

V

F

F

F

F

V

F

F

F

V

F

F

F

F

V

F

F

3 premières pièces

V

F

F

V

F

V

F

F

V

V

F

F

V

F

V

F

F

4 premières pièces

V

F

F

V

F

V

F

F

V