Quelle est la différence entre l'approche ascendante et l'approche descendante ?

Question

El ascendant (à la programmation dynamique) consiste à examiner d'abord les "petits" sous-problèmes, puis à résoudre les grands sous-problèmes en utilisant la solution des petits problèmes.

El de haut en bas consiste à résoudre le problème de "manière naturelle" et à vérifier si vous avez déjà calculé la solution du sous-problème.

Je suis un peu perdu. Quelle est la différence entre ces deux-là ?

Answer 1

rev4 : Un commentaire très éloquent de l'utilisateur Sammaron a noté que, peut-être, cette réponse a précédemment confondu top-down et bottom-up. Alors qu'à l'origine cette réponse (rev3) et d'autres réponses disaient que "bottom-up est la mémorisation" ("assumer les sous-problèmes"), c'est peut-être l'inverse (c'est-à-dire que "top-down" peut être "assumer les sous-problèmes" et "bottom-up" peut être "composer les sous-problèmes"). Auparavant, j'ai lu que la mémorisation était un type différent de programmation dynamique, par opposition à un sous-type de programmation dynamique. Je citais ce point de vue bien que n'y adhérant pas. J'ai réécrit cette réponse pour être agnostique sur la terminologie jusqu'à ce que des références appropriées puissent être trouvées dans la littérature. J'ai également converti cette réponse en un wiki communautaire. Veuillez préférer les sources académiques. Liste de références : {Web : 1 , 2 } {Littérature : 5 }

Récapitulatif

La programmation dynamique consiste à ordonner vos calculs de manière à éviter de recalculer le travail en double. Vous avez un problème principal (la racine de votre arbre de sous-problèmes), et des sous-problèmes (sous-arbres). Les sous-problèmes se répètent et se chevauchent généralement. .

Par exemple, considérez votre exemple préféré de Fibonnaci. Voici l'arbre complet des sous-problèmes, si nous faisions un appel récursif naïf :

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(Dans certains autres problèmes rares, cet arbre pourrait être infini dans certaines branches, représentant la non-termination, et donc le bas de l'arbre peut être infiniment grand. En outre, dans certains problèmes, il se peut que vous ne sachiez pas à l'avance à quoi ressemble l'arbre complet. Ainsi, vous pourriez avoir besoin d'une stratégie/algorithme pour décider des sous-problèmes à révéler).

---

Mémorisation, tabulation

Il existe au moins deux techniques principales de programmation dynamique, qui ne s'excluent pas mutuellement :

• Mémorisation - Il s'agit d'une approche de laissez-faire : Vous supposez que vous avez déjà calculé tous les sous-problèmes et que vous n'avez aucune idée de l'ordre d'évaluation optimal. Typiquement, vous effectuez un appel récursif (ou un équivalent itératif) à partir de la racine, et vous espérez soit vous rapprocher de l'ordre d'évaluation optimal, soit obtenir une preuve qui vous aidera à arriver à l'ordre d'évaluation optimal. Vous vous assurerez que l'appel récursif ne recompile jamais un sous-problème parce que vous cache les résultats, et donc les sous-arbres dupliqués ne sont pas recalculés.

  • ejemplo: Si vous calculez la séquence de Fibonacci fib(100) tu appellerais juste ça, et ça appellerait fib(100)=fib(99)+fib(98) qui appellerait fib(99)=fib(98)+fib(97) , ...etc..., qui appellerait fib(2)=fib(1)+fib(0)=1+0=1 . Ensuite, il serait enfin résolu fib(3)=fib(2)+fib(1) mais il n'a pas besoin de recalculer. fib(2) parce que nous l'avons mis en cache.
  • Cela commence au sommet de l'arbre et évalue les sous-problèmes des feuilles/sous-arbres en remontant vers la racine.

• Tabulation - Vous pouvez également considérer la programmation dynamique comme un algorithme de "remplissage de table" (bien que généralement multidimensionnelle, cette "table" peut avoir une géométrie non euclidienne dans de très rares cas*). C'est comme la mémorisation mais plus actif, et implique une étape supplémentaire : Vous devez choisir, à l'avance, l'ordre exact dans lequel vous allez effectuer vos calculs. Cela ne signifie pas que l'ordre doit être statique, mais que vous avez beaucoup plus de flexibilité que la mémorisation.

  • ejemplo: Si vous faites du fibonacci, vous pouvez choisir de calculer les nombres dans cet ordre : fib(2) , fib(3) , fib(4) ... mettre en cache chaque valeur afin de pouvoir calculer les suivantes plus facilement. Vous pouvez également considérer que cela revient à remplir une table (une autre forme de mise en cache).
  • Personnellement, je n'entends pas souvent le mot "tabulation", mais c'est un terme très correct. Certaines personnes considèrent cela comme de la "programmation dynamique".
  • Avant d'exécuter l'algorithme, le programmeur considère l'arbre entier, puis écrit un algorithme pour évaluer les sous-problèmes dans un ordre particulier vers la Racine, en remplissant généralement un tableau.
  • *Note de bas de page : Parfois, le "tableau" n'est pas un tableau rectangulaire avec une connectivité de type grille, en soi. Elle peut plutôt avoir une structure plus complexe, comme un arbre, ou une structure spécifique au domaine du problème (par exemple, les villes situées à une distance de vol sur une carte), ou même un diagramme en treillis, qui, bien que semblable à une grille, n'a pas une structure de connectivité haut-bas-gauche-droite, etc. Par exemple, l'utilisateur 3290797 a lié un exemple de programmation dynamique visant à trouver le ensemble indépendant maximal dans un arbre ce qui correspond à remplir les cases vides d'un arbre.

(Dans sa forme la plus générale, dans un paradigme de "programmation dynamique", je dirais que le programmeur considère l'arbre entier, puis écrit un algorithme qui met en œuvre une stratégie d'évaluation des sous-problèmes qui peut optimiser les propriétés que vous souhaitez (généralement une combinaison de complexité temporelle et spatiale). Votre stratégie doit commencer quelque part, avec un sous-problème particulier, et peut éventuellement s'adapter en fonction des résultats de ces évaluations. Dans le sens général de la "programmation dynamique", vous pourriez essayer de mettre en cache ces sous-problèmes, et plus généralement, essayer d'éviter de revisiter les sous-problèmes, une distinction subtile étant peut-être le cas des graphes dans diverses structures de données. Très souvent, ces structures de données sont à la base comme des tableaux ou des tables. Les solutions aux sous-problèmes peuvent être jetées si nous n'en avons plus besoin).

[Il existe clairement deux approches principales appelées Mémorisation et Tabulation qui peuvent être en bijection avec ces termes (mais pas entièrement). Le terme général que la plupart des gens utilisent reste "Programmation dynamique" et certains parlent de "mémorisation" pour désigner ce sous-type particulier de "Programmation dynamique". Cette réponse refuse de dire ce qui est descendant et ascendant jusqu'à ce que la communauté puisse trouver les références appropriées dans des articles universitaires. En définitive, il est important de comprendre la distinction plutôt que la terminologie].

---

Avantages et inconvénients

Facilité de codage

La mémorisation est très facile à coder (vous pouvez généralement* écrire une annotation "memoizer" ou une fonction wrapper qui le fait automatiquement pour vous), et devrait être votre première ligne d'approche. L'inconvénient de la tabulation est que vous devez trouver un ordre.

*(en fait, cela n'est facile que si vous écrivez la fonction vous-même, et/ou si vous codez dans un langage de programmation impur/non fonctionnel... par exemple si quelqu'un a déjà écrit une fonction précompilée fib elle fait nécessairement des appels récursifs à elle-même, et vous ne pouvez pas magiquement mémoriser la fonction sans vous assurer que ces appels récursifs appellent votre nouvelle fonction mémorisée (et non la fonction originale non mémorisée)).

Récursivité

Notez que les deux méthodes, descendante et ascendante, peuvent être implémentées avec une récursion ou un remplissage itératif du tableau, bien que cela ne soit pas naturel.

Préoccupations pratiques

Avec la mémoïsation, si l'arbre est très profond (par ex. fib(10^6) ), vous manquerez d'espace sur la pile, car chaque calcul retardé doit être mis sur la pile, et vous en aurez 10^6.

Optimalité

L'une ou l'autre approche peut ne pas être optimale en termes de temps si l'ordre dans lequel vous visitez (ou essayez de visiter) les sous-problèmes n'est pas optimal, en particulier s'il existe plus d'une façon de calculer un sous-problème (normalement, la mise en cache devrait résoudre ce problème, mais il est théoriquement possible que la mise en cache ne le fasse pas dans certains cas exotiques). La mémorisation ajoutera généralement à votre complexité temporelle une complexité spatiale (par exemple, avec la tabulation, vous avez plus de liberté pour jeter des calculs, comme l'utilisation de la tabulation avec Fib vous permet d'utiliser O(1) d'espace, mais la mémorisation avec Fib utilise O(N) d'espace de pile).

Optimisations avancées

Si vous faites aussi des problèmes extrêmement compliqués, vous n'aurez peut-être pas d'autre choix que de faire de la tabulation (ou au moins de jouer un rôle plus actif en dirigeant la mémorisation là où vous voulez qu'elle aille). De même, si vous êtes dans une situation où l'optimisation est absolument critique et que vous devez optimiser, la tabulation vous permettra de faire des optimisations que la mémoïsation ne vous permettrait pas de faire de manière sensée. À mon humble avis, dans le génie logiciel normal, aucun de ces deux cas ne se présente jamais, donc j'utiliserais simplement la mémorisation ("une fonction qui met en cache ses réponses") à moins que quelque chose (comme l'espace de la pile) rende la tabulation nécessaire... bien que techniquement pour éviter une explosion de la pile vous pouvez 1) augmenter la taille limite de la pile dans les langages qui le permettent, ou 2) manger un facteur constant de travail supplémentaire pour virtualiser votre pile (ick), ou 3) programmer dans le style continuation-passing, qui en effet virtualise également votre pile (je ne suis pas sûr de la complexité de ceci, mais fondamentalement vous allez effectivement prendre la chaîne d'appel différé de la pile de taille N et de-facto la coller dans N fonctions thunk successivement imbriquées. ... bien que dans certains langages sans optimisation des appels de queue, vous pouvez avoir à trampiler les choses pour éviter une explosion de la pile).

---

Des exemples plus compliqués

Nous énumérons ici des exemples d'intérêt particulier, qui ne sont pas seulement des problèmes généraux de DP, mais qui distinguent de manière intéressante la mémorisation et la tabulation. Par exemple, une formulation peut être beaucoup plus facile que l'autre, ou il peut y avoir une optimisation qui nécessite essentiellement la tabulation :

• l'algorithme pour calculer l'edit-distance[ 4 ], intéressant en tant qu'exemple non trivial d'un algorithme de remplissage de tableaux à deux dimensions

Answer 2

La DP descendante et la DP ascendante sont deux façons différentes de résoudre les mêmes problèmes. Considérons une solution de programmation mémorisée (top down) par rapport à une solution de programmation dynamique (bottom up) pour calculer les nombres de 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émorisation beaucoup plus naturelle. Vous pouvez prendre une fonction récursive et la mémoriser par un processus mécanique (d'abord chercher la réponse dans le cache et la retourner si possible, sinon la calculer récursivement et avant de retourner, vous sauvegardez le calcul dans le cache pour une utilisation future), alors que la programmation dynamique ascendante vous oblige à encoder un ordre dans lequel les solutions sont calculées, de sorte qu'aucun "gros problème" ne soit calculé avant le plus petit problème dont il dépend.

Answer 3

Une caractéristique essentielle de la programmation dynamique est la présence de sous-problèmes se chevauchant . En d'autres termes, le problème que vous essayez de résoudre peut être divisé en sous-problèmes, et beaucoup de ces sous-problèmes partagent des sous-sous-problèmes. C'est comme "Diviser pour mieux régner", mais on finit par faire la même chose de très nombreuses fois. Un exemple que j'utilise depuis 2003 pour enseigner ou expliquer ces questions : vous pouvez calculer Les nombres de Fibonacci de manière récursive.

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

Utilisez votre langage préféré et essayez de l'exécuter pour fib(50) . Cela prendra un temps très, très long. A peu près autant de temps que fib(50) même ! Cependant, beaucoup de travail inutile est effectué. fib(50) appellera fib(49) y fib(48) mais alors les deux finiront par appeler fib(47) même si la valeur est la même. En effet, fib(47) sera calculée 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 .

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

En général, vous pouvez également écrire un programme itératif équivalent qui fonctionne de bas en haut, sans récursion. Dans ce cas, il s'agit de l'approche la plus naturelle : boucle de 1 à 50 en calculant tous les nombres de Fibonacci au fur et à mesure.

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'avez comprise, vous obtenez généralement une image globale beaucoup plus claire du fonctionnement de l'algorithme. En pratique, pour résoudre des problèmes non triviaux, je recommande d'écrire d'abord 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. Écrivez une petite routine qui générerait beaucoup de tests, idéalement -- todo petits tests jusqu'à une certaine taille --- et valider que les deux solutions donnent le même résultat. Ensuite, utilisez la solution ascendante en production, mais conservez le code ascendant, commenté. Cela permettra aux autres développeurs de comprendre plus facilement ce que vous faites : le code bottom-up peut être assez 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 surcharge des appels récursifs. Le débordement de pile peut également être un problème dans certains problèmes, et notez que cela peut beaucoup dépendre des données d'entrée. Dans certains cas, vous ne serez pas en mesure d'écrire un test provoquant un débordement de pile si vous ne comprenez pas assez bien la programmation dynamique, mais un jour, cela peut tout de même arriver.

Or, il existe des problèmes pour lesquels l'approche descendante est la seule solution réalisable, car l'espace du 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 en un temps raisonnable car 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'un autre côté, il y a des situations où vous savez que vous devrez résoudre todo sous-problèmes. Dans ce cas, continuez et utilisez la méthode ascendante.

J'utiliserais personnellement l'option top-bottom pour l'optimisation des paragraphes, c'est-à-dire l'optimisation de l'ensemble de l'organisation. Problème d'optimisation de l'habillage des mots (consultez les algorithmes de rupture de ligne de Knuth-Plass ; au moins TeX l'utilise, et certains logiciels d'Adobe Systems utilisent une approche similaire). J'utiliserais la méthode ascendante pour le Transformée de Fourier rapide .

Answer 4

Prenons l'exemple des séries de Fibonacci.

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

Dans le cas des cinq premiers nombres de Fibonacci

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

Voyons maintenant l'algorithme récursif des séries de Fibonacci comme exemple.

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 regardons de près l'algorithme, pour générer le cinquième nombre, il faut les troisième et quatrième nombres. Donc ma récursion commence en fait par le haut (5) et va ensuite jusqu'aux numéros 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 les valeurs calculées précédemment et les réutilisons. Cette technique est appelée mémorisation. Il y a plus à la programmation dynamique autre que la mémorisation qui n'est pas nécessaire pour discuter le problème actuel.

De haut en bas

Réécrivons notre algorithme original et ajoutons des techniques mémorisées.

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 car l'algorithme part de la valeur supérieure et va vers le bas à chaque étape pour obtenir notre valeur supérieure.

De bas en haut

Mais la question est de savoir si l'on peut commencer par le bas, comme le premier nombre de Fibonacci, puis remonter vers le haut. Réécrivons-le 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 cet algorithme, il commence en fait par les valeurs les plus basses puis va vers le haut. Si j'ai besoin du 5e nombre de Fibonacci, je calcule en fait le 1er, puis le 2e, puis le 3e, jusqu'au 5e nombre. Cette technique est appelée technique ascendante.

Les deux derniers algorithmes répondent pleinement aux exigences de la programmation dynamique. Mais l'un est descendant et l'autre ascendant. Les deux algorithmes ont une complexité spatiale et temporelle similaire.

Answer 5

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

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

2.DP trouve la solution en commençant par le(s) cas de base et en remontant vers le haut. DP résout tous les sous-problèmes, car elle le fait de bas en haut.

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

1. Le DP a le potentiel de transformer les solutions de force brute en temps exponentiel en algorithmes en temps polynomial.

2. DP peut être beaucoup plus efficace parce que son approche itérative est plus efficace.

Au contraire, la mémorisation doit payer le surcoût (souvent important) dû à la récursion.

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, puis le décompose en sous-problèmes et les résout de manière similaire. Dans cette approche, le même sous-problème peut se présenter plusieurs fois et consommer plus de cycles CPU, ce qui augmente la complexité temporelle. Alors que dans la programmation dynamique, le même sous-problème ne sera pas résolu plusieurs fois mais le résultat antérieur sera utilisé pour optimiser la solution.