Bons exemples, articles, livres pour comprendre la programmation dynamique

Question

Je ne peux pas comprendre les principes de la programmation dynamique et vraiment, je ne le souhaitez. DP est très puissant, il peut résoudre ce type de problèmes:

D'obtenir le plus bas possible de la somme de nombres différence

Donc, pouvez-vous me suggérer de bons livres ou d'articles (de préférence avec des exemples de code réel) qui pourrait m'expliquer ce qu'est la programmation dynamique? J'ai vraiment envie d'exemples simples d'abord, puis je vais passer à autre chose.

Answer 1

La programmation dynamique est une catégorie utile de l'algorithme qui peut être utilisé pour optimiser des problèmes difficiles par les diviser en plus petits sous-problèmes. Par le stockage et la réutilisation des solutions partielles, il parvient à éviter les pièges de l'utilisation d'un algorithme glouton. Il existe deux types de programmation dynamique, bottom-up et top-down.

Pour un problème résoluble à l'aide de la programmation dynamique, le problème doit posséder la propriété de ce qui est appelé un sous-structure optimale. Cela signifie que, si le problème a été divisé en une série de sous-problèmes et la solution optimale pour chaque subproblem a été trouvé, la solution pourrait être réalisé grâce à la solution de ces sous-problèmes. Un problème qui n'a pas cette structure ne peut pas être résolu par programmation dynamique.

De Haut En Bas

De haut en bas est mieux connu sous le nom memoization. C'est l'idée de stocker des dernières calculs afin d'éviter de re-calcul à chaque fois.

Étant donné une fonction récursive, dire:

fib(n) = 0 if n = 0
         1 if n = 1
         fib(n - 1) + fib(n - 2) if n >= 2

On peut facilement écrire de cette manière récursive à partir de sa mathématiques formulaire comme:

function fib(n)
  if(n == 0 || n == 1)
    n
  else
    fib(n-1) + fib(n-2)

Désormais, toute personne qui a été de programmation pour un certain temps ou qui sait une chose ou deux au sujet de l'efficacité algorithmique vous diront que c'est une idée terrible. La raison en est que, à chaque étape, vous devez re-calculer la valeur de la fib(i), où i est 2..n-2.

Plus efficace exemple de ceci est le stockage de ces valeurs, la création d'un top-down algorithme de programmation dynamique.

m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
  if(m[n] does not exist)
    m[n] = fib(n-1) + fib(n-2)

En faisant cela, nous calculons fib(i) au plus une fois.

---

Bottom-Up

Bottom-up utilise la même technique de memoization qui est utilisé dans de haut en bas. La différence, cependant, est que bottom-up utilise comparative des sous-problèmes connus sous le nom de récidives pour optimiser votre résultat final.

Dans la plupart des bas-dynamique des problèmes de programmation, vous êtes souvent essayer de les minimiser ou maximiser une décision. Vous avez droit à deux (ou plus) des options à tout moment et vous aurez à décider qui est le plus optimal pour le problème que vous essayez de résoudre. Ces décisions sont basées sur les choix que vous faites.

En faisant le plus de décision optimale à chaque point (chaque subproblem), vous vous assurer que votre résultat global est la plus optimale.

La partie la plus difficile de ces problèmes est de trouver les relations de récurrence pour la résolution de votre problème.

Payer pour un tas d'algorithme de manuels scolaires, vous envisagez de voler un magasin qui contient n éléments. Le problème, c'est que votre minuscule sac à dos ne peut contenir au plus W kg. Connaissant le poids (w[i]) et la valeur (v[i]) de chaque élément, vous voulez maximiser la valeur de vos biens volés qui, dans l'ensemble de poids à la plupart des W. Pour chaque élément, vous devez faire un choix binaire - à prendre ou à laisser.

Maintenant, vous devez trouver ce que le subproblem est. Très lumineux voleur, vous vous rendez compte que la valeur maximale d'un élément donné, j'ai, avec un maximum de poids, w, peut être représentée de la m[i, w]. En outre, m[0, w] (0 articles à la plupart des poids w) et m[i, 0] (je les éléments avec 0 poids max.) sera toujours égale à la valeur 0.

donc,

m[i, w] = 0 if i = 0 or w = 0

Avec votre façon de penser masque facial sur, vous remarquerez que si vous avez rempli votre sac avec autant de poids que vous le pouvez, un nouvel élément ne peut pas être prise en considération que si son poids est inférieur ou égal à la différence entre le max de poids et le poids actuel du sac. Un autre cas où vous pourriez envisager un élément est de savoir si elle est inférieure ou égale à la masse d'un élément dans le sac, mais encore plus de valeur.

 m[i, w] = 0 if i = 0 or w = 0
           m[i - 1, w] if w[i] > w
           max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w

Ce sont les relations de récurrence décrit ci-dessus. Une fois que vous avez ces relations, l'écriture de l'algorithme est très facile (et court!).

v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack

m[n, n] = array(int, int)
function knapsack
  for w=0..W
    m[0, w] = 0
  for i=1 to n
    m[i, 0] = 0
    for w=1..W
      if w[i] <= w
        if v[i] + m[i-1, w - w[i]] > m[i-1, w]
           m[i, w] = v[i] + m[i-1, w - w[i]]
        else
           m[i, w] = m[i-1, w]
      else
        m[i, w] = c[i-1, w]

  return m[n, n]

---

Des Ressources Supplémentaires

1. Introduction aux Algorithmes
2. Des Défis De Programmation
3. La Conception D'Un Algorithme Manuel

---

Exemple De Problèmes

Heureusement, la programmation dynamique est devenu vraiment dans quand il s'agit de la concurrence de la programmation. Découvrez la Programmation Dynamique sur UVAJudge pour une certaine pratique de problèmes qui permettra de tester votre capacité à mettre en œuvre et de trouver des récidives pour les problèmes de programmation dynamique.

Answer 2

En bref, la Programmation Dynamique est une méthode pour résoudre des problèmes complexes en les décomposant dans le plus simple des étapes, qui est, en passant par la résolution d'un problème étape par étape.

1. La programmation dynamique;
2. Introduction à la Programmation Dynamique;
3. MIT Introduction aux Algorithmes, des Conférences, 15: Programmation Dynamique;
4. La Conception d'un algorithme (livre).

J'espère que ce lien va aider au moins un peu.

Answer 3

Voir ci-dessous

• http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

et il y a trop d'échantillons et articles de référence à l'article ci-dessus.

Après l'apprentissage de la programmation dynamique, vous pouvez améliorer vos compétences en résolution de rayons UVA problèmes, Il existe des listes de certains rayons UVA dynamique des problèmes de programmation dans le forum de discussion des rayons UVA

Également Wiki a un bon de simples échantillons pour elle.

Edit: pour réserver algorithme à ce sujet, vous pouvez utiliser:

• Python Algorithmes: Maîtrise Des Bases De La Algorithmes en Langage Python: Dans ce livre, vous pouvez voir le travail pratique avec DP.
• Introduction aux Algorithmes: Le plus simple possible de décrire des algorithmes de faire dans ce livre.

Aussi, vous devriez jeter un oeil à Memoization de la programmation dynamique.

Answer 4

Je pense Algébrique De La Programmation Dynamique la peine de mentionner. C'est très inspirant de la présentation de DP technique et est largement utilisé dans la communauté bio-informatique. Aussi, le Groom du principe de l'optimalité indiqué dans très manière compréhensible.

Traditionnellement, le DP est enseigné par l'exemple: les algorithmes sont exprimés dans des termes les récurrences entre les entrées de la table qui stockent des solutions intermédiaires problèmes, à partir de ce tableau, la solution globale est construite via certains cas l'analyse.

ADP organise DP algorithme tel que le problème de la décomposition en sous-problèmes et l'analyse de cas sont complètement séparées de la destinée de l'optimisation objectif. Cela permet de réutiliser et de combiner les différentes parties de DP algorithmes pour des problèmes similaires.

Il y a trois faiblement couplé pièces en ADP algorithme:

• construction de l'espace de recherche (ce qui est indiqué dans les termes de l'arbre grammaires);
• la notation de chaque élément de l'espace de recherche;
• objectif de la fonction en sélectionnant les éléments de l'espace de recherche, qui nous intéresse.

Toutes ces pièces alors automatiquement fusionnés rendement algorithme efficace.