Qu'est-ce que la programmation dynamique?

Question

Qu'est-ce que la programmation dynamique?

Qu'est-ce que programmation dynamique ?

en quoi cela diffère-t-il de la récursion, de la mémoization, etc.?

j'ai lu l'article wikipedia dessus, mais je ne le comprends toujours pas vraiment.

226

algorithm dynamic-programming

demandé sur nbro 2009-06-30 23:10:24

11 réponses

score 172 · Answer 1

la programmation dynamique est quand vous utilisez les connaissances passées pour rendre la résolution d'un problème futur plus facile.

un bon exemple est la résolution de la séquence de Fibonacci pour n=1.000.002.

ce sera un processus très long, mais que faire si je vous donne les résultats pour n=1.000.000 et n=1.000.001? Soudain, le problème est devenu plus gérable.

la programmation dynamique est beaucoup utilisée dans les problèmes de chaîne, comme le problème d'édition de chaîne. Vous résolvez un ou plusieurs sous-ensembles du problème, puis utilisez cette information pour résoudre le problème initial plus difficile.

avec la programmation dynamique, vous stockez vos résultats dans une sorte de tableau en général. Quand vous avez besoin de la réponse à un problème, vous faites référence au tableau et voyez si vous savez déjà ce que c'est. Si non, vous utilisez les données de votre table pour vous donner un tremplin vers la réponse.

Le Livre D'algorithmes Cormen a un grand chapitre sur la programmation dynamique. Et C'est gratuit sur Google Books! Regardez ici.

score 122 · Answer 2

la programmation dynamique est une technique utilisée pour éviter de calculer plusieurs fois le même sous-problème dans un algorithme récursif.

prenons l'exemple simple des nombres de fibonacci: trouver le N ^th nombre de fibonacci défini par

F _n = F _n-1 + F _n-2 et F ₀ = 0, F ₁ = 1

récursion

la façon évidente de faire ceci est récursive:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Programmation Dynamique

De Haut En Bas - Memoization

la récursion fait beaucoup de calculs inutiles parce qu'un nombre de fibonacci donné sera calculé plusieurs fois. Un moyen facile d'améliorer ceci est de mettre en cache les résultats:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

Bottom-Up

une meilleure façon de faire ceci est de se débarrasser de la récursion tout-ensemble en évaluant les résultats dans le bon ordre:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

nous pouvons même utiliser l'espace constant et stocker seulement les résultats partiels nécessaires le long du chemin:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

Comment appliquer la programmation dynamique?
1. trouvez la récursion dans le problème.
2. top-down: stockez la réponse pour chaque sous-problème dans une table pour éviter d'avoir à les recalculer.
3. Bottom-up: trouver le bon ordre pour évaluer les résultats afin que des résultats partiels soient disponibles au besoin.

la programmation dynamique fonctionne généralement pour les problèmes qui ont un ordre inhérent de gauche à droite tels sous forme de chaînes, d'arbres ou de séquences entières. Si l'algorithme récursif naïf ne calcule pas le même sous-problème plusieurs fois, la programmation dynamique n'aidera pas.

j'ai fait une série de problèmes pour aider à comprendre la logique: https://github.com/tristanguigue/dynamic-programing

score 58 · Answer 3

Ici est mon answe r dans des sujets similaires

commence par

article de wikipedia sur programmation dynamique puis
je vous suggère de lire cet article dans topcoder
ch6 sur la programmation dynamique dans les algorithmes (Vazirani)
programmation dynamique chapitre du manuel de conception des algorithmes
chapitre de programmation dynamique dans le livre d'algorithmes classique ( Introduction aux algorithmes )

Si vous voulez tester vous-même mon choix en ligne juges sont

et bien sûr

regardez algorithmist programmation dynamique catégorie

, Vous pouvez aussi les vérifications de bonnes universités algorithmes de cours

après tout, si vous ne pouvez pas résoudre les problèmes Demander afin que de nombreux algorithmes addict existent ici

score 33 · Answer 4

Memoization est le moment où vous stockez les résultats précédents d'un appel de fonction (une fonction réelle retourne toujours la même chose, avec les mêmes entrées). Cela ne fait pas de différence pour la complexité algorithmique avant que les résultats soient stockés.

récursion est la méthode d'une fonction qui s'appelle elle-même, généralement avec un plus petit ensemble de données. Comme la plupart des fonctions récursives peuvent être converties en fonctions itératives similaires, cela ne fait pas de différence pour la complexité algorithmique soit.

la programmation dynamique est le processus de résolution de sous-problèmes plus faciles à résoudre et de construire la réponse à partir de cela. La plupart des algorithmes DP seront dans les temps d'exécution entre un algorithme gourmand (s'il en existe un) et un algorithme exponentiel (énumérer toutes les possibilités et trouver le meilleur).

les algorithmes DP peuvent être mis en œuvre avec récursion, mais ils ne doivent pas l'être.
les algorithmes DP ne peuvent pas être accélérés par memoization, puisque chaque sous-problème n'est résolu qu'une seule fois (ou la fonction "résoudre" appelée).

score 17 · Answer 5

c'est une optimisation de votre algorithme qui réduit le temps d'exécution.

alors qu'un algorithme cupide est généralement appelé naïf , parce qu'il peut courir plusieurs fois sur le même ensemble de données, la programmation dynamique évite cet écueil par une compréhension plus approfondie des résultats partiels qui doivent être stockés pour aider à construire la solution finale.

Un exemple simple est de traverser un arbre ou un graphe seulement à travers les nœuds qui serait contribuez avec la solution, ou mettez dans une table les solutions que vous avez trouvées jusqu'à présent de sorte que vous pouvez éviter de traverser les mêmes noeuds encore et encore.

voici un exemple de problème adapté à la programmation dynamique, tiré de uva's online judge: Edit Steps Ladder.

je vais faire un briefing rapide de la partie importante de l'analyse de ce problème, pris du Livre De La programmation des défis, je vous suggère de vérifier hors.

regardez bien ce problème, si nous définissons une fonction de coût à nous dire dans quelle mesure l'appart deux chaînes sont, nous deux considérons les trois naturel types de modifications:

Substitution-changer un seul caractère du modèle "s" à un le caractère différent dans le texte "t", tel que comme changer "shot" en"spot".

Insertion-insérer un seul caractère dans le modèle "s" pour l'aider à correspondre texte "t", comme changer" ago "en"agog".

suppression-supprimer un seul caractère de modèle "s" pour l'aider à comparer le texte "t", comme changer" heure "en"notre".

quand nous définissons chacune de ces opérations à le coût d'une étape, nous définissons les modifier la distance entre deux chaînes de caractères. Alors, comment ne nous le calculer?

Nous pouvons définir un algorithme récursif en utilisant l'observation que le dernier caractère de la chaîne doit être soit apparié, substitué, inséré ou supprimer. Hacher hors les personnages dans la dernière opération d'édition laisse un paire opération laisse une paire de les petites chaînes. Que j Et moi soyons dernier caractère du préfixe correspondant de et t, respectivement. il y a trois paires de cordes plus courtes après la dernière opération, correspondant à la chaîne après une correspondance / substitution, insertion ou suppression. Si nous savions que le coût d'édition des trois paires de les petites chaînes, on pourrait décider qui option mène à la meilleure solution et choisissez cette option en conséquence. Nous pouvons apprendre ce coût, à travers le impressionnant chose qui est récursion:

      #define MATCH 0 /* enumerated type symbol for match */
>     #define INSERT 1 /* enumerated type symbol for insert */
>     #define DELETE 2 /* enumerated type symbol for delete */
>     
> 
>     int string_compare(char *s, char *t, int i, int j)
>     
>     {
> 
>     int k; /* counter */
>     int opt[3]; /* cost of the three options */
>     int lowest_cost; /* lowest cost */
>     if (i == 0) return(j * indel(’ ’));
>     if (j == 0) return(i * indel(’ ’));
>     opt[MATCH] = string_compare(s,t,i-1,j-1) +
>       match(s[i],t[j]);
>     opt[INSERT] = string_compare(s,t,i,j-1) +
>       indel(t[j]);
>     opt[DELETE] = string_compare(s,t,i-1,j) +
>       indel(s[i]);
>     lowest_cost = opt[MATCH];
>     for (k=INSERT; k<=DELETE; k++)
>     if (opt[k] < lowest_cost) lowest_cost = opt[k];
>     return( lowest_cost );
> 
>     }

Cet algorithme est correct, mais il est aussi incroyablement lent.

tournant sur notre ordinateur, il faut plusieurs secondes pour comparer deux 11-les chaînes de caractères, et l' calcul disparaît dans jamais-jamais sur terre quelque chose de plus long.

Pourquoi l'algorithme si lent? Il faut le temps exponentiel parce qu'il recompute des valeurs encore et encore et encore. À chaque position dans la chaîne, le la récursion se divise en trois branches, ce qui signifie il croît à un taux d'au moins 3^n – en effet, même plus rapide que la plupart des les appels réduisent seulement un des deux les indices, pas deux.

alors comment pouvons-nous faire l'algorithme la pratique? l'important observation est que la plupart de ces appels récursifs calculent des choses qui ont déjà été calculées à l'avant. Comment faire savez? Eh bien, il ne peut y avoir que |s| · | t / appels récursifs uniques possibles, comme il ya seulement que de nombreux distinctes (i, j) paires de servir paramètres des appels récursifs.

en stockant les valeurs pour chacune de ces paires (I, j) dans une table, nous pouvons évitez de les recalculer et regardez comme nécessaire.

le tableau est une matrice bidimensionnelle m où chacune des cellules |s|·|t| contient le coût de l'utilisation optimale solution de ce sous-problème, ainsi que comme un indicateur de parent expliquant comment nous arrivé à cet endroit:
    typedef struct {
    int cost; /* cost of reaching this cell */
    int parent; /* parent cell */
    } cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */
la version de programmation dynamique a trois différences par rapport à l'récursive version.

premier, il obtient ses valeurs intermédiaires utiliser la recherche de table au lieu de les appels récursifs.

* * Second,**il met à jour le champ parent de chaque cellule, ce qui nous permettra de reconstruire la séquence d'édition plus tard.

****en Troisième lieu, il est instrumenté à l'aide d'un objectif plus général de la cellule() fonction au lieu de simplement retourner m [|s|] [|t/].coût. Cela nous permettra pour appliquer cette routine à une catégorie plus large de problèmes.

Ici, un très particulier l'analyse de ce qu'il faut pour obtenir les résultats partiels les plus optimaux, est ce qui fait de la solution une solution "dynamique".

Voici une solution de rechange complète au même problème. C'est aussi une "dynamique", même si son exécution est différente. Je vous suggère de vérifier l'efficacité de la solution en la soumettant au juge en ligne de L'UVA. Je trouve incroyable la façon dont un problème aussi lourd a été abordé si efficacement.

score 9 · Answer 6

les éléments clés de la programmation dynamique sont les" sous-problèmes qui se chevauchent "et l' "infrastructure optimale". Ces propriétés d'un problème qu'une solution optimale est composée de solutions optimales à ses sous-problèmes. Par exemple, les problèmes de chemin le plus court présentent une structure optimale. Le chemin le plus court de A à C est le chemin le plus court de A à un noeud B suivi du chemin le plus court de ce noeud B à C.

plus en détail, pour résoudre un problème de chemin le plus court vous serez:

trouvez les distances entre le noeud de départ et chaque noeud le touchant (disons de A à B et C)
trouver les distances entre ces noeuds et les noeuds les touchant (de B à D et E, et de C à E et F)
nous connaissons maintenant le chemin le plus court de A à E: c'est la somme la plus courte de A-x et x-E pour un noeud x que nous avons visité (soit B ou c)
répétez ce processus jusqu'à ce que nous atteignions le nœud de destination finale

parce que nous travaillons de bas en haut, nous avons déjà des solutions aux sous-problèmes quand vient le temps de les utiliser, en les mémoizant.

rappelez-vous que les problèmes de programmation dynamique doivent comporter à la fois des sous-problèmes qui se chevauchent et une sous-structure optimale. La génération de la séquence de Fibonacci n'est pas un problème de programmation dynamique; elle utilise la mémorisation parce qu'elle a des sous-problèmes qui se chevauchent, mais elle n'a pas d'optimum. sous-structure (parce qu'il n'y a pas de problème d'optimisation).

score 5 · Answer 7

Programmation Dynamique

définition

programmation dynamique (DP) est une technique générale de conception d'algorithme pour résoudre problèmes de chevauchement des sous-problèmes. Cette technique a été inventée par American mathématicien "Richard Bellman" dans les années 1950.

Idée-Clé

l'idée clé est de sauvegarder les réponses de plus petites se chevauchant les sous-problèmes à éviter recalcul.

Propriétés De Programmation Dynamique

une instance est résolue en utilisant les solutions pour les instances plus petites.
les solutions pour une instance plus petite pourraient être nécessaires plusieurs fois, afin de stocker leurs résultats dans un tableau.
ainsi, chaque instance plus petite n'est résolue qu'une seule fois.
espace supplémentaire est utilisé pour enregistrer temps.

score 4 · Answer 8

voici un tutoriel de Michael A. Trick de CMU que j'ai trouvé particulièrement utile:

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

il est certainement en plus de toutes les ressources autres ont recommandé (toutes les autres ressources, spécialement CLR et Kleinberg,Tardos sont très bons!).

la raison pour laquelle j'aime ce tutoriel est qu'il introduit des concepts avancés assez progressivement. Il est peu un peu vieux matériel, mais c'est un bon ajout à la liste de ressources présentées ici.

aussi consulter la page de Steven Skiena et des conférences sur la programmation dynamique: http://www.cs.sunysb.edu / ~algorithith / video-lectures/

http://www.cs.sunysb.edu / ~algorithh / video-lectures / 1997 / lecture12.pdf

score 3 · Answer 9

Je suis également très nouveau à la programmation dynamique (un algorithme puissant pour des types particuliers de problèmes)

dans les mots les plus simples, il suffit de penser programmation dynamique comme une approche récursive avec l'utilisation de la connaissance antérieure

connaissance antérieure est ce qui importe le plus ici, garder une trace de la solution des sous-problèmes que vous avez déjà.

considérez ceci, la plupart exemple de base pour dp de Wikipedia

trouver la séquence de fibonacci

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

permet de décomposer l'appel de fonction avec say n =5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

en particulier, fib(2) a été calculé trois fois à partir de zéro. Dans les exemples plus larges, beaucoup plus de valeurs de fib, ou de sous-problèmes, sont recalculées, conduisant à un algorithme de temps exponentiel.

maintenant, essayons en stockant la valeur que nous avons déjà trouvée dans une structure de données disent un carte

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

ici nous sauvons la solution des sous-problèmes dans la carte, si nous ne l'avons pas déjà. Cette technique d'économie des valeurs que nous avions déjà calculées est appelée Memoization.

enfin, Pour un problème, essayez d'abord de trouver les états (sous-problèmes et essayer de penser à la meilleure récursivité approche de sorte que vous pouvez utiliser la solution du sous-problème en d'autres).

score 1 · Answer 10

, bref, à la différence entre la récursivité memoization et de la programmation Dynamique

la programmation dynamique comme son nom l'indique utilise la valeur calculée précédente pour construire dynamiquement la nouvelle solution suivante

où appliquer la programmation dynamique : si votre solution est basée sur la sous-structure optimale et le chevauchement de sous-problèmes, alors dans ce cas, en utilisant la valeur calculée plus tôt sera utile de sorte que vous n'avez pas à la recalculer. Il est une approche "ascendante". Supposons que vous devez calculer fib (n) dans ce cas, tout ce que vous devez faire est d'ajouter la valeur calculée précédente de fib(n-1) et fib(n-2)

récursion: essentiellement subdiviser votre problème en une plus petite partie pour le résoudre facilement, mais gardez à l'esprit qu'il n'évite pas de recalcul si nous avons la même valeur calculée précédemment dans un autre appel de récursion.

Memoization: essentiellement le stockage de l'ancienne valeur de récursion calculée dans la table est connu comme memoization qui évitera le re-calcul si elle a déjà été calculée par un appel précédent ainsi n'importe quelle valeur sera calculée une fois. Donc, avant de calculer nous vérifions si cette valeur a déjà été calculée ou non si déjà calculé, puis nous retournons la même de table au lieu de recalculer. Il est également l'approche top down

score -1 · Answer 11

voici un exemple simple de code python Recursive , Top-down , Bottom-up approche pour la série fibonacci:

Recursive: O (2^n)

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

de Haut en bas: O(n) Efficace pour les plus grandes d'entrée

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Bottom-up: O(n) Pour des raisons de simplicité et de faible apport tailles

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))

Las etiquetas más populares

Qu'est-ce que la programmation dynamique?

11 réponses

récursion

Programmation Dynamique

Recursive: O (2^n)

de Haut en bas: O(n) Efficace pour les plus grandes d'entrée

Bottom-up: O(n) Pour des raisons de simplicité et de faible apport tailles