Diviser pour mieux régner

Dans l'approche "diviser pour régner", le problème à résoudre 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 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 régner" par un processus en trois étapes.

Diviser/Rompre

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 atomiques par nature mais représentent toujours une partie du problème réel.

Conquérir/Solvabiliser