Cours 8 : programmation dynamique
11
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
11
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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.
Voir
- 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
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/vpièces et calculer i i i R := R - c .v i i
2
1
•
•
•
•
• •
Optimalité de cet algorithme pour lensemble 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, soitS/10piè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 lalgorithme (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
Lalgorithme glouton nest 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 lalgorithme 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 loptimalité de lalgorithme 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 lheuristique 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), doù 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 loptimisation)
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 lon 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 quils 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 à lheure, 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 la 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 seffectue 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 seffectue en respectant les dépendances : le calcul de m(i,j) demande tous les m(i,k) et tous les m(k+1,j) Linitialisation 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 dune 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 dabord 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 cest b qui j y appartient, et on a p(i,j) = p(i-1,j), soit aucun des deux nappartient 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 cbdab, 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
