OCaml使用指南

Chapitre 6 Programmation dynamique 6.1 Programmation dynamique et proble`mes d’op- timisation La programmation dynamique est une me´thodologie ge´ne´rale pour conce- voir des algorithmes qui permettent de re´soudre efficacement certains proble`mes d’optimisation. Un proble`me d’optimisation admet un grand nombre de so- lutions. Chaque solution a une certaine valeur, et on veut identifier une solution dont la valeur est optimale (minimale ou maximale). Trouver un plus court chemin pour aller d’un point a` un autre dans un re´seau de trans- port est un proble`me d’optimisation La conception d’un algorithme de programmation dynamique se de´compose en quatre e´tapes. 1. Caracte´risation de la structure d’une solution optimale. 2. De´finition re´cursive de la valeur de la solution optimale. 3. Calcul ascendant de la valeur de la solution optimale. 4. Construction de la solution optimale a` partir des informations obtenues a` l’e´tape pre´ce´dente. L’e´tape 4 peut eˆtre omise si on a seulement besoin de la valeur de la solution optimale et non de la solution elle meˆme. Les sections suivantes de´crivent l’utilisation de la programmation dyna- mique pour re´soudre en temps polynomial trois proble`mes d’optimisation : le calcul d’un parcours optimal dans un atelier de montage, le calcul d’une chaˆıne de mulplications matricielles avec un nombre minimum d’ope´rations 71 72 CHAPITRE 6. PROGRAMMATION DYNAMIQUE scalaires, le calcul d’un arbre binaire de recherche optimal. Ensuite, nous mettrons en e´vidence deux caracte´ristiques que doit posse´der un proble`me d’optimisation pour que la programmation dynamique soit applicable. 6.2 Ordonnancement optimal d’une chaˆıne de mon- tage Un constructeur automobile posse`de un atelier avec deux chaˆınes de montage comportant chacune n postes de montages. Chaque ve´hicule doit passer par les n postes dans l’ordre. Le constructeur cherche a` de´terminer quels sont les postes a` se´lectionner sur la chaˆıne 1 et sur la chaˆıne 2 pour minimiser le de´lai de transit d’une voiture a` travers l’atelier. Les donne´es du proble`me d’optimisation qu’il doit re´soudre sont les suivantes. Pour i = 1, 2 et j = 1, . . . , n, on note Si,j le je`me poste de la chaˆıne i, ei le temps d’entre´e d’un ve´hicule sur la chaˆıne i, ai,j le temps de montage pour le poste j sur la chaˆıne i, ti,j le temps de transfert d’un ve´hicule de la chaˆıne i vers l’autre chaˆıne apre`s le poste Si,j et finallement xi le temps de sortie d’un ve´hicule de la chaˆıne i (voir Figure 6.1a). Chaque solution de ce proble`me d’optimisation est de´finie par le sous- ensemble de postes de la chaˆıne 1 utilise´s (les postes restant sont choisis dans la chaˆıne 2). Il y a donc 2n solutions possibles, i.e. le nombre de sous- ensembles d’un ensemble a` n e´le´ments. Par conse´quent, l’approche na¨ıve consistant a` conside´rer tous les chemins possibles est inefficace. La program- mation dynamique permet de re´soudre ce proble`me efficacement. La premie`re e´tape consiste a` identifier des sous-proble`mes dont les solu- tions optimales vont nous permettre de reconstituer une solution optimale du proble`me initial. Les sous-proble`mes a` conside´rer ici consistent a` calculer un itine´raire optimal jusqu’au poste Si,j pour i = 1, 2 et j = 1, . . . , n. Par exemple, conside´rons un itine´raire optimal jusqu’au poste S1,j . Si j = 1, il n’y a qu’un seul chemin possible. Pour j = 2, . . . , n, il y a deux possibilite´s. Un itine´raire optimal jusqu’a` S1,j est ou bien, un itine´raire optimal jusqu’a` S1,j−1 suivi du poste S1,j , ou bien, un itine´raire optimal jusqu’a` S2,j−1 suivi d’un changement de chaˆıne et du poste S1,j . La deuxie`me e´tape consiste a` de´finir la valeur optimale de manie`re re´cursive a` partir des valeurs des solutions optimales des sous-proble`mes. Soit fi[j] le de´lai optimal jusqu’a` Si,j et f∗ le de´lai optimal total. Pour traverser l’ate- lier, il faut atteindre ou bien S1,n ou bien S2,n et sortir de l’atelier. Par 6.2. ORDONNANCEMENTOPTIMAL D’UNE CHAIˆNE DEMONTAGE73 (a) j (b) 9 17 19 32 2929221513 1 2 1 1 221l2[j] l1[j]f1[j] f2[j] j 1 2 3 4 5 2 3 4 5 Entree S2,2 S2,3 S2,4 S2,5 Sortie S1,5S1,4S1,3S1,1 S1,2 23 1 f ∗ = 32 l∗ = 2 3 6 8 2 4 9 8 4 7 7 3 S2,1 5 2 1 5 3 2 3 3 2 1 2 Figure 6.1 – Exemple d’instance du proble`me d’ordonnacement optimal d’une chaˆıne de montage : (a) les donne´es du proble`me et (b) les tables de programmation dynamique. conse´quent, on a f∗ = min(f1[n] + x1, f2[n] + x2). Pour le poste 1 de chaque chaˆıne, il n’y a qu’un itine´raire possible : f1[1] = e1 + a1,1 f2[1] = e2 + a2,1 Pour le poste j = 2, . . . , n de la chaˆıne 1, il y a deux possibilite´s : f1[j] = min(f1[j − 1] + a1,j , f2[j − 1] + t2,j−1 + a1,j), (6.1) et syme´triquement f2[j] = min(f2[j − 1] + a2,j , f1[j − 1] + t1,j−1 + a2,j). (6.2) Les fi[j] sont les valeurs des solutions optimales des sous-proble`mes. Pour pouvoir reconstruire les solutions optimales elles-meˆmes, on de´finit li[j] le nume´ro de la chaˆıne (1 ou 2) dont le poste j − 1 est utilise´ par un chemin 74 CHAPITRE 6. PROGRAMMATION DYNAMIQUE optimal jusqu’au poste Si,j pour j = 2, . . . , n, (li[1] n’est pas de´fini car aucun poste ne vient avant le poste 1). La troisie`me e´tape consiste a` concevoir un algorithme qui calcule en temps polynomial les valeurs fi[j] des solutions optimales et les informations li[j] ne´cessaires a` la construction de ces solutions. L’algorithme suivant fait ce travail en O(n) en utilisant les formules re´cursives (6.1) et (6.2). Il revient a` remplir les tables de la Figure 6.1b de la gauche vers la droite. Plus-Rapide-Chemin(a, t, e, x, n) 1. f1[1]← e1 + a1,1 2. f2[1]← e2 + a2,1 3. pour j ← 2 a` n faire 4. si f1[j − 1] ≤ f2[j − 1] + t2,j−1 5. alors f1[j]← f1[j − 1] + a1,j 6. l1[j]← 1 7. sinon f1[j]← f2[j − 1] + t2,j−1 + a1,j 8. l1[j]← 2 9. si f2[j − 1] ≤ f1[j − 1] + t1,j−1 10. alors f2[j]← f2[j − 1] + a2,j 11. l2[j]← 2 12. sinon f2[j]← f1[j − 1] + t1,j−1 + a2,j 13. l2[j]← 1 14. si f1[n] + x1 ≤ f2[n] + x2 15. alors f∗ = f1[n] + x1 16. l∗ = 1 17. sinon f∗ = f2[n] + x2 18. l∗ = 2 Finalement, la quatrie`me et dernie`re e´tape consiste a` reconstruire une solution optimale en utilisant les informations sauvegarde´es a` l’e´tape 3. La proce´dure suivante affiche les postes utilise´s par une solution optimale par ordre de´croissant de nume´ro de poste. Afficher-Postes(l, n) 1. i← l∗ 2. afficher “chaˆıne” i, “poste” n 3. pour j ← n jusqu’a` 2 4. faire i← li[j] 5. afficher “chaˆıne” i, “poste” j − 1 6.3. CHAIˆNE DE MULTIPLICATIONS MATRICIELLES 75 6.3 Chaˆıne de multiplications matricielles On se donne une suite de n matrices A1, . . . , An et on veut calculer le produit A1A2 . . . An (6.3) Une fois que l’on a parenthe´se´ cette expression de manie`re a` supprimer l’am- bigu¨ıte´ lie´e a` l’ordre dans lequel les multiplications doivent eˆtre effectue´es, on peut e´valuer l’expression (6.3) en utilisant comme routine l’algorithme standard de multiplication de deux matrices. On dit d’un produit de matrices qu’il est comple`tement parenthe´se´ dans les deux cas suivants : – c’est une matrice isole´e, – c’est le produit de deux matrices comple`tement parenthe´se´es. Le produit de matrices est associatif par conse´quent quelque soit le pa- renthe´sage on obtient le meˆme re´sultat. Par exemple, si la chaˆıne de matrices est A1, A2, A3, A4, le produit A1A2A3A4 peut eˆtre parenthe´se´ de 5 fac¸ons diffe´rentes : (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4), (((A1A2)A3)A4). La fac¸on dont on parenthe`se une telle chaˆıne de matrices peut avoir une grande importance sur le nombre d’ope´rations ne´cessaires pour effectuer le produit. Si A est une matrice p × q et B une matrice q × r, la matrice produit est une matrice q× r. La complexite´ du calcul du produit est domine´ par le nombre de multiplications scalaires qui est e´gal a` pqr. Pour illustrer les diffe´rences de couˆts obtenus en adoptant des parenthe´sages diffe´rents, conside´rons un produit de 3 matrices A1, A2, A3 de dimensions respectives 10 × 100, 100 × 5 et 5 × 50. Si on effectue les multiplications dans l’ordre donne´ par le parenthe´sage ((A1A2)A3), le nombre d’ope´rations ne´cessaires est 10×100×5 = 5000 pour obtenir le produit A1A2, qui est une matrice 10× 5, plus 10× 5× 50 = 2500 pour obtenir le produit ((A1A2)A3), soit 7500 ope´rations en tout. Si on adopte le parenthe´sage (A1(A2A3)), le nombre d’ope´rations ne´cessaires est 100×5×50 = 25000 pour obtenir le pro- 76 CHAPITRE 6. PROGRAMMATION DYNAMIQUE duit A2A3, qui est une matrice 100×50, plus 10×100×50 = 50000 pour ob- tenir le produit (A1(A2A3)), soit 75000 ope´rations en tout. Par conse´quent, calculer le produit en accord avec le premier parenthe´sage est 10 fois plus rapide. Notre proble`me se formule de la fac¸on suivante : e´tant donne´ une suite de n matrices A1, . . . , An, avec pi−1×pi la dimension de la matrice Ai, pour i = 1, . . . , n, trouver le parenthe`sage du produit A1A2 . . . An qui minimise le nombre de multiplications scalaires a` effectuer. Remarque : le nombre de parenthe´sages diffe´rents est une fonction exponentielle de n. Par conse´quent, la strate´gie qui consiste a` e´nume´rer tous les parenthe´sages est exclue pour de grandes valeurs de n. 6.3.1 Structure d’un parenthe´sage optimal La premie`re e´tape dans une approche de type programmation dynamique consiste a` identifier la structure des solutions optimales. NotonsAi..j la matrice qui re´sulte de l’e´valuation du produitAiAi+1 . . . Aj . Un parenthe´sage optimal de A1 . . . An de´coupe le produit entre les matrices Ak et Ak+1 pour un certain k compris entre 1 et n − 1. C’est-a`-dire que pour un certain k, on calcule d’abord le produit A1..k et Ak+1..n, ensuite on multiplie ces produits pour obtenir le produit final A1..n. Le couˆt de ce pa- renthe´sage est la somme des couˆts du calcul de A1..k et Ak+1..n et du produit de ces deux matrices. Remarquons que le parenthe´sage de A1..k doit eˆtre lui-meˆme un pa- renthe´sage optimal de A1 . . . Ak, de meˆme le parenthe´sage de Ak+1..n doit eˆtre optimal. Par conse´quent, une solution optimal d’un proble`me de pa- renthe´sage contient elle-meˆme des solutions optimales de sous-proble`mes de parenthe´sage. La pre´sence de sous-structures optimales dans une solution optimale est l’une des caracte´ristiques des proble`mes pour lesquels la pro- grammation dynamique est applicable. 6.3.2 Une solution re´cursive La seconde e´tape dans une approche de type programmation dynamique consiste a` de´finir la valeur de la solution en fonction des solutions optimales de sous-proble`mes. Dans notre cas, un sous-proble`me consiste a` de´terminer le 6.3. CHAIˆNE DE MULTIPLICATIONS MATRICIELLES 77 couˆt minimal d’un parenthe´sage de Ai . . . Aj pour 1 ≤ i ≤ j ≤ n. Soit m[i, j] le nombre minimum de multiplications scalaires ne´cessaires pour obtenir le produit Ai..j . Le nombre minimum de multiplications scalaires ne´cessaires pour obtenir A1..n sera m[1, n]. On peut calculer m[i, j] re´cursivement de la fac¸on suivante. Si i = j, la chaˆıne de matrices se re´duit a` une seule matrice Ai..i = Ai, aucune ope´ration n’est ne´cessaire, et donc m[i, i] = 0 pour i = 1, . . . , n. Pour calculer m[i, j] quand i < j, on se sert de la structure des solutions optimales que nous avons pre´ce´demment mise en e´vidence. Supposons que la solution optimale du sous-proble`me de´coupe le produit Ai . . . Aj entre Ak et Ak+1 avec i ≤ k < j. Alors, m[i, j] est e´gal au nombre minimum de multiplications scalaires pour obtenir Ai..k et Ak+1..j plus le nombre de multiplications ne´cessaires pour ef- fectuer le produit matriciel Ai..kAk+1..j , c’est-a`-dire pi−1pkpj multiplications scalaires, on obtient m[i, j] = m[i, k] +m[k + 1, j] + pi−1pkpj . Cette e´quation re´cursive suppose que nous connaissions la valeur de k, ce qui n’est pas le cas. Il y a seulement j − i valeurs possibles pour k : les valeurs i, i + 1, . . . , j − 1. Puisque la solution optimale correspond a` l’une de ces valeurs, il suffit de les essayer toutes et de garder la meilleure. Par conse´quent, notre de´finition re´cursive pour le couˆt minimum d’un pa- renthe`sage de Ai . . . Aj devient m[i, j] = � 0 si i = j, mini≤k