Cours 8 : programmation dynamique

Claude Jard

Description

11 Cours 8 : “programmation”dynamique• 1. Pièces de monnaie• 2. Sac à dos• 3. Multiplications matricielles• 4. Plus longue sous-suite C. JARDCours ALGO1MMI+MIT2007-2008 2 • On dispose de pièces en nombre illimité, de valeurs10, 5, 2 et 1. Etant donné une somme S, on veut laréaliser avec un nombre minimum de pièces• Algorithme glouton : – On trie les tas de pièces par ordre décroissant de valeur– Pour chaque valeur (dans cet ordre), on prend le maximumde pièces possibles– Plus formellement, soit R la somme restante, initialisée à S.

• sac detaille
• contrainte ∑wi ≤
• gloutonne en remplissantle sac
• jeux de pièces pour lesquelsl'algorithme glouton
• nb minimum de pièces choisies parmi les ipremières
• sac àlui
• sac
• sacs
• pièces
• pièce

Sujets

• Algorithmique
• Glouton
• Detaille
• Extremum
• cours

Informations

• Publié par: phios
• Nombre de lectures: 185
• Langue: Français

Extrait

Cours 8 : “programmation” C. JARD dynamique Cours ALGO1 MMI+MIT 2007-2008

• 1. Pièces de monnaie • 2. Sac à dos • 3. Multiplications matricielles • 4. Plus longue sous-suite

1. Pièces de monnaie

1

• On dispose de pièces en nombre illimité, de valeurs 10, 5, 2 et 1. Etant donné une somme S, on veut la réaliser avec un nombre minimum de pièces

• Algorithme glouton :

– On trie les tas de pièces par ordre décroissant de valeur – Pour chaque valeur (dans cet ordre), on prend le maximum de pièces possibles – Plus formellement, soit R la somme restante, initialisée à S. Pour chaque valeur v , prendre c =R/vpièces et calculer i i i R := R - c .v i i

2

1

•

•

•

•

• •

Optimalité de cet algorithme pour lensemble de valeurs {10,5,2,1}

Quelque soit S : – On a au plus une pièce de 5 (sinon une de 10) – On a au plus une pièce de 1 (sinon une de 2) – On a au plus deux pièces de 2 (sinon une de 5 et une de 1) – On a au plus trois pièces qui ne sont pas des pièces de 10, pour un total≤9 (1x5 + 1x1 + 2x2 = 1x10) – Le reste de la somme est donc formé avec des pièces de 10, soitS/10  pièces de 10 – R vaut alors S mod 10 – Pour conclure, il suffit de voir les coefficients optimaux pour les sommes≤9 et de constater que ce sont bien ceux calculés par lalgorithme (1:1x1, 2:1x2, 3:1x2+1x1, 4: 2x2, 5:1x5, 6:1x5+1x1, 7: 1x5+1x2, 8: 1x5+1x2+1x1, 9:1x5+2x2) 3

Lalgorithme glouton nest pas optimal pour le jeu de pièces {6,4,1} (par exemple, 8 = 1x6+4x1 = 2x4).

Caractériser les jeux de pièces pour lesquels lalgorithme glouton est optimal est un problème ouvert !

i Un cas générique particulier : {d } , d>1 0≤i≤n-1 On peut montrer loptimalité de lalgorithme glouton dans ce cas

4

2

Preuve :

Soit g=g g la solution gloutonne et o=o o la solution 1 n 1 n optimale. Si g=o alors ok. Sinon, soitjle plus grand indice tel que g≠o . g >o par définition de j j j j lheuristique gloutonne. De plus, les deux sont  i-1 i-1 solutions, doncΣ=g d Σ. Comme g o d =o 1≤i≤1n j ≤i≤i in j i-1 i-1 j-1 pour i>j,Σo d =Σ+(g -o ) dg d ≥(g -o ) 1≤i≤j-1 j 1≤i≤j j j-1 j j j j-1 j-1 d≥d . Cela implique∃k, 1≤k≤oj-1 / ≥d. En effet,  k i-1 i-1 j-1 j-1 sinonΣo d≤Σ, ce quid -1 < d (d-1)d = 1≤i≤1j-1 j ≤i≤j-1 est faux. Mais alors o défini par o =o pour l≠k et l≠ l l k+1, o =o -d et o =o +1 est toujours solution k k k+1 k+1 k-1 k k-1 k k-1 k (o d + o d = (o -d)d + (o +1)d = o d + o d ) k k+1 k k+1 k k+1 et comporte moins de pièces (d>1), doù contradiction. Seule la première alternative est ok. 5

•

•

•

• •

Retour au cas général

On cherche m(S) le minimum de pièces avec les valeurs (v ,,v ), triées par valeurs croissantes (v =1) 1 n 1 Soit z(S,i) = nb minimum de pièces choisies parmi lesi premières (v ,,v ) pour faire S (z(S,n) = m(S)) 1 i Récurrence : z(S,i) = z(S,i-1) si S < v i z(S,i) = min { z(S,i-1) (pièce de val i non utilisée)  z(S-v ,i) + 1 } (on utilise une pièce de val i) i  sinon z(0,i) = 0 z(S,1) = S

6

3

i

0

0

0

1

1

1

Complexité en O(n x S), alors que le glouton coûtait O(n log n)

(v ,v ,v ) = (1,4,6) 1 2 3

2

2

2

3

3

3

1

1

4

2

2

5

2+1>2

1

3

6

2

4

7

S

2. Le problème du sac à dos (classique de loptimisation)

2

2

8

7

• On se donnenobjets ayant pour valeurs (entières) c ,,c et pour poids entier (ou volume) w ,,w 1 n 1 n • Le but est de remplir le sac à dos en maximisant∑c i sous la contrainte∑w≤W où W est la contenance i maximale du sac • En glouton: on trie en fonction du rapport “qualité/prix” c /w , puis on gloutonne en remplissant i i le sac avec le plus grand élément possible à chaque tour • Question: est-ce optimal ? • Le problème est que lon travaille avec des entiers (on ne peut pas couper les objets) 8

4

Contre-exemple

• Soit 3 objets. • Le premier (c /w max) remplissant le sac à i i lui tout seul et les deuxième et troisième tels que c >c et c >c , mais c +c >c et quils 1 2 1 3 2 3 1 puissent rentrer ensemble dans le sac • W = 10, (w ,w ,w )=(6,5,5), (c ,c ,c )=(7,5,5) 1 2 3 1 2 3

7

5

5

En programmation dynamique Credo : “demain est le premier jour du reste de ma vie”

9

• Comme tout à lheure, on décide de calculer une fonction un peu plus complexe pour avoir une expression récursive de la solution • C(v,i) : meilleur coût pour remplir un sac de taille v avec les i premiers objets -> calcul C(W,n) • Récurrence(soit on a pris le dernier objet, soit on ne la pas pris) : – C(v,i) = max { C(v,i-1), C(v-w ,i-1) + c } i i

10

5

i

n

i

i-1

Complexité en O(n x W), alors que le glouton coûtait O(n log n)

5

5

0

C(v-w ,i-1) i

v-w i

C(v,i)

v

Le calcul seffectue en remplissant la table en faisant bien attention à respecter les dépendances causales

C(v,i-1)

W

(w ,w ,w ) = (6,5,5), (c ,c ,c ) = (7,5,5) 1 2 3 1 2 3

5

7

7

0

6

7

7

7

7

7 +5

7

7

8

7

7

7

9

10

7

7

10

v

11

12

6

•

•

•

•

•

•

•

• •

•

3. Multiplication enchaînée de matrices

Donné une chaîne A ..A de matrices A (p ,p ) 1 n i i-1 i

Trouver un parenthèsage qui minimise le nombre de multiplications (ce calcul est plus important que le calcul du produit lui-même) Nombre de parenthèsages : – Pour n=1, une seule solution – Pour n≥2, le produit peut être vu comme le produit de deux sous produits bien parenthèsés avec une démarcation qui peut avoir lieu entre les k et (k+1)ème matrices, pour tout k≤n-1. On obtient donc la récurrence : – P(1)=1, P(n)=∑C(n-1,2n-2) (nombres deP(k)P(n-k) (=1/n k=1..n-1 n 1.5 Catalan) -> O(4 /n ) (croissance exponentielle) – La force brute doit être abandonnée 13

Généralisons : cherchons le parenthèsage optimal pour la chaîne A ..A i j

Ce parenthèsage sépare A ..A en deux parties A ..A i j i k A ..A pour un k tel que i≤k<j k+1 j Pour que le parenthèsage A ..A soit optimal, il faut i j que ceux de A ..A et A ..A le soient aussi i k k+1 j Soit m(i,j) le nb minimum de multiplications pour le calcul de A ..A i j Si j=i, le problème est trivial : m(i,i) = 0 Sinon m(i,j) = m(i,k) + m(k+1,j) + p p p i-1 k j [ A ..A (p ,p ), A ..A (p ,p ) ] i k i-1 k k+1 j k j Mais on ne connait pas k -> on explore toutes les solutions, en prenant la meilleure 14

7

• •

•

•

m(i,j) = min {m(i,k) + m(k+1,j) + p p p } i≤k jk<j i-1 Le calcul seffectue en respectant les dépendances : le calcul de m(i,j) demande tous les m(i,k) et tous les m(k+1,j) Linitialisation se fait sur m(i,i+1) = p p p i-1 i i+1 et m(i,i) = 0 3 Le coût est en O(n )

4. Plus longue sous-suite

15

• Motivation: calculer une distance entre les mots (par exemple pour distinguer une réponse fausse dune réponse mal orthographiée) • A = a a , B = b b 1 n 1 m • Sous-chaîne de A : a a i1 ik • On recherche les sous-chaînes communes à A et B et plus particulièrement la plus longue sous-chaîne commune (PLSCC) • Exemple: A =aabaababaa, B =ababaaabb • PLSCC = ababaaa (non consécutifs)

16

8

•

•

•

•

n Solution exhaustive: essai des 2 sous- suites dans chaque chaîne (peu efficace) Programmation dynamique: – p(i,j) : longueur de la PLSCC entre les i et j premières lettres de A et de B respectivement – p(i,j) = max { p(i,j-1), p(i-1,j), p(i-1,j-1) + [a =b ] } i j  avec [a =b ] = 1 si a =b , 0 sinon i j i j

Preuve

17

On constate dabord que ce max≤p(i,j) (trivial car p(i,j) est croissant en i et en j) Preuve de légalité : – Si a≠b , a et b ne peuvent pas appartenir tous deux à la i j i j même sous-suite commune. On a donc trois cas, soit a i appartient à la sous-suite et p(i,j) = p(i,j-1), soit cest b qui j y appartient, et on a p(i,j) = p(i-1,j), soit aucun des deux nappartient et p(i,j) = p(i-1,j-1) – Si a = b , la PLSCC contient a = b , et alors p(i,j) = p(i-1,j-1) i j i j + 1

18

9

b a d b c b a

Code

PLSCC(A,B) : n := longueur(A) ; m := longueur(B) ; pour i de 1 à n faire p[i,0] := (0,|) ; pour j de 0 à m faire p[0,j] := (0,-) ; pour i de 1 à n faire pour j de 1 à m faire si a = b alors i j p[i,j] := (p[i-1,j-1]+1,/) sinon si p[i-1,j]≥p[i,j-1] alors p[i,j] := (p[i-1,j],|)  sinon p[i,j] := (p[i,j-1],-)

0,| 0,| 0,| 0,| 0,| 0,| 0,| 0,-

PLSCC = b c b a : les lettres communes sont lorsque le trait plonge en diagonale

A = ab cbdab, B =bdcab a

1,/ 1,| 1,| 1,/ 1,| 1,/ 0,| 0,- b

2,| 2,| 2,/ 1,| 1,| 1,- 0,| 0,- d

2,| 2,| 2,| 2,| 2,/ 1,- 0,| 0,- c

3,| 3,/ 2,| 2,| 2,- 1,| 1,/ 0,- a

4,/ 3,| 3,| 3,/ 2,| 2,/ 1,- 0,- b

4,| 3,/ 3,| 3,- 2,| 2,- 1,- 0,- a

19

20

10

• •

•

Le coût est en O(nm) Il existe de meilleurs algorithmes dans la littérature pour : – Les cas où les séquences sont ressemblantes – Les cas où les séquences sont très différentes On trouve alors des algorithmes en O((n-r)m) ou en O(rm) avec r la longueur de la PLSCC de deux mots de longueurs n et m

21

11