Différence entre Divide and Conquer Algo et programmation dynamique

Quelle est la différence entre les algorithmes Divide and Conquer et les algorithmes de programmation dynamique? En quoi les deux termes sont-ils différents? Je ne comprends pas la différence entre eux.

Veuillez prendre un exemple simple pour expliquer toute différence entre les deux et pour quelle raison ils semblent similaires.

Diviser et conquérir

Divide and Conquer fonctionne en divisant le problème en sous-problèmes, conquérir chaque sous-problème de manière récursive et combiner ces solutions.

Programmation dynamique

La programmation dynamique est une technique pour résoudre des problèmes avec des sous-problèmes qui se chevauchent. Chaque sous-problème est résolu une seule fois et le résultat de chaque sous-problème est stocké dans une table (généralement implémentée sous forme de tableau ou de table de hachage) pour des références futures. Ces sous-solutions peuvent être utilisées pour obtenir la solution originale et la technique de stockage des solutions de sous-problème est connue sous le nom de mémorisation.

Vous pouvez penser à DP = recursion + re-use

Un exemple classique pour comprendre la différence serait de voir ces deux approches pour obtenir le nième nombre de fibonacci. Vérifiez ce matériel du MIT.

Approche Divide and Conquer

Approche de programmation dynamique

L'autre différence entre diviser pour conquérir et la programmation dynamique pourrait être:

Diviser et conquérir:

1. Travaille plus sur les sous-problèmes et consomme donc plus de temps.
2. Dans la division pour la conquête, les sous-problèmes sont indépendants les uns des autres.

Programmation dynamique:

1. Résout les sous-problèmes une seule fois, puis les stocke dans la table.
2. En programmation dynamique, les sous-problèmes ne sont pas indépendants.

parfois lors de la programmation récursive, vous appelez la fonction avec les mêmes paramètres plusieurs fois, ce qui n'est pas habituel.

Le fameux exemple de nombres de Fibonacci:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Lançons F (5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

Nous avons donc appelé: 1 fois F (4) 2 fois F (3) 3 fois F (2) 2 fois F (1)

Approche de programmation dynamique: si vous appelez une fonction avec le même paramètre plus d'une fois, enregistrez le résultat dans une variable pour y accéder directement la prochaine fois. La manière itérative:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Appelons à nouveau F (5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

Comme vous pouvez le voir, chaque fois que vous avez besoin de l'appel multiple, vous accédez simplement à la variable correspondante pour obtenir la valeur au lieu de la recalculer.

À propos, la programmation dynamique ne signifie pas convertir un code récursif en code itératif. Vous pouvez également enregistrer les sous-résultats dans une variable si vous souhaitez un code récursif. Dans ce cas, la technique s'appelle la mémorisation. Pour notre exemple, cela ressemble à ceci:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Donc, la relation avec Divide and Conquer est que les algorithmes de D&D reposent sur la récursivité. Et certaines versions d'entre eux ont cet «appel de fonctions multiples avec le même problème de paramètre». Recherchez «multiplication de chaîne matricielle» et «sous-séquence commune la plus longue» pour de tels exemples où DP est nécessaire pour améliorer le T (n) de l'algo D&D.

Programmation dynamique et similitudes diviser-pour-conquérir

Comme je le vois pour le moment, je peux dire que la programmation dynamique est une extension du paradigme diviser pour conquérir .

Je ne les traiterais pas comme quelque chose de complètement différent. Parce qu'ils fonctionnent tous les deux en décomposant récursivement un problème en deux ou plusieurs sous-problèmes du même type ou d'un type apparenté, jusqu'à ce que ceux-ci deviennent suffisamment simples pour être résolus directement. Les solutions aux sous-problèmes sont ensuite combinées pour donner une solution au problème d'origine.

Alors pourquoi avons-nous encore des noms de paradigme différents alors et pourquoi j'ai appelé la programmation dynamique une extension. C'est parce que l'approche de programmation dynamique peut être appliquée au problème uniquement si le problème comporte certaines restrictions ou conditions préalables . Et après cette programmation dynamique étend l'approche diviser pour conquérir avec la technique de mémorisation ou de tabulation .

Allons-y étape par étape…

Conditions préalables / restrictions de programmation dynamique

Comme nous venons de le découvrir, il y a deux attributs clés que le problème de division et de conquête doit avoir pour que la programmation dynamique soit applicable:

• Sous-structure  optimale - une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes

• Chevauchement des sous-problèmes  - le problème peut être décomposé en sous-problèmes qui sont réutilisés plusieurs fois ou un algorithme récursif pour le problème résout le même sous-problème à plusieurs reprises plutôt que de toujours générer de nouveaux sous-problèmes

Une fois ces deux conditions remplies, nous pouvons dire que ce problème de division pour vaincre peut être résolu en utilisant une approche de programmation dynamique.

Extension de programmation dynamique pour Divide and Conquer

L'approche de programmation dynamique étend l'approche de division pour conquérir avec deux techniques ( mémorisation et tabulation ) qui ont toutes deux pour but de stocker et de réutiliser des solutions de sous-problèmes susceptibles d'améliorer considérablement les performances. Par exemple, l'implémentation récursive naïve de la fonction de Fibonacci a une complexité temporelle O(2^n)où la solution DP fait la même chose avec seulement le O(n)temps.

La mémorisation (remplissage du cache de haut en bas) fait référence à la technique de mise en cache et de réutilisation des résultats précédemment calculés. La fibfonction mémorisée ressemblerait donc à ceci:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

La tabulation (remplissage du cache de bas en haut) est similaire mais se concentre sur le remplissage des entrées du cache. Le calcul des valeurs dans le cache est plus simple de manière itérative. La version tabulation de fibressemblerait à ceci:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Vous pouvez en savoir plus sur la mémorisation et la comparaison des tableaux ici .

L'idée principale que vous devez comprendre ici est que, parce que notre problème de division et de conquête a des sous-problèmes qui se chevauchent, la mise en cache des solutions de sous-problèmes devient possible et ainsi la mémorisation / tabulation entre en scène.

Alors, quelle est la différence entre DP et DC après tout

Puisque nous connaissons maintenant les prérequis DP et ses méthodologies, nous sommes prêts à rassembler tout ce qui a été mentionné ci-dessus en une seule image.

Si vous souhaitez voir des exemples de code, vous pouvez consulter des explications plus détaillées ici où vous trouverez deux exemples d'algorithmes: la recherche binaire et la distance minimale d'édition (distance de Levenshtein) qui illustrent la différence entre DP et DC.

Je suppose que vous avez déjà lu Wikipédia et d'autres ressources académiques à ce sujet, je ne recyclerai donc aucune de ces informations. Je dois également souligner que je ne suis en aucun cas un expert en informatique, mais je vais partager mes deux cents sur ma compréhension de ces sujets ...

Programmation dynamique

Décompose le problème en sous-problèmes discrets. L'algorithme récursif pour la séquence de Fibonacci est un exemple de programmation dynamique, car il résout pour fib (n) en résolvant d'abord pour fib (n-1). Afin de résoudre le problème d'origine, il résout un autre problème .

Diviser et conquérir

Ces algorithmes résolvent généralement des éléments similaires du problème, puis les rassemblent à la fin. Mergesort est un exemple classique de division et de conquête. La principale différence entre cet exemple et l'exemple de Fibonacci est que dans un tri de fusion, la division peut (théoriquement) être arbitraire, et quelle que soit la façon dont vous la découpez, vous fusionnez et triez toujours. La même quantité de travail doit être effectuée pour fusionner le tableau, quelle que soit la façon dont vous le divisez. La résolution de fib (52) nécessite plus d'étapes que la résolution de fib (2).

Je pense Divide & Conquerà une approche récursive et Dynamic Programmingà un remplissage de tableau.

Par exemple, Merge Sortest un Divide & Conqueralgorithme, comme à chaque étape, vous divisez le tableau en deux moitiés, appelez récursivementMerge Sort les deux moitiés, puis fusionnez-les.

Knapsackest un Dynamic Programmingalgorithme lorsque vous remplissez un tableau représentant des solutions optimales aux sous-problèmes du sac à dos global. Chaque entrée du tableau correspond à la valeur maximale que vous pouvez transporter dans un sac de poids w en fonction des articles 1-j.

Divide and Conquer comporte trois étapes à chaque niveau de récursivité:

1. Diviser le problème en sous-problèmes.
2. Conquérir les sous-problèmes en les résolvant de manière récursive.
3. Combinez la solution pour les sous-problèmes dans la solution pour le problème d'origine.
   
   • C'est une approche descendante .
     
   • Il travaille plus sur les sous-problèmes et consomme donc plus de temps.
   • par exemple. Le n-ième terme de la série de Fibonacci peut être calculé en complexité temporelle O (2 ^ n).
     
     

La programmation dynamique comprend les quatre étapes suivantes:

1. Caractériser la structure des solutions optimales.
2. Définissez récursivement les valeurs des solutions optimales.
3. Calculez la valeur des solutions optimales.
4. Construisez une solution optimale à partir d'informations calculées .

• Il est un ascendantes approche.
• Moins de temps que de diviser pour conquérir puisque nous utilisons les valeurs calculées plus tôt, plutôt que de calculer à nouveau.
• par exemple. Le n-ième terme de la série de Fibonacci peut être calculé en complexité temporelle O (n).
  
  

Pour une compréhension plus facile, voyons diviser et conquérir comme une solution de force brute et son optimisation en tant que programmation dynamique.

NB Les algorithmes de division et de conquête avec des sous-problèmes qui se chevauchent ne peuvent être optimisés qu'avec dp.

• Diviser et conquérir
  • Ils ont éclaté en sous-problèmes qui ne se chevauchent pas
  • Exemple: nombres factoriels ie fait (n) = n * fait (n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

Comme nous pouvons le voir ci-dessus, aucun fait (x) n'est répété donc factoriel a des problèmes non chevauchants.

• Programmation dynamique
  • Ils ont éclaté en sous-problèmes qui se chevauchent
  • Exemple: nombres de Fibonacci ie fib (n) = fib (n-1) + fib (n-2)

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

Comme nous pouvons le voir ci-dessus, fib (4) et fib (3) utilisent tous deux fib (2). de même, tant de fib (x) se répètent. c'est pourquoi Fibonacci a des sous-problèmes qui se chevauchent.

• En raison de la répétition du sous-problème dans DP, nous pouvons conserver ces résultats dans un tableau et économiser des efforts de calcul. c'est ce qu'on appelle la mémorisation