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

Quelle est la différence entre la mémorisation et la programmation dynamique? Je pense que la programmation dynamique est un sous-ensemble de la mémorisation. Est ce juste?

Article pertinent sur Programming.Guide: programmation dynamique vs mémorisation vs tabulation

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

La mémorisation est un terme décrivant une technique d'optimisation dans laquelle vous mettez en cache les résultats précédemment calculés et renvoyez le résultat mis en cache lorsque le même calcul est à nouveau nécessaire.

La programmation dynamique est une technique de résolution itérative de problèmes de nature récursive et est applicable lorsque les calculs des sous-problèmes se chevauchent.

La programmation dynamique est généralement implémentée à l'aide de la tabulation, mais peut également être implémentée à l'aide de la mémorisation. Comme vous pouvez le voir, aucun des deux n'est un "sous-ensemble" de l'autre.

Une question de suivi raisonnable est la suivante: quelle est la différence entre la tabulation (la technique de programmation dynamique typique) et la mémorisation?

Lorsque vous résolvez un problème de programmation dynamique en utilisant la tabulation, vous résolvez le problème "de bas en haut ", c'est-à-dire en résolvant d'abord tous les sous-problèmes associés, généralement en remplissant un tableau à n dimensions. Sur la base des résultats du tableau, la solution au problème "top" / original est ensuite calculée.

Si vous utilisez la mémorisation pour résoudre le problème, vous le faites en maintenant une carte des sous-problèmes déjà résolus. Vous le faites «de haut en bas » dans le sens où vous résolvez d'abord le problème de «haut» (qui revient généralement vers le bas pour résoudre les sous-problèmes).

Une bonne diapositive d' ici (le lien est maintenant mort, la diapositive est toujours bonne cependant):

• Si tous les sous-problèmes doivent être résolus au moins une fois, un algorithme de programmation dynamique ascendant surpasse généralement un algorithme mémorisé de haut en bas par un facteur constant
  • Pas de surcharge pour la récursivité et moins de surcharge pour la maintenance de la table
  • Il existe certains problèmes pour lesquels le modèle régulier d'accès aux tables dans l'algorithme de programmation dynamique peut être exploité pour réduire encore plus les besoins en temps ou en espace.
• Si certains sous-problèmes dans l'espace de sous-problèmes n'ont pas du tout besoin d'être résolus, la solution mémorisée a l'avantage de résoudre uniquement les sous-problèmes qui sont définitivement nécessaires.

Ressources supplémentaires:

• Wikipédia: mémorisation , programmation dynamique
• SO Q / A: approche de mémorisation ou de tabulation pour la programmation dynamique

La programmation dynamique est un paradigme algorithmique qui résout un problème complexe donné en le décomposant en sous-problèmes et stocke les résultats des sous-problèmes pour éviter de calculer à nouveau les mêmes résultats.

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

La mémorisation est une méthode facile pour suivre les solutions précédemment résolues (souvent implémentées comme une paire de valeurs de clé de hachage, par opposition à la tabulation qui est souvent basée sur des tableaux) afin qu'elles ne soient pas recalculées lorsqu'elles sont rencontrées à nouveau. Il peut être utilisé dans les deux méthodes ascendantes ou descendantes.

Voir cette discussion sur la mémorisation vs la tabulation.

La programmation dynamique est donc une méthode pour résoudre certaines classes de problèmes en résolvant les relations de récurrence / récursivité et en stockant les solutions précédemment trouvées via la tabulation ou la mémorisation. La mémorisation est une méthode pour garder une trace des solutions aux problèmes précédemment résolus et peut être utilisée avec n'importe quelle fonction qui a des solutions déterministes uniques pour un ensemble donné d'entrées.

La programmation dynamique est souvent appelée mémorisation!

1. La mémorisation est la technique descendante (commencez à résoudre le problème donné en le décomposant) et la programmation dynamique est une technique ascendante (commencez à résoudre à partir du sous-problème trivial, vers le problème donné)

2. DP trouve la solution en partant du ou des cas de base et progresse vers le haut. DP résout tous les sous-problèmes, car il le fait de bas en haut

   Contrairement à la mémorisation, qui ne résout que les sous-problèmes nécessaires

3. DP a le potentiel de transformer des solutions de force brute à temps exponentiel en algorithmes à temps polynomial.

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

   Au contraire, la mémorisation doit payer les frais généraux (souvent importants) dus à la récursivité.

Pour être plus simple, la mémorisation utilise l'approche descendante pour résoudre le problème, c'est-à-dire qu'elle commence par le problème principal (principal), puis le décompose en sous-problèmes et résout ces sous-problèmes de la même manière. Dans cette approche, le même sous-problème peut se produire plusieurs fois et consommer plus de cycle CPU, augmentant ainsi la complexité temporelle. Alors qu'en programmation dynamique, le même sous-problème ne sera pas résolu plusieurs fois mais le résultat précédent sera utilisé pour optimiser la solution.

(1) La mémorisation et le DP, conceptuellement , c'est vraiment la même chose. Parce que: considérez la définition de DP: "sous-problèmes qui se chevauchent" "et sous-structure optimale". La mémorisation possède pleinement ces 2.

(2) La mémorisation est DP avec le risque de débordement de pile si la récursivité est profonde. DP bottom up n'a pas ce risque.

(3) La mémorisation a besoin d'une table de hachage. Donc de l'espace supplémentaire et du temps de recherche.

Donc pour répondre à la question:

- Conceptuellement , (1) signifie que c'est la même chose.

-En tenant compte (2), si vous voulez vraiment, la mémorisation est un sous-ensemble de DP, dans le sens où un problème résolu par mémorisation sera résolu par DP, mais un problème résolu par DP pourrait ne pas être résolu par mémorisation (car il pourrait empiler le débordement).

-Tenant (3) en compte, ils présentent de légères différences de performances.

De wikipedia:

Mémorisation

En informatique, la mémorisation est une technique d'optimisation utilisée principalement pour accélérer les programmes informatiques en ayant des appels de fonction évitant de répéter le calcul des résultats pour les entrées précédemment traitées.

Programmation dynamique

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

Lorsque nous divisons un problème en sous-problèmes plus petits / plus simples, nous rencontrons souvent le même sous-problème plus d'une fois - nous utilisons donc la mémorisation pour enregistrer les résultats des calculs précédents afin de ne pas avoir à les répéter.

La programmation dynamique rencontre souvent des situations où il est logique d'utiliser la mémorisation, mais vous pouvez utiliser l'une ou l'autre technique sans nécessairement utiliser l'autre.

La mémorisation et la programmation dynamique ne résolvent le sous-problème individuel qu'une seule fois.

La mémorisation utilise la récursivité et fonctionne de haut en bas, tandis que la programmation dynamique se déplace dans la direction opposée pour résoudre le problème de bas en haut.

Voici une analogie intéressante -

De haut en bas - D'abord, vous dites que je vais conquérir le monde. Comment feras-tu cela? Vous dites que je prendrai le contrôle de l'Asie en premier. Comment feras-tu cela? Je vais d'abord prendre le contrôle de l'Inde. Je deviendrai le ministre en chef de Delhi, etc. etc.

De bas en haut - Vous dites que je deviendrai le CM de Delhi. Ensuite, je reprendrai l'Inde, puis tous les autres pays d'Asie et enfin je prendrai le contrôle du monde.

Je voudrais aller avec un exemple ;

Problème:

Vous montez un escalier. Il faut n étapes pour atteindre le sommet.

Chaque fois, vous pouvez gravir 1 ou 2 marches. De combien de façons différentes pouvez-vous grimper au sommet?

Récursivité avec mémorisation

De cette façon, nous élaguons (une suppression de l'excès de matière d'un arbre ou d'un arbuste) l'arbre de récursivité à l'aide du tableau de mémos et réduisons la taille de l'arbre de récursion jusqu'à nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Programmation dynamique

Comme nous pouvons voir que ce problème peut être divisé en sous-problèmes et qu'il contient la propriété de sous-structure optimale, c'est-à-dire que sa solution optimale peut être construite efficacement à partir de solutions optimales de ses sous-problèmes, nous pouvons utiliser une programmation dynamique pour résoudre ce problème.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Les exemples proviennent de https://leetcode.com/problems/climbing-stairs/

Pensez simplement à deux façons,

1. Nous décomposons le problème le plus important en sous-problèmes plus petits - approche descendante.
2. Nous partons du plus petit sous-problème et atteignons le plus gros problème - Approche ascendante.

Dans la mémorisation, nous allons avec (1.) où nous enregistrons chaque appel de fonction dans un cache et rappelons à partir de là. C'est un peu cher car cela implique des appels récursifs.

Dans la programmation dynamique, nous allons avec (2.) où nous maintenons une table, de bas en haut en résolvant des sous-problèmes en utilisant les données enregistrées dans la table, communément appelées dp-table.

Remarque:

• Les deux sont applicables aux problèmes de sous-problèmes se chevauchant.

• La mémorisation est relativement médiocre par rapport à DP en raison des frais généraux impliqués lors des appels de fonction récursifs.

• La complexité temporelle asymptotique reste la même.

En programmation dynamique ,

• Pas de surcharge pour la récursivité, moins de surcharge pour la maintenance de la table.
• Le modèle régulier des accès à la table peut être utilisé pour réduire les besoins en temps ou en espace.

En mémorisation ,

• Certains sous-problèmes n'ont pas besoin d'être résolus.