Introduction à l'approche diviser pour régner
Dans l'approche diviser pour régner, le problème en question est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment. Si nous continuons à diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement atteindre un stade où plus aucune division n'est possible. Les "sous-problèmes" les plus petits "atomiques" possibles sont résolus. La solution de tous les sous-problèmes est finalement fusionnée afin d'obtenir la solution d'un problème original.
Un algorithme typique de Diviser pour régner résout un problème en utilisant les trois étapes suivantes :
Diviser
Cette étape implique la décomposition du problème en sous-problèmes plus petits. Les sous-problèmes devraient représenter une partie du problème initial. Cette étape adopte généralement une approche récursive pour diviser le problème jusqu'à ce qu'aucun sous-problème ne soit divisible. À ce stade, les sous-problèmes deviennent de nature atomique mais représentent toujours une partie du problème actuel.
Régner/Résoudre
Cette étape reçoit beaucoup de problèmes secondaires plus petits à résoudre. Généralement, à ce niveau, les problèmes sont résoulées à l'aide de cas de base de l'algorithme récursive.
Combiner
Lorsque les plus petits problèmes sont résolus, cette étape les combine de manière récursive jusqu'à ce qu'ils formulent une solution au problème initial.
Cette approche algorithmique fonctionne de façon récursive et les étapes de conquête et de fusion fonctionnent si près qu'ils apparaissent comme un seul.
cette approche suit l'algorithme ci-dessous
Fonction DiviserRegner(problème P) SI (problème plus petit) ALORS Résoudre(P) SINON Diviser P en P1,P2,P3,..., Pk Appliquer DiviserRegner(P1),DiviserRegner(P2),DiviserRegner(P3),...,DiviserRegner(Pk) Combiner(DiviserRegner(P1),DiviserRegner(P2),DiviserRegner(P3),...,DiviserRegner(Pk)) FINSI FINFonction
Applications
Voici quelques algorithmes standard basés sur une approche de programmation diviser pour régner
- La recherche binaire. À chaque étape, l'algorithme compare l'élément d'entrée x à la valeur de l'élément intermédiaire du tableau. Si les valeurs correspondent, retourne l'index du milieu. Sinon, si x est inférieur à l'élément du milieu, l'algorithme est récurrent pour le côté gauche de l'élément du milieu, sinon, pour le côté droit de l'élément du milieu.
- Tri rapide. L'algorithme sélectionne un élément de pivot, réorganise les éléments du tableau de manière à ce que tous les éléments plus petits que l'élément de pivot se déplacent vers le côté gauche du pivot et que tous les éléments plus grands se déplacent vers le côté droit. Enfin, l'algorithme tri de manière récursive les sous-tableau gauche et droit.
- Le tri par fusion. L'algorithme divise le tableau en deux moitiés, les trie de façon récursive et fusionne finalement les deux moitiés triées
- Paire de points la plus proche Le problème est de trouver la paire de points la plus proche dans un ensemble de points dans le plan x-y. Le problème peut être résolu en un temps O(n2) en calculant les distances de chaque paire de points et en comparant les distances pour trouver le minimum. L'algorithme Diviser pour régner résout le problème en temps O(nLogn).
- L’algorithme de Strassen est un algorithme efficace pour multiplier deux matrices. Une méthode simple pour multiplier deux matrices nécessite 3 boucles imbriquées en temps O (n3). L’algorithme de Strassen multiplie deux matrices en temps O(n2,8974).
- L'algorithme Cooley–Tukey de transformation de Fourier rapide (FFT) est l'algorithme le plus courant pour la FFT. C'est un algorithme qui fonctionne en temps O(nlogn).
- Algorithme de Karatsuba pour une multiplication rapide