dynamic-programming Tutoriel
Démarrer avec la programmation dynamique

Remarques

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 de diviser et conquérir, où le problème est partitionné en sous-problèmes disjoints, les sous-problèmes sont résolus de manière récursive et ensuite 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-problèmes. Dans ce contexte, un algorithme de division et de conquête fait plus de travail que nécessaire, résolvant de manière répétée les sous-problèmes communs. Un algorithme de programmation dynamique résout chaque sous-problème une seule fois, puis enregistre sa réponse dans un tableau, évitant ainsi de recalculer la réponse chaque fois qu’il résout chaque sous-problème.

Regardons 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 . La série est:

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

Nous pouvons remarquer que chaque nombre après les deux premiers est la somme des deux nombres précédents. Formulons maintenant une fonction F (n) qui nous renverra le nième nombre de Fibonacci, ce qui signifie

F(n) = nth Fibonacci Number

Jusqu'ici, nous avons su que,

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

Nous pouvons le 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 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) , ce qui appellera un peu plus. Représentons cela graphiquement:

Sur la photo, 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) , on peut sûrement dire que toutes les fonctions appelées par F(5) ont déjà été calculées. Cela veut dire que nous avons déjà calculé F(4) . Mais nous calculons encore F(4) comme l'indique l'enfant droit de F(6) . Avons-nous vraiment besoin de recalculer? Ce que nous pouvons faire, une fois que nous avons calculé la valeur de F(4) , nous allons le stocker dans un tableau nommé dp , et nous le réutiliserons si nécessaire. Nous allons initialiser notre tableau dp avec -1 (ou toute valeur qui ne viendra 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 effectué la même tâche qu'auparavant, mais avec une optimisation simple. Autrement dit, nous avons utilisé la technique de mémo . Au début, toutes les valeurs de dp array seront -1 . Lorsque F(4) est appelée, nous vérifions si elle est vide ou non. S'il stocke -1 , nous allons calculer sa valeur et la stocker dans dp [4] . S'il stocke autre chose que -1 , cela signifie que nous avons déjà calculé sa valeur. Nous allons donc simplement retourner la valeur.

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

Un problème peut être résolu en utilisant la programmation dynamique si elle présente certaines caractéristiques. Ceux-ci sont:

• Sous-problèmes:
  Un problème de 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 de 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 plus d'une fois. Par exemple: F(5) et F(6) ont en commun F(3) et F(4) . C'est la raison pour laquelle nous avons stocké les valeurs dans notre tableau.

• Structure optimale:
  Disons que l'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 on peut minimiser g(x) en minimisant à la fois g(y) et g(z) , alors seulement on peut dire que le problème a une sous-structure optimale. Si g(x) est minimisé en minimisant seulement g(y) et si minimiser ou maximiser g(z) n'a aucun effet sur g(x) , alors ce problème n'a pas de sous-structure optimale. En termes simples, si une 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.

Comprendre l'état dans la programmation dynamique

Discutons avec un exemple. À partir de n éléments, de combien de façons pouvez-vous choisir r objets? Vous savez qu'il est désigné par . Maintenant, pensez à un seul article.

• Si vous ne sélectionnez pas l’élément, vous devez ensuite récupérer les éléments de n-1 restants, qui sont donnés par .
• Si vous sélectionnez l'élément, vous devez ensuite prendre les éléments r-1 des n-1 éléments restants, qui sont donnés par .

La somme de ces deux valeurs nous donne le nombre total de façons. C'est:

Si on pense nCr(n,r) comme une fonction qui prend n et r comme paramètre et détermine , 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 ou les cas de base. Nous savons que, et . En utilisant ces deux cas de base, notre algorithme pour déterminer 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 la procédure graphiquement, nous pouvons voir que certaines récurrences sont appelées plus d'une fois. Par exemple: si on prend n = 8 et r = 5 , on obtient:

Nous pouvons éviter cet appel répété en utilisant un tableau, dp . Comme il y a 2 paramètres, nous avons besoin d'un tableau 2D. Nous initialisons 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]

Déterminer , 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 dimensions du tableau dp . La taille du tableau changera selon nos besoins. Nos algorithmes de programmation dynamique maintiendront le schéma 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

L' état déterminant est l'un des éléments les plus cruciaux de la programmation dynamique. Il comprend le nombre de paramètres qui définissent notre problème et optimise leur calcul, nous pouvons optimiser l'ensemble du problème.

Construire une solution DP

Peu importe le nombre de problèmes que vous résolvez en utilisant la programmation dynamique (DP), cela peut tout de même 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 pour les 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 rien.

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

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

Par exemple, un algorithme de calcul de la longueur de la sous- séquence commune la plus longue de deux chaînes s1 et s2 ressemblerait à ceci:

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]

C'est une solution itérative. Il y a quelques raisons pour lesquelles il est codé de cette manière:

• 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 mentionnées ci-dessus se traduisent en deux pseudo-codes différents. L'une utilise l'itération (Bottom-Up) et une autre utilise l'approche par récursion (Top-Down). Ce dernier est également connu sous le nom de technique de mémo. Cependant, les deux solutions sont plus ou moins équivalentes et l'une peut être facilement transformée en une autre. Pour cet exemple, nous allons montrer comment trouver une solution récursive à un problème.

Exemple problème:
Disons que vous avez N ( 1, 2, 3, ...., N ) vins placés côte à côte sur une étagère. Le prix du vin est i e p [i]. Le prix des vins augmente chaque année. Supposons que cette année est 1, l'année y le prix du i e 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 ne pouvez 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: disons que vous avez 4 vins dans le rayon et que leurs prix sont (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 donnerait un profit total de:

Approche gourmande:
Après un certain temps de brainstorming, vous pourriez trouver la solution pour vendre le vin le plus tard possible. Donc, 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 ce qu'il faut faire lorsque les deux vins coûtent le même prix, la stratégie se sent bien. 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:

Mais nous pouvons faire mieux si nous vendons les vins dans l'ordre 1 -> 5 -> 4 -> 2 -> 3 pour un bénéfice total de:

Cet exemple devrait vous convaincre que le problème n’est pas si simple qu’il se présente à première vue. Mais il peut être résolu en utilisant la programmation dynamique.

Backtracking:
Pour trouver la solution de mémo pour un problème, trouver une solution de backtrack est pratique. La solution Backtrack évalue toutes les réponses valides au 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 retourner la réponse avec une déclaration de retour .
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 de manière récursive la réponse et renvoyer la meilleure. La solution de backtrack ressemblerait à ceci:

// 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, la réponse sera renvoyée.

Cette solution tente simplement toutes les combinaisons possibles de vente des vins. S'il y a n vins au début, il vérifiera 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 arrière correctement écrite devrait toujours représenter une réponse à une question bien définie. Dans notre exemple, la procédure profitDetermination représente une réponse à la question: quel est le meilleur bénéfice que nous pouvons tirer de la vente des vins dont les prix sont stockés dans le tableau p, lorsque l’année en cours , fin], inclusif? Vous devriez toujours essayer de créer une telle question pour votre fonction de backtrack pour voir si vous l'avez bien comprise et comprendre exactement ce qu'elle fait.

Etat déterminant:
Etat est le nombre de paramètres utilisés dans la solution DP. Dans cette étape, nous devons réfléchir aux arguments que vous transmettez à la fonction, c’est-à-dire que nous pouvons les construire à partir des autres arguments ou que nous n’en avons pas besoin du tout. S'il existe de tels arguments, nous n'avons pas besoin de les transmettre à la fonction, nous les calculerons dans la fonction.

Dans l'exemple de fonction profitDetermination illustré ci-dessus, l' year argument est redondante. Cela équivaut au nombre de vins que nous avons déjà vendus plus un. Il peut être déterminé en utilisant le nombre total de vins du début moins le nombre de vins que nous n'avons pas vendus plus un. Si nous stockons le nombre total de vins n en tant que variable globale, nous pouvons réécrire la fonction en:

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 gamme 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 allant de 0 à n-1 . Dans une entrée valide, nous nous attendons également à begin <= end + 1 . Il peut y avoir O(n²) arguments différents avec lesquels notre fonction peut être appelée.

Mémo:
Nous sommes maintenant presque finis. Transformer la solution backtrack avec la complexité du temps dans la solution de mémo avec la complexité du temps , nous allons utiliser un petit truc qui ne nécessite pas beaucoup d'effort.

Comme indiqué ci-dessus, il n'y a que paramètres différents notre fonction peut être appelée avec. En d'autres termes, il n'y a que différentes choses que nous pouvons réellement calculer. Alors, où est-ce que la complexité du temps vient et que calcule-t-il!

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 les mêmes valeurs encore et encore. Si vous exécutez le code mentionné ci-dessus pour un tableau arbitraire de n = 20 vins et que vous calculez combien de fois la fonction appelée pour les arguments begin = 10 et end = 10 , vous obtiendrez un nombre 92378 . C'est une énorme perte de temps pour calculer la même réponse à plusieurs reprises. Ce que nous pourrions faire pour améliorer ceci 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 plus besoin d’exécuter toute la récursivité. Nous aurons un tableau dp [N] [N] , initialisons-le avec -1 (ou toute valeur qui ne viendra pas dans notre calcul), où -1 indique que la valeur n'a pas encore été calculée. La taille du tableau est déterminée par la valeur maximale possible de début et de fin, car nous stockons les valeurs correspondantes de certaines valeurs de début et de fin dans notre tableau. Notre procédure ressemblerait à ceci:

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]

C'est notre solution de DP requise. Avec notre truc très simple, la solution fonctionne temps, car il y a paramètres différents notre fonction peut être appelée avec et pour chacun d'eux, la fonction s'exécute une seule fois avec complexité.

Estival:
Si vous pouvez identifier un problème pouvant être résolu à l'aide de DP, procédez comme suit pour créer une solution DP:

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

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