Quand puis-je utiliser la programmation dynamique pour réduire la complexité temporelle de mon algorithme récursif?

13

La programmation dynamique peut réduire le temps nécessaire pour exécuter un algorithme récursif. Je sais que la programmation dynamique peut aider à réduire la complexité temporelle des algorithmes. Les conditions générales sont-elles telles que si elles sont satisfaites par un algorithme récursif, cela impliquerait que l'utilisation de la programmation dynamique réduira la complexité temporelle de l'algorithme? Quand dois-je utiliser la programmation dynamique?

Anonyme
la source

Réponses:

9

La programmation dynamique est utile si votre algorithme récursif se retrouve plusieurs fois dans les mêmes situations (paramètres d'entrée). Il y a une transformation générale des algorithmes récursifs à la programmation dynamique connue sous le nom de mémorisation , dans laquelle il y a un tableau stockant tous les résultats jamais calculés par votre procédure récursive. Lorsque la procédure récursive est appelée sur un ensemble d'entrées déjà utilisées, les résultats sont simplement extraits de la table. Cela réduit Fibonacci récursif à Fibonacci itératif.

La programmation dynamique peut être encore plus intelligente, en appliquant des optimisations plus spécifiques. Par exemple, il n'est parfois pas nécessaire de stocker la table entière en mémoire à un moment donné.

Yuval Filmus
la source
Le compteur serait alors que chaque fois que la complexité de l'espace de la mémorisation est supérieure aux données d'entrée (peut-être juste> O (N)), il est probable que la programmation dynamique ne va pas aider. Autrement dit, lorsque vous rencontrez rarement la même situation.
edA-qa mort-ora-y
1
Memoisation! = Programmation dynamique!
Raphael
1
Je ne pense pas que nous disions cela, mais la question indique une réduction de la complexité temporelle. La programmation dynamique à elle seule partitionne simplement le problème. La programmation dynamique + mémorisation est un moyen générique d'améliorer la complexité du temps lorsque cela est possible .
edA-qa mort-ora-y
@ edA-qamort-ora-y: C'est vrai. Je pense qu'il est important de le souligner clairement, car apparemment le PO confond / mélange les concepts.
Raphael
8

Si vous cherchez simplement à accélérer votre algorithme récursif, la mémoisation pourrait être suffisante. Il s'agit de la technique de stockage des résultats des appels de fonction afin que les appels futurs avec les mêmes paramètres puissent simplement réutiliser le résultat. Ceci est applicable si (et seulement si) votre fonction

  • n'a pas d'effets secondaires et
  • ne dépend que de ses paramètres (c'est-à-dire pas d'un certain état).

Cela vous fera gagner du temps si (et seulement si) la fonction est appelée avec les mêmes paramètres encore et encore. Des exemples populaires incluent la définition récursive des nombres de Fibonacci, c'est-à-dire

f(0)=0f(1)=1f(n+2)=f(n+1)+f(n), n0

Lorsqu'il est évalué naïvement, est souvent appelé exponentiellement. Avec la mémoisation, a toujours été calculé par déjà, donc il ne reste qu'un nombre linéaire d'appels.f ( n ) f ( n + 1 )ff(n)f(n+1)

Notez que, en revanche, la mémoisation est presque inutile pour des algorithmes comme le tri par fusion: généralement peu (le cas échéant) de listes partielles sont identiques, et les contrôles d'égalité sont chers (le tri n'est que légèrement plus coûteux!).

Dans les implémentations pratiques, la façon dont vous stockez les résultats est d'une grande importance pour les performances. L'utilisation de tables de hachage peut être le choix évident, mais peut casser la localité. Si vos paramètres sont des entiers non négatifs, les tableaux sont un choix naturel mais peuvent entraîner une surcharge de mémoire énorme si vous n'utilisez que certaines entrées. Par conséquent, la mémoisation est un compromis entre effet et coût; son efficacité dépend de votre scénario spécifique.


La programmation dynamique est une bête complètement différente. Il est applicable aux problèmes avec la propriété qui

  • il peut être partitionné en sous-problèmes (probablement de plusieurs manières),
  • ces sous-problèmes peuvent être résolus indépendamment,
  • des solutions (optimales) de ces sous-problèmes peuvent être combinées à des solutions (optimales) du problème d'origine et
  • les sous-problèmes ont la même propriété (ou sont triviaux).

Ceci est généralement (implicitement) sous-entendu lorsque les gens invoquent le principe d'optimalité de Bellman .

Maintenant, cela ne décrit qu'une classe de problèmes qui peuvent être exprimés par un certain type de récursivité. Leur évaluation est (souvent) efficace, car la mémoisation peut être appliquée à bon escient (voir ci-dessus); généralement, des sous-problèmes plus petits surviennent en tant que parties de nombreux problèmes plus importants. Les exemples populaires incluent la distance d'édition et l' algorithme Bellman-Ford .

Raphael
la source
Êtes-vous en train de dire qu'il existe des cas où la programmation dynamique entraînera une meilleure complexité temporelle, mais la mémorisation n'aiderait pas (ou du moins pas autant)? Avez-vous des exemples? Ou dites-vous simplement que la programmation dynamique n'est utile que pour un sous-ensemble de problèmes où la mémorisation est?
svick
@svick: La programmation dynamique n'accélère rien en soi, seulement si la récursion DP est évaluée avec mémoisation (ce qui est généralement (!) le cas). Encore une fois: DP est un moyen de modéliser des problèmes en termes de récursivité, la mémoisation est une technique pour accélérer des algorithmes récursifs appropriés (que ce soit DP). Il n'est pas logique de comparer les deux directement. Bien sûr, vous essayez de modéliser un problème comme DP parce que vous vous attendez à appliquer la mémoisation et donc à le résoudre plus rapidement que les approches naïves (r) ne le pourraient. Mais un point de vue DP ne conduit pas toujours non plus à l'algorithme le plus efficace.
Raphael
Si vous disposez de plusieurs processeurs, la programmation dynamique améliore considérablement les performances du monde réel, car vous pouvez paralléliser les pièces. Cela ne change cependant pas la complexité du temps.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Cela est vrai pour toute récursivité. Cependant, il n'est pas clair que cela crée une bonne accélération, car la mémoisation est moins efficace au-delà des limites du processeur.
Raphael
Correction: les récurrences de DP d'évaluation naïvement peuvent toujours être (beaucoup) plus rapides que la force brute; cf. ici .
Raphael