Quelle est la différence entre memoization et de la programmation dynamique?
Quelle est la différence entre memoization et de la programmation dynamique? Je pense que la programmation dynamique est un sous-ensemble de memoization. Est-il juste?
- Voici un article qui explique cela très bien: la programmation Dynamique vs memoization vs tabulation.
Vous devez vous connecter pour publier un commentaire.
Memoization est un terme qui décrit une technique d'optimisation où vous cache précédemment calculés les résultats, et de retourner le résultat mis en cache lorsque le même calcul est à nouveau nécessaire.
De la programmation dynamique est une technique pour résoudre des problèmes de nature récursive, de manière itérative, est applicable lorsque les calculs de la sous-problèmes de chevauchement.
La programmation dynamique est généralement mis en œuvre à l'aide de tabulation, mais peut également être mis en œuvre à l'aide de memoization. Donc, comme vous pouvez le voir, ni l'un est un "sous-ensemble" de l'autre.
Raisonnable question qui suit est: Quelle est la différence entre la tabulation (typique de la dynamique de la technique de programmation) et de memoization?
Lorsque vous résolvez un problème de programmation dynamique à l'aide de tabulation vous résoudre le problème de "de bas en haut", c'est à dire, en résolvant tous les sous-problèmes en premier, généralement en remplissant 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.
Si vous utilisez memoization pour résoudre le problème, vous le faites par le maintien d'une carte de déjà permis de résoudre des sous-problèmes. Vous le faites "de haut en bas" 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 de
ici(le lien est maintenant mort, la diapositive est toujours bon tout de même):Ressources supplémentaires:
Cela a été réécrit comme un article ici.
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é à la fois de bas en haut ou de haut en bas des méthodes.
Voir cette discussion sur memoization vs tabulation.
Donc 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é et de stockage déjà trouvé des solutions par le biais soit de totalisation ou memoization. Memoization est une méthode pour garder une trace de solutions à déjà résolu des problèmes et peut être utilisé avec n'importe quelle fonction qui est unique déterministe des solutions pour un ensemble donné d'intrants.
La Programmation dynamique est souvent appelé Memoization!
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é)
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
DP a le potentiel de transformer exponentielle en temps par la force brute des solutions dans polynôme algorithmes temps.
DP peut être beaucoup plus efficace, car son itératif
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) 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.
(1) Memoization et DP, conceptuellement, 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:
-Conceptuellement, (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).
Prise (3) en compte, ils ont de légères différences dans la performance.
De wikipedia:
Memoization
De La Programmation Dynamique
Lors du bris 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.
De 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.
Les deux Memoization et de la Programmation Dynamique résout personne subproblem qu'une seule fois.
Memoization utilise la récursivité et travaille de haut en bas, tandis que la Dynamique de programmation se déplace dans le sens opposé à la résolution du problème bottom-up.
Ci-dessous est une analogie intéressante -
De haut en bas - d'Abord vous dire que je vais prendre dans le monde entier. Comment allez-vous faire? Vous dire que je vais prendre sur l'Asie en premier. Comment allez-vous faire? Je vais prendre de l'Inde la première. Je vais devenir le Ministre en Chef de Delhi, etc. etc.
Bottom-up - Vous dire que je vais devenir le CM de Delhi. Ensuite prendre le relais de l'Inde, puis tous les autres pays de l'Asie et enfin je vais conquérir le monde.
Je voudrais aller avec un exemple;
Problème:
La récursivité avec Memoization
De cette façon, nous sommes en élagage (un retrait de l'excédent de matériau à partir d'un arbre ou un arbuste) la récursivité de l'arbre avec l'aide de mémo tableau et la réduction de la taille de la récursivité de l'arbre jusqu'à la nn.
De La Programmation Dynamique
Comme nous pouvons le voir, ce problème peut être décomposé en sous-problèmes, et il contient les sous-structure optimale de la propriété c'est à dire sa solution optimale peut être réalisée de manière efficace à partir des solutions optimales de ses sous-problèmes, on peut utiliser la programmation dynamique pour résoudre ce problème.
Exemples prendre de https://leetcode.com/problems/climbing-stairs/