Programmation dynamique et memorisation: approches ascendantes et approches descendantes

du haut vers le bas et le PDD du bas vers le haut sont deux façons différentes de résoudre les mêmes problèmes. Envisagez une solution de programmation memoized (du haut vers le bas) vs dynamique (du bas vers le haut) pour le calcul des nombres fibonacci.

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

personnellement, je trouve la mémoïsation beaucoup plus naturelle. Vous pouvez prendre une fonction récursive et la mémoize par un processus mécanique (d'abord Réponse de recherche dans le cache et le retourner si possible, sinon le calculer de façon récursive et puis avant de retourner, vous sauvez le calcul dans le cache pour une utilisation future), alors que faire de la programmation dynamique ascendante exige que vous encodiez un ordre dans lequel les solutions sont calculées, de sorte qu'aucun "gros problème" n'est calculé avant le petit problème dont il dépend.

une caractéristique clé de la programmation dynamique est la présence de sous-problèmes se chevauchant . C'est le problème que vous essayez de résoudre peut être décomposé en sous-problèmes, et beaucoup de ces sous-problèmes partager subsubproblems. C'est comme" diviser pour mieux régner", mais on finit par faire la même chose de nombreuses fois. Un exemple que j'utilise depuis 2003 pour enseigner ou expliquer ces choses: vous pouvez calculer nombres de Fibonacci récursivement.

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

utilisez votre langue préférée et essayez de l'Exécuter pour fib(50) . Il faudra un très, très longtemps. A peu près autant de temps que fib(50) lui-même! Toutefois, beaucoup de travail inutile. fib(50) appellera fib(49) et fib(48) , mais alors les deux finiront par appeler fib(47) , même si la valeur est la même. En fait, fib(47) sera calculé trois fois: par un appel direct de fib(49) , par un appel direct de fib(48) , et aussi par un appel direct d'un autre fib(48) , celui qui a été engendré par le calcul de fib(49) ... Donc, vous voyez, nous avons sous-problèmes se chevauchant .

grande nouvelle: il n'est pas nécessaire de calculer la même valeur plusieurs fois. Une fois que vous l'avez calculé une fois, mettez en cache le résultat, et la prochaine fois utilisez la valeur mise en cache! C'est l'essence même de la programmation dynamique. Vous pouvez l'appeler "top-down", "memoization", ou tout ce que vous voulez. Cette approche est très intuitive et très facile à mettre en œuvre. Il suffit d'écrire une solution récursive d'abord, le tester sur de petits tests, ajouter memoization (mise en cache des valeurs déjà calculées), et --- bingo! --- vous avez terminé.

habituellement, vous pouvez aussi écrire un programme itératif équivalent qui fonctionne de bas en haut, sans récursion. Dans ce cas, ce serait l'approche la plus naturelle: boucle de 1 à 50 calculant tous les nombres de Fibonacci que vous allez.

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

dans tout scénario intéressant, la solution ascendante est généralement plus difficile à comprendre. Cependant, une fois que vous l'aurez compris, vous aurez habituellement une idée plus claire de la façon dont l'algorithme fonctionne. En pratique, pour résoudre des problèmes non triviaux, je recommande d'abord d'écrire l'approche descendante et de la tester sur de petits exemples. Ensuite, écrivez la solution ascendante et comparez les deux pour vous assurer que vous obtenez la même chose. Idéalement, comparez les deux solutions automatiquement. Écrire une petite routine qui générerait beaucoup de tests, idéalement -- tous petits tests jusqu'à une certaine taille --- et valider que les deux solutions donnent le même résultat. Après cela, utilisez la solution ascendante dans la production, mais garder le code Haut-Bas, commenté. Cela permettra aux autres développeurs de comprendre plus facilement ce que vous faites: le code ascendant peut être tout à fait incompréhensible, même si vous l'avez écrit et même si vous savez exactement ce que vous faites.

dans de nombreuses applications, l'approche ascendante est légèrement plus rapide en raison de la surabondance d'appels récursifs. Le débordement de la pile peut aussi être un problème dans certains problèmes, et notez que cela peut dépendre beaucoup des données d'entrée. Dans certains cas, il se peut que vous ne puissiez pas écrire un test provoquant un débordement de la pile si vous ne comprenez pas suffisamment la programmation dynamique, mais un jour cela peut encore arriver.

Maintenant, il y a des problèmes où l'approche descendante est la seule solution possible parce que l'espace de problème est si grand qu'il n'est pas possible de résoudre tous les sous-problèmes. Cependant, la" mise en cache " fonctionne toujours dans un délai raisonnable parce que votre entrée ne nécessite qu'une fraction des sous-problèmes à résoudre - - -mais il est trop délicat de définir explicitement, quels sous-problèmes vous devez résoudre, et donc d'écrire une solution ascendante. D'autre part, il ya des situations où vous savez que vous aurez besoin de résoudre tous sous-problèmes. Dans ce cas, allez sur et ascendantes.

j'utiliserais personnellement top-bottom pour l'optimisation de paragraphe a. K. a le Word wrap optimization problem (rechercher les algorithmes de cassage de ligne Knuth-Plass; au moins TeX l'utilise, et certains logiciels D'Adobe Systems utilise une approche similaire). J'utiliserais bottom-up pour la Fast Fourier Transform .

prenons la série fibonacci comme exemple

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

une autre façon de le dire,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

pour les cinq premiers numéros fibonacci

Bottom(first) number :1
Top (fifth) number: 5 

voyons maintenant un exemple D'algorithme récursif de la série Fibonacci

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Maintenant, si nous exécutons ce programme avec les commandes suivantes

rcursive(5);

si nous examinons de près l'algorithme, pour générer un cinquième nombre, il faut des numéros 3 et 4. Donc, ma récursion commence en fait par le haut (5) et va ensuite jusqu'aux nombres inférieurs/inférieurs. Cette approche est en fait une approche descendante.

pour éviter de faire le même calcul plusieurs fois, nous utilisons des techniques de programmation dynamique. Nous stockons la valeur calculée et la réutilisons. Cette technique s'appelle la mémoïsation. Il y a plus à la programmation dynamique autre que la mémorisation qui n'est pas nécessaire de discuter le problème actuel.

Top-Down

permet de réécrire notre algorithme d'origine et d'ajouter des techniques de mémoire.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

et nous exécutons cette méthode comme suit

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

cette solution est toujours descendante que l'algorithme de départ à partir de la valeur supérieure et aller vers le bas à chaque étape pour obtenir notre valeur supérieure.

Bottom-Up

mais, la question Est, pouvons-nous commencer par le bas, comme du premier nombre de fibonacci puis marcher notre chemin vers le haut. Permet de le réécrire en utilisant cette technique,

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

maintenant, si nous regardons dans cet algorithme, il commence en fait à partir de valeurs plus basses, puis aller en haut. Si j'ai besoin du 5e numéro de fibonacci, Je calcule le 1er, puis le 2e, puis le 3e, jusqu'au 5e numéro. Cette technique s'appelle en fait des techniques ascendantes.

deux dernières, algorithmes exigences de programmation dynamique complètes. Mais l'un est descendant et l'autre est ascendant. Les deux algorithmes ont la même complexité spatiale et temporelle.

la programmation dynamique est souvent appelée 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(des) scénario (s) de base et en se déplaçant vers le haut. DP résout tous les sous-problèmes, car il le fait de bas en haut

contrairement à la Mémoization, qui ne résout que les sous-problèmes nécessaires

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

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

au contraire, la Memoization doit payer pour le important) frais généraux dus à la récursion.

pour être plus simple, Memoization utilise l'approche descendante pour résoudre le problème i.e. il commence avec le problème de base(principal) puis le divise en sous-problèmes et résoudre ces sous-problèmes de la même façon. Dans cette approche, le même sous-problème peut se produire plusieurs fois et consommer plus de cycle CPU, donc augmenter la complexité du temps. Alors que la programmation Dynamique d'un même sous-problème ne sera pas résolu plusieurs fois mais le résultat avant sera utilisé pour optimiser la solution.

simplement dire approche du haut vers le bas utilise la récursion pour appeler des problèmes de sous encore et encore

où comme approche du bas vers le haut utilisent le simple sans appeler personne et donc il est plus efficace.

ci-dessous est la solution basée DP pour le problème de distance D'édition qui est du haut vers le bas. J'espère qu'il sera également aider à comprendre le monde de la Programmation Dynamique:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

vous pouvez penser à son implémentation récursive chez vous. C'est tout à fait bon et stimulant Si vous n'avez pas résolu quelque chose comme ça avant.