Quelle est la différence entre de bas en haut et de haut en bas?

177

Le bottom-up consiste à regarder d' abord l' approche (à la programmation dynamique) aux « petits » sous - problèmes, puis résoudre les sous - problèmes plus importants en utilisant la solution aux petits problèmes.

Le top-down 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 confus. Quelle est la différence entre ces deux?

Client
la source

Réponses:

247

rev4: Un commentaire très éloquent de l'utilisateur Sammaron a noté que, peut-être, cette réponse confondait auparavant le haut vers le bas et le bas vers le haut. Alors qu'à l'origine cette réponse (rev3) et d'autres réponses disaient que "de bas en haut est la mémorisation" ("assumer les sous-problèmes"), cela peut être l'inverse (c'est-à-dire que "de haut en bas" peut être "assumer les sous-problèmes" et " de bas en haut "peut être" composer les sous-problèmes "). Auparavant, j'avais 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 je n'y souscris pas. J'ai réécrit cette réponse pour être indépendante de 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:} {Littérature: 5 }

résumer

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 arborescence de sous-problèmes), et des sous-problèmes (sous-arborescences). 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 avons fait 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 peut être infini dans certaines branches, ce qui représente la non-terminaison, et ainsi le bas de l'arbre peut être infiniment grand. De plus, dans certains problèmes, vous pourriez ne pas savoir à quoi ressemble l'arbre complet avant Vous aurez peut-être besoin d’une stratégie / d’un 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 sont pas mutuellement exclusives:

  • Mémorisation - Il s'agit d'une approche de laisser-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. En règle générale, vous effectuez un appel récursif (ou un équivalent itératif) à partir de la racine, et espérez que vous vous rapprocherez de l'ordre d'évaluation optimal, ou obtenez une preuve que vous vous aiderez à arriver à l'ordre d'évaluation optimal. Vous vous assurez que l'appel récursif ne recalcule jamais un sous-problème car vous mettez en cache les résultats et ainsi les sous-arborescences dupliquées ne sont pas recalculées.

    • exemple: Si vous calculez la séquence de Fibonacci fib(100), vous appelleriez simplement ceci, et il 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 finalement résolu fib(3)=fib(2)+fib(1), mais il n'a pas besoin de recalculer fib(2), car nous l'avons mis en cache.
    • Cela commence au sommet de l'arborescence et évalue les sous-problèmes des feuilles / sous-arbres vers la racine.
  • Tabulation - Vous pouvez également considérer la programmation dynamique comme un algorithme de «remplissage de table» (bien que généralement multidimensionnel, 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 ferez vos calculs. Cela ne doit pas impliquer que l'ordre doit être statique, mais que vous avez beaucoup plus de flexibilité que la mémorisation.

    • exemple: Si vous effectuez fibonacci, vous pouvez choisir de calculer les chiffres dans cet ordre: fib(2), fib(3), fib(4)... la mise en cache toutes les valeurs pour que vous puissiez calculer les prochains plus facilement. Vous pouvez également penser que cela remplit une table (une autre forme de mise en cache).
    • Personnellement, je n'entends pas beaucoup le mot «tabulation», mais c'est un terme très décent. Certaines personnes considèrent cette "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é en forme de grille, en soi. Au contraire, il peut avoir une structure plus compliquée, comme un arbre, ou une structure spécifique au domaine du problème (par exemple des villes à 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, user3290797 a lié un exemple de programmation dynamique de recherche de l' ensemble indépendant maximum dans une arborescence , ce qui correspond à remplir les espaces dans une arborescence.

(Au plus général, dans un paradigme de "programmation dynamique", je dirais que le programmeur considère l'ensemble de l'arbre, alorsécrit un algorithme qui implémente une stratégie pour évaluer les sous-problèmes qui peuvent optimiser les propriétés que vous voulez (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-être s’adapter en fonction des résultats de ces évaluations. Dans le sens général de "programmation dynamique", vous pouvez essayer de mettre en cache ces sous-problèmes, et plus généralement, éviter de revoir les sous-problèmes avec une distinction subtile pouvant être le cas des graphiques dans diverses structures de données. Très souvent, ces structures de données sont à leur base comme des tableaux ou des tableaux. Les solutions aux sous-problèmes peuvent être jetées si nous n'en avons plus besoin.)

[Auparavant, cette réponse faisait une déclaration sur la terminologie descendante et ascendante; 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 est toujours «programmation dynamique» et certaines personnes disent «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 les articles universitaires. En fin de compte, 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 "mémo" 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 établir une commande.

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

Récursivité

Notez que le haut et le bas peuvent être implémentés avec une récursivité ou un remplissage de table itératif, bien que cela ne soit pas naturel.

Préoccupations pratiques

Avec la mémorisation, si l'arbre est très profond (par exemple fib(10^6)), vous manquerez d'espace de 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 dans le temps si l'ordre dans lequel vous passez (ou essayez) de visiter les sous-problèmes n'est pas optimal, en particulier s'il existe plusieurs façons de calculer un sous-problème (normalement, la mise en cache résoudrait cela, mais il est théoriquement possible que la mise en cache puisse pas dans certains cas exotiques). La mémorisation ajoutera généralement de votre complexité temporelle à votre complexité spatiale (par exemple, avec la tabulation, vous avez plus de liberté pour rejeter les calculs, comme l'utilisation de la tabulation avec Fib vous permet d'utiliser l'espace O (1), mais la mémorisation avec Fib utilise O (N) espace de pile).

Optimisations avancées

Si vous faites également un problème extrêmement compliqué, vous n'aurez peut-être pas d'autre choix que de faire une tabulation (ou du moins de jouer un rôle plus actif en dirigeant la mémorisation là où vous voulez qu'elle aille). De plus, 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émorisation ne vous permettrait pas autrement de faire de manière saine. À mon humble avis, dans l'ingénierie logicielle normale, 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 pile) ne rende la tabulation nécessaire ... techniquement pour éviter une explosion de pile, vous pouvez 1) augmenter la limite de taille de pile dans les langues qui le permettent, ou 2) consommer un facteur constant de travail supplémentaire pour virtualiser votre pile (ick),


Exemples plus compliqués

Nous énumérons ici des exemples présentant un intérêt particulier, qui ne sont pas seulement des problèmes généraux de DP, mais 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 une tabulation:

  • l'algorithme de calcul de la distance d'édition [ 4 ], intéressant comme exemple non trivial d'algorithme de remplissage de table bidimensionnel
ninjagecko
la source
3
@ coder000001: pour les exemples python, vous pouvez rechercher sur Google python memoization decorator; certains langages vous permettront d'écrire une macro ou un code qui encapsule le modèle de mémorisation. Le modèle de mémorisation n'est rien de plus que "plutôt que d'appeler la fonction, recherchez la valeur dans un cache (si la valeur n'est pas là, calculez-la et ajoutez-la d'abord au cache)".
ninjagecko
16
Je ne vois personne en parler mais je pense qu'un autre avantage de Top down est que vous ne construirez que rarement la table de consultation / le cache. (c'est-à-dire que vous remplissez les valeurs là où vous en avez réellement besoin). Cela pourrait donc être un avantage en plus d'un codage facile. En d'autres termes, de haut en bas peut vous faire gagner du temps d'exécution réel puisque vous ne calculez pas tout (vous pourriez avoir un temps d'exécution considérablement meilleur mais le même temps d'exécution asymptotique cependant). Pourtant, il faut de la mémoire supplémentaire pour conserver les cadres de pile supplémentaires (encore une fois, la consommation de mémoire «peut» (seulement peut) doubler mais asymptotiquement, c'est la même chose.
Informé le
2
J'ai l'impression que les approches descendantes qui mettent en cache les solutions aux sous-problèmes qui se chevauchent sont une technique appelée mémorisation . Une technique ascendante qui remplit un tableau et évite également de recalculer les sous-problèmes qui se chevauchent est appelée tabulation . Ces techniques peuvent être utilisées lors de l'utilisation de la programmation dynamique , qui se réfère à la résolution de sous-problèmes pour résoudre un problème beaucoup plus important. Cela semble contradictoire avec cette réponse, où cette réponse utilise la programmation dynamique au lieu de la tabulation dans de nombreux endroits. Qui a raison?
Sammaron
1
@Sammaron: hmm, vous faites un bon point. J'aurais peut-être dû vérifier ma source sur Wikipedia, que je ne trouve pas. Après avoir vérifié un peu cstheory.stackexchange, je suis maintenant d'accord que "bottom-up" impliquerait que le bas est connu à l'avance (tabulation), et "top-down" est que vous supposez la solution aux sous-problèmes / sous-arbres. A l'époque, j'ai trouvé le terme ambigu, et j'ai interprété les phrases dans la double vue ("de bas en haut" vous supposez une solution aux sous-problèmes et mémorisez, "de haut en bas" vous savez de quels sous-problèmes vous êtes et pouvez tabuler). Je vais essayer de résoudre ce problème dans une modification.
ninjagecko
1
@mgiuffrida: l'espace de pile est parfois traité différemment selon le langage de programmation. Par exemple en python, essayer d'effectuer un fib récursif mémorisé échouera par exemple fib(513). La terminologie surchargée qui me semble gêne ici. 1) Vous pouvez toujours jeter les sous-problèmes dont vous n'avez plus besoin. 2) Vous pouvez toujours éviter de calculer les sous-problèmes dont vous n'avez pas besoin. 3) 1 et 2 peuvent être beaucoup plus difficiles à coder sans une structure de données explicite pour stocker les sous-problèmes, OU, plus difficile si le flux de contrôle doit tisser entre les appels de fonction (vous pourriez avoir besoin d'un état ou de continuations).
ninjagecko
76

DP de haut en bas et de bas en haut sont deux façons différentes de résoudre les mêmes problèmes. Considérons une solution de programmation mémorisée (de haut en bas) vs dynamique (de bas en haut) 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 (première recherche de réponse dans le cache et retournez-la si possible, sinon calculez-la récursivement puis avant de la retourner, vous enregistrez le calcul dans le cache pour une utilisation future), tout en faisant de bas en haut la programmation dynamique vous oblige à coder 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.

Rob Neuhaus
la source
1
Ah, maintenant je vois ce que signifient «de haut en bas» et «de bas en haut»; il ne s'agit en fait que de mémorisation vs DP. Et penser que c'est moi qui ai édité la question pour mentionner DP dans le titre ...
ninjagecko
quel est le temps d'exécution du fib récursif normal mémorisé?
Siddhartha
exponentiel (2 ^ n) pour le coz normal c'est un arbre de récursivité je pense.
Siddhartha
1
Ouais c'est linéaire! J'ai dessiné l'arbre de récursivité et j'ai vu quels appels pouvaient être évités et j'ai réalisé que les appels memo_fib (n - 2) seraient tous évités après le premier appel, et ainsi toutes les bonnes branches de l'arbre de récursivité seraient coupées et il va réduire à linéaire.
Siddhartha
1
Étant donné que DP implique essentiellement la création d'une table de résultats où chaque résultat est calculé au plus une fois, un moyen simple de visualiser l'exécution d'un algorithme DP est de voir la taille de la table. Dans ce cas, il est de taille n (un résultat par valeur d'entrée) donc O (n). Dans d'autres cas, il pourrait s'agir d'une matrice n ^ 2, résultant en O (n ^ 2), etc.
Johnson Wong
22

Une caractéristique clé de la programmation dynamique est la présence de sous-problèmes qui se chevauchent . Autrement dit, 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 conquérir", mais vous finissez par faire la même chose de 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 langue préférée et essayez de l'exécuter pour fib(50). Cela prendra très, très longtemps. À peu près autant de temps que fib(50)lui-même! Cependant, beaucoup de travail inutile est en cours. fib(50)appellera fib(49)et fib(48), mais 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 des sous-problèmes qui se chevauchent .

Bonne 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 le résultat en cache et la prochaine fois, utilisez la valeur mise en cache! C'est l'essence de la programmation dynamique. Vous pouvez l'appeler "de haut en bas", "mémorisation" ou tout ce que vous voulez. Cette approche est très intuitive et très simple à mettre en œuvre. Écrivez d'abord une solution récursive, testez-la sur de petits tests, ajoutez une mémorisation (mise en cache de valeurs déjà calculées), et --- bingo! --- vous avez terminé.

Habituellement, vous pouvez également écrire un programme itératif équivalent qui fonctionne de bas en haut, sans récursivité. Dans ce cas, ce serait 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 compris, vous aurez généralement une vue d'ensemble beaucoup plus claire du fonctionnement de l'algorithme. En pratique, lors de la résolution de 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. Écrivez une petite routine qui générerait de nombreux tests, idéalement - touspetits tests jusqu'à une certaine taille --- et valider que les deux solutions donnent le même résultat. Après cela, utilisez la solution ascendante en production, mais gardez le code de haut en bas, commenté. Cela permettra aux autres développeurs de comprendre plus facilement ce que vous faites: le code ascendant 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 pourrez peut-être pas écrire un test provoquant un débordement de pile si vous ne comprenez pas assez bien 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 des problèmes 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 temps raisonnable car votre entrée n'a besoin que d'une fraction des sous-problèmes pour être résolue --- mais il est trop difficile de définir explicitement, quels sous-problèmes vous devez résoudre, et donc d'écrire un fond- solution. D'un autre côté, il existe des situations où vous savez que vous devrez résoudre tous les sous-problèmes. Dans ce cas, continuez et utilisez de bas en haut.

Personnellement, j'utiliserais de haut en bas pour l'optimisation de paragraphe, c'est-à-dire le problème d'optimisation du wrapping Word (recherchez les algorithmes de rupture de ligne Knuth-Plass; au moins TeX l'utilise, et certains logiciels d'Adobe Systems utilisent une approche similaire). J'utiliserais de bas en haut pour la transformation de Fourier rapide .

osa
la source
Bonjour!!! Je veux déterminer si les propositions suivantes sont justes. - Pour un algorithme de Programmation Dynamique, le calcul de toutes les valeurs avec bottom-up est asymptotiquement plus rapide que l'utilisation de la récursion et de la mémorisation. - Le temps d'un algorithme dynamique est toujours Ο (Ρ) où Ρ est le nombre de sous-problèmes. - Chaque problème dans NP peut être résolu en temps exponentiel.
Mary Star
Que pourrais-je dire sur les propositions ci-dessus? Avez-vous une idée? @osa
Mary Star
@evinda, (1) est toujours faux. C'est soit le même soit asymptotiquement plus lent (lorsque vous n'avez pas besoin de tous les sous-problèmes, la récursivité peut être plus rapide). (2) n'est correct que si vous pouvez résoudre tous les sous-problèmes dans O (1). (3) est en quelque sorte juste. Chaque problème de NP peut être résolu en temps polynomial sur une machine non déterministe (comme un ordinateur quantique, qui peut faire plusieurs choses simultanément: avoir son gâteau, le manger simultanément, et tracer les deux résultats). Donc, dans un sens, chaque problème de NP peut être résolu en temps exponentiel sur un ordinateur ordinaire. Remarque: tout en P est également en NP. Par exemple, ajouter deux entiers
osa
19

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

En cas de cinq premiers numéros de fibonacci

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

Jetons maintenant un coup d'œil à l'algorithme de la série récursive de Fibonacci à titre d'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 examinons de près l'algorithme, pour générer un cinquième nombre, il faut des 3e et 4e nombres. Donc, ma récursivité commence en fait à partir du 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 précédemment calculée et la réutilisons. Cette technique s'appelle la mémorisation. Il y a plus à la programmation dynamique que la mémorisation qui n'est pas nécessaire pour discuter du 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 maximale.

De bas en haut

Mais, la question est, pouvons-nous commencer par le bas, comme à partir du premier numéro de fibonacci, puis marcher vers le haut. Réécrivons-le en utilisant ces techniques,

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 examinons cet algorithme, il commence en fait à partir de valeurs inférieures, puis va en haut. Si j'ai besoin du cinquième numéro de fibonacci, je calcule en fait le premier, puis le deuxième puis le troisième jusqu'au cinquième numéro. Ces techniques sont en fait appelées techniques ascendantes.

Deux derniers, les algorithmes remplissent les exigences de programmation dynamique. Mais l'un est descendant et un autre est ascendant. Les deux algorithmes ont une complexité spatiale et temporelle similaire.

minhaz
la source
Peut-on dire que l'approche ascendante est souvent mise en œuvre de manière non récursive?
Lewis Chan
Non, vous pouvez convertir n'importe quelle logique de boucle en récursivité
Ashvin Sharma
3

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

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, jusqu'au 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

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

  2. DP peut être beaucoup plus efficace car il est 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 survenir plusieurs fois et consommer plus de cycle CPU, augmentant ainsi la complexité du temps. Alors qu'en 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.

Farah Nazifa
la source
4
ce n'est pas vrai, la mémorisation utilise un cache qui vous aidera à économiser la complexité du temps au même titre que DP
Informé un
3

Le simple fait de dire que l'approche descendante utilise la récursivité pour appeler les problèmes Sub encore et encore,
alors que l'approche ascendante utilise le single sans appeler personne et donc c'est plus efficace.


la source
1

Voici la solution basée sur DP pour le problème d'édition de distance qui est de haut en bas. J'espère que cela aidera également à 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 à sa mise en œuvre récursive chez vous. C'est assez bon et stimulant si vous n'avez pas encore résolu quelque chose comme ça.

piyush121
la source
1

De haut en bas : garder une trace de la valeur calculée jusqu'à présent et renvoyer le résultat lorsque la condition de base est remplie.

int n = 5;
fibTopDown(1, 1, 2, n);

private int fibTopDown(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibTopDown(j, i + j, count + 1, n);
}

Bottom-Up : Le résultat actuel dépend du résultat de son sous-problème.

int n = 5;
fibBottomUp(n);

private int fibBottomUp(int n) {
    if (n <= 1) return 1;
    return fibBottomUp(n - 1) + fibBottomUp(n - 2);
}
Ashwin
la source