la différence entre le suivi et la programmation Dynamique
J'ai entendu la seule différence entre la dynamique de programmation et de suivi est DP permet le chevauchement des sous-problèmes. (fib(n) = fib(n-1)+ fib (n-2)). Est-il juste ? Existe-il d'autres différences ? Aussi, je voudrais savoir quelques problèmes communs résolu à l'aide de ces techniques.
Vous devez vous connecter pour publier un commentaire.
Il existe deux implémentations typiques de la Programmation Dynamique d'approche: de bas en haut et de haut en bas.
De haut en bas de la Programmation Dynamique n'est rien d'autre qu'à l'ordinaire la récursivité, renforcée avec de la mémorisation de la solutions pour les sous-problèmes. Quand un sous-problème se pose de la deuxième (troisième, quatrième...), il n'est pas résolu à partir de zéro, mais plutôt précédemment mémorisé solution est utilisée tout de suite. Cette technique est connue sous le nom de memoization (pas de 'r' avant 'i').
C'est effectivement ce que votre exemple avec la suite de Fibonacci est censé illustrer. Suffit d'utiliser la formule récursive pour la suite de Fibonacci, mais de construire la table de
fib(i)valeurs le long du chemin, et vous obtenez un Haut-de-bas DP algorithme pour résoudre ce problème (de sorte que, par exemple, si vous avez besoin de calculerfib(5)deuxième temps, vous l'obtenez à partir de la table au lieu de calculer à nouveau).Dans de Bas en haut de la Programmation Dynamique l'approche est également basé sur le stockage de sous-solutions en mémoire, mais ils sont résolus dans un ordre différent (de la plus petite à la plus grande), et la résultante de la structure générale de l'algorithme n'est pas récursive. LCS algorithme est un classique de Bas en haut DP exemple.
De bas en haut DP algorithmes sont généralement plus efficaces, mais ils sont généralement plus difficile (voire impossible) à construire, car il n'est pas toujours facile de prédire ce qui primitif sous-problèmes, vous allez avoir besoin de résoudre l'ensemble du problème original, et le chemin d'accès que vous avez à prendre de petits sous-problèmes pour arriver à la solution finale de la façon la plus efficace.
Les problèmes de dynamique exige également "sous-structure optimale".
Selon Wikipedia:
Pour une discussion détaillée de "sous-structure optimale", veuillez lire le PLC livre.
Problèmes communs pour les retours en arrière, je peux penser sont:
DP problèmes:
DP permet de résoudre un grand, de calcul intensif problème en le décomposant en sous-problèmes dont la solution ne nécessite que la connaissance de l'immédiat avant la solution. Vous obtiendrez une très bonne idée de ramasser Needleman-Wunsch et la résolution d'un échantillon, car il est si facile de voir l'application.
Retour en arrière semble être plus compliqué, d'où la solution de l'arbre est élagué est, il est connu qu'un chemin d'accès spécifique ne sera pas d'obtenir un résultat optimal.
Donc on pourrait dire que les retours en arrière optimise pour mémoire, depuis DP suppose que tous les calculs sont effectués et ensuite l'algorithme remonte pas à pas dans le coût le plus bas nœuds.
Une différence pourrait être que la programmation Dynamique problèmes comptent habituellement sur le principe de l'optimalité. Le principe de l'optimalité stipule qu'une séquence optimale de la décision ou de choix de chaque sous-séquence doit également être optimale.
Mandature problèmes ne sont généralement PAS optimale sur leur chemin! Ils ne peuvent être appliqués à des problèmes qui admettent le concept de partielle candidat de la solution.
Profondeur de premier nœud de la génération de l'espace d'état de l'arbre avec cadre fonction est appelée mandature. Ici, le nœud courant est dépendante sur le nœud qui les a générés.
Profondeur de premier nœud de la génération de l'espace d'état de l'arbre avec de la mémoire fonction est appelée de haut en bas de la programmation dynamique. Ici, le nœud courant est personne à charge sur le nœud qu'il génère.
Dans un très simple phrase que je peux dire: de la programmation Dynamique est une stratégie pour résoudre les problème d'optimisation. problème d'optimisation est sur le minimum ou le maximum de résultat (un seul résultat). mais, Mandature nous utilisons l'approche par force brute, pas de problème d'optimisation. c'est pour quand vous avez de nombreux résultats et vous voulez que tous ou de certains d'entre eux.