Il s'agit d'une question très générale. Qu'est-ce que la programmation dynamique (en quoi est-elle différente de la récursion, de la mémorisation, etc.) J'ai lu le article de wikipédia sur le sujet mais je ne le comprends toujours pas vraiment.
Aidez-moi à comprendre la programmation dynamique. Merci.
La programmation dynamique consiste à utiliser les connaissances passées pour faciliter la résolution d'un problème futur.
Un bon exemple est la résolution de la suite de Fibonacci pour n=1,000,002.
Ce sera un processus très long, mais que se passe-t-il si je vous donne les résultats pour n=1 000 000 et n=1 000 0001 ? Tout à coup, le problème est devenu plus facile à gérer.
La programmation dynamique est très utilisée dans les problèmes de chaînes de caractères, tels que le problème de l'édition de chaînes de caractères. Vous résolvez un ou plusieurs sous-ensembles du problème, puis vous utilisez ces informations pour résoudre le problème original, plus difficile.
Avec la programmation dynamique, vous stockez vos résultats dans une sorte de tableau en général. Lorsque vous avez besoin de la réponse à un problème, vous faites référence à la table et voyez si vous la connaissez déjà. Si ce n'est pas le cas, vous utilisez les données de votre tableau pour vous donner un tremplin vers la réponse.
Le livre de Cormen sur les algorithmes contient un excellent chapitre sur la programmation dynamique. ET il est gratuit sur Google Books ! Consultez-le ici.
La mémorisation est le moment où vous stockez les résultats précédents d'un appel de fonction (une vraie fonction renvoie toujours la même chose, étant donné les mêmes entrées). Cela ne fait pas de différence pour la complexité algorithmique avant le stockage des résultats.
La récursion consiste à ce qu'une fonction s'appelle elle-même, généralement avec un ensemble de données plus petit. Comme la plupart des fonctions récursives peuvent être converties en fonctions itératives similaires, cela ne fait pas non plus de différence pour la complexité algorithmique.
La programmation dynamique consiste à résoudre des sous-problèmes plus faciles à résoudre et à construire la réponse à partir de ceux-ci. La plupart des algorithmes de programmation dynamique ont un temps d'exécution compris entre celui d'un algorithme de type Greedy (s'il existe) et celui d'un algorithme exponentiel (qui énumère toutes les possibilités et trouve la meilleure).
C'est une optimisation de votre algorithme qui réduit le temps d'exécution.
Alors qu'un Algorithme Greedy est généralement appelé naïf Comme elle peut être exécutée plusieurs fois sur le même ensemble de données, la programmation dynamique évite cet écueil grâce à une meilleure compréhension des résultats partiels qui doivent être stockés pour aider à construire la solution finale.
Un exemple simple est la traversée d'un arbre ou d'un graphe uniquement à travers les nœuds qui contribueraient à la solution, ou la mise dans un tableau des solutions que vous avez trouvées jusqu'à présent afin d'éviter de traverser les mêmes nœuds encore et encore.
Voici un exemple de problème adapté à la programmation dynamique, tiré du juge en ligne de l'UVA : Editer l'échelle des marches.
Je vais faire un bref résumé de la partie importante de l'analyse de ce problème, tirée du livre Programming Challenges, je vous suggère de le consulter.
Regardez bien ce problème, si on définit une fonction de coût qui nous dit la distance entre deux cordes, nous devons considérer les trois types naturels types de changements :
Substitution - changer un seul caractère unique du motif "s" à un caractère différent dans le texte "t", par exemple par exemple, remplacer "shot" par "spot".
Insertion - insérer un seul caractère dans le motif "s" pour l'aider à correspondre au texte "t", par exemple en remplaçant "ago" par "agog".
Suppression - supprime un seul caractère du motif "s" pour l'aider à correspondre au texte "t", par exemple en remplaçant "hour" par "our".
Lorsque nous définissons chacune de ces opérations pour coûtent une étape, nous définissons la distance d'édition entre deux chaînes de caractères. Alors comment la calculons-nous ?
Nous pouvons définir un algorithme récursif en utilisant l'observation que le dernier caractère de la chaîne doit être soit correspondre, substitué, inséré ou supprimé. La suppression des caractères dans la dernière opération d'édition laisse une laisse une paire de chaînes de caractères plus petites. Soit i et j le dernier caractère du préfixe pertinent de et t, respectivement. il existe trois paires de chaînes plus courtes après la dernière opération, correspondant à la chaîne après une correspondance/substitution, insertion ou suppression. Si nous connaissions le coût de l'édition des trois paires de petites chaînes, nous pourrions décider quelle option conduit à la meilleure solution et choisir cette option en conséquence. Nous pouvons apprendre ce coût, grâce à cette impressionnante chose qu'est la 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.
Sur notre ordinateur, il faut plusieurs secondes pour comparer deux chaînes de 11 caractères, et le calcul disparaît dans jamais sur une plus longue période.
Pourquoi l'algorithme est-il si lent ? Il prend temps exponentiel car il recalcule les valeurs encore et encore et encore. Sur chaque position dans la chaîne, la récursion se ramifie de trois façons, ce qui signifie qu'elle croît à un rythme d'au moins 3^n - en fait, encore plus vite puisque la plupart des ne réduisent qu'un seul des deux indices, et non les deux.
Alors comment pouvons-nous rendre l'algorithme pratique ? L'observation importante est que la plupart de ces appels récursifs calculent des choses qui ont déjà déjà été calculées auparavant. Comment pouvons-nous savons-nous ? Eh bien, il ne peut y avoir que |s| - |t| appels récursifs uniques possibles, puisqu'il n'y a que ce nombre de paires (i, j) distinctes pouvant servir de paramètres des appels récursifs.
En stockant les valeurs de chacune de ces paires (i, j) dans un tableau, nous pouvons éviter de les recalculer et simplement les les consulter en cas de besoin.
Le tableau est une matrice bidimensionnelle m où chacune des cellules |s|-|t| contient le coût de la solution optimale. contient le coût de la solution optimale solution optimale de ce sous-problème, ainsi que ainsi qu'un pointeur parent expliquant comment nous sommes arrivés à 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 présente trois différences par rapport à la version récursive récursive.
D'abord, il obtient ses valeurs intermédiaires en utilisant la consultation de tables au lieu de appels récursifs.
Deuxièmement, il met à jour le champ parent de chaque cellule, ce qui nous permettra de reconstruire la séquence d'édition plus tard.
Troisièmement, Troisièmement, il est instrumenté en utilisant une fonction plus générale de cellule de but() plus générale, au lieu de retourner simplement m[|s|][|t|].cost. Cela nous permettra d'appliquer cette routine à une classe plus de problèmes.
Ici, c'est une analyse très particulière de ce qu'il faut faire pour obtenir les résultats partiels les plus optimaux qui fait de la solution une solution "dynamique".
Voici une solution alternative et complète au même problème. Il s'agit également d'une solution "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 étonnant qu'un problème aussi lourd ait été résolu de manière aussi efficace.
Voici ma réponse r dans un sujet similaire
Commencez par
Si vous voulez vous tester, mes choix concernant les juges en ligne sont les suivants
et bien sûr
Vous pouvez également vérifier les cours d'algorithmes des bonnes universités
Après tout, si vous ne pouvez pas résoudre les problèmes, demandez à SO que de nombreux algorithmes addict existent ici.
Les éléments clés de la programmation dynamique sont le "chevauchement des sous-problèmes" et la "sous-structure optimale". Ces propriétés d'un problème signifient qu'une solution optimale est composée des solutions optimales de ses sous-problèmes. Par exemple, les problèmes de plus court chemin présentent une sous-structure optimale. Le plus court chemin de A à C est le plus court chemin de A à un certain nœud B suivi du plus court chemin de ce nœud B à C.
De manière plus détaillée, pour résoudre un problème de chemin le plus court, vous allez.. :
Parce que nous travaillons de manière ascendante, nous disposons déjà de solutions aux sous-problèmes lorsque le moment est venu de les utiliser, en les mémorisant.
Rappelez-vous que les problèmes de programmation dynamique doivent avoir à 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 ; il utilise la mémorisation parce qu'il a des sous-problèmes qui se chevauchent, mais il n'a pas de sous-structure optimale (parce qu'il n'y a pas de problème d'optimisation).
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
