Dans l’approche “diviser pour mieux régner”, le problème en question est divisé en petits sous-problèmes, 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 finalement 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 pour mieux régner” dans un processus en trois étapes.
Diviser/Rupture
Cette étape consiste à décomposer 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/résoudre
Cette étape comporte de nombreux petits sous-problèmes à 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 petits sous-problèmes sont résolus, cette étape les combine récursivement jusqu’à ce qu’ils formulent une solution au problème initial. Cette approche algorithmique fonctionne de manière récursive et les étapes “conquérir et fusionner” sont si proches qu’elles apparaissent comme une seule.
Exemples
Les algorithmes informatiques suivants sont basés sur l’approche de programmation “diviser pour mieux régner” –
- Fusionner le tri
- Tri rapide
- Recherche binaire
Il existe différentes façons de résoudre un problème informatique, mais celles qui sont mentionnées sont un bon exemple de l’approche “diviser pour mieux régner“.
