W podejściu divide and conquer, problem w ręku, jest podzielony na mniejsze pod-problemy, a następnie każdy problem jest rozwiązywany niezależnie. Gdy będziemy dalej dzielić podproblemy na jeszcze mniejsze podproblemy, możemy w końcu dojść do etapu, w którym żaden podział nie będzie już możliwy. Rozwiązujemy wtedy „atomowo” najmniejsze możliwe podproblemy (ułamki). Rozwiązanie wszystkich podproblemów jest w końcu łączone w celu uzyskania rozwiązania oryginalnego problemu.
Szerzej, możemy rozumieć podejście „podziel i podbij” jako trzyetapowy proces.
Podziel/rozbij
Ten krok polega na rozbiciu problemu na mniejsze podproblemy. Podproblemy powinny reprezentować część oryginalnego problemu. W tym kroku zazwyczaj stosuje się podejście rekurencyjne do dzielenia problemu, aż żaden podproblem nie będzie dalej podzielny. Na tym etapie podproblemy stają się atomowe, ale nadal reprezentują część rzeczywistego problemu.
Pokonaj/Rozwiąż
Ten krok otrzymuje wiele mniejszych podproblemów do rozwiązania. Ogólnie, na tym poziomie, problemy są uważane za „rozwiązane” same w sobie.
Merge/Combine
Kiedy mniejsze pod-problemy są rozwiązane, ten etap rekurencyjnie łączy je aż do sformułowania rozwiązania oryginalnego problemu. To podejście algorytmiczne działa rekurencyjnie i podbija & merge kroki działają tak blisko siebie, że pojawiają się jako jeden.
Przykłady
Następujące algorytmy komputerowe są oparte na podejściu programistycznym divide-and-conquer podejście programistyczne –
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (points)
Są różne sposoby na rozwiązanie dowolnego problemu komputerowego, ale te wymienione są dobrym przykładem podejścia divide and conquer.