Quelle est la différence entre la mémorisation et la programmation dynamique?

Question

Je pense que la programmation dynamique est un sous-ensemble de la mémorisation. Est ce bien?

Answer 1

Quelle est la différence entre memoization et de la programmation dynamique?

La programmation dynamique vous résoudre le problème de "bas en haut", c'est à dire, en résolvant tous les sous-problèmes en premier, généralement par le remplissage d'un n-dimensions de la table. Basé sur les résultats dans le tableau, la solution à la "top" / problème original est ensuite calculée.

Dans memoization vous permet généralement de résoudre le problème langoureusement tout en conservant une carte de déjà permis de résoudre des sous-problèmes. Vous le faites "top-down" dans le sens où vous résoudre le "top" en premier lieu le problème (qui, généralement, se répète en bas à résoudre les sous-problèmes).

Une bonne glisse à partir d' ici:

• Si tous les sous-problèmes doivent être résolus au moins une fois, un bas-dynamique-algorithme de programmation généralement surpasse haut vers le bas, memoized algorithme par un facteur constant
  • Pas de frais généraux pour la récursivité et moins de frais généraux pour le maintien de la table
  • Il y a certains problèmes pour lesquels le modèle régulier de table accède à la programmation dynamique algorithme peut être exploité afin de réduire le temps ou dans l'espace encore les besoins
• Si certains sous-problèmes dans la subproblem de l'espace n'a pas besoin d'être résolu, le memoized solution a l'avantage de résoudre seul de ces sous-problèmes qui sont certainement nécessaires

 

Je pense que la programmation dynamique est sous-ensemble de memoization. Est-il juste?

Je ne dirais pas cela.

Si vous parvenez à résoudre le problème, par exemple, en remplissant certaines n-dimensions de la table avec les réponses à des sous-problèmes (bottom-up), vous ne faites rien "paresseusement"/"à la demande" ou "top down", ce qui est assez central dans memoization.

Answer 2

La accepté de répondre (et bon nombre de réponses) sont dans l'erreur. Les auteurs semblent avoir été confondu par mal formulé des sources.

La Programmation dynamique est une algorithmique paradigme qui permet de résoudre un problème complexe en le divisant en sous-problèmes et stocke les résultats de sous-problèmes pour éviter de faire la même nouveau les résultats.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Memoization est une méthode facile à suivre déjà résolu des solutions (souvent mis en œuvre comme une clé de hachage valeur paire, contrairement à la totalisation qui est souvent basée sur des tableaux), de sorte qu'ils ne sont pas recalculées quand ils se sont rencontrés de nouveau. Il peut être utilisé dans les deux à la fois de bas en haut ou de haut en bas des méthodes.

Voir cette discussion sur memoization vs tabulation.

La mémorisation ou de tableaux, approche de programmation Dynamique

Si la programmation Dynamique est une méthode pour résoudre certaines classes de problèmes par la résolution des relations de récurrence/récursivité. Memoization est une méthode pour garder une trace de déjà résolu les problèmes.

Answer 3

La Programmation dynamique est souvent appelé Memoization!

1. Memoization est la descendante de la technique(commencer à résoudre le problème en le décomposant) et de la programmation dynamique est une technique de(commencer à résoudre la banalité sous-problème, vers le problème donné)

2. DP trouve la solution en partant du cas de base(s) et travaille son chemin vers le haut. DP résout tous les sous-problèmes, parce qu'il ne bottom-up

   À la différence de Memoization, ce qui résout seulement les sous-problèmes

3. DP a le potentiel de transformer exponentielle en temps par la force brute des solutions en polynomiale en temps des algorithmes.

4. DP peut être beaucoup plus efficace, car son itératif

   Au contraire, Memoization doit payer pour l' (souvent importante) les frais généraux en raison de la récursivité.

Pour être le plus simple, Memoization utilise l'approche top-down pour résoudre le problème, c'est à dire de commencer avec core(principale) de problème, alors la décompose en sous-problèmes et de les résoudre de ces sous-problèmes de la même façon. Dans cette approche, même sous-problème peut se produire plusieurs fois et consomment plus de cycle du PROCESSEUR, d'où augmentation de la complexité du temps. Alors que la programmation Dynamique d'un même sous-problème ne sera pas résolu plusieurs fois, mais l'avant résultat sera utilisé pour optimiser la solution.

Answer 4

(1) Memoization et DP, sur le plan conceptuel, c'est vraiment la même chose. Parce que: considérer la définition de DP: "le chevauchement des sous-problèmes" "et de sous-structure optimale". Memoization possède pleinement ces 2.

(2) Memoization est DP avec le risque de débordement de pile est la récursivité est profonde. DP de bas en haut n'a pas ce risque.

(3) Memoization besoin d'une table de hachage. Afin de plus d'espace, et quelques temps de recherche.

Donc pour répondre à la question:

-Sur le plan conceptuel, (1) signifie qu'ils sont la même chose.

-La prise (2) en compte, si vous voulez vraiment, memoization est un sous-ensemble de la DP, en ce sens qu'un problème résoluble par memoization seront résolues par le DP, mais un problème résoluble par DP peuvent pas être résolues par memoization (parce qu'il peut débordement de pile).

-La prise de (3) en compte, ils ont de légères différences dans la performance.

Answer 5

De wikipedia:

"En informatique, memoization est une technique d'optimisation utilisée principalement pour accélérer les programmes d'ordinateur par le fait d'avoir des appels de fonction d'éviter de répéter le calcul des résultats déjà traitées entrées."

"En mathématiques et en informatique, la programmation dynamique est une méthode pour la résolution de problèmes complexes en les décomposant en sous-problèmes plus simples."

Lors de la rupture d'un problème dans les plus petites/plus simple sous-problèmes, on rencontre souvent la même subproblem plus d'une fois - alors, nous utilisons Memoization pour enregistrer les résultats des calculs précédents, donc nous n'avons pas besoin de les répéter.

La programmation dynamique se heurte souvent à des situations où il est logique d'utiliser memoization mais Vous pouvez utiliser une technique sans nécessairement à l'aide de l'autre.