Beim Teilen und Erobern Ansatz, wird das vorliegende Problem in kleinere Unterprobleme aufgeteilt und jedes Problem wird dann unabhängig gelöst. Wenn man die Teilprobleme immer weiter in noch kleinere Teilprobleme unterteilt, kommt man irgendwann an einen Punkt, an dem keine Unterteilung mehr möglich ist. Diese „atomar“ kleinstmöglichen Teilprobleme (Brüche) werden gelöst. Die Lösung aller Teilprobleme wird schließlich zusammengeführt, um die Lösung des ursprünglichen Problems zu erhalten.
Grundsätzlich können wir den Divide-and-Conquer-Ansatz in einem dreistufigen Prozess verstehen.
Divide/Break
In diesem Schritt wird das Problem in kleinere Teilprobleme zerlegt. Die Unterprobleme sollten einen Teil des ursprünglichen Problems darstellen. In diesem Schritt wird das Problem in der Regel rekursiv aufgeteilt, bis kein Teilproblem mehr teilbar ist. Auf dieser Stufe werden die Unterprobleme atomarer Natur, stellen aber immer noch einen Teil des eigentlichen Problems dar.
Bezwingen/Lösen
Dieser Schritt erhält eine Menge kleinerer Unterprobleme, die gelöst werden müssen. Im Allgemeinen werden die Probleme auf dieser Stufe als eigenständig „gelöst“ betrachtet.
Merge/Combine
Wenn die kleineren Teilprobleme gelöst sind, werden sie in dieser Stufe rekursiv kombiniert, bis sie eine Lösung des ursprünglichen Problems formulieren. Dieser algorithmische Ansatz arbeitet rekursiv und conquer &Merge-Schritte arbeiten so eng zusammen, dass sie wie ein einziger erscheinen.
Beispiele
Die folgenden Computeralgorithmen basieren auf dem divide-and-conquer-Programmieransatz –
- Merge Sort
- Quick Sort
- Binäre Suche
- Strassens Matrix-Multiplikation
- Closest pair (Punkte)
Es gibt verschiedene Möglichkeiten, ein beliebiges Computerproblem zu lösen, aber die genannten sind ein gutes Beispiel für den „Divide and Conquer“-Ansatz.