algorithm
Applications de programmation dynamique
Recherche…
Introduction
L'idée de base de la programmation dynamique consiste à casser un problème complexe en plusieurs petits problèmes simples qui se répètent. Si vous pouvez identifier un sous-problème simple, calculé de manière répétée, il existe une approche dynamique du problème.
Ce sujet étant intitulé Applications de programmation dynamique , il se concentrera davantage sur les applications que sur le processus de création d’algorithmes de programmation dynamiques.
Remarques
Définitions
Mémo - technique d'optimisation utilisée principalement pour accélérer les programmes informatiques en stockant les résultats d'appels de fonctions coûteux et en renvoyant le résultat en cache lorsque les mêmes entrées se reproduisent.
Programmation dynamique - une méthode pour résoudre un problème complexe en la décomposant en un ensemble de sous-problèmes plus simples, résolvant chacun de ces sous-problèmes une seule fois et en stockant leurs solutions.
Numéros de Fibonacci
Les nombres de Fibonacci sont un sujet de choix pour la programmation dynamique car l'approche récursive traditionnelle fait beaucoup de calculs répétés. Dans ces exemples, j'utiliserai le cas de base de f(0) = f(1) = 1 .
Voici un exemple d'arbre récursif pour fibonacci(4) , notez les calculs répétés: 
Programmation non dynamique O(2^n) Complexité d'exécution, O(n) Complexité de la pile
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
C'est la manière la plus intuitive d'écrire le problème. Tout au plus, l’espace de la pile sera O(n) lorsque vous descendez la première branche récursive en faisant des appels à fibonacci(n-1) jusqu’à ce que vous atteigniez le cas de base n < 2 .
La preuve de complexité d'exécution O(2^n) que l'on peut voir ici: la complexité informatique de la séquence de Fibonacci . Le point principal à noter est que l’exécution est exponentielle, ce qui signifie que le temps d’exécution doublera pour chaque terme suivant, fibonacci(15) prendra deux fois plus de temps que fibonacci(14) .
Memoized O(n) Runtime Complexité, O(n) Complexité de l'espace, O(n) Complexité de la pile
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
Avec l'approche mémo, nous introduisons un tableau qui peut être considéré comme tous les appels de fonction précédents. Le memo[n] localisation memo[n] est le résultat de l'appel de fonction fibonacci(n) . Cela nous permet d'échanger la complexité d'espace de O(n) pour un runtime O(n) car nous n'avons plus besoin de calculer les appels de fonction en double.
Programmation dynamique itérative O(n) Complexité d'exécution, O(n) Complexité spatiale, Pas de pile récursive
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
Si nous divisons le problème en éléments centraux, vous remarquerez que pour calculer fibonacci(n) nous avons besoin de fibonacci(n-1) et de fibonacci(n-2) . Nous pouvons également remarquer que notre cas de base apparaîtra à la fin de cet arbre récursif, comme indiqué ci-dessus.
Avec cette information, il est maintenant logique de calculer la solution à rebours, en commençant par les cas de base et en remontant. Maintenant, pour calculer fibonacci(n) nous calculons d'abord tous les nombres de fibonacci jusqu'à et par n .
Cet avantage principal est que nous avons maintenant éliminé la pile récursive tout en conservant le runtime O(n) . Malheureusement, nous avons toujours une complexité d'espace O(n) mais cela peut aussi être changé.
Programmation dynamique itérative avancée O(n) Complexité d'exécution, O(1) Complexité spatiale, Pas de pile récursive
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
Comme indiqué ci-dessus, l'approche de programmation dynamique itérative commence à partir des cas de base et fonctionne jusqu'au résultat final. L'observation clé à faire pour arriver à la complexité d'espace à O(1) (constante) est la même observation que nous avons faite pour la pile récursive - nous avons seulement besoin de fibonacci(n-1) et de fibonacci(n-2) fibonacci(n) . Cela signifie que nous avons seulement besoin de sauvegarder les résultats pour fibonacci(n-1) et fibonacci(n-2) à tout moment de notre itération.
Pour stocker ces 2 derniers résultats, j'utilise un tableau de taille 2 et je retourne simplement l'index auquel je l'affecte en utilisant i % 2 qui alternera comme suit: 0, 1, 0, 1, 0, 1, ..., i % 2 .
J'ajoute les deux index du tableau car nous savons que l'addition est commutative ( 5 + 6 = 11 et 6 + 5 == 11 ). Le résultat est ensuite attribué à la plus ancienne des deux taches (notée i % 2 ). Le résultat final est ensuite stocké à la position n%2
Remarques
- Il est important de noter que parfois, il peut être préférable de proposer une solution mémorisée itérative pour les fonctions qui effectuent des calculs importants à plusieurs reprises, car vous construirez un cache de la réponse aux appels de fonction et les appels suivants pourront être
O(1)si il a déjà été calculé.