Débuter avec la programmation dynamique

Introduction à la programmation dynamique

La programmation dynamique résout les problèmes en combinant les solutions aux sous-problèmes. Cela peut être analogue à la méthode diviser pour mieux régner, où le problème est divisé en sous-problèmes disjoints, les sous-problèmes sont résolus de manière récursive puis combinés pour trouver la solution du problème d’origine. En revanche, la programmation dynamique s’applique lorsque les sous-problèmes se chevauchent, c’est-à-dire lorsque les sous-problèmes partagent des sous-sous-problèmes. Dans ce contexte, un algorithme diviser pour régner fait plus de travail que nécessaire, résolvant à plusieurs reprises les sous-sous-problèmes courants. Un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois, puis enregistre sa réponse dans un tableau, évitant ainsi le travail de recalcul de la réponse à chaque fois qu’il résout chaque sous-sous-problème.

Prenons un exemple. Le mathématicien italien Leonardo Pisano Bigollo, que nous appelons communément Fibonacci, a découvert une série de nombres en considérant la [croissance idéalisée de la population de lapins](https://en .wikipedia.org/wiki/Fibonacci_number#Origins). La série est :

1, 1, 2, 3, 5, 8, 13, 21, ......

On peut remarquer que chaque nombre après les deux premiers est la somme des deux nombres précédents. Maintenant, formulons une fonction F(n) qui nous renverra le nième nombre de Fibonacci, c’est-à-dire,

F(n) = nth Fibonacci Number

Jusqu’à présent, nous le savions,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

On peut généraliser par :

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Maintenant, si nous voulons l’écrire comme une fonction récursive, nous avons F(1) et F(2) comme cas de base. Donc, notre fonction de Fibonacci serait :

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Maintenant, si nous appelons F(6), il appellera F(5) et F(4), qui en appelleront d’autres. Représentons cela graphiquement :

[![Arbre de récursivité pour F(6)][1]][1]

Sur l’image, nous pouvons voir que F(6) appellera F(5) et F(4). Maintenant F(5) appellera F(4) et F(3). Après avoir calculé F(5), nous pouvons sûrement dire que toutes les fonctions qui ont été appelées par F(5) ont déjà été calculées. Cela signifie que nous avons déjà calculé F(4). Mais nous calculons à nouveau F(4) comme l’indique l’enfant droit de F(6). A-t-on vraiment besoin de recalculer ? Ce que nous pouvons faire, c’est qu’une fois que nous avons calculé la valeur de F(4), nous la stockons dans un tableau nommé dp et la réutilisons en cas de besoin. Nous allons initialiser notre tableau dp avec -1 (ou toute valeur qui n’entrera pas dans notre calcul). Ensuite, nous appellerons F(6) où notre F(n) modifié ressemblera à :

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Nous avons fait la même tâche qu’avant, mais avec une simple optimisation. Autrement dit, nous avons utilisé la technique memoization. Au début, toutes les valeurs du tableau dp seront -1. Lorsque F(4) est appelé, nous vérifions s’il est vide ou non. S’il stocke -1, nous calculerons sa valeur et la stockerons dans dp[4]. S’il stocke autre chose que -1, cela signifie que nous avons déjà calculé sa valeur. Nous renverrons donc simplement la valeur.

Cette optimisation simple utilisant la mémorisation s’appelle la programmation dynamique.

Un problème peut être résolu à l’aide de la programmation dynamique s’il présente certaines caractéristiques. Ceux-ci sont:

  • Sous-problèmes :
    Un problème DP peut être divisé en un ou plusieurs sous-problèmes. Par exemple : F(4) peut être divisé en sous-problèmes plus petits F(3) et F(2). Comme les sous-problèmes sont similaires à notre problème principal, ceux-ci peuvent être résolus en utilisant la même technique. - Sous-problèmes qui se chevauchent :
    Un problème DP doit avoir des sous-problèmes qui se chevauchent. Cela signifie qu’il doit y avoir une partie commune pour laquelle la même fonction est appelée plusieurs fois. Par exemple : F(5) et F(6) ont F(3) et F(4) en commun. C’est la raison pour laquelle nous avons stocké les valeurs dans notre tableau.

[![Graphique de sous-problèmes superposés][2]][2]

  • Sous-structure optimale :
    Supposons qu’on vous demande de minimiser la fonction g(x). Vous savez que la valeur de g(x) dépend de g(y) et g(z). Maintenant, si nous pouvons minimiser g(x) en minimisant à la fois g(y) et g(z), alors seulement nous pouvons dire que le problème a une sous-structure optimale. Si g(x) est minimisé en minimisant uniquement g(y) et si minimiser ou maximiser g(z) n’a aucun effet sur g(x), alors ce problème n’a pas sous-structure optimale. En termes simples, si la solution optimale d’un problème peut être trouvée à partir de la solution optimale de son sous-problème, alors nous pouvons dire que le problème a une propriété de sous-structure optimale.

[1] : https://i.stack.imgur.com/ngSbS.jpg [2] : https://i.stack.imgur.com/7OVJm.jpg

Comprendre l’état dans la programmation dynamique

Discutons avec un exemple. Parmi n articles, de combien de façons pouvez-vous choisir r articles ? Vous savez qu’il est noté [![nCr][1]][1]. Pensez maintenant à un seul élément.

  • Si vous ne sélectionnez pas l’élément, vous devez ensuite prendre r éléments parmi les n-1 éléments restants, ce qui est donné par [![(n-1)Cr][2] ][2].
  • Si vous sélectionnez l’élément, après cela, vous devez prendre r-1 éléments parmi les n-1 éléments restants, ce qui est donné par [![(n-1)C(r-1) ][3]][3].

La somme de ces deux nous donne le nombre total de voies. C’est-à-dire :
[![nCr = (n-1)Cr + (n-1)C(r-1)][4]][4]

Si nous pensons nCr(n,r) comme une fonction qui prend n et r comme paramètre et détermine [![nCr][1]][1], nous pouvons écrire la relation mentionnée ci-dessus comme :

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

C’est une relation récursive. Pour y mettre fin, nous devons déterminer le(s) cas de base. Nous savons que [![nC1 = n][5]][5] et [![nCn = 1][6]][6]. En utilisant ces deux cas de base, notre algorithme pour déterminer [![nCr][1]][1] sera :

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Si nous regardons graphiquement la procédure, nous pouvons voir que certaines récursions sont appelées plus d’une fois. Par exemple : si on prend n = 8 et r = 5, on obtient :

[![Arbre de récursivité montrant les sous-problèmes qui se chevauchent][7]][7]

Nous pouvons éviter cet appel répété en utilisant un tableau, dp. Puisqu’il y a 2 paramètres, nous aurons besoin d’un tableau 2D. Nous allons initialiser le tableau dp avec -1, où -1 indique que la valeur n’a pas encore été calculée. Notre procédure sera :

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Pour déterminer [![nCr][1]][1], nous avions besoin de deux paramètres n et r. Ces paramètres sont appelés état. On peut simplement en déduire que le nombre d’états détermine le nombre de dimension du tableau dp. La taille du tableau changera en fonction de nos besoins. Nos algorithmes de programmation dynamique maintiendront le modèle général suivant :

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

La détermination de l’état est l’une des parties les plus cruciales de la programmation dynamique. Il se compose du nombre de paramètres qui définissent notre problème et en optimisant leur calcul, nous pouvons optimiser l’ensemble du problème.

[1] : https://i.stack.imgur.com/WDYXl.png [2] : https://i.stack.imgur.com/UnhcW.png [3] : https://i.stack.imgur.com/TfAm6.png [4] : https://i.stack.imgur.com/2ayHg.png [5] : https://i.stack.imgur.com/r1oSW.png [6] : https://i.stack.imgur.com/af8ba.png [7] : https://i.stack.imgur.com/DQatV.jpg

Construire une solution DP

Peu importe le nombre de problèmes que vous résolvez à l’aide de la programmation dynamique (DP), cela peut toujours vous surprendre. Mais comme tout le reste dans la vie, la pratique vous rend meilleur. En gardant cela à l’esprit, nous examinerons le processus de construction d’une solution aux problèmes de DP. D’autres exemples sur ce sujet vous aideront à comprendre ce qu’est DP et comment cela fonctionne. Dans cet exemple, nous allons essayer de comprendre comment créer une solution DP à partir de zéro.

Itératif VS Récursif :
Il existe deux techniques de construction de solution DP. Elles sont:

  • Itératif (utilisant des cycles for)
  • Récursif (en utilisant la récursivité)

Par exemple, l’algorithme de calcul de la longueur de la [Longest Common Subsequence](https://www.wikiod.com/fr/dynamic-programming/algorithmes-lies-aux-sous-sequences#Sous-séquence commune la plus longue t=201611230422107601679) de deux chaînes s1 et s2 ressemblerait à :

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Il s’agit d’une solution itérative. Il y a plusieurs raisons pour lesquelles il est codé de cette façon :

  • L’itération est plus rapide que la récursivité.
  • La détermination de la complexité temporelle et spatiale est plus facile.
  • Le code source est court et propre

En regardant le code source, vous pouvez facilement comprendre comment et pourquoi cela fonctionne, mais il est difficile de comprendre comment trouver cette solution. Cependant les deux approches évoquées ci-dessus se traduisent par deux pseudo-codes différents. L’un utilise l’itération (Bottom-Up) et l’autre utilise l’approche de récursivité (Top-Down). Cette dernière est également connue sous le nom de technique de mémorisation. Cependant, les deux solutions sont plus ou moins équivalentes et l’une peut facilement se transformer en une autre. Pour cet exemple, nous allons montrer comment trouver une solution récursive à un problème.

Exemple de problème :
Disons que vous avez N (1, 2, 3, …., N) vins placés les uns à côté des autres sur une étagère. Le prix du ie vin est de p[i]. Le prix des vins augmente chaque année. Supposons que nous soyons en l’année 1, l’année y le prix du ième vin sera : année * prix du vin = y*p[i ]. Vous voulez vendre les vins que vous avez, mais vous devez vendre exactement un vin par an, à partir de cette année. Encore une fois, chaque année, vous n’êtes autorisé à vendre que le vin le plus à gauche ou le plus à droite et vous ne pouvez pas réorganiser les vins, cela signifie qu’ils doivent rester dans le même ordre qu’au début.

Par exemple : supposons que vous ayez 4 vins dans l’étagère, et que leurs prix soient (de gauche à droite) :

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

La solution optimale serait de vendre les vins dans l’ordre 1 -> 4 -> 3 -> 2, ce qui nous rapportera un gain total de : [! [11+32+23+44=29][1]][1]

Approche gourmande :
Après un moment de remue-méninges, vous pourriez trouver la solution pour vendre le vin cher le plus tard possible. Ainsi, votre stratégie gourmande sera :

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Bien que la stratégie ne mentionne pas quoi faire lorsque les deux vins coûtent le même prix, la stratégie semble plutôt juste. Mais malheureusement, ce n’est pas le cas. Si les prix des vins sont :

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

La stratégie gourmande les vendrait dans l’ordre 1 -> 2 -> 5 -> 4 -> 3 pour un profit total de : [ ! [21+32+43+14+5*5=49][2]][2]

Mais on peut faire mieux si on vend les vins dans l’ordre 1 -> 5 -> 4 -> 2 -> 3 pour un bénéfice total de : [![21+42+13+34+5*5=50][3]][3]

Cet exemple devrait vous convaincre que le problème n’est pas aussi simple qu’il y paraît à première vue. Mais il peut être résolu en utilisant la programmation dynamique.

Retour en arrière :
Pour trouver la solution de mémorisation d’un problème, trouver une solution de retour en arrière est pratique. La solution Backtrack évalue toutes les réponses valides pour le problème et choisit la meilleure. Pour la plupart des problèmes, il est plus facile de trouver une telle solution. Il peut y avoir trois stratégies à suivre pour aborder une solution de retour en arrière :

  1. ce devrait être une fonction qui calcule la réponse en utilisant la récursivité.
  2. il doit renvoyer la réponse avec l’instruction return.
  3. toutes les variables non locales doivent être utilisées en lecture seule, c’est-à-dire que la fonction ne peut modifier que les variables locales et ses arguments.

Pour notre exemple de problème, nous allons essayer de vendre le vin le plus à gauche ou le plus à droite et calculer récursivement la réponse et renvoyer la meilleure. La solution de retour en arrière ressemblerait à :

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Si nous appelons la procédure en utilisant profitDetermination(1, 0, n-1), où n est le nombre total de vins, elle renverra la réponse.

Cette solution essaie simplement toutes les combinaisons valables possibles de vente des vins. S’il y a n vins au début, il vérifiera [![2^n][4]][4] possibilités. Même si nous obtenons la bonne réponse maintenant, la complexité temporelle de l’algorithme augmente de façon exponentielle.

La fonction de retour en arrière correctement écrite doit toujours représenter une réponse à une question bien formulée. Dans notre exemple, la procédure profitDetermination représente une réponse à la question : Quel est le meilleur profit que nous pouvons tirer de la vente des vins avec des prix stockés dans le tableau p, lorsque l’année en cours est l’année et que l’intervalle des vins invendus s’étend through [begin, end], inclusivement ? Vous devriez toujours essayer de créer une telle question pour votre fonction backtrack pour voir si vous avez bien compris et comprendre exactement ce qu’elle fait.

État déterminant :
State est le nombre de paramètres utilisés dans la solution DP. Dans cette étape, nous devons réfléchir aux arguments que vous passez à la fonction qui sont redondants, c’est-à-dire que nous pouvons les construire à partir des autres arguments ou nous n’en avons pas du tout besoin. S’il y a de tels arguments, nous n’avons pas besoin de les passer à la fonction, nous les calculerons à l’intérieur de la fonction.

Dans l’exemple de fonction “profitDetermination” présenté ci-dessus, l’argument “année” est redondant. C’est l’équivalent du nombre de vins que nous avons déjà vendus plus un. Il peut être déterminé en utilisant le nombre total de vins depuis le début moins le nombre de vins que nous n’avons pas vendus plus un. Si nous stockons le nombre total de vins n comme variable globale, nous pouvons réécrire la fonction comme suit :

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Nous devons également réfléchir à la plage de valeurs possibles des paramètres pouvant être obtenues à partir d’une entrée valide. Dans notre exemple, chacun des paramètres begin et end peut contenir des valeurs comprises entre 0 et n-1. Dans une entrée valide, nous attendrons également begin <= end + 1. Il peut y avoir O(n²) différents arguments avec lesquels notre fonction peut être appelée.

Mémoisation :
Nous avons maintenant presque terminé. Pour transformer la solution de backtrack de complexité temporelle [![O(2^n)][5]][5] en solution de mémorisation de complexité temporelle [![O(n^2)][6]][6], nous utilisera une petite astuce qui ne demande pas beaucoup d’effort.

Comme indiqué ci-dessus, il n’y a que [![O(n^2)][6]][6] paramètres différents avec lesquels notre fonction peut être appelée. En d’autres termes, il n’y a que [![O(n^2)][6]][6] différentes choses que nous pouvons réellement calculer. Alors d’où vient la complexité temporelle [![O(2^n)][5]][5] et que calcule-t-elle !!

La réponse est la suivante : la complexité temporelle exponentielle provient de la récursivité répétée et, à cause de cela, elle calcule encore et encore les mêmes valeurs. Si vous exécutez le code mentionné ci-dessus pour un tableau arbitraire de n = 20 vins et calculez combien de fois la fonction a été appelée pour les arguments begin = 10 et **end ** = 10, vous obtiendrez un numéro 92378. C’est une énorme perte de temps de calculer la même réponse autant de fois. Ce que nous pourrions faire pour améliorer cela, c’est de stocker les valeurs une fois que nous les avons calculées et chaque fois que la fonction demande une valeur déjà calculée, nous n’avons pas besoin de réexécuter toute la récursivité. Nous aurons un tableau dp[N][N], initialisez-le avec -1 (ou toute valeur qui n’entrera pas dans notre calcul), où -1 indique la valeur n’a pas encore été calculé. La taille du tableau est déterminée par la valeur maximale possible de begin et end car nous stockerons les valeurs correspondantes de certaines valeurs begin et end dans notre tableau. Notre procédure ressemblerait à :

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Ceci est notre solution DP requise. Avec notre astuce très simple, la solution tourne [![O(n^2)][6]][6] fois, car il y a [![O(n^2)][6]][6] paramètres différents notre fonction peut être appelée avec et pour chacun d’eux, la fonction ne s’exécute qu’une seule fois avec une complexité de [![O(1)][7]][7].

Résumé :
Si vous pouvez identifier un problème qui peut être résolu à l’aide de DP, utilisez les étapes suivantes pour construire une solution DP :

  • Créez une fonction de retour en arrière pour fournir la bonne réponse.
  • Supprimer les arguments redondants.
  • Estimer et minimiser la plage maximale des valeurs possibles des paramètres de la fonction.
  • Essayez d’optimiser la complexité temporelle d’un appel de fonction.
  • Enregistrez les valeurs afin de ne pas avoir à les calculer deux fois.

La complexité d’une solution DP est : plage de valeurs possibles avec lesquelles la fonction peut être appelée * complexité temporelle de chaque appel.

[1] : https://i.stack.imgur.com/4QXSS.png [2] : https://i.stack.imgur.com/VSftx.png [3] : https://i.stack.imgur.com/BAecO.png [4] : https://i.stack.imgur.com/R8ime.png [5] : https://i.stack.imgur.com/sbk1b.png [6] : https://i.stack.imgur.com/GpKoh.png [7] : https://i.stack.imgur.com/ZiTVI.png