Les différence principale entre diviser pour régner et la programmation dynamique est que le diviser pour régner combine les solutions des sous-problèmes pour obtenir la solution du problème principal tandis que la programmation dynamique utilise le résultat des sous-problèmes pour trouver la solution optimale du problème principal.

Diviser pour mieux régner et la programmation dynamique sont deux algorithmes ou approches pour résoudre des problèmes. L'algorithme Diviser pour mieux régner divise le problème en sous-problèmes et combine ces solutions pour trouver la solution au problème d'origine. Cependant, la programmation dynamique ne résout pas les sous-problèmes indépendamment. Il stocke les réponses des sous-problèmes pour les utiliser pour des problèmes similaires.

Diviser pour mieux régner, programmation dynamique

Qu'est-ce que Diviser pour mieux régner

Diviser pour mieux régner divise le problème principal en petits sous-problèmes. Les sous-problèmes sont divisés encore et encore. À un moment donné, il y aura une étape où nous ne pourrons plus diviser les sous-problèmes. Ensuite, nous pouvons résoudre chaque sous-problème indépendamment. Enfin, nous pouvons combiner les solutions de tous les sous-problèmes pour obtenir la solution du problème principal.

Il y a trois étapes principales dans diviser pour régner. Ils sont les suivants.

Diviser (Casser) – Implique de diviser le problème principal en une collection de sous-problèmes

Conquérir (Résoudre) – Implique la résolution de chaque sous-problème séparément

Combiner (Fusionner) – Joint les solutions des sous-problèmes pour obtenir la solution du problème principal

Qu'est-ce que la programmation dynamique

La programmation dynamique divise le problème principal en sous-problèmes plus petits, mais elle ne résout pas les sous-problèmes indépendamment. Il stocke les résultats des sous-problèmes à utiliser lors de la résolution de sous-problèmes similaires. Le stockage des résultats des sous-problèmes est appelé mémorisation. Avant de résoudre le sous-problème courant, il vérifie les résultats des sous-problèmes précédents. Enfin, il vérifie les résultats de tous les sous-problèmes pour trouver la meilleure solution ou la solution optimale. Cette méthode est efficace car elle ne calcule pas les réponses encore et encore. Habituellement, la programmation dynamique est utilisée pour l'optimisation.

Les éléments de programmation dynamique sont les suivants.

Sous-problèmes simples – Divisez le problème original en petits sous-problèmes qui ont une structure similaire

Sous-structure optimale du problème – La solution optimale au problème principal se trouve dans la solution optimale à ses sous-problèmes

Chevauchement de sous-problèmes – Situations de résolution des mêmes sous-problèmes encore et encore

Différence entre diviser pour régner et la programmation dynamique

Définition

Diviser pour mieux régner est un algorithme qui décompose récursivement un problème en deux ou plusieurs sous-problèmes du même type ou de type apparenté jusqu'à ce qu'il devienne suffisamment simple pour être résolu directement. Cependant, la programmation dynamique est un algorithme qui aide à résoudre efficacement une classe de problèmes qui ont des sous-problèmes qui se chevauchent et une propriété de sous-structure optimale.

Taper

La principale différence entre diviser pour régner et la programmation dynamique est que diviser pour régner est récursive tandis que la programmation dynamique est non récursive.

Sous-problèmes

Dans diviser pour régner, les sous-problèmes sont indépendants les uns des autres. Cependant, en programmation dynamique, les sous-problèmes sont interdépendants. C'est donc une autre différence majeure entre diviser pour régner et la programmation dynamique.

Consommation de temps

La consommation de temps est une autre différence entre diviser pour régner et la programmation dynamique. Diviser pour régner résout chaque sous-problème indépendamment. Par conséquent, cela prend plus de temps. La programmation dynamique, quant à elle, utilise les réponses des sous-problèmes précédents. Ainsi, cela prend moins de temps.

Efficacité

L'efficacité fait également la différence entre diviser pour régner et la programmation dynamique. La programmation dynamique est plus efficace que diviser pour régner.

Applications

Le tri par fusion, le tri rapide et la recherche binaire utilisent la division pour régner tandis que la multiplication de chaînes matricielles et l'arbre de recherche binaire optimal utilisent la programmation dynamique.

Conclusion

le différence principale entre diviser pour régner et la programmation dynamique est que le diviser pour régner combine les solutions des sous-problèmes pour obtenir la solution du problème principal tandis que la programmation dynamique utilise le résultat des sous-problèmes pour trouver la solution optimale du problème principal.

Référence:

1. "DAA Divide and Conquer Introduction - Javatpoint". Www.javatpoint.com, disponible ici.2. "Introduction à la programmation dynamique - Javatpoint." Www.javatpoint.com, disponible ici.3. Programmation dynamique | Steps to Design & Applications |, Education 4u, 2 avril 2018, disponible ici.4. “Programmation Dynamique”, Programiz. com, disponible ici.

Image de courtoisie:

1. «Diagramme d'algorithme de tri de fusion» de VineetKumar sur Wikipedia anglais - Transféré de en.wikipedia à Commons par Eric Bauman à l'aide de CommonsHelper (domaine public) via Commons Wikimedia2. "Programmation dynamique de Fibonacci" Par en:User:Dcoatzee, tracé par User:Stannered - en:Image:Fibonacci dynamic programming.png (Domaine public) via Commons Wikimedia