"Dziel i rządź" to następny termin algorytmiki jaki weźmiemy sobie pod lupę i wyjaśnimy. Jest jednym z najważniejszych wątków, więc lektura OBOWIĄZKOWA dla każdego mojego czytelnika!
| Tweet |
"DZIEL I RZĄDŹ" W KONTEKŚCIE ALGORYTMU
To może się Wam wydać dziwne, aczkolwiek nie chodzi tu o roztrząsanie sensu gramatycznego. "Divide and conquer" z angielskiego (lub też "Divide and rule"), opisuje metodę rozwiązywania postawionego problemu dzieląc go na mniejsze kawałeczki, aby krok po kroku dojść do ostatecznego rozwiązania. To tak w największym skrócie o co "come on" w tym terminie. Teraz wytłumaczę to już w sposób bardziej naukowy.
"Dziel i rządź" (ludzie czasami zamiennie używają synonimu "dziel i zwyciężaj") to jest analizowanie problemu przy użyciu rekurencji. Rekurencja jest kolejnym arcyważnym terminem w nauce informatycznej, który oznacza odwoływanie się funkcji do samej siebie. Chodzi o to, żeby sprowadzić rekurencyjne rozwiązywanie problemu do przypadku podstawowego. Przypadek podstawowy to moment, w którym następuje przerwanie rekursywnego "dzielenia" problemu. Przypadek rekurencyjny z kolei jest to zapętlone wykonywanie instrukcji mających na celu "ćwiartowanie" problemu na coraz mniejsze części, aż do spełnienia określonego warunku np. osiągnięto dostateczny próg błędu, licznik iteracji doszedł do zadanego N i tak dalej.
Przykładem przypadku podstawowego może być pusty zbiór danych w algorytmie aproksymacyjnym rozwiązującym problem wędrującego komiwojażera jaki zaprezentowałem. Fakt, tam była pętla "while" sprawdzająca liczbę elementów, jednakże przypominam że każdą postać iteracyjną można przekształcić na postać rekurencyjną (jak nie wiecie o czym ja plotę, klikać tutaj) i bez problemu dałoby się dodawać kolejne miasta do trasy jeden po drugim za pomocą funkcji rekursywnej (wtedy trzeba byłoby wywoływać metodę usuwającą element w części rekurencyjnej). Przykładem przypadku rekurencyjnego może być sytuacja, kiedy jeszcze nie wyczerpano zbioru danych (trzymając się tego samego algorytmu), czyli posiada on co najmniej jeden element. Wtedy dajemy programowi do zrozumienia, że musi tak długo budować trasę dla komiwojażera, aż wszystkie miasta zostaną uwzględnione.
Należy bardzo uważać przy programowaniu podejściem "dziel i rządź" ze względu na naturę działania rekurencji. Kiedy nie uwzględnimy sprowadzenia do przypadku podstawowego, grozi nam działanie programu w kółko, aż do "słitaśnego" powiadomienia o przepełnieniu stosu ;).
KOD ŹRÓDŁOWY
Nie jest to wprawdzie konkretny problem do rozwiązania, aczkolwiek taki prosty przykład pomoże Wam dojść do sedna sprawy co autor miał na myśli. Dobra, dwie postacie tego samego algorytmu wypisującego aktualną wartość licznika iteracji w terminalu 100 razy (słodziutka Java, oczywiście):
KLASA "MAIN"
public class Main {
public static void main(String[] args) {
new DivideAndConquer();
}
}KLASA "DIVIDEANDCONQUER"
import java. io.PrintStream;
public class DivideAndConquer {
private final int end = 100;
private final PrintStream printStream = System.out;
public DivideAndConquer() {
int start = 1;
printStream.println("Wypisywanie iteracyjnie:");
printIteratively(start);
printStream.println("Wypisywanie rekurencyjnie:");
printRecursively(start);
}
private void printIteratively(int i) {
for (; i <= end; ++i) {
printStream.println(i);
}
}
private void printRecursively(int i) {
if(i <= end) {
printStream.println(i);
printRecursively(i + 1);
}
// dowolne instrukcje wykonywane w momencie "zawracania" do początku stosu
}
}Początkowo kod przedstawiający "dziel i rządź" może wyglądać niecodziennie, natomiast nie ma w nim niczego co wymagałoby przetrząśnięcia encyklopedii o informatyce. Za dane składowe podstawiłem warunek zakończenia funkcjonowania obu pętli (iteracyjnie i rekurencyjnie) oraz instancję typu "PrintStream", żeby sobie uprościć wyrażenia wywołań metod "println". W środku konstruktora, podstawiam początkową wartość licznika jako liczba całkowita i zasuwam z uruchamianiem obu podejść tego samego algorytmu wypisywania numerków w terminalu.
W metodzie wykonującej algorytm iteracyjnie mamy zwyczajną pętlę "for", w której to ustalamy warunek zakończenia w sposób jawny (i <= end). W środku niej wprowadzamy instrukcję wypisywania aktualnego stanu licznika i śluz. Zaś w podejściu rekursywnym, mamy z kolei instrukcję warunkową, która odgrywa bardzo ważną rolę i stanowi taką jakby "granicę" pomiędzy przypadkiem podstawowym, a przypadkiem rekurencyjnym. Przypadek rekurencyjny zachodzi w momencie wejścia do ciała instrukcji warunkowej po spełnieniu warunku (zwróćcie uwagę, że warunek jest taki sam, jak przy podejściu iteracyjnym!). W środku mamy to samo wypisywanie w terminalu, a potem mamy rekursywne wywołanie tej samej metody, ale ze zwiększonym licznikiem "i"!!! To oznacza, że za każdym razem gdy program wejdzie do środka instrukcji "if", cała metoda wywoła się ponownie i każdorazowo będzie sprawdzać ten sam warunek biorąc pod uwagę nowy stan licznika (to jest moment tego podziału). Dlatego pisałem o zadbaniu o przypadek podstawowy (który w tym przypadku będzie częścią "else"), gdyż bez inkrementacji program zapętliłby się w nieskończoność.
Zwrócę na sam koniec Waszą uwagę na komentarz jaki zostawiłem za instrukcją warunkową. Ci z Was, którzy nie do końca jeszcze rozumieją działania rekurencji, mogą się bardzo zdziwić kiedy obstawią że wszystko co tam zostanie zawarte, wykona się jeden raz. Wcale nie! Pamiętajcie, że rekursja to jest stos jednego bądź wielu wywołań tej samej metody, a co za tym idzie, po przerwaniu tego "łańcuszka" zapętlonych wywołań, program "wraca" do pierwszego stanu wywołania metody wykonując przy tym ZA KAŻDYM RAZEM resztę instrukcji, i dopiero wtedy kończy swoje działanie. Ale jak wspomniałem, wszystko w osobnym artykule.
W ramach lepszego zrozumienia zasady działania "dziel i rządź", polecę Wam poszukać w Internecie jakiegoś przykładowego algorytmu napisanego zarówno iteracyjnie (poznacie po pętli), jak i rekurencyjnie (poznacie po wywołaniu metody w treści tej samej metody), i najlepiej postawić te postacie obok siebie, żeby je mieć na widoku. Jak dostrzeżecie to "ćwiartowanie" problemu na mniejsze kawałki przy pomocy rekurencji, to składam gratulacje bo właśnie zrozumieliście "clue" tego terminu.
 |
"Dziel i rządź" (nazywane też "dziel i zwyciężaj") to technika "ćwiartująca" dany problem na mniejsze części używając rekurencyjnych wywołań metody.
I to wszystko na dziś! Radzę Wam jak dobry przyjaciel - nie pomijajcie tego tematu, gdyż jest jednym z kluczowych w dziedzinie algorytmiki.