Aller au menu - Aller au contenu

Icône Introduction à la programmation dynamique

Avatar
Par Avatar yoch
Mise à jour : 25/08/2011
Difficulté : Intermédiaire Intermédiaire Creative Commons BY
237 visites depuis 7 jours, classé 390/786
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.
Retour en haut
Sommaire du tutoriel :
Icône du chapitre
Retour en haut

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).

Image utilisateur


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 :

Code : Autre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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(10+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.
Retour en haut

Problème de partition de nombres

Problè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 :

Code : Autre
1

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...

Code : Autre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

É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.


Code : Autre
1
2
3
4
5
6
7
8
9

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 :

Code : Autre
1
2
3
4
5
6
7

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\j0001020304050607080910111213141516
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 :

Code : Autre
1
2
3
4

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\j0001020304050607080910111213141516
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 V F V V V V F V

Chaque ligne représente les combinaisons possibles avec les i premières pièces.


Dans ce cas précis, on s'arrête à la ligne 4 car la solution idéale a été trouvée.

Sinon, on continuera à remplir le tableau jusqu'à la dernière ligne, et nous connaîtrons de ce fait la solution optimale : la valeur maximale de la dernière ligne du tableau représente l'une des deux sous-sommes optimales (la plus petite), l'autre sous-somme optimale étant alors la somme globale moins cette valeur.

Code : Autre
1
2
3
4
5
6
7
8
9

DEFINIT sousListe1, sousListe2, ecart
i = nombrePieces, j = miSommeGlobale + 1

TANT QUE M[i][j] EST FAUX
   décrémente j

sousListe1 = j
sousListe2 = sommePieces - j
ecart = sommePieces-(j*2)


Et si je veux récupérer la sous-liste en question, y a-t-il un moyen ?

Eh bien en fait, si tu as gardé le tableau ci-dessus, je pense qu'il doit y avoir un moyen. ;)

Récupérer la sous-liste


Nous allons récupérer la sous-liste obtenue en suivant le procédé à l'envers.

Analysons le tableau :

- En M[3][16], nous avons le résultat optimal. Or le quatrième nombre (piece[3]) est 8.
- Passons alors en M[2][16-8] ; à nouveau, le résultat est optimal (la case au-dessus est false). De plus, nous savons que le troisième nombre (piece[2]) est 3.
- On passe à M[1][8-3] ; le résultat n'est pas optimal.
- Puis on passe à M[0][5] ; le résultat est optimal, donc on ajoute le premier nombre (piece[0]) à notre sous-liste.
- On retrouve bien notre sous-liste optimale : 8, 3 et 5.

Algorithme


Une fois que l'on a trouvé la sous-liste optimale, on fait :

Code : Autre
1
2
3
4
5
6
7

TANT QUE j > 0
   TANT QUE i > 0 ET M[i-1][j] EST VRAI
      décrémente i
   j = j - piece[i]
   SI j > 0
      Ajoute-a-petite-sous-liste ( piece[i] )
   décrémente i
Retour en haut

Problème du sac à dos

Problème


J'ai un sac à dos de capacité maximale k (poids). J'ai n objets de poids et de valeurs diverses. Je souhaite remplir ledit sac de façon à cumuler un maximum de valeurs. Quel est le bénéfice maximum que je peux faire ?

Ce problème est un grand classique en algorithmique et il existe diverses méthodes pour le résoudre.
Je vais vous présenter ici la méthode dite par programmation dynamique.

Mais auparavant, prenons un cas concret :

Code : Autre
1
2
3
4
5

MAX CONTENANCE : 12

- OBJET : A| B|  C| D|  E|  F|  G| H
- POIDS : 2| 3|  5| 2|  4|  6|  3| 1
- VALUE : 5| 8| 14| 6| 13| 17| 10| 4


Analyse



C'est là que la fameuse règle « toute politique optimale est composée de sous-politiques optimales » prend tout son sens. Nous allons l'appliquer à nouveau et traiter le problème depuis le bas.

On a :
Code : Autre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

ÉTAPE 1 : pour l'objet A
 - COMBINAISONS OPTIMALES CONNUES :
 - OBJET À ÉVALUER : A
 - NOUVELLES COMBINAISONS OPTIMALES : 
    - je peux avoir un bénéfice de 5 pour un poids de 2 (A).

ÉTAPE 2 : pour les objets A et B
 - COMBINAISONS OPTIMALES CONNUES :
    - je peux avoir un bénéfice de 5 pour un poids de 2 (A).
 - OBJET À ÉVALUER : B
 - NOUVELLES COMBINAISONS OPTIMALES : 
    - je peux avoir un bénéfice de 8 pour un poids de 3 (B).
    - je peux avoir un bénéfice de 13 pour un poids de 5 (A+B).

ÉTAPE 3 : pour les objets A, B et C
 - COMBINAISONS OPTIMALES CONNUES :
    - je peux avoir un bénéfice de 5 pour un poids de 2 (A).
    - je peux avoir un bénéfice de 8 pour un poids de 3 (B).
    - je peux avoir un bénéfice de 13 pour un poids de 5 (A+B).
 - OBJET À ÉVALUER : C
 - NOUVELLES COMBINAISONS OPTIMALES : 
    - je peux avoir un bénéfice de 14 pour un poids de 5 (C).
    - je peux avoir un bénéfice de 19 pour un poids de 7 (A+C).
    - je peux avoir un bénéfice de 22 pour un poids de 8 (B+C).
    - je peux avoir un bénéfice de 27 pour un poids de 10 (A+B+C).

ÉTAPE 4 : pour les objets A, B ,C et D
 - COMBINAISONS OPTIMALES CONNUES :
    - je peux avoir un bénéfice de 5 pour un poids de 2 (A).
    - je peux avoir un bénéfice de 8 pour un poids de 3 (B).
    - je peux avoir un bénéfice de 14 pour un poids de 5 (C).
    - je peux avoir un bénéfice de 19 pour un poids de 7 (A+C).
    - je peux avoir un bénéfice de 22 pour un poids de 8 (B+C).
    - je peux avoir un bénéfice de 27 pour un poids de 10 (A+B+C).
 - OBJET À ÉVALUER : D
 - NOUVELLES COMBINAISONS OPTIMALES : 
    - je peux avoir un bénéfice de 6 pour un poids de 2 (D).
    - je peux avoir un bénéfice de 11 pour un poids de 4 (A+D).
    - je peux avoir un bénéfice de 20 pour un poids de 7 (C+D).
    - je peux avoir un bénéfice de 25 pour un poids de 9 (A+C+D).
    - je peux avoir un bénéfice de 28 pour un poids de 10 (B+C+D).
    - je peux avoir un bénéfice de 33 pour un poids de 12 (A+B+C+D).
    

Et ainsi de suite...


Et si tu nous disais comment tu expliques ça au programme ?

C'est vrai que la récurrence est ici moins évidente à trouver. ;) Voici comment nous allons procéder.

Mise en oeuvre



Nous allons créer une matrice d'entiers M de dimensions nombreObjets * (maxContenance+1), que nous appellerons M[i][j].

Puis on remplit la première ligne comme ceci :
Code : Autre
1
2
3
4
5
6

POUR j=0 TANT QUE j < maxContenance
   SI poidsObjet[0] > j
       M[0][j] = 0
   SINON
       M[0][j] = valeurObjet[0]
   incrémente j


Ce qui nous donne :

i\j 00 01 02 03 04 05 06 07 08 09 10 11 12
1er objet 0 0 5 5 5 5 5 5 5 5 5 5 5

Chaque case du tableau représente le bénéfice maximum possible pour les i premiers objets avec un poids j.


Ensuite, nous allons remplir les autres lignes du tableau (ligne par ligne) ainsi :
Code : Autre
1
2
3
4

SI poidsObjet[i] > j
    M[i][j] = M[i-1][j]
SINON
    M[i][j] = maximum ( M[i-1][j], M[i-1][j-poidsObjet[i]] + valeurObjet[i] )


Ce qui nous donne au final :

i\j 00 01 02 03 04 05 06 07 08 09 10 11 12
1er objet 0 0 5 5 5 5 5 5 5 5 5 5 5
2 premiers objets 0 0 5 8 8 13 13 13 13 13 13 13 13
3 premiers objets 0 0 5 8 8 14 14 19 22 22 27 27 27
4 premiers objets 0 0 6 8 11 14 14 20 22 25 28 28 33
5 premiers objets 0 0 6 8 13 14 19 21 24 27 28 33 35
6 premiers objets 0 0 6 8 13 14 19 21 24 27 30 33 36
7 premiers objets 0 0 6 10 13 16 19 23 24 29 31 34 37
8 premiers objets 0 4 6 10 14 17 20 23 27 29 33 35 38


Le plus grand bénéfice possible se trouve dans la dernière case du tableau (en bas à droite). Celui-ci est donc de 38.

Le poids nécessaire pour faire un tel bénéfice se retrouve en reculant horizontalement depuis la dernière case du tableau (en bas à droite) tant que le bénéfice reste le même. Donc ici le poids nécessaire est 12 (car on ne peut pas reculer).

Récupérer la liste d'objets



Le principe est le même que plus haut. Tout d'abord, on récupère dans la dernière ligne le poids minimal nécessaire pour faire le bénéfice optimal :

Code : Autre
1
2

TANT QUE M[i][j] EGALE M[i][j-1]
   décrémente j

Et puis, de là, on récupère les objets :
Code : Autre
1
2
3
4
5
6
7

TANT QUE j > 0
   TANT QUE i > 0 ET M[i][j] EGALE M[i-1][j]
      décrémente i
   j = j - PoidsObjet[i]
   SI j > 0
      Ajoute-objet ( Objet[i] )
   décrémente i
Retour en haut
Voilà, ce (court) tuto touche à sa fin. J'espère que vous avez bien compris et qu'il vous aura donné matière à réflexion.

Pour résumer :Citation : candide
1°) La programmation dynamique est simplement le fait de construire un tableau dont chaque ligne se déduira d'une ou de plusieurs lignes précédentes.
2°) La programmation dynamique a ses limites (la taille des instances du problème).


Cette approche permettra (sous certaines conditions) de résoudre nombre de problèmes « difficiles ».
Exemples de problèmes que l'on peut résoudre par programmation dynamique (en anglais) : http://people.csail.mit.edu/bdean/6.046/dp/

Remerciements à candide pour sa relecture et ses commentaires pertinents.
Retour en haut

Partager

Retour en haut
27 commentaires pour "Introduction à la programmation dynamique"
Note moyenne : 3.73 / 4 (22 votes)
Pseudo Commentaire
Hors ligne louk # Posté le 08/11/2011 à 18:59:36
Lis tes ratures...
Avatar

 Je voudrais ajouter un commentaire pour signaler que j'étais plutôt très d'accord avec JeromeJ (oui, je sais, ça fait plus de deux ans :-° )
Mais, moi je n'ai pas du tout trouvé ça clair, je n'ai même pas vraiment compris le but du deuxième exemple avec les pièces. J'ai eu un peu de mal à comprendre le premier exemple aussi. Je trouve que tu ne décris/détaille pas assez tes algorithmes, les tutos de m@teo, je les ai toujours trouvé géniaux à ce point, et là, j'ai l'impression qu'il faut un minimum d'expérience assez élevé. C'est dommage, parce que comme l'a dit JeromeJ, ça avait l'air intéressant, surtout que l'algorithmique me plait énormément.

Sur ce, je souhaite une bonne soirée à tous, je vais manger :).
Loukiluk. Celui qui calcule plus vite que son ombre (ou pas) et le gros chipoteur orthographique...

Pensez à mettre vos topiques en résolu ! (le bouton tout en bas ou tout en haut, au milieu)
 
Hors ligne Tiamat # Posté le 23/11/2011 à 20:23:06
Uttini !!!
Avatar

 ce tuto est très intéressant mais il y a quelques trucs qu'il faudrait que tu explicites plus. On pourrait ainsi comprendre le tuto sans avoir besoin de relire plusieurs fois et de se fatiguer la cervelle.
Hors ligne Pito18 # Posté le 08/03/2012 à 10:10:54

J'ai mis un bout de temps a comprendre le truc de la pyramide :
voici ce que j'ai trouve sur le net qui m'a convaincu de l'interet de cette methode :
http://www.ilemaths.net/forum-sujet-433358.html

"on dessine un triangle vide de la même taille.
- on copie la dernière ligne du triangle original dans la dernière ligne du triangle vide.
- dans chaque case de l'avant-dernière ligne, on indique le nombre original + le plus grand des deux nombres se trouvant dans les deux cases inférieures (donc : 16 + max(6,15) = 31 pour la première case de l'avant-dernière ligne).
- on remonte d'une ligne et on recommence (donc : 8 + max(31,24) = 39 pour la première case de l'antépénultième ligne...)
- on arrive au sommet avec le maximum de 131.
- il suffit ensuite de "détricoter" ce maximum pour retrouver la séquence..."
Hors ligne olivia35 # Posté le 09/04/2012 à 11:28:32

Salut tout le monde !

Est-ce que quelqu'un pourrait m'expliquer la ligne :


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

Pourquoi M[i-1][j-piece[i]] ?

Merci :D
Hors ligne benji61 # Posté le 21/04/2012 à 20:14:03

Je ne suis pas sûr de mon coup, mais n'y aurait-il pas une erreur concernant l'algorithme des pièces la partie où l'on retourne une sous-liste? En effet, j'ai déroulé l'algorithme en enlevant le dernier "décrémente i". Tout allait bien jusqu'à ce que "j" vaille 0 et que l'on veuille intégrer pièce[0]. Or comme "j" vaut 0, on sort du programme sans ajouter la première pièce.

Par contre, en changeant le "SI j > 0" en "SI j >= 0", ça marche. De plus, on ne rentre pas dans le premier TANT QUE vu que "j" n'est pas supérieur strictement à 0.

En espérant avoir été clair. Sans doute suis-je passé à côté de quelque chose ...

Voir tous les commentaires
Ce tutoriel a été corrigé par les zCorrecteurs.