La Programmation Dynamique - Cours d'Introduction

8/4/2019 La Programmation Dynamique - Cours d'Introduction

1/20

1

Chapitre 5: La programmation dynamique

1. Introduction

La programmation dynamique est un paradigme de conception quil est possible de voir commeune amlioration ou une adaptation de la mthode diviser et rgner. Ce concept a t introduit parBellman, dans les annes 50, pour rsoudre typiquement des problme doptimisation.

Pour la petite histoire, Bellman a choisi le terme programmation dynamique dans un souci decommunication : son suprieur ne supportait ni le mot recherche ni celui de mathmatique . Alors il lui a sembl que les termes programmation et dynamique

donnaient une apparence qui plairait son suprieur. En ralit, le terme programmation signifiait lpoque plus planification et ordonnancement que la programmation au sens quon lui donnede nos jours. En un mot, la programmation dynamique est un ensemble de rgles que tout unchacun peut suivre pour rsoudre un problme donn.

La programmation dynamique est similaire la mthode diviser et rgner en ce sens que, unesolution dun problme dpend des solutions prcdentes obtenues des sous-problmes. Ladiffrence significative entre ces deux mthodes est que la programmation dynamique permetaux sous-problemes de se superposer. Autrement dit, un sous-problmes peut tre utilis dans lasolution de deux sous-problmes diffrents. Tandis que lapproche diviser et rgner cre dessous-problmes qui sont compltement spars et peuvent tre rsolus indpendamment lun delautre. Une illustration de cette diffrence est montre par la Figure 5.1. Dans cette figure, le problme rsoudre est la racine, et les descendants sont les sous-problmes, plus faciles rsoudre. Les feuilles de ce graphe constituent des sous-problmes dont la rsolution est triviale.Dans la programmation dynamique, ces feuilles constituent souvent les donnes de lalgorithme.La diffrence fondamentale entre ces deux mthodes devient alors claire: les sous-problmesdans la programmation dynamique peuvent tre en interaction, alors dans la mthode diviser etrgner, ils ne le sont pas.

diviser et rgner programmation dynamique

Une seconde diffrence entre ces deux mthodes est, comme illustr par la figure ci-dessus, estque la mthode diviser et rgner est rcursive, les calculs se font de haut en bas. Tandis que la programmation dynamique est une mthode dont les calculs se font de bas en haut : on


2/20

2

commence par rsoudre les plus petits sous-problmes. En combinant leur solution, on obtient lessolutions des sous-problmes de plus en plus grands.

Illustration 1: On dbute nos exemples par celui du calcul des nombres de Fibonacci. Leproblme est de calculer le n premiers nombres de Fibonacci donns par la formule suivante :

)2()1()(

;1)1(;1)0(

+=

==

nFnFnF

FF

Lalgorithme implantant cette formule est alors comme suit :

Algorithme 1

int function Fibo(int n){

if (n


3/20

3

La clef une solution plus efficace est dviter la multiplicit de rsolution du mme sous-problme. On amliore de loin la complexit temporelle si, une fois calcul, on sauvegarde unrsultat, par exemple dans une table. Et au besoin, on le prend de cette table. Cette remarque nous

amne la solution suivante :

Algorithme 2

int function Fib(int n){

if (Fib(n) solution est dans la table)return table[n] ;

if (n


4/20

4

int function B(int n,k) {if (k = = 0) || (k = = n)

return 1

else return(B(n-1,k-1) + B(n-1,k);} \\ fin de fonction

Voyons voir lexcution de cette fonction sur un exemple de donnes: n = 5 et k = 2. Remarquez

le nombre de fois, par exemple que, le terme

1

2est calcul.

Exercice: montrer que la complexit temporelle de cette fonction est en

k

n .

Pour viter de calculer plusieurs fois un nombre, lide est de crer un tableau o on calcule tousles nombres de petites tailles, ensuite, de tailles de plus en plus grandes avant darriver aunombre dsir. Pour ce faire, on procde comme suit :


5/20

5

Pour calculer donc B(n,k), on procde comme suit:

for(i=0 ; i


6/20

6

2. Quand et comment utiliser la mthode de la programmation dynamique

La programmation est un outil gnral de rsolution de problmes. Toutefois, il ny pas de rglepour affirmer que la programmation dynamique peut ou ne peut tre utilise pour rsoudre tel outel problme.Le gros du travail, si on veut utiliser cette mthode, rside tout dabord dans lobtention delexpression rcursive de la solution en fonction de celle des sous-problmes (de taille plus petite). Notons que dans les problmes doptimisation, cette manire dobtenir la solutionoptimale partir des solutions optimales des sous problmes sappelle le principe doptimalit

de Bellman. Il est important de souligner que ce principe, bien que naturel, nest pas toujoursapplicable.

Exercice : Trouver un exemple o ce principe nest pas applicable.

Une fois cette expression obtenue, on analyse ce qui se passe dans une implantation rcursivenave : si on se rend compte que la solution de mme problmes est calcule plusieurs fois, on estalors dans le cadre de la programmation dynamique. Le dcoupage du problme devraitnaturellement conduire la dfinition de la table (qui peut tre de dimension 1,2,3, ).Remarquez quune case de la table correspond un sous-problme. Par ailleurs, le nombre desous-problmes peut tre trs grand. La complexit obtenue, de lalgorithme de programmation

dynamique, nest pas forcment polynomial.

Si on est dans le cadre de la mthode de la programmation dynamique, les tape suivies peuventtre rsumes comme suit :

a. obtention de lquation rcursive liant la solution dun problme celle de sous-problmes.

b. initialisation de la table: cette tape est donne par les condition initiale de lquationobtenue ltape 1.

c. remplissage de la table: cette tape consiste rsoudre les sous-problmes de taille deplus en plus grandes, en se servant bien entendu de lquation obtenue ltape 1.


7/20

7

d. lecture de la solution : ltape 3 ne conduit qu la valeur (optimale) du problme dedpart. Elle ne donne pas directement la solution conduisant cette valeur. En gnrale,pour avoir cette solution, on fait un travail inverse en lisant dans la table en partant de la

solution finale et en faisant le chemin inverse des calculs effectus en ltape 3.

3. tude de quelques exemples.

Dans cette section, il sera question de voir en action la mthode de la programmation dynamiquesur des problmes essentiellement doptimisation.

3.1. Dterminer le plus court chemin dans un graphe algorithme de Floyd

Soit un graphe ),( VXG = ayantXcomme ensemble de sommets et Vcomme ensemble d'arcs.Le poids de larc a est un entier naturel not )(al . La longueur d'un chemin est gale la sommedes longueurs des arcs qui le composent. Le problme consiste dterminer pour chaque couple

),( ji xx de sommets, le plus court chemin, s'il existe, qui joint ix jx .

Nous commenons par donner un algorithme qui dtermine les longueurs des plus courts cheminsnotes ),( ji xx . Par convention, on note =),( ji xx s'il n'existe pas de chemin entre ix et jx

(en fait il suffit dans la suite de remplacer par un nombre suffisamment grand par exemple lasomme des longueurs de tous les arcs du graphe). La construction effective des chemins seraexamine ensuite. On suppose qu'entre deux sommets il y a au plus un arc. En effet, s'il en existeplusieurs, il suffit de ne retenir que le plus court.

Les algorithmes de recherche de chemins les plus courts reposent sur l'observation trs simple(mais combien importante) suivante:

Remarque

Si f est un chemin de longueur minimale joignant x y et qui passe par , alors il se dcompose

en deux chemins de longueur minimale l'un qui joint x z et l'autre qui joint z y.

Dans la suite, on suppose les sommets numrots nxxx ,...,, 21 et, pour tout 0>k , on considre la

proprit kP suivante pour un chemin: )(fPk : Tous les sommets def, autres que son origine etson extrmit, ont un indice strictement infrieur k.

On peut remarquer dune part qu'un chemin vrifie 1P si, et seulement si, il se compose d'un

unique arc. Dautre part la condition 1+nP est satisfaite par tous les chemins du graphe. Notons

par ),( jik xx la longueur du plus court chemin vrifiant la proprit kP et qui a pour origine ix

et pour extrmit jx . Cette valeur est si aucun tel chemin n'existe. Ainsi =),(1 ji xx s'il

n'y a pas d'arc entre ix et jx , et vaut )(al , si a est cet arc. D'autre part =+1n .


8/20

8

Le lemme suivant permet de calculer les 1+k connaissant les ),( jik xx . On en dduira un

algorithme itratif.

Lemme Les relations suivantes sont satisfaites par les k :

)),(),(),,(min(),(1 jkkjikjikjik xxxxxxxx +=+

Preuve

Soit un chemin de longueur minimale satisfaisant 1+kP , ou bien il ne passe pas par kx et on a la

relation suivante qui est vrifie :

),(),(1 jikjik xxxx

=+

ou bien il passe par kx et, d'aprs la remarque ci-dessus, il est compos d'un chemin de longueur

minimale joignant ix kx et satisfaisant kP et d'un autre minimal aussi joignant kx jx . Ce

chemin est donc de longueur : ),(),( jkkjik xxxx + .

L'algorithme suivant pour la recherche du plus court chemin met jour une matrice delta[i,j] quia t initialise par les longueurs des arcs et par un entier suffisamment grand s'il n'y a pas d'arcentre ix et jx . chaque itration de la boucle externe, on fait crotre l'indice kdu kP calcul.

for k := 1 to nfor i := 1 to n

for j := 1 to ndelta[i,j] := min(delta[i,j], delta[i,k] + delta[k,j])

Sur l'exemple du graphe donn sur la Figure 5.3, on part de la matrice 1 donne par


9/20

9

Figure 5.3: Un graphe aux arcs valus

Aprs le calcul on obtient:

Pour le calcul effectif des chemins les plus courts, on utilise une matrice qui contient suiv[i,j], lesommet qui suit i dans le chemin le plus court qui va de i j. Les valeurs suiv[i,j] sont initialisesj s'il existe un arc de i versj et sinon ; suiv[i,i] est lui initialis i. Le calcul prcdent quia donn peut s'accompagner de celui de en procdant comme suit:

for k := 1 to nfor i := 1 to n

for j := 1 to nif delta[i, j] > (delta[i, k] + delta[k, j]) then

begin

delta[i, j] := delta[i, k] + delta[k, j];suivant[i, j] := suivant[i, k];end;

Une fois le calcul des deux matrices effectu, on peut retrouver le plus court chemin qui joint i j , laide la procdure ci-dessous:


10/20

10

procedure PlusCourtChemin(i, j: integer);

var k: integer;

begink := i;while k j do

beginwrite (k, ' ');k := suivant[k, j];end;

writeln(j);end;

Sur l'exemple prcdent, on obtient la matrice suivante:

3.2: Multiplication chane de matrices

Soit n matrices nMMM ,...,, 21 ; chaque matrice iM possde 1id lignes et id colonnes. Le

problme est deffectuer nMMM ...21 en un minimum doprations de multiplications.

Rappels

a. Pour faire le produit 21 MM , il est ncessaire que le nombre de colonnes de 1M soit gal au

nombre de ligne de 2M

b. Le nombre de multiplications engendres par ji MM , de dimension respectivement de

)( 1 ii dd et )( ji dd est gal jii ddd 1 .

Parce que la multiplication est une opration associative ( 321321 )()( MMMMMM = , il

existe une multitude de manires deffectuer le produit entre les matrices. Par exemple, soit lestrois matrices suivantes :

)513( A ; )895( B ; );389( C )343( D


11/20

11

Effectuons les calculs des combinaisons de produit suivants :

DCBAM ))(( = :AB 578589513 = multiplications

:)( CAB 347138913 = multiplications:))(( DCAB 132634313 = multiplications

---------------------10 582 multiplications

:))(( DCAB 10582 multiplications:))(( CDAB 52201 multiplications

:))(( DBCA 2856 multiplications:))(( DBCA 4 055 multiplications:))(( CDBA 26 418 multiplications

Ide 1 : la mthode brute: On insre les parenthses de toutes les manires possibles et ensuite,pour chacune delle, on compte le nombre de multiplications engendres. Procdons comme pourdiviser et rgner en subdivisant le problme en deux sous-problmes comme suit :

)...)(...( 2121 niii MMMMMMM = ++ (1)

Si )(nt est le cot pour effectuer le produit ci-dessus, alors )(it va reprsenter le cot duproduit )...( 21 iMMM et )( int celui de )...( 21 nii MMM ++ . Alors, pour un i

donn, le cot du produit est clairement )( int )(it . Comme lindice i de sparation peut tre nimporte laquelle des positions 1,2,,n-1, alors la relation entre )(nt , )(it et )( int estcomme suit :

)()()(1

1

intitntn

i

=

=

1)1( =t (pourquoi donc ?)

Exercice : rsoudre lquation rcurrente ci-dessus.

Ide 2: la programmation dynamique

1. caractriser la structure dune solution optimale

si njimij 1; : solution optimale pour le faire le produit )...( 21 jii MMM ++ , alors la

solution du problme est le calcul de nm1


12/20

12

)...)(...( 2121 niii MMMMMMM = ++

solution optimale solution optimale

im1 nim 1+

2. dfinir rcursivement la valeur dune solution optimale en fonction des solution optimalesdes sous-problmes.

Les sous-problmes : Dterminer le cot minimum dun parenthtisage de

)...( 2 jii MMM +

i = j : aucune multiplication : 0=ijm

i < j : ijm = cot minimum pour calculer le produit )...( 2 kii MMM +

+cot minimum pour calculer le produit )...( 21 jkk MMM ++

+cot pour multiplier les deux matrices jki ddd 1

Comme, on ne sait pas priori o placer lindice k, on doit essayer toutes les positions et prendrecelle qui engendre le moins de multiplications. Cela donne donc :


13/20

13

;0=s ;0=iim ;,...,2,1 ni =

;1=

s ;111 ++=

iiiii dddm ;1,...,2,1=

ni

;1 ns


14/20

14

3.3. Problme du sac dos en nombres entiers

Nous avons introduit au chapitre prcdent le problme du sac dos. Rappelons la dfinition de

ce problme.

Soit un ensemble de n objets { }nN ,...,2,1= , et un sac dos pouvant contenir un poids maximalde W. Chaque objet a un poids iw et un gain iv . Le problme consiste choisir un ensemble

d'objets parmi les n objets, au plus un de chaque, de telle manire que le gain total soit maximis,sans dpasser la capacit Wdu sac. Dans cette version que nous prsentons dans ce chapitre, unobjet est soit choisi soit ignor. Autrement dit, les objets sont indivisibles, et de ce fait nous nepouvons pendre une portion dun objet dans le sac.

En termes mathmatiques, nous avons ce qui suit :

.1,0

max1

=

=

i

ii

i

n

i

i

x

Wxw

xv

Lintgralit des objets rend ce problme difficile rsoudre. La stratgie vorace propose dansle chapitre prcdent ne fonctionne plus dans ce cas.

Exercice : Donner un exemple o les diffrentes stratgies voraces auxquelles vous pourriezpenser ne gnrent pas la solution optimale.

Exercice : un simple algorithme pour ce problme est de gnrer toutes les solutions possibles(un objet est soit choisi soit ignor). Concevoir lalgorithme bas sur cette stratgie. Montrer quesa complexit est en )2( nO

Proprit rcursive du problme :

La programmation dynamique peut tre dveloppe en divisant le problme en deux sous-

problme comme suit :

jiP, dsigne le gain maximum gnr par le choix des i premiers objets dont la somme des poids

ne dpasse pas W, alors rsoudre le problme revient trouver la valeur de WnP, .

En calculant jiP, la squences dobjets peut tre divise en deux : les )1( i premiers objets et

lobjet i. Lobjet i est soit choisi soit ignor dans jiP, .


15/20

15

si lobjet i est choisi, avant de linclure, on doit sassurer que son poids ne dpasse pas la capacitj du sac dos. Si tel est le cas, alors il contribue la solution optimale par le gain iv . Par

consquent, nous avons bien

ijP= iwji vP i + ,1

Si lobjet i nest pas choisi dans la solution optimale. Dans ce cas, nous avons la capacit du sacinchange. Il suffirait donc de trouver la solution optimale parmi les 1i premiers objets, soit

jiP ,1 .

Bien entendu, pour trouver jiP, , il suffirait de prendre le maximum entre le cas o lobjet est

choisi ou ignor.

Les cas de base sont : jiP, = 0 pouri = 0 ouj = 0 (pourquoi donc ?)

Cela nous amne aux relations rcursives suivantes :

+

>

Documents

La Programmation Dynamique - Cours d'Introduction