Datenstrukturen - Teilen und Erobern
Beim Divide and Conquer-Ansatz wird das vorliegende Problem in kleinere Unterprobleme unterteilt, und dann wird jedes Problem unabhängig gelöst. Wenn wir die Teilprobleme weiter in noch kleinere Teilprobleme aufteilen, erreichen wir möglicherweise ein Stadium, in dem keine weitere Aufteilung möglich ist. Diese "atomaren" kleinstmöglichen Unterprobleme (Brüche) werden gelöst. Die Lösung aller Unterprobleme wird schließlich zusammengeführt, um die Lösung eines ursprünglichen Problems zu erhalten.
Im Großen und Ganzen können wir verstehen divide-and-conquer Ansatz in einem dreistufigen Prozess.
Teilen / Brechen
Dieser Schritt beinhaltet das Aufteilen des Problems in kleinere Unterprobleme. Unterprobleme sollten einen Teil des ursprünglichen Problems darstellen. Dieser Schritt verwendet im Allgemeinen einen rekursiven Ansatz, um das Problem zu teilen, bis kein Unterproblem mehr teilbar ist. In diesem Stadium werden Unterprobleme atomarer Natur, stellen jedoch immer noch einen Teil des eigentlichen Problems dar.
Erobern / Lösen
Dieser Schritt erhält viele kleinere Teilprobleme, die gelöst werden müssen. Auf dieser Ebene werden die Probleme im Allgemeinen als eigenständig „gelöst“ betrachtet.
Zusammenführen / kombinieren
Wenn die kleineren Teilprobleme gelöst sind, werden sie in dieser Phase rekursiv kombiniert, bis sie eine Lösung des ursprünglichen Problems formulieren. Dieser algorithmische Ansatz funktioniert rekursiv und Conquer & Merge-Schritte arbeiten so nahe, dass sie als eins angezeigt werden.
Beispiele
Die folgenden Computeralgorithmen basieren auf divide-and-conquer Programmieransatz -
- Zusammenführen, sortieren
- Schnelle Sorte
- Binäre Suche
- Strassens Matrixmultiplikation
- Nächstes Paar (Punkte)
Es gibt verschiedene Möglichkeiten, um jedes Computerproblem zu lösen, aber die genannten sind ein gutes Beispiel für den Divide and Conquer-Ansatz.