De quoi parle la programmation dynamique?

33

Désolé à l'avance si cette question vous semble stupide ...

Pour autant que je sache, la construction d'un algorithme utilisant la programmation dynamique fonctionne de cette façon:

  1. exprimer le problème comme une relation de récurrence;
  2. mettre en œuvre la relation de récurrence soit par mémorisation, soit par une approche ascendante.

Pour autant que je sache, j'ai tout dit sur la programmation dynamique. Je veux dire: la programmation dynamique ne donne pas d'outils / règles / méthodes / théorèmes pour exprimer des relations de récurrence, ni pour les transformer en code.

Alors, quelle est la particularité de la programmation dynamique? Qu'est-ce que cela vous apporte, à part une méthode vague pour aborder un certain type de problèmes?

hé hé
la source
11
Factoid historique (ce commentaire ne vous aidera pas, mais Bellman est en fait une bonne piste si vous voulez approfondir la théorie sur la programmation dynamique): quand Bellman est venu avec ce qui est maintenant connu sous le nom de programmation dynamique, il a appelé l'idée "programmation dynamique "Parce que le travail purement théorique ne volait pas avec son employeur à ce moment-là, il avait donc besoin de quelque chose de plus à la mode qui ne pouvait pas être utilisé de manière péjorative .
G. Bach
3
Autant que je sache, ce sont exactement ces deux points que vous mentionnez. Il devient spécial lorsqu'il évite une explosion exponentielle en raison de chevauchements de sous-problèmes. C'est tout. Ah, au fait, mon professeur préfère le "paradigme algorithmique" à la "méthode vague".
Hendrik Jan
La «programmation dynamique» semble être principalement un mot à la mode (qui a depuis perdu son buzz). Cela ne veut pas dire que ce n'est pas utile bien sûr.
user253751
3
Pas digne d'une réponse, mais pour moi, la programmation dynamique est certainement "cette chose que vous utilisez lorsque vous essayez de résoudre un problème récursivement, mais vous finissez par perdre du temps à revoir les mêmes sous-problèmes encore et encore."
hobbs
@hobbs: Exactement, mais l'habileté est de trouver cette façon initiale de perdre du temps;)
j_random_hacker

Réponses:

27

La programmation dynamique vous permet de penser à la conception d'algorithmes. C'est souvent très utile.

La mémorisation et les méthodes ascendantes vous donnent une règle / méthode pour transformer les relations de récurrence en code. La mémorisation est une idée relativement simple, mais les meilleures idées le sont souvent!

La programmation dynamique vous donne une façon structurée de penser au temps d'exécution de votre algorithme. Le temps d'exécution est essentiellement déterminé par deux nombres: le nombre de sous-problèmes que vous devez résoudre et le temps qu'il faut pour résoudre chaque sous-problème. Cela fournit un moyen simple et pratique de réfléchir au problème de conception de l'algorithme. Lorsque vous avez une relation de récurrence candidate, vous pouvez l'examiner et obtenir très rapidement une idée de la durée d'exécution (par exemple, vous pouvez souvent dire très rapidement combien de sous-problèmes il y aura, ce qui est une limite inférieure de la temps d'exécution; s'il y a de façon exponentielle de nombreux sous-problèmes que vous devez résoudre, la récurrence ne sera probablement pas une bonne approche). Cela vous aide également à exclure les décompositions de sous-problèmes potentiels. Par exemple, si nous avons une chaîne , définissant un sous-problème par un préfixe S [ 1 .. i ] ou un suffixe S [ j . . n ] ou sous-chaîne S [ i . . j ] pourrait être raisonnable (le nombre de sous-problèmes est polynomial en n ), mais définir un sous-problème par une sous-séquence de S n'est probablement pas une bonne approche (le nombre de sous-problèmes est exponentiel en n ). Cela vous permet d'élaguer "l'espace de recherche" des récidives possibles.S[1..n]S[1..je]S[j..n]S[je..j]nSn

La programmation dynamique vous offre une approche structurée pour rechercher des relations de récurrence candidates. Empiriquement, cette approche est souvent efficace. En particulier, il existe des modèles heuristiques / communs que vous pouvez reconnaître pour des manières courantes de définir des sous-problèmes, selon le type d'entrée. Par exemple:

  • Si l'entrée est un entier positif , une façon possible de définir un sous-problème consiste à remplacer n par un entier plus petit n (st 0 n n ).nnn0nn

  • Si l'entrée est une chaîne , certaines façons possibles de définir un sous-problème incluent: remplacer S [ 1 .. n ] par un préfixe S [ 1 .. i ] ; remplacerS[1..n]S[1..n]S[1..je] par un suffixe S [ j . . n ] ; remplacer S [ 1 .. n ] par une sous-chaîne S [ i . . j ]S[1..n]S[j..n]S[1..n]S[je..j]. (Ici, le sous-problème est déterminé par le choix de .)je,j

  • Si l'entrée est une liste , faites la même chose que pour une chaîne.

  • Si l'entrée est un arbre , une façon possible de définir un sous-problème consiste à remplacer T par n'importe quel sous-arbre de T (c'est-à-dire, choisir un nœud x et remplacer T par le sous-arbre enraciné en x ; le sous-problème est déterminé par le choix de x ).TTTXTXX

  • Si l'entrée est une paire , examinez récursivement le type de x et le type de y pour identifier une façon de choisir un sous-problème pour chacun. En d'autres termes, une façon possible de définir un sous-problème est de remplacer ( x , y ) par ( x(X,y)Xy(X,y) x est un sous-problème pour x et y est un sous-problème pour y . (Vous pouvez également considérer les sous-problèmes du formulaire ( x , y(X,y)XXyy Ou ( x , y ) .)(X,y)(X,y)

Etc. Cela vous donne une heuristique très utile: juste en regardant la signature de type de la méthode, vous pouvez trouver une liste de façons possibles de définir des sous-problèmes. En d'autres termes, juste en regardant l'énoncé du problème - en ne regardant que les types d'entrées - vous pouvez trouver une poignée de façons possibles de définir un sous-problème.

C'est souvent très utile. Il ne vous dit pas quelle est la relation de récurrence, mais lorsque vous avez un choix particulier pour définir le sous-problème, il n'est souvent pas trop difficile de trouver une relation de récurrence correspondante. Ainsi, cela transforme souvent la conception d'un algorithme de programmation dynamique en une expérience structurée. Vous écrivez sur du papier brouillon une liste de façons possibles de définir les sous-problèmes (en utilisant l'heuristique ci-dessus). Ensuite, pour chaque candidat, vous essayez d'écrire une relation de récurrence et d'évaluer son temps d'exécution en comptant le nombre de sous-problèmes et le temps passé par sous-problème. Après avoir essayé chaque candidat, vous gardez le meilleur que vous ayez pu trouver. Fournir une certaine structure au processus de conception de l'algorithme est une aide majeure, car sinon la conception de l'algorithme peut être intimidante (il '

DW
la source
Vous confirmez donc que la programmation dynamique ne fournit pas de "procédures" concrètes à suivre. C'est juste "une façon de penser", comme vous l'avez dit. Notez que je ne dis pas que le DP est inutile (au contraire!), J'essaie juste de comprendre s'il y a quelque chose qui me manque ou si je devrais simplement pratiquer plus.
hey hey
@heyhey, eh bien, oui ... et non. Voir ma réponse révisée pour plus de détails. Ce n'est pas une solution miracle, mais elle fournit des procédures semi-concrètes qui sont souvent utiles (pas garanties de fonctionner, mais s'avèrent souvent utiles).
DW
Merci beaucoup! En pratiquant, je me familiarise de plus en plus avec certaines de ces «procédures semi-concrètes» que vous décrivez.
hey hey
"S'il y a de façon exponentielle de nombreux sous-problèmes à résoudre, alors la récurrence ne sera probablement pas une bonne approche". Pour de nombreux problèmes, il n'y a pas d'algorithme de temps polynomial connu. Pourquoi cela devrait-il être un critère pour utiliser DP?
Chiel ten Brinke
@Chiel, ce n'est pas un critère pour utiliser DP. Si vous avez un problème où vous seriez satisfait d'un algorithme à temps exponentiel, vous pouvez ignorer cette remarque entre parenthèses particulière. C'est juste un exemple pour essayer d'illustrer le point général que je faisais - pas quelque chose que vous devriez prendre trop au sérieux ou interpréter comme une règle stricte et rapide.
DW
9

Votre compréhension de la programmation dynamique est correcte ( afaik ) et votre question est justifiée.

Je pense que l'espace de conception supplémentaire que nous obtenons du type de récurrences que nous appelons "programmation dynamique" peut être mieux vu en comparaison avec d'autres schémas d'approches récursives.

Imaginons que nos entrées soient des tableaux pour mettre en évidence les concepts.UNE[1..n]

  1. Approche inductive

    Ici, l'idée est de rendre votre problème plus petit, de résoudre la version plus petite et de dériver une solution pour l'original. Schématiquement,

    F(UNE)=g(F(UNE[1..n-c]),UNE)

    avec la fonction / algorithme qui traduit la solution.g

    Exemple: recherche de superstars en temps linéaire

  2. Diviser et conquérir

    Partitionnez l'entrée en plusieurs parties plus petites, résolvez le problème pour chacune et combinez. Schématiquement (pour deux parties),

    .F(UNE)=g(F(UNE[1..c]),F(UNE[c+1..n]),UNE)

    Exemples: Fusion / Tri rapide, Distance par paire la plus courte dans le plan

  3. Programmation dynamique

    Considérez toutes les façons de partitionner le problème en problèmes plus petits et choisissez le meilleur. Schématiquement (pour deux parties),

    .F(UNE)=meilleur{g(F(UNE[1..c]),F(UNE[c+1..n]))|1cn-1}

    Exemples: modification de la distance, problème de modification

    Remarque importante: la programmation dynamique n'est pas une force brute ! L'application du meilleur à chaque étape réduit considérablement l'espace de recherche.

Dans un sens, vous savez de moins en moins statiquement aller de haut en bas et devez prendre de plus en plus de décisions de manière dynamique.

La leçon de l'apprentissage de la programmation dynamique est qu'il est correct d'essayer tous les partitionnements possibles (enfin, c'est nécessaire pour l'exactitude) car il peut toujours être efficace en utilisant la mémorisation.

Raphaël
la source
La "programmation dynamique élaguée" (lorsqu'elle s'applique) prouve qu'il n'est PAS nécessaire d'essayer toutes les possibilités pour être correct.
Ben Voigt
@BenVoigt Bien sûr. Je suis resté délibérément vague sur ce que signifie «toutes les façons de partitionner»; vous voulez exclure autant que possible, bien sûr! (Cependant, même si vous essayez toutes les manières de partitionner, vous n'obtenez pas la force brute puisque vous étudiez uniquement les combinaisons de solutions optimales aux sous-problèmes, tandis que la force brute enquêterait sur toutes les combinaisons de toutes les solutions.)
Raphael
Continuons cette discussion dans le chat .
Apass.Jack
5

La programmation dynamique vous permet d'échanger de la mémoire contre du temps de calcul. Prenons l'exemple classique, Fibonacci.

Fibonacci est défini par la récurrence . Si vous résolvez en utilisant cette récursivité, vous finissez par faire des appels O ( 2 n ) à F i b ( ) , car l'arbre de récursivité est un arbre binaire de hauteur nFjeb(n)=Fjeb(n-1)+Fjeb(n-2)O(2n)Fjeb()n .

Fjeb(2)Fjeb(3)Fjeb(4)O(n)

mm

Kittsil
la source
1
Vous ne parlez que de la partie mémorisation, qui manque le point de la question.
Raphael
1
«La programmation dynamique vous permet d'échanger de la mémoire contre du temps de calcul» n'est pas quelque chose que j'ai entendu lorsque je faisais un premier cycle, et c'est une excellente façon de voir ce sujet. Il s'agit d'une réponse intuitive avec un exemple succinct.
vrai
@trueshot: Sauf que parfois la programmation dynamique (et en particulier, la "Programmation dynamique élaguée") est capable de réduire les besoins en temps et en espace.
Ben Voigt
@Ben, je n'ai pas dit qu'il s'agissait d'un échange individuel. Vous pouvez également tailler un arbre de récurrence. Je suppose que j'ai répondu à la question, qui était: "Que nous apporte DP?" Il nous permet d'obtenir des algorithmes plus rapides en échangeant de l'espace contre du temps. Je conviens que la réponse acceptée est plus approfondie, mais cela est également valable.
Kittsil
2

Voici une autre façon légèrement différente de formuler ce que la programmation dynamique vous offre. La programmation dynamique réduit un nombre exponentiel de solutions candidates en un nombre polynomial de classes d'équivalence, de sorte que les solutions candidates dans chaque classe sont indiscernables dans un certain sens.

kUNEn2nO(n2)F(je,)je

F(je,)=Σj<je tel queUNE[j]<UNE[je]F(j,-1)
F(je,1)=1 pour tous je=1n

O(n2k)

jnalanko
la source