Comprendre la programmation dynamique pour pouvoir l'utiliser efficacement

Cet article n'est pas lié au développement de la production, mais concerne la programmation. Je discuterai de la programmation dynamique (DP) et de la manière d'utiliser efficacement l'expérience de calcul précédente. J'espère que tu vas trouver ça intéressant.

Introduction à la programmation dynamique

Le terme programmation dynamique a été utilisé pour la première fois dans les années 1950 par le célèbre mathématicien américain, l'un des principaux spécialistes de l'informatique, Richard Bellman. La programmation dynamique (DP) est une méthode permettant de résoudre des tâches complexes en les décomposant en sous-problèmes plus petits.

Le type de problèmes que DP peut résoudre doit répondre à deux critères :

1. Sous-structure optimale . La programmation dynamique signifie que la solution de sous-problèmes plus petits peut être utilisée pour résoudre le problème initial. La sous-structure optimale est la principale caractéristique du paradigme « Diviser pour régner ».

Un exemple classique de mise en œuvre est l'algorithme de tri par fusion, dans lequel nous décomposons de manière récursive le problème en sous-problèmes les plus simples (tableaux de taille 1), après quoi nous effectuons des calculs basés sur chacun d'entre eux. Les résultats sont utilisés pour résoudre la couche suivante (sous-problèmes plus importants) jusqu'à ce que la couche initiale soit atteinte.

2. Sous-problèmes qui se chevauchent . En informatique, on dit qu'un problème comporte des sous-problèmes qui se chevauchent si le problème peut être décomposé en sous-problèmes réutilisés plusieurs fois. En d’autres termes, exécuter le même code avec les mêmes données d’entrée et les mêmes résultats. Un exemple classique de ce problème est le calcul d’un N-ième élément dans une séquence de Fibonacci, que nous examinerons ci-dessous.

On pourrait dire que DP est un cas particulier d’utilisation du paradigme Divide and Conquer, ou une version plus complexe de celui-ci. Le modèle est bien adapté à la résolution de tâches impliquant la combinatoire, dans lesquelles un grand nombre de combinaisons différentes sont calculées, mais la quantité N d'éléments est souvent monotone et identique.

Dans les problèmes de sous-structure optimale et de sous-problèmes qui se chevauchent, nous avons de nombreux calculs et opérations répétés, si nous appliquons une approche par force brute. DP nous aide à optimiser la solution, et à éviter le doublement des calculs en utilisant deux approches principales : la mémorisation et la tabulation :

1. La mémorisation (approche descendante) est mise en œuvre par récursivité. Une tâche est décomposée en sous-problèmes plus petits, leurs résultats sont stockés dans une mémoire et combinés pour résoudre le problème initial grâce à une utilisation répétée.

• Inconvénients : cette approche utilise la mémoire de la pile via des appels de méthode récursifs
• Avantages : Flexibilité envers les tâches DP.

2. La tabulation (approche ascendante) est mise en œuvre à l'aide d'une méthode itérative. Les sous-problèmes du plus petit au premier sont calculés successivement, de manière itérative.

• Inconvénients : champ d'application limité. Cette approche nécessite une compréhension initiale de l’ensemble de la séquence des sous-problèmes. Mais dans certains cas, cela n’est pas réalisable.
• Avantages : utilisation efficace de la mémoire, car tout est exécuté dans une seule fonction.

La théorie peut paraître fastidieuse et incompréhensible – examinons quelques exemples.

Problème : séquence de Fibonacci

Un exemple classique de DP consiste à calculer un N-ième élément dans une séquence de Fibonacci, où chaque élément est la somme des deux précédents, et les premier et deuxième éléments sont égaux à 0 et 1.

Par hypothèse, nous nous concentrons dans un premier temps sur la nature de la sous-structure optimale, car pour calculer une valeur, il faut trouver la précédente. Pour calculer la valeur précédente, nous devons retrouver celle qui l’a précédée, et ainsi de suite. La nature des sous-tâches qui se chevauchent est illustrée dans le diagramme ci-dessous.

Pour cette tâche, nous examinerons trois cas :

1. Approche simple : quels sont les inconvénients ?
2. Une solution optimisée utilisant la mémorisation
3. Une solution optimisée utilisant la tabulation

Approche simple/force brute

La première chose à laquelle vous pourriez penser est d'entrer dans la récursion, de résumer les deux éléments précédents et de donner leur résultat.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

Sur l'écran ci-dessous, vous pouvez voir une pile d'appels de fonctions, pour calculer le cinquième élément de la séquence.

Notez que la fonction fib(1) est appelée cinq fois et fib(2) trois fois. Les fonctions avec une seule signature, avec les mêmes paramètres, sont lancées à plusieurs reprises et font la même chose. Lorsque le nombre N augmente, l’arbre augmente, non pas de manière linéaire, mais de manière exponentielle, ce qui entraîne une duplication colossale des calculs.

Analyse mathématique :

Complexité temporelle : O(2n),

Complexité spatiale : O(n) -> proportionné à la profondeur maximale de l'arbre récursif, car il s'agit du nombre maximum d'éléments pouvant être présents dans la pile d'appels de fonction implicites.

Résultat : Cette approche est extrêmement inefficace. Par exemple, 1 073 741 824 opérations sont nécessaires pour calculer le 30ème élément.

Mémorisation (approche descendante)

Dans cette approche, la mise en œuvre n'est pas si différente de la solution « force brute » précédente, à l'exception de l'allocation de mémoire. Soit le mémo de variable, dans lequel nous collectons les résultats des calculs de toute fonction fib() terminée dans notre pile.

Il convient de noter qu'il aurait suffi d'avoir un tableau d'entiers et de s'y référer par index, mais, par souci de clarté conceptuelle, une carte de hachage a été créée.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Concentrons-nous à nouveau sur la pile d'appels de fonctions :

• La première fonction terminée qui écrit le résultat dans le mémo est la fib(2) en surbrillance. Il rend le contrôle au fib(3) en surbrillance.
• Le fib(3) en surbrillance trouve sa valeur après avoir résumé les résultats des appels fib(2) et fib(1) , entre sa solution dans le mémo et rend le contrôle à fib(4) .
• Nous avons atteint le stade de la réutilisation d'expériences antérieures : lorsque le contrôle est rendu à fib(4) , l'appel fib(2) y attend son tour. fib(2) à son tour, au lieu d'appeler ( fib(1) + fib(0) ), utilise l'intégralité de la solution terminée du mémo et la renvoie immédiatement.
• fib(4) est calculé et rend le contrôle à fib(5) , qui n'a plus qu'à lancer fib(3) . Dans la dernière analogie, fib(3) renvoie immédiatement une valeur du mémo sans calculs.

On peut observer une réduction du nombre d’appels de fonctions et de calculs. De plus, lorsque N augmente, il y aura de façon exponentielle moins de réductions.

Analyse mathématique :

Complexité temporelle : O(n)

Complexité spatiale : O(n)

Résultat : Il existe une nette différence de complexité asymptotique. Cette approche l'a réduit à être linéaire dans le temps, par rapport à la solution primitive, et ne l'a pas augmenté en mémoire.

Tabulation (approche ascendante)

Comme mentionné ci-dessus, cette approche implique un calcul itératif d'un sous-problème plus petit à un sous-problème plus grand. Dans le cas de Fibonacci, les plus petits « sous-problèmes » sont les premier et deuxième éléments de la séquence, respectivement 0 et 1.

Nous connaissons bien la façon dont les éléments sont liés les uns aux autres, ce qui s'exprime dans la formule : fib(n) = fib(n-1) + fib(n-2) . Parce que nous connaissons les éléments précédents, nous pouvons facilement déterminer le suivant, celui d’après, et ainsi de suite.

En résumant les valeurs dont nous sommes conscients, nous pouvons trouver l’élément suivant. Nous implémentons cette opération de manière cyclique jusqu'à ce que nous trouvions la valeur souhaitée.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Analyse mathématique :

Complexité temporelle : O(n)

Complexité spatiale : O(1)

Résultat : Cette approche est tout aussi efficace que la mémorisation en terme de rapidité, mais elle consomme une quantité de mémoire constante.

Problème : arbres binaires uniques

Regardons un problème plus complexe : nous devons trouver le nombre de tous les arbres binaires structurellement uniques qui peuvent être créés à partir de N nœuds.

Un arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud n'a pas plus de deux descendants. En règle générale, le premier est appelé nœud parent et a deux enfants : l’enfant de gauche et l’enfant de droite.

Supposons que nous devions trouver une solution pour N = 3. Il existe 5 arbres structurellement uniques pour les trois nœuds. Nous pouvons les compter dans notre tête, mais si le N augmente, les variations augmenteraient énormément et il serait impossible de les visualiser dans notre tête.

Cette tâche pourrait être attribuée à la combinatoire. Voyons quelles combinaisons peuvent être formées et comment trouver un modèle pour leur formation.

1. Chaque arbre part du nœud supérieur (sommet de l'arbre). L’arbre s’étend alors en profondeur.
2. Chaque nœud est le début d'un nouvel arbre enfant (sous-arbre), comme indiqué à l'écran. Le sous-arbre de gauche est de couleur verte et celui de droite en rouge. Chacun a son propre sommet.

Regardons un exemple de tâche, où N = 6 au niveau conceptuel. Nous appellerons notre fonction de calcul numOfUniqueTrees(n: Int) .

Dans notre exemple, 6 nœuds sont donnés, dont l'un, selon le principe évoqué précédemment, forme le sommet de l'arbre, et les 5 autres — le reste.

A partir de maintenant, nous interagissons avec les nœuds restants. Cela peut être fait de différentes façons. Par exemple, en utilisant les cinq nœuds pour former le sous-arbre de gauche ou en envoyant les cinq au sous-arbre de droite. Ou en divisant les nœuds en deux – 2 à gauche et 3 à droite (voir écran ci-dessous), nous avons un nombre limité de telles variantes.

Pour obtenir le résultat numOfUniqueTrees(6) , nous devons considérer toutes les variantes de distribution de nos nœuds. Ils sont présentés dans le tableau :

Le tableau montre 6 distributions différentes des nœuds. Si nous trouvons combien d’arbres uniques peuvent être générés pour chaque distribution et les résumons, nous obtiendrons notre résultat final.

Comment trouver le nombre d’arbres uniques à distribuer ?

Nous avons deux paramètres : les nœuds gauches et les nœuds droits (colonnes gauche et droite du tableau).

Le résultat sera égal à : numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Pourquoi? A gauche, nous aurons X arbres uniques, et pour chacun, nous pourrons mettre Y variations uniques d'arbres à droite. Nous les multiplions pour obtenir le résultat.

Découvrons donc les variations pour la première distribution (5 à gauche, 0 à droite)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , car nous n'avons aucun nœud à droite. Le résultat est numOfUniqueTrees(5) — le nombre de sous-arbres uniques à gauche avec une droite constante.

Calcul de numOfUniqueTrees(5) .

Nous avons maintenant le plus petit sous-problème. Nous fonctionnerons avec lui comme nous l'avons fait avec le plus grand. À ce stade, les caractéristiques des tâches DP sont claires : sous-structure optimale, comportement récursif.

Un nœud (le nœud vert) est envoyé au sommet. Nous distribuons les (quatre) nœuds restants d'une manière analogue à l'expérience précédente (4:0), (3:1), (2:2), (1:3), (0:4).

Nous calculons la première distribution (4:0). Il est égal à numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) par analogie antérieure.

Calcul de numOfUniqueTrees(4) . Si nous allouons un nœud au sommet, il nous en reste 3.

Distributions (3:0), (2:1), (1:2), (0:3).

Pour 2 nœuds, il n'y a que deux arbres binaires uniques, pour 1 — un. Nous avons déjà mentionné qu'il existe 5 variantes d'arbres binaires uniques pour trois nœuds.

En conséquence — les distributions(3:0), (0:3) sont égales à 5, (2:1), (1:2) — 2. Si on additionne 5 + 2 + 2 + 5, on obtient 14 numOfUniqueTrees(4) = 14.

Entrons le résultat du calcul dans la variable memo en fonction de l'expérience de mémorisation. Chaque fois que nous avons besoin de trouver des variations pour quatre nœuds, nous ne les calculerons pas à nouveau, mais réutiliserons l'expérience antérieure.

Revenons au calcul (5:0), qui est égal à la somme des distributions (4:0), (3:1), (2:2), (1:3), (0:4). Nous savons que (4:0) = 14. Passons au mémo, (3:1) = 5, (2:2) = 4 (2 variations à gauche * 2 à droite), (1:3) = 5, (0:4) = 14. Si nous les résumons, nous obtenons 42, numOfUniqueTrees(5) = 42.

Revenons au calcul de numOfUniqueTrees(6) , qui est égal à la somme des distributions.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 à gauche * 2 à droite), (2:3) = 10, (1:4) = 14, (0 : 5) = 42. Si nous les résumons, nous obtenons 132, numOfUniqueTrees(5) = 132 .

Tâche résolue !

Résultat : Notons les sous-problèmes qui se chevauchent dans la solution où N = 6. Dans la solution simple, numOfUniqueTrees(3) serait appelé 18 fois (écran ci-dessous). Avec l'augmentation de N, les répétitions du même calcul seraient bien plus nombreuses.

Je souligne que le nombre d'arbres uniques pour (5 à gauche, 0 à droite) et (0 à gauche, 5 à droite) sera le même. Seulement dans un cas, ils seront à gauche et dans l'autre à droite. Cela fonctionne également pour (4 à gauche, 1 à droite) et (1 à gauche, 4 à droite).

La mémorisation, en tant qu'approche de programmation dynamique, nous a permis d'optimiser la solution pour une tâche aussi complexe.

Mise en œuvre

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Conclusion

Dans certains cas, la résolution de tâches au moyen de la programmation dynamique peut permettre de gagner beaucoup de temps et de faire fonctionner l'algorithme avec une efficacité maximale.

Merci d'avoir lu cet article jusqu'au bout. Je serai heureux de répondre à vos questions.