Diviser pour régner
Définition : Définition
La méthode « Diviser pour régner » (divide and conquer) est une méthode de résolution de problème qui consiste à décomposer un problème en sous-problèmes de taille inférieure, et à les résoudre afin d'en déduire une solution au problème initial.
Cela consiste donc en trois étapes :
Diviser : on divise le problème initial en sous-parties, la majorité du temps en deux parties de taille semblable.
Régner : on résout le sous-problème, soit trivialement, soit en ré-appliquant la méthode « Diviser pour régner ».
Combiner : on calcule la solution du problème initial grâce aux solutions des sous-problèmes.
Comme dit en introduction, les sous-problèmes peuvent être calculés par plusieurs programmes qui collaborent, ou simplement par un unique programme qui traite les sous-problèmes les uns après les autres.
En effet, la méthode « Diviser pour régner » peut être plus efficace, même si le programme traite les opérations séquentiellement.
Simulation : Complexité
L'intérêt de cette méthode est avant tout de proposer une meilleure complexité pour une partie des problèmes existants.