Différence entre l'algo Diviser et Conquérir et la programmation dynamique

Question

Quelle est la différence entre les algorithmes de type Diviser et Conquérir et les algorithmes de programmation dynamique ? En quoi ces deux termes sont-ils différents ? Je ne comprends pas la différence entre les deux.

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

Answer 1

Diviser pour mieux régner

Diviser et Conquérir fonctionne en divisant le problème en sous-problèmes, en conquérant chaque sous-problème de manière récursive et en combinant ces solutions.

Programmation dynamique

La programmation dynamique est une technique permettant de résoudre des problèmes dont les sous-problèmes se chevauchent. Chaque sous-problème n'est résolu qu'une seule fois et le résultat de chaque sous-problème est stocké dans un tableau (généralement implémenté comme un tableau ou une 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 des sous-problèmes 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 ceci matériel du MIT.

---

Approche "Diviser pour mieux régner

Approche de la programmation dynamique

Answer 2

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

Diviser pour mieux régner :

1. Effectue plus de travail sur les sous-problèmes et consomme donc plus de temps.
2. Dans la méthode "diviser pour régner", 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 enregistre dans le tableau.
2. En programmation dynamique, les sous-problèmes ne sont pas indépendants.

Answer 3

Parfois, lorsque l'on programme de manière récurrente, on appelle la fonction avec les mêmes paramètres plusieurs fois, ce qui n'est pas nécessaire.

Le célèbre exemple des 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 la programmation dynamique : si vous appelez une fonction avec le même paramètre plus d'une fois, sauvegardez le résultat dans une variable pour y accéder directement la fois suivante. La méthode 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, il suffit d'accéder à la variable correspondante pour obtenir la valeur au lieu de la recalculer.

Par ailleurs, la programmation dynamique ne signifie pas la conversion d'un code récursif en un code itératif. Vous pouvez également sauvegarder les sous-résultats dans une variable si vous voulez un code récursif. Dans ce cas, la technique est appelée 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]                
    }
}

Le rapport avec le Diviser et Conquérir est donc que les algorithmes de D&D reposent sur la récursion. Et certaines versions d'entre eux ont ce "problème d'appels multiples de fonctions avec le même paramètre". Cherchez "matrix chain multiplication" et "longest common subsequence" pour de tels exemples où DP est nécessaire pour améliorer le T(n) de l'algo D&D.

Answer 4

Je suppose que vous avez déjà lu Wikipédia et d'autres ressources universitaires sur le sujet, je ne vais donc pas recycler ces informations. Je dois également préciser que je ne suis en aucun cas un expert en informatique, mais je vais vous faire part de mon point de vue sur ces sujets...

Programmation dynamique

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

Diviser pour mieux régner

Ces algorithmes résolvent généralement des parties similaires du problème, puis les assemblent à la fin. Mergesort est un exemple classique de diviser pour régner. La principale différence entre cet exemple et celui de Fibonacci est que dans un mergesort, 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 fait pour trier le tableau, peu importe comment vous le divisez. La résolution de fib(52) nécessite plus d'étapes que la résolution de fib(2).

Answer 5

Je pense à Divide & Conquer comme une approche récursive et Dynamic Programming comme garniture de table.

Par exemple, Merge Sort est un Divide & Conquer puisque, à chaque étape, vous divisez le tableau en deux moitiés, vous appelez récursivement Merge Sort sur les deux moitiés, puis les fusionner.

Knapsack est un Dynamic Programming comme vous remplissez un tableau représentant les 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 compte tenu des articles 1-j.