Dans l’approche diviser et conquérir, le problème en main, est divisé en sous-problèmes plus petits et ensuite chaque problème est résolu indépendamment. Lorsque 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. Ces sous-problèmes « atomiques » les plus petits possibles (fractions) 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.
De manière générale, nous pouvons comprendre l’approche diviser et conquérir en un processus en trois étapes.
Diviser/Casser
Cette étape consiste à diviser le problème en sous-problèmes plus petits. Les sous-problèmes doivent 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 plus divisible. À ce stade, les sous-problèmes deviennent de nature atomique mais représentent toujours une partie du problème réel.
Conquérir/Solvabiliser
Cette étape reçoit un grand nombre de sous-problèmes plus petits à résoudre. Généralement, à ce niveau, les problèmes sont considérés comme » résolus » par eux-mêmes.
Fusionner/Combiner
Lorsque les sous-problèmes plus petits sont résolus, cette étape les combine récursivement jusqu’à ce qu’ils formulent une solution du problème original. Cette approche algorithmique fonctionne de manière récursive et conquiert & étapes de fusion travaille si proche qu’ils apparaissent comme un seul.
Exemples
Les algorithmes informatiques suivants sont basés sur l’approche de programmation diviser-et-conquer –
- Tri par fusion
- Tri rapide
- Recherche binaire
- Multiplication matricielle de Strassen
- Paire la plus proche (points)
Il existe différentes façons de résoudre tout problème informatique, mais celles mentionnées sont un bon exemple de l’approche « diviser pour régner ».
.