Programmation dynamique - Dynamic programming

Figure 1. Trouver le chemin le plus court dans un graphe en utilisant une sous-structure optimale ; une ligne droite indique un seul bord; une ligne ondulée indique un chemin le plus court entre les deux sommets qu'elle relie (parmi d'autres chemins, non représentés, partageant les deux mêmes sommets) ; la ligne en gras est le chemin le plus court du début au but.

La programmation dynamique est à la fois une méthode d' optimisation mathématique et une méthode de programmation informatique. La méthode a été développée par Richard Bellman dans les années 1950 et a trouvé des applications dans de nombreux domaines, de l'ingénierie aérospatiale à l' économie .

Dans les deux contextes, il s'agit de simplifier un problème compliqué en le décomposant en sous-problèmes plus simples de manière récursive . Alors que certains problèmes de décision ne peuvent pas être séparés de cette façon, les décisions qui s'étendent sur plusieurs points dans le temps se séparent souvent de manière récursive. De même, en informatique, si un problème peut être résolu de manière optimale en le divisant en sous-problèmes puis en trouvant récursivement les solutions optimales aux sous-problèmes, on dit alors qu'il a une sous-structure optimale .

Si les sous-problèmes peuvent être imbriqués récursivement dans des problèmes plus grands, de sorte que les méthodes de programmation dynamique soient applicables, alors il existe une relation entre la valeur du problème plus large et les valeurs des sous-problèmes. Dans la littérature sur l'optimisation, cette relation est appelée équation de Bellman .

Aperçu

Optimisation mathématique

En termes d'optimisation mathématique, la programmation dynamique fait généralement référence à la simplification d'une décision en la décomposant en une séquence d'étapes de décision au fil du temps. Cela se fait en définissant une séquence de fonctions de valeur V 1 , V 2 , ..., V n prenant y comme argument représentant l' état du système aux instants i de 1 à n . La définition de V n ( y ) est la valeur obtenue dans l' état y au dernier instant n . Les valeurs V i à des moments antérieurs i  =  n -  1,  n  - 2, ..., 2, 1 se trouve en travaillant vers l' arrière, en utilisant un récursif relation appelée équation de Bellman . Pour i  = 2, ...,  n , V i −1 à tout état y est calculé à partir de V i en maximisant une fonction simple (généralement la somme) du gain d'une décision à l'instant i  − 1 et la fonction V i au nouvel état du système si cette décision est prise. Puisque V i a déjà été calculé pour les états nécessaires, l'opération ci-dessus donne V i -1 pour ces états. Enfin, V 1 à l'état initial du système est la valeur de la solution optimale. Les valeurs optimales des variables de décision peuvent être récupérées, une par une, en retraçant les calculs déjà effectués.

Théorie du contrôle

En théorie du contrôle , un problème typique est de trouver un contrôle admissible qui amène le système à suivre une trajectoire admissible sur un intervalle de temps continu qui minimise une fonction de coût

La solution à ce problème est une loi ou politique de contrôle optimal , qui produit une trajectoire optimale et une fonction de coût restant à parcourir . Cette dernière obéit à l'équation fondamentale de la programmation dynamique :

une équation différentielle partielle connue sous le nom d' équation de Hamilton-Jacobi-Bellman , dans laquelle et . On trouve que la minimisation en termes de , , et la fonction inconnue , puis substitue le résultat dans l'équation de Hamilton-Jacobi-Bellman pour obtenir l'équation aux dérivées partielles à résoudre avec la condition aux limites . En pratique, cela nécessite généralement des techniques numériques pour une certaine approximation discrète de la relation d'optimisation exacte.

Alternativement, le processus continu peut être approximé par un système discret, ce qui conduit à une relation de récurrence suivante analogue à l'équation de Hamilton-Jacobi-Bellman :

au -ième étage d' intervalles de temps discrets également espacés, et où et désignent des approximations discrètes de et . Cette équation fonctionnelle est connue sous le nom d' équation de Bellman , qui peut être résolue pour une solution exacte de l'approximation discrète de l'équation d'optimisation.

Exemple d'économie : le problème de l'épargne optimale de Ramsey

En économie, l'objectif est généralement de maximiser (plutôt que de minimiser) une fonction dynamique de bien-être social . Dans le problème de Ramsey, cette fonction relie les quantités de consommation aux niveaux d' utilité . En gros, le planificateur est confronté au compromis entre la consommation contemporaine et la consommation future (via l'investissement dans le stock de capital utilisé dans la production), connu sous le nom de choix intertemporel . Les consommations futures sont actualisées à taux constant . Une approximation discrète de l'équation de transition du capital est donnée par

où est la consommation, est le capital, et est une fonction de production satisfaisant les conditions d'Inada . Un stock de capital initial est supposé.

Soit la consommation à la période t , et supposons que la consommation donne une utilité aussi longtemps que le consommateur vit. Supposons que le consommateur soit impatient, de sorte qu'il actualise l' utilité future d'un facteur b à chaque période, où . Laissez - être le capital en période t . Supposons que le capital initial est un montant donné , et supposons que le capital et la consommation de cette période déterminent le capital de la période suivante comme , où A est une constante positive et . Supposons que le capital ne peut pas être négatif. Le problème de décision du consommateur peut alors s'écrire comme suit :

soumis à pour tous

Écrit de cette façon, le problème semble compliqué, car il implique la résolution de toutes les variables de choix . (Le capital n'est pas une variable de choix - le capital initial du consommateur est considéré comme donné.)

L'approche de programmation dynamique pour résoudre ce problème consiste à le diviser en une séquence de décisions plus petites. Pour ce faire, nous définissons une séquence de fonctions de valeur , pour lesquelles représentent la valeur d'avoir n'importe quelle quantité de capital k à chaque instant t . Il n'y a (par hypothèse) aucune utilité à avoir un capital après le décès, .

La valeur de n'importe quelle quantité de capital à n'importe quel moment précédent peut être calculée par induction en arrière en utilisant l' équation de Bellman . Dans ce problème, pour chaque , l'équation de Bellman est

sujet à

Ce problème est beaucoup plus simple que celui que nous avons écrit précédemment, car il n'implique que deux variables de décision, et . Intuitivement, au lieu de choisir son plan à vie à la naissance, le consommateur peut procéder étape par étape. Au temps t , son capital actuel est donné, et il lui suffit de choisir la consommation courante et l'épargne .

Pour résoudre réellement ce problème, nous travaillons à rebours. Pour simplifier, le niveau actuel de capital est noté k . est déjà connue, donc en utilisant l'équation de Bellman une fois que nous pouvons calculer , et ainsi de suite jusqu'à ce que nous arrivions à , qui est la valeur du problème de décision initial pour toute la durée de vie. En d'autres termes, une fois que nous connaissons , nous pouvons calculer , qui est le maximum de , où est la variable de choix et .

En travaillant à rebours, on peut montrer que la fonction de valeur au temps est

où chacun est une constante, et la quantité optimale à consommer à un moment donné est

qui peut être simplifié en

Nous voyons qu'il est optimal de consommer une fraction plus importante de la richesse actuelle à mesure que l'on vieillit, consommant finalement toute la richesse restante à la période T , la dernière période de la vie.

Programmation informatique

Il y a deux attributs clés qu'un problème doit avoir pour que la programmation dynamique soit applicable : la sous - structure optimale et les sous-problèmes qui se chevauchent . Si un problème peut être résolu en combinant des solutions optimales à des sous-problèmes qui ne se chevauchent pas , la stratégie est plutôt appelée « diviser pour régner ». C'est pourquoi le tri par fusion et le tri rapide ne sont pas classés comme des problèmes de programmation dynamique.

Une sous-structure optimale signifie que la solution à un problème d'optimisation donné peut être obtenue par la combinaison de solutions optimales à ses sous-problèmes. De telles sous-structures optimales sont généralement décrites au moyen de la récursivité . Par exemple, étant donné un graphe G=(V,E) , le plus court chemin p d'un sommet u à un sommet v présente une sous-structure optimale : prendre n'importe quel sommet intermédiaire w sur ce plus court chemin p . Si p est vraiment le chemin le plus court, alors il peut être divisé en sous-chemins p 1 de u à w et p 2 de w à v tels que ceux-ci, à leur tour, sont bien les chemins les plus courts entre les sommets correspondants (par le simple l'argument couper-coller décrit dans Introduction aux algorithmes ). Par conséquent, on peut facilement formuler la solution pour trouver les chemins les plus courts de manière récursive, ce que fait l' algorithme de Bellman-Ford ou l' algorithme de Floyd-Warshall .

Le chevauchement des sous-problèmes signifie que l'espace des sous-problèmes doit être petit, c'est-à-dire que tout algorithme récursif résolvant le problème devrait résoudre les mêmes sous-problèmes encore et encore, plutôt que de générer de nouveaux sous-problèmes. Par exemple, considérons la formulation récursive pour générer la série de Fibonacci : F i = F i −1 + F i −2 , avec le cas de base F 1  =  F 2  = 1. Alors F 43F 42  +  F 41 , et F 42F 41  +  F 40 . Maintenant F 41 est résolu dans les sous-arbres récursifs de F 43 ainsi que de F 42 . Même si le nombre total de sous-problèmes est en fait petit (seulement 43 d'entre eux), nous finissons par résoudre les mêmes problèmes encore et encore si nous adoptons une solution récursive naïve comme celle-ci. La programmation dynamique tient compte de ce fait et ne résout chaque sous-problème qu'une seule fois.

Figure 2. Le graphe du sous-problème pour la séquence de Fibonacci. Le fait qu'il ne s'agisse pas d'un arbre indique des sous-problèmes qui se chevauchent.

Ceci peut être réalisé de deux manières :

  • Approche descendante : C'est la conséquence directe de la formulation récursive de n'importe quel problème. Si la solution à n'importe quel problème peut être formulée récursivement en utilisant la solution de ses sous-problèmes, et si ses sous-problèmes se chevauchent, alors on peut facilement mémoriser ou stocker les solutions des sous-problèmes dans un tableau. Chaque fois que nous essayons de résoudre un nouveau sous-problème, nous vérifions d'abord le tableau pour voir s'il est déjà résolu. Si une solution a été enregistrée, nous pouvons l'utiliser directement, sinon nous résolvons le sous-problème et ajoutons sa solution au tableau.
  • Approche ascendante : une fois que nous avons formulé la solution à un problème de manière récursive en termes de sous-problèmes, nous pouvons essayer de reformuler le problème de manière ascendante : essayez de résoudre d'abord les sous-problèmes et utilisez leurs solutions pour construire- et trouver des solutions à des sous-problèmes plus importants. Cela se fait également généralement sous forme de tableau en générant de manière itérative des solutions à des sous-problèmes de plus en plus gros en utilisant les solutions à de petits sous-problèmes. Par exemple, si nous connaissons déjà les valeurs de F 41 et F 40 , nous pouvons calculer directement la valeur de F 42 .

Certains langages de programmation peuvent mémoriser automatiquement le résultat d'un appel de fonction avec un ensemble particulier d'arguments, afin d'accélérer l' évaluation de l' appel par nom (ce mécanisme est appelé appel par besoin ). Certains langages le permettent de manière portable (par exemple Scheme , Common Lisp , Perl ou D ). Certaines langues ont une mémorisation automatique intégrée, comme le Prolog et le J , qui prennent en charge la mémorisation avec l' adverbe M .. Dans tous les cas, cela n'est possible que pour une fonction référentiellement transparente . La mémorisation est également rencontrée en tant que modèle de conception facilement accessible dans les langages basés sur la réécriture de termes tels que Wolfram Language .

Bioinformatique

La programmation dynamique est largement utilisée en bioinformatique pour des tâches telles que l' alignement de séquences , le repliement des protéines , la prédiction de la structure de l'ARN et la liaison protéine-ADN. Les premiers algorithmes de programmation dynamique pour la liaison protéine-ADN ont été développés dans les années 1970 indépendamment par Charles DeLisi aux États-Unis et Georgii Gurskii et Alexander Zasedatelev en URSS. Récemment, ces algorithmes sont devenus très populaires en bioinformatique et en biologie computationnelle , en particulier dans les études du positionnement des nucléosomes et de la liaison aux facteurs de transcription .

Exemples : algorithmes informatiques

Algorithme de Dijkstra pour le problème du plus court chemin

Du point de vue de la programmation dynamique, l'algorithme de Dijkstra pour le problème du plus court chemin est un schéma d'approximations successives qui résout l'équation fonctionnelle de programmation dynamique pour le problème du plus court chemin par la méthode Reaching .

En fait, l'explication de Dijkstra de la logique derrière l'algorithme, à savoir

Problème 2. Trouver le chemin de longueur totale minimale entre deux nœuds donnés et .

On utilise le fait que, si est un nœud sur le chemin minimal de à , la connaissance de ce dernier implique la connaissance du chemin minimal de à .

est une paraphrase du célèbre principe d'optimalité de Bellman dans le contexte du problème du plus court chemin .

séquence de Fibonacci

L'utilisation de la programmation dynamique dans le calcul du n ème membre de la séquence de Fibonacci améliore considérablement ses performances. Voici une implémentation naïve, basée directement sur la définition mathématique :

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

Notez que si nous appelons, disons, fib(5), nous produisons un arbre d'appels qui appelle la fonction sur la même valeur plusieurs fois :

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particulier, a fib(2)été calculé trois fois à partir de zéro. Dans les exemples plus grands, beaucoup plus de valeurs de fib, ou de sous - problèmes , sont recalculées, ce qui conduit à un algorithme de temps exponentiel.

Maintenant, supposons que nous ayons un objet map simple , m , qui mappe chaque valeur de fibqui a déjà été calculée à son résultat, et nous modifions notre fonction pour l'utiliser et la mettre à jour. La fonction résultante ne nécessite que O ( n ) temps au lieu d'un temps exponentiel (mais nécessite O ( n ) espace):

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Cette technique de sauvegarde des valeurs déjà calculées s'appelle la mémorisation ; c'est l'approche descendante, puisque nous décomposons d'abord le problème en sous-problèmes, puis calculons et stockons les valeurs.

Dans le bas vers le haut approche, on calcule les valeurs plus petites de la fibpremière, puis construire des valeurs plus élevées de leur part . Cette méthode utilise également le temps O( n ) car elle contient une boucle qui se répète n − 1 fois, mais elle ne prend qu'un espace constant (O(1)), contrairement à l'approche descendante qui nécessite un espace O( n ) pour stocker la carte.

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
    return currentFib

Dans les deux exemples, nous ne calculons qu'une fib(2)seule fois, puis nous l'utilisons pour calculer à la fois fib(4)et fib(3), au lieu de le calculer chaque fois que l'un d'eux est évalué.

La méthode ci-dessus prend en fait du temps pour un grand n car l'addition de deux entiers avec des bits chacun prend du temps. (Le n ième nombre de Fibonacci a des bits.) En outre, il existe une forme fermée pour la séquence de Fibonacci, connue sous le nom de formule de Binet , à partir de laquelle le -ième terme peut être calculé en un temps approximatif , ce qui est plus efficace que la technique de programmation dynamique ci-dessus. . Cependant, la récurrence simple donne directement la forme matricielle qui conduit à un algorithme approximatif par exponentiation matricielle rapide .

Un type de matrice 0-1 équilibrée

Considérons le problème de l'attribution de valeurs, soit zéro, soit un, aux positions d'une matrice n × n , avec n pair, de sorte que chaque ligne et chaque colonne contienne exactement n /2 zéros et n /2 uns. Nous demandons combien de missions différentes il y a pour une donnée . Par exemple, lorsque n = 4 , quatre solutions possibles sont

Il existe au moins trois approches possibles : la force brute , le backtracking et la programmation dynamique.

La force brute consiste à vérifier toutes les affectations de zéros et de uns et à compter celles qui ont des lignes et des colonnes équilibrées ( n /2 zéros et n /2 uns). Comme il existe des affectations possibles et des affectations sensées, cette stratégie n'est pas pratique sauf peut-être jusqu'à .

Le retour en arrière pour ce problème consiste à choisir un certain ordre des éléments de la matrice et à placer récursivement des uns ou des zéros, tout en vérifiant que dans chaque ligne et colonne le nombre d'éléments qui n'ont pas été attribués plus le nombre de uns ou de zéros sont tous les deux d'au moins n / 2 . Bien que plus sophistiquée que la force brute, cette approche visitera chaque solution une fois, ce qui la rend peu pratique pour n supérieur à six, car le nombre de solutions est déjà de 116 963 796 250 pour n  = 8, comme nous le verrons.

La programmation dynamique permet de compter le nombre de solutions sans les visiter toutes. Imaginez un retour en arrière des valeurs pour la première ligne : de quelles informations aurions-nous besoin sur les lignes restantes, afin de pouvoir compter avec précision les solutions obtenues pour chaque valeur de la première ligne ? Nous considérons k × n planches, où 1 kn , dont les lignes contiennent des zéros et des uns. La fonction f à laquelle la mémoisation est appliquée mappe des vecteurs de n paires d'entiers au nombre de planches admissibles (solutions). Il y a une paire pour chaque colonne, et ses deux composantes indiquent respectivement le nombre de zéros et de uns qui n'ont pas encore été placés dans cette colonne. On cherche la valeur de ( arguments ou un vecteur d' éléments). Le processus de création de sous-problèmes consiste à parcourir chacune des affectations possibles pour la rangée supérieure du tableau, et à parcourir chaque colonne, en soustrayant une de l'élément approprié de la paire pour cette colonne, selon que l'affectation de la rangée supérieure contenait un zéro ou un à cette position. Si l'un des résultats est négatif, alors l'affectation n'est pas valide et ne contribue pas à l'ensemble des solutions (arrêts de récursivité). Sinon, nous avons une affectation pour la rangée supérieure du tableau k × n et calculons récursivement le nombre de solutions pour le tableau restant ( k − 1) × n , en ajoutant les nombres de solutions pour chaque affectation admissible de la rangée supérieure et en retournant la somme, qui est en cours de mémorisation. Le cas de base est le sous-problème trivial, qui se produit pour une carte 1 × n . Le nombre de solutions pour cette carte est nul ou un, selon que le vecteur est une permutation de n /2 et n /2 paires ou non.

Par exemple, dans les deux premières planches illustrées ci-dessus, les séquences de vecteurs seraient

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0      0      1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

Le nombre de solutions (séquence A058527 dans l' OEIS ) est

Des liens vers la mise en œuvre MAPLE de l'approche de programmation dynamique peuvent être trouvés parmi les liens externes .

Damier

Considérons un damier avec n × n carrés et une fonction de coût c(i, j)qui renvoie un coût associé au carré (i,j)( iétant la ligne, jétant la colonne). Par exemple (sur un damier 5 × 5),

5 6 7 4 7 8
4 7 6 1 1 4
3 3 5 7 8 2
2 6 7 0
1 *5*
1 2 3 4 5

Ainsi c(1, 3) = 5

Disons qu'il y avait un vérificateur qui pouvait commencer à n'importe quelle case du premier rang (c'est-à-dire une rangée) et que vous vouliez connaître le chemin le plus court (la somme des coûts minimaux à chaque rang visité) pour arriver au dernier rang ; en supposant que le contrôleur ne puisse se déplacer qu'en diagonale vers la gauche vers l'avant, en diagonale vers l'avant à droite ou vers l'avant. C'est-à-dire qu'un contrôleur sur (1,3)peut se déplacer vers (2,2), (2,3)ou (2,4).

5
4
3
2 X X X
1 o
1 2 3 4 5

Ce problème présente une sous-structure optimale . C'est-à-dire que la solution à l'ensemble du problème repose sur des solutions aux sous-problèmes. Définissons une fonction q(i, j)comme

q ( i , j ) = le coût minimum pour atteindre le carré ( i , j ).

En commençant au rang net en descendant jusqu'au rang 1, nous calculons la valeur de cette fonction pour tous les carrés à chaque rang successif. Choisir le carré qui détient la valeur minimale à chaque rang nous donne le chemin le plus court entre le rang net le rang 1.

La fonction q(i, j)est égale au coût minimum pour accéder à l'une des trois cases en dessous (puisque ce sont les seules cases qui peuvent l'atteindre) plus c(i, j). Par exemple:

5
4 UNE
3 B C
2
1
1 2 3 4 5

Maintenant, définissons q(i, j)en termes un peu plus généraux :

La première ligne de cette équation traite d'un tableau modélisé sous forme de carrés indexés 1à la borne la plus basse et nà la borne la plus élevée. La deuxième ligne précise ce qui se passe au premier rang ; fournir un cas de base. La troisième ligne, la récursivité, est la partie importante. Il représente les A,B,C,Dtermes de l'exemple. De cette définition, nous pouvons dériver un code récursif simple pour q(i, j). Dans le pseudocode suivant, nest la taille du tableau, c(i, j)est la fonction de coût et min()renvoie le minimum d'un certain nombre de valeurs :

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

Cette fonction ne calcule que le coût du chemin, pas le chemin réel. Nous discutons du chemin réel ci-dessous. Ceci, comme l'exemple des nombres de Fibonacci, est horriblement lent car il présente également l' attribut de sous-problèmes qui se chevauchent . C'est-à-dire qu'il recalcule les mêmes coûts de chemin encore et encore. Cependant, nous pouvons le calculer beaucoup plus rapidement de manière ascendante si nous stockons les coûts de chemin dans un tableau à deux dimensions q[i, j]plutôt que d'utiliser une fonction. Cela évite le recalcul ; toutes les valeurs nécessaires pour le tableau q[i, j]sont calculées à l'avance une seule fois. Les valeurs précalculées pour (i,j)sont simplement recherchées chaque fois que nécessaire.

Nous devons également savoir quel est le chemin le plus court. Pour ce faire, nous utilisons un autre tableau p[i, j]; un tableau prédécesseur . Ce tableau enregistre le chemin vers n'importe quel carré s. Le prédécesseur de sest modélisé comme un décalage par rapport à l'indice (en q[i, j]) du coût de chemin précalculé de s. Pour reconstruire le chemin complet, nous recherchons le prédécesseur de s, puis le prédécesseur de ce carré, puis le prédécesseur de ce carré, et ainsi de suite de manière récursive, jusqu'à ce que nous atteignions le carré de départ. Considérez le code suivant :

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

Maintenant, le reste est une simple question de trouver le minimum et de l'imprimer.

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if q[n, i] < min
            minIndex := i
            min := q[n, i]
    printPath(n, minIndex)
function printPath(y, x)
    print(x)
    print("<-")
    if y = 2
        print(x + p[y, x])
    else
        printPath(y-1, x + p[y, x])

Alignement de séquence

En génétique , l' alignement de séquences est une application importante où la programmation dynamique est essentielle. Typiquement, le problème consiste à transformer une séquence en une autre à l'aide d'opérations d'édition qui remplacent, insèrent ou suppriment un élément. Chaque opération a un coût associé, et l'objectif est de trouver la séquence de modifications avec le coût total le plus bas .

Le problème peut être énoncé naturellement comme une récursivité, une séquence A est éditée de manière optimale en une séquence B soit :

  1. insérer le premier caractère de B, et effectuer un alignement optimal de A et la queue de B
  2. supprimer le premier caractère de A, et effectuer l'alignement optimal de la queue de A et B
  3. remplacer le premier caractère de A par le premier caractère de B, et effectuer des alignements optimaux des queues de A et B.

Les alignements partiels peuvent être tabulés dans une matrice, où la cellule (i,j) contient le coût de l'alignement optimal de A[1..i] à B[1..j]. Le coût dans la cellule (i,j) peut être calculé en ajoutant le coût des opérations pertinentes au coût de ses cellules voisines, et en sélectionnant l'optimum.

Différentes variantes existent, voir algorithme Smith-Waterman et algorithme Needleman-Wunsch .

Casse-tête Tour de Hanoï

Une maquette des Tours de Hanoï (avec 8 disques)
Une solution animée du puzzle de la Tour de Hanoï pour T(4,3) .

La Tour de Hanoï ou Tours de Hanoï est un jeu mathématique ou un puzzle . Il se compose de trois tiges et d'un certain nombre de disques de différentes tailles qui peuvent glisser sur n'importe quelle tige. Le puzzle commence avec les disques dans une pile ordonnée par ordre croissant de taille sur une tige, le plus petit en haut, créant ainsi une forme conique.

L'objectif du puzzle est de déplacer la pile entière vers une autre tige, en obéissant aux règles suivantes :

  • Un seul disque peut être déplacé à la fois.
  • Chaque mouvement consiste à prendre le disque supérieur d'une des tiges et à le faire glisser sur une autre tige, au-dessus des autres disques éventuellement déjà présents sur cette tige.
  • Aucun disque ne peut être placé sur un disque plus petit.

La solution de programmation dynamique consiste à résoudre l' équation fonctionnelle

S(n,h,t) = S(n-1,h, non(h,t)) ; S(1,h,t) ; S(n-1,pas(h,t),t)

où n désigne le nombre de disques à déplacer, h désigne la tige mère, t désigne la tige cible, not(h,t) désigne la troisième tige (ni h ni t), ";" désigne la concaténation, et

S(n, h, t) := solution à un problème composé de n disques qui doivent être déplacés de la tige h à la tige t.

Pour n=1 le problème est trivial, à savoir S(1,h,t) = "déplacer un disque de la tige h vers la tige t" (il ne reste qu'un disque).

Le nombre de coups requis par cette solution est de 2 n  − 1. Si l'objectif est de maximiser le nombre de coups (sans faire de vélo), alors l' équation fonctionnelle de programmation dynamique est légèrement plus compliquée et 3 n  − 1 coups sont nécessaires.

Puzzle de chute d'oeufs

Ce qui suit est une description de l'instance de ce célèbre puzzle impliquant N=2 œufs et un bâtiment avec H=36 étages :

Supposons que nous souhaitions savoir de quels étages d'un immeuble de 36 étages peuvent déposer des œufs en toute sécurité et lesquels provoqueront la rupture des œufs à l'atterrissage (en utilisant la terminologie anglaise des États-Unis , dans laquelle le premier étage est au niveau du sol). Nous faisons quelques hypothèses :
  • Un œuf qui survit à une chute peut être réutilisé.
  • Un œuf cassé doit être jeté.
  • L'effet d'une chute est le même pour tous les œufs.
  • Si un œuf se brise en tombant, il se brisera s'il tombe d'une fenêtre plus haute.
  • Si un œuf survit à une chute, il survivra à une chute plus courte.
  • Il n'est pas exclu que les fenêtres du premier étage cassent des œufs, ni que les œufs puissent survivre aux fenêtres du 36e étage.
Si un seul œuf est disponible et que l'on souhaite être sûr d'obtenir le bon résultat, l'expérience ne peut être réalisée que d'une seule manière. Déposez l'œuf par la fenêtre du premier étage ; s'il survit, laissez-le tomber de la fenêtre du deuxième étage. Continuez vers le haut jusqu'à ce qu'il casse. Dans le pire des cas, cette méthode peut nécessiter 36 fientes. Supposons que 2 œufs soient disponibles. Quel est le plus petit nombre de crottes d'œufs garantis de fonctionner dans tous les cas ?

Pour dériver une équation fonctionnelle de programmation dynamique pour ce puzzle, supposons que l' état du modèle de programmation dynamique soit une paire s = (n,k), où

n = nombre d'œufs d'essai disponibles, n = 0, 1, 2, 3, ..., N  − 1.
k = nombre d'étages (consécutifs) encore à tester, k = 0, 1, 2, ..., H  − 1.

Par exemple, s = (2,6) indique que deux œufs de test sont disponibles et que 6 étages (consécutifs) doivent encore être testés. L'état initial du processus est s = ( N , H ) où N désigne le nombre d'œufs d'essai disponibles au début de l'expérience. Le processus se termine soit lorsqu'il n'y a plus d'œufs de test ( n = 0) ou lorsque k = 0, selon la première éventualité. Si la terminaison se produit à l'état s = (0, k ) et k  > 0, alors le test a échoué.

Maintenant, laisse

W ( n , k ) = nombre minimum d'essais requis pour identifier la valeur du plancher critique dans le pire des cas étant donné que le processus est dans l'état s = ( n , k ).

On peut alors montrer que

W ( n , k ) = 1 + min{max( W ( n − 1, x − 1), W ( n , kx )): x = 1, 2, ..., k }

avec W ( n ,0) = 0 pour tout n  > 0 et W (1, k ) = k pour tout  k . Il est facile de résoudre cette équation de manière itérative en augmentant systématiquement les valeurs de n et  k .

Solution DP plus rapide utilisant un paramétrage différent

Notez que la solution ci-dessus prend du temps avec une solution DP. Cela peut être amélioré dans le temps par une recherche binaire sur l'optimal dans la récurrence ci-dessus, puisque augmente dans tandis que diminue dans , donc un minimum local de est un minimum global. De plus, en stockant l'optimal pour chaque cellule dans le tableau DP et en se référant à sa valeur pour la cellule précédente, l'optimal pour chaque cellule peut être trouvé en temps constant, en l'améliorant dans le temps. Cependant, il existe une solution encore plus rapide qui implique une paramétrisation différente du problème :

Soit le nombre total d'étages tels que les œufs se cassent lorsqu'ils tombent du e étage (L'exemple ci-dessus équivaut à prendre ).

Soit le plancher minimum à partir duquel l'œuf doit être déposé pour être cassé.

Soit le nombre maximum de valeurs de qui sont distinguables à l'aide d' essais et d' œufs.

Alors pour tous .

Soit le sol à partir duquel le premier œuf est déposé dans la stratégie optimale.

Si le premier œuf s'est cassé, est de à et peut être distingué en utilisant au plus des essais et des œufs.

Si le premier œuf ne s'est pas cassé, est de à et distinguable à l'aide d' essais et d' œufs.

Par conséquent, .

Alors le problème est équivalent à trouver le minimum tel que .

Pour ce faire, nous pourrions calculer par ordre croissant , ce qui prendrait du temps.

Ainsi, si nous traitons séparément le cas de , l'algorithme prendrait du temps.

Mais la relation de récurrence peut en fait être résolue, donnant , qui peut être calculée en temps en utilisant l'identité pour tout .

Puisque pour tout , nous pouvons rechercher binairement sur trouver , ce qui donne un algorithme.

Multiplication en chaîne matricielle

La multiplication de chaînes matricielles est un exemple bien connu qui démontre l'utilité de la programmation dynamique. Par exemple, les applications d'ingénierie doivent souvent multiplier une chaîne de matrices. Il n'est pas surprenant de trouver des matrices de grandes dimensions, par exemple 100×100. Par conséquent, notre tâche est de multiplier les matrices . La multiplication matricielle n'est pas commutative, mais associative ; et nous ne pouvons multiplier que deux matrices à la fois. Ainsi, nous pouvons multiplier cette chaîne de matrices de différentes manières, par exemple :

((A 1 × A 2 ) × A 3 ) × ... A n
A 1 ×(((A 2 ×A 3 )× ... ) × A n )
(A 1 × A 2 ) × (A 3 × ... A n )

etc. Il existe de nombreuses façons de multiplier cette chaîne de matrices. Ils produiront tous le même résultat final, mais ils prendront plus ou moins de temps à calculer, en fonction des matrices particulières qui sont multipliées. Si la matrice A a des dimensions m×n et la matrice B a des dimensions n×q, alors la matrice C=A×B aura des dimensions m×q et nécessitera des multiplications scalaires m*n*q (en utilisant un algorithme de multiplication de matrice simpliste à des fins d'illustration).

Par exemple, multiplions les matrices A, B et C. Supposons que leurs dimensions soient respectivement m×n, n×p et p×s. La matrice A×B×C sera de taille m×s et peut être calculée de deux manières illustrées ci-dessous :

  1. Ax(B×C) Cet ordre de multiplication matricielle nécessitera des multiplications scalaires nps + mns.
  2. (A×B)×C Cet ordre de multiplication matricielle nécessitera des calculs scalaires mnp + mps.

Supposons que m = 10, n = 100, p = 10 et s = 1000. Ainsi, la première façon de multiplier la chaîne nécessitera 1 000 000 + 1 000 000 de calculs. La deuxième méthode ne nécessitera que 10 000 + 100 000 calculs. Évidemment, la deuxième façon est plus rapide, et nous devrions multiplier les matrices en utilisant cet arrangement de parenthèses.

Par conséquent, notre conclusion est que l'ordre des parenthèses est important et que notre tâche est de trouver l'ordre optimal des parenthèses.

À ce stade, nous avons plusieurs choix, dont l'un est de concevoir un algorithme de programmation dynamique qui divisera le problème en problèmes qui se chevauchent et calculera l'arrangement optimal des parenthèses. La solution de programmation dynamique est présentée ci-dessous.

Appelons m[i,j] le nombre minimum de multiplications scalaires nécessaires pour multiplier une chaîne de matrices de la matrice i à la matrice j (c'est-à-dire A i × .... × A j , c'est-à-dire i<=j). Nous divisons la chaîne au niveau d'une matrice k, telle que i <= k < j, et essayons de trouver quelle combinaison produit le minimum m[i,j].

La formule est :

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of k (m[i,k]+m[k+1,j] + ) 

k est compris entre i et j  − 1.

  • est la dimension ligne de la matrice i,
  • est la dimension de la colonne de la matrice k,
  • est la dimension de la colonne de la matrice j.

Cette formule peut être codée comme indiqué ci-dessous, où le paramètre d'entrée "chaîne" est la chaîne des matrices, c'est -à- dire :

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + 
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update
                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

Jusqu'à présent, nous avons calculé les valeurs de tous les m [ i , j ] possibles , le nombre minimum de calculs pour multiplier une chaîne de la matrice i à la matrice j , et nous avons enregistré le "point de partage" correspondant s [ i , j ] . Par exemple, si nous multiplions la chaîne A 1 ×A 2 ×A 3 ×A 4 , et qu'il s'avère que m [1, 3] = 100 et s [1, 3] = 2 , cela signifie que le placement optimal de la parenthèse pour les matrices 1 à 3 est et pour multiplier ces matrices, il faudra 100 calculs scalaires.

Cet algorithme produira des "tables" m [, ] et s [, ] qui auront des entrées pour toutes les valeurs possibles de i et j. La solution finale pour toute la chaîne est m[1, n], avec une division correspondante en s[1, n]. Démêler la solution sera récursif, en commençant par le haut et en continuant jusqu'à ce que nous atteignions le cas de base, c'est-à-dire la multiplication de matrices simples.

Par conséquent, l'étape suivante consiste à diviser réellement la chaîne, c'est-à-dire à placer la parenthèse là où elle appartient (de manière optimale). Pour cela, nous pourrions utiliser l'algorithme suivant :

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 
        print ")"

Bien sûr, cet algorithme n'est pas utile pour la multiplication réelle. Cet algorithme est juste un moyen convivial de voir à quoi ressemble le résultat.

Pour multiplier réellement les matrices en utilisant les divisions appropriées, nous avons besoin de l'algorithme suivant :

   function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         LeftSide = OptimalMatrixMultiplication(s, i, s[i, j])
         RightSide = OptimalMatrixMultiplication(s, s[i, j] + 1, j)
         return MatrixMultiply(LeftSide, RightSide) 
      else if i = j
         return Ai   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 
          print "error, incompatible dimensions."

Histoire

Le terme programmation dynamique a été utilisé à l'origine dans les années 1940 par Richard Bellman pour décrire le processus de résolution de problèmes où l'on doit trouver les meilleures décisions les unes après les autres. En 1953, il a affiné cela au sens moderne, se référant spécifiquement à l'imbrication de problèmes de décision plus petits dans des décisions plus larges, et le domaine a ensuite été reconnu par l' IEEE comme un sujet d' analyse et d' ingénierie des systèmes . La contribution de Bellman est rappelée sous le nom de l' équation de Bellman , un résultat central de la programmation dynamique qui reformule un problème d'optimisation sous forme récursive .

Bellman explique le raisonnement derrière le terme programmation dynamique dans son autobiographie, Eye of the Hurricane: An Autobiography :

J'ai passé le trimestre d'automne (de 1950) à RAND . Ma première tâche était de trouver un nom pour les processus de décision en plusieurs étapes. Une question intéressante est : « D'où vient le nom de programmation dynamique ? Les années 50 n'étaient pas de bonnes années pour la recherche mathématique. Nous avions un monsieur très intéressant à Washington nommé Wilson . Il était secrétaire à la Défense, et il avait en fait une peur et une haine pathologiques du mot « recherche ». Je n'utilise pas le terme à la légère ; Je l'utilise précisément. Son visage s'emplirait, il deviendrait rouge et il deviendrait violent si les gens utilisaient le terme de recherche en sa présence. Vous pouvez imaginer ce qu'il ressentait alors à propos du terme mathématique. La RAND Corporation était employée par l'Air Force, et l'Air Force avait essentiellement Wilson comme patron. Par conséquent, j'ai senti que je devais faire quelque chose pour protéger Wilson et l'Air Force du fait que je faisais vraiment des mathématiques au sein de la RAND Corporation. Quel titre, quel nom pourrais-je choisir ? En premier lieu, je m'intéressais à la planification, à la prise de décision, à la réflexion. Mais planification, n'est pas un bon mot pour diverses raisons. J'ai donc décidé d'utiliser le mot "programmation". Je voulais faire passer l'idée que c'était dynamique, c'était en plusieurs étapes, c'était variable dans le temps. J'ai pensé, faisons d'une pierre deux coups. Prenons un mot qui a un sens absolument précis, à savoir dynamique, au sens physique classique. Il a aussi une propriété très intéressante en tant qu'adjectif, c'est qu'il est impossible d'utiliser le mot dynamique dans un sens péjoratif. Essayez de penser à une combinaison qui lui donnera peut-être un sens péjoratif. C'est impossible. Ainsi, je pensais que la programmation dynamique était un bon nom. C'était une chose à laquelle même un membre du Congrès ne pouvait s'opposer. Je l'ai donc utilisé comme parapluie pour mes activités.

—  Richard Bellman, Eye of the Hurricane: An Autobiography (1984, page 159)

Le mot dynamique a été choisi par Bellman pour saisir l'aspect variable dans le temps des problèmes, et parce qu'il semblait impressionnant. Le mot programmation renvoyait à l'utilisation de la méthode pour trouver un programme optimal , au sens d'un calendrier militaire d'entraînement ou de logistique. Cet usage est le même que celui des expressions programmation linéaire et programmation mathématique , synonyme d' optimisation mathématique .

L'explication ci-dessus de l'origine du terme fait défaut. Comme Russell et Norvig l'ont écrit dans leur livre, se référant à l'histoire ci-dessus : « Cela ne peut pas être strictement vrai, car son premier article utilisant le terme (Bellman, 1952) est paru avant que Wilson ne devienne secrétaire à la Défense en 1953. » Aussi, il y a un commentaire dans un discours de Harold J. Kushner , où il se souvient de Bellman. Citant Kushner lorsqu'il parle de Bellman : "D'un autre côté, quand je lui ai posé la même question, il m'a répondu qu'il essayait de surpasser la programmation linéaire de Dantzig en ajoutant de la dynamique. Peut-être que les deux motivations étaient vraies."

Algorithmes utilisant la programmation dynamique

Voir également

Les références

Lectures complémentaires

Liens externes