Algorytm dziel i zwyciężaj - Divide-and-conquer algorithm

W informatyce , dziel i rządź jest paradygmat projektowania algorytm . Algorytm dziel i zwyciężaj rekursywnie dzieli problem na dwa lub więcej podproblemów tego samego lub pokrewnego typu, aż staną się one wystarczająco proste, aby można je było rozwiązać bezpośrednio. Rozwiązania podproblemów są następnie łączone w celu uzyskania rozwiązania pierwotnego problemu.

Technika dziel i przejęcie jest podstawą skutecznych algorytmów wiele problemów, takich jak sortowanie (np quicksort , scalania rodzaju ), mnożenia dużej liczby (np algorytm karacuby ) znalezienia najbliższego pary punktów , składniowej analizy ( np. parsery top-down ) i obliczanie dyskretnej transformacji Fouriera ( FFT ).

Projektowanie wydajnych algorytmów dziel i zwyciężaj może być trudne. Podobnie jak w przypadku indukcji matematycznej , często konieczne jest uogólnienie problemu, aby można go było rozwiązać rekurencyjnie. Prawidłowość algorytmu dziel i zwyciężaj zwykle potwierdza indukcja matematyczna, a jego koszt obliczeniowy jest często określany poprzez rozwiązywanie relacji rekurencyjnych .

Dziel i rządź

Metoda dziel i zwyciężaj, aby posortować listę (38, 27, 43, 3, 9, 82, 10) w kolejności rosnącej. Górna połowa: podział na podlisty; mid: lista jednoelementowa jest posortowana w trywialny sposób; dolna połowa: tworzenie posortowanych podlist.

Paradygmat dziel i zwyciężaj jest często używany do znalezienia optymalnego rozwiązania problemu. Jego podstawową ideą jest dekompozycja danego problemu na dwa lub więcej podobnych, ale prostszych podproblemów, aby kolejno je rozwiązać i komponować ich rozwiązania w celu rozwiązania danego problemu. Problemy o wystarczającej prostocie są rozwiązywane bezpośrednio. Na przykład, aby posortować podaną listę n liczb naturalnych, należy podzielić ją na dwie listy po około n /2 liczb każda, posortować każdą z nich po kolei i odpowiednio przełożyć oba wyniki, aby otrzymać posortowaną wersję danej listy (patrz zdjęcie). Takie podejście jest znane jako algorytm sortowania przez scalanie .

Nazwa „dziel i zwyciężaj” jest czasami stosowana do algorytmów, które redukują każdy problem tylko do jednego podproblemu, takich jak algorytm wyszukiwania binarnego do znajdowania rekordu na posortowanej liście (lub jego odpowiednik w obliczeniach numerycznych , algorytm bisekcji dla pierwiastka znalezienie ). Algorytmy te mogą być zaimplementowane wydajniej niż ogólne algorytmy dziel i zwyciężaj; w szczególności, jeśli używają rekurencji ogonowej , można je przekształcić w proste pętle . Jednak zgodnie z tą szeroką definicją każdy algorytm wykorzystujący rekurencję lub pętle można uznać za „algorytm dziel i zwyciężaj”. Dlatego niektórzy autorzy uważają, że nazwa „dziel i rządź” powinna być używana tylko wtedy, gdy każdy problem może generować dwa lub więcej podproblemów. Zamiast tego zaproponowano nazwę zmniejszanie i podbijanie dla klasy pojedynczego podproblemu.

Ważnym zastosowaniem metody dziel i rządź jest optymalizacja, gdzie jeśli przestrzeń poszukiwań jest redukowana ("przycinana") o stały współczynnik na każdym kroku, cały algorytm ma taką samą asymptotyczną złożoność jak krok przycinania, przy czym stała zależy od współczynnik przycinania (przez zsumowanie szeregu geometrycznego ); jest to znane jako prune i search .

Wczesne przykłady historyczne

Wczesne przykłady tych algorytmów są przede wszystkim zmniejszane i zwyciężane – pierwotny problem jest sukcesywnie dzielony na pojedyncze podproblemy i rzeczywiście można go rozwiązać iteracyjnie.

Wyszukiwanie binarne, algorytm zmniejszania i zwyciężania, w którym podproblemy mają mniej więcej połowę pierwotnego rozmiaru, ma długą historię. Podczas gdy jasny opis algorytmu na komputerach pojawił się w 1946 r. w artykule Johna Mauchly'ego , pomysł wykorzystania posortowanej listy elementów w celu ułatwienia wyszukiwania sięga co najmniej Babilonii w 200 r. p.n.e. Innym starożytnym algorytmem zmniejszania i zwyciężania jest algorytm Euklidesa do obliczania największego wspólnego dzielnika dwóch liczb przez sprowadzanie liczb do coraz mniejszych równoważnych podproblemów, datowany na kilka wieków przed naszą erą.

Wczesnym przykładem algorytmu dziel i zwyciężaj z wieloma podproblemami jest opis Gaussa z 1805 r., który nazywa się teraz algorytmem szybkiej transformacji Fouriera Cooleya-Tukeya (FFT), chociaż nie analizował on ilościowo jego operacji , nie stały się powszechne, dopóki nie zostały ponownie odkryte ponad sto lat później.

Wczesnym algorytmem D&C składającym się z dwóch podproblemów, opracowanym specjalnie dla komputerów i odpowiednio przeanalizowanym, jest algorytm sortowania przez scalanie , wynaleziony przez Johna von Neumanna w 1945 roku.

Innym godnym uwagi przykładem jest algorytm wynaleziony przez Anatolija A. Karatsubę w 1960 roku, który potrafił mnożyć w operacjach dwie liczby n- cyfrowe (w notacji Big O ). Algorytm ten obalił przypuszczenie Andrieja Kołmogorowa z 1956 r., że do wykonania tego zadania potrzebne będą operacje. ${\ Displaystyle O (n ^ {\ log _ {2} 3})}$ ${\ Displaystyle \ Omega (n ^ {2})}$

Jako kolejny przykład algorytmu dziel i zwyciężaj, który pierwotnie nie obejmował komputerów, Donald Knuth podaje metodę, której poczta zwykle używa do kierowania poczty: listy są sortowane w oddzielnych torebkach dla różnych obszarów geograficznych, każda z tych toreb jest sama sortowana na partie dla mniejszych podregionów i tak dalej, aż zostaną dostarczone. Jest to związane z sortowaniem radix , opisanym dla maszyn do sortowania kart perforowanych już w 1929 roku.

Zalety

Rozwiązywanie trudnych problemów

Dziel i rządź to potężne narzędzie do rozwiązywania koncepcyjnie trudnych problemów: wszystko, czego wymaga, to sposób na rozbicie problemu na podproblemy, rozwiązanie trywialnych przypadków i połączenie podproblemów z pierwotnym problemem. Podobnie, zmniejszanie i podbijanie wymaga tylko zredukowania problemu do jednego mniejszego problemu, takiego jak klasyczna łamigłówka Wieża Hanoi , która ogranicza przesuwanie wieży wysokości do przesuwania wieży wysokości . ${\ Displaystyle n}$ $n-1$

Wydajność algorytmu

Paradygmat dziel i zwyciężaj często pomaga w odkrywaniu wydajnych algorytmów. Był to klucz, na przykład, do szybkiej metody mnożenia Karatsuby, algorytmów szybkiego sortowania i sortowania przez scalanie, algorytmu Strassena do mnożenia macierzy i szybkich przekształceń Fouriera.

We wszystkich tych przykładach podejście D&C doprowadziło do poprawy asymptotycznego kosztu rozwiązania. Na przykład, jeśli (a) przypadki bazowe mają stałą wielkość, praca nad dzieleniem problemu i łączeniem rozwiązań częściowych jest proporcjonalna do wielkości problemu i (b) istnieje ograniczona liczba podproblemów o rozmiarze ~ na każdym etapie koszt algorytmu dziel i zwyciężaj będzie wynosił . ${\ Displaystyle n}$ $p$ $n/p$ ${\ Displaystyle O (n \ log _ {p} n)}$

Równoległość

Algorytmy typu „dziel i zwyciężaj” są naturalnie przystosowane do realizacji w maszynach wieloprocesorowych, zwłaszcza w systemach ze współdzieloną pamięcią , w których komunikacja danych między procesorami nie musi być planowana z wyprzedzeniem, ponieważ różne podproblemy mogą być wykonywane na różnych procesorach.

Dostęp do pamięci

Algorytmy typu „dziel i zwyciężaj” naturalnie mają tendencję do efektywnego wykorzystywania pamięci podręcznych . Powodem jest to, że gdy problem podrzędny jest wystarczająco mały, to i wszystkie jego podproblemy można zasadniczo rozwiązać w pamięci podręcznej, bez dostępu do wolniejszej pamięci głównej. Algorytm zaprojektowany do wykorzystywania pamięci podręcznej w ten sposób nazywa się cache-oblivious , ponieważ nie zawiera rozmiaru pamięci podręcznej jako jawnego parametru. Co więcej, algorytmy D&C można zaprojektować tak, aby ważne algorytmy (np. sortowanie, FFT i mnożenie macierzy) były optymalnymi algorytmami nieświadomymi pamięci podręcznej – wykorzystują pamięć podręczną w prawdopodobnie optymalny sposób, w sensie asymptotycznym, niezależnie od rozmiaru pamięci podręcznej. W przeciwieństwie do tego tradycyjne podejście do wykorzystywania pamięci podręcznej polega na blokowaniu , jak w przypadku optymalizacji gniazd pętli , gdzie problem jest jawnie podzielony na części o odpowiednim rozmiarze — to może również optymalnie wykorzystać pamięć podręczną, ale tylko wtedy, gdy algorytm jest dostrojony do konkretnego rozmiary pamięci podręcznej konkretnego komputera.

Ta sama zaleta istnieje w przypadku innych hierarchicznych systemów pamięci masowej, takich jak NUMA lub pamięć wirtualna , a także w przypadku wielu poziomów pamięci podręcznej: gdy problem podrzędny jest wystarczająco mały, można go rozwiązać na danym poziomie hierarchii, bez dostęp do wyższych (wolniejszych) poziomów.

Kontrola zaokrągleń

W obliczeniach z zaokrąglonymi arytmetykami, np. z liczbami zmiennoprzecinkowymi , algorytm dziel i zwyciężaj może dać dokładniejsze wyniki niż powierzchownie równoważna metoda iteracyjna. Na przykład, można dodać N liczb albo za pomocą prostej pętli, która dodaje każdą daną do pojedynczej zmiennej, albo za pomocą algorytmu D&C zwanego sumowaniem parami, który dzieli zbiór danych na dwie połowy, rekursywnie oblicza sumę każdej połowy, a następnie dodaje dwie sumy. Podczas gdy druga metoda wykonuje taką samą liczbę dodawania jak pierwsza i pokrywa koszty wywołań rekurencyjnych, jest zwykle bardziej dokładna.

Problemy wdrożeniowe

Rekurencja

Algorytmy typu „dziel i zwyciężaj” są naturalnie implementowane jako procedury rekurencyjne . W takim przypadku częściowe podproblemy prowadzące do tego, który jest aktualnie rozwiązywany, są automatycznie zapisywane w stosie wywołań procedury . Funkcja rekurencyjna to funkcja, która wywołuje siebie w ramach swojej definicji.

Wyraźny stos

Algorytmy typu „dziel i zwyciężaj” mogą być również zaimplementowane przez program nierekurencyjny, który przechowuje częściowe podproblemy w jakiejś jawnej strukturze danych, takiej jak stos , kolejka lub kolejka priorytetowa . Takie podejście pozwala na większą swobodę w wyborze sub-problem, który należy rozwiązać, obok funkcji, które są ważne w niektórych zastosowaniach - np w wszerz rekursji oraz oddział-and-bound metody optymalizacji funkcji. Takie podejście jest również standardowym rozwiązaniem w językach programowania, które nie zapewniają obsługi procedur rekurencyjnych.

Rozmiar stosu

W rekurencyjnych implementacjach algorytmów D&C należy upewnić się, że jest wystarczająca ilość pamięci przydzielonej dla stosu rekurencji, w przeciwnym razie wykonanie może się nie powieść z powodu przepełnienia stosu . Algorytmy D&C, które są wydajne czasowo, często mają stosunkowo małą głębokość rekurencji. Na przykład algorytm szybkiego sortowania można zaimplementować tak, aby nigdy nie wymagał więcej niż zagnieżdżonych wywołań rekurencyjnych do sortowania elementów. $\log_{2}n$ ${\ Displaystyle n}$

Przepełnienie stosu może być trudne do uniknięcia podczas korzystania z procedur rekurencyjnych, ponieważ wiele kompilatorów zakłada, że stos rekurencji jest ciągłym obszarem pamięci, a niektóre przydzielają mu stałą ilość miejsca. Kompilatory mogą również zapisać więcej informacji w stosie rekurencji niż jest to absolutnie konieczne, takie jak adres zwrotny, niezmienne parametry i zmienne wewnętrzne procedury. W ten sposób ryzyko przepełnienia stosu można zmniejszyć, minimalizując parametry i zmienne wewnętrzne procedury rekurencyjnej lub stosując jawną strukturę stosu.

Wybór bazowych etui

W każdym algorytmie rekurencyjnym istnieje duża dowolność w doborze przypadków bazowych , czyli małych podproblemów, które są rozwiązywane bezpośrednio w celu zakończenia rekurencji.

Wybór najmniejszych lub najprostszych możliwych przypadków bazowych jest bardziej elegancki i zwykle prowadzi do prostszych programów, ponieważ jest mniej przypadków do rozważenia i są one łatwiejsze do rozwiązania. Na przykład algorytm FFT może zatrzymać rekurencję, gdy dane wejściowe są pojedynczą próbką, a algorytm sortowania listy szybkiego sortowania może zatrzymać się, gdy dane wejściowe są pustą listą; w obu przykładach jest tylko jeden przypadek bazowy do rozważenia i nie wymaga on przetwarzania.

Z drugiej strony wydajność często poprawia się, jeśli rekurencja zostaje zatrzymana przy stosunkowo dużych przypadkach bazowych, a te są rozwiązywane nierekurencyjnie, co skutkuje algorytmem hybrydowym . Ta strategia pozwala uniknąć narzutu wywołań rekurencyjnych, które wykonują niewiele pracy lub nie wykonują żadnej pracy, a także mogą pozwalać na użycie wyspecjalizowanych algorytmów nierekurencyjnych, które w tych przypadkach bazowych są bardziej wydajne niż jawna rekursja. Ogólna procedura dla prostego hybrydowego algorytmu rekurencyjnego polega na zwarciu przypadku podstawowego , znanego również jako rekurencja na długość ramienia . W tym przypadku to, czy następny krok spowoduje, że przypadek podstawowy będzie sprawdzany przed wywołaniem funkcji, pozwala uniknąć niepotrzebnego wywołania funkcji. Na przykład w drzewie, zamiast rekursywnie do węzła podrzędnego, a następnie sprawdzanie, czy jest null, sprawdzanie null przed rekurencją; unika połowy wywołań funkcji w niektórych algorytmach na drzewach binarnych. Ponieważ algorytm D&C ostatecznie redukuje każdy problem lub instancję podproblemu do dużej liczby instancji podstawowych, często dominują one nad ogólnym kosztem algorytmu, zwłaszcza gdy narzut związany z dzieleniem/łączeniem jest niski. Należy zauważyć, że te rozważania nie zależą od tego, czy rekursja jest implementowana przez kompilator, czy przez jawny stos.

Na przykład wiele bibliotecznych implementacji szybkiego sortowania przełączy się na prosty algorytm sortowania z wstawianiem (lub podobny) oparty na pętli, gdy liczba elementów do posortowania jest wystarczająco mała. Zauważ, że jeśli pusta lista byłaby jedynym przypadkiem podstawowym, sortowanie listy z wpisami wiązałoby się z maksymalnie szybkim sortowaniem wywołań, które nie zrobiłyby nic poza natychmiastowym powrotem. Zwiększenie przypadków bazowych do list o rozmiarze 2 lub mniejszym wyeliminuje większość tych wywołań typu „nic nie rób”, a bardziej ogólnie przypadek bazowy większy niż 2 jest zwykle używany do zmniejszenia ułamka czasu spędzonego na narzutach wywołań funkcji lub manipulacji stosem. ${\ Displaystyle n}$ ${\ Displaystyle n}$

Alternatywnie można zastosować duże przypadki bazowe, które nadal używają algorytmu dziel i zwyciężaj, ale zaimplementuj algorytm dla z góry określonego zestawu stałych rozmiarów, gdzie algorytm może zostać całkowicie rozwinięty w kod, który nie ma rekurencji, pętli ani warunków (związanych z technika oceny cząstkowej ). Na przykład to podejście jest stosowane w niektórych wydajnych implementacjach FFT, gdzie przypadki bazowe są nierozwiniętymi implementacjami algorytmów FFT typu dziel i zwyciężaj dla zestawu stałych rozmiarów. Metody generowania kodu źródłowego mogą być wykorzystywane do tworzenia dużej liczby oddzielnych przypadków bazowych, pożądanych do efektywnej realizacji tej strategii.

Uogólniona wersja tego pomysłu jest znana jako rekurencja „rozwijanie” lub „zgrubienie” i zaproponowano różne techniki automatyzacji procedury powiększania przypadku bazowego.

Udostępnianie powtarzających się podproblemów

W przypadku niektórych problemów rekurencja rozgałęziona może zakończyć się wielokrotną oceną tego samego podproblemu. W takich przypadkach warto zidentyfikować i zapisać rozwiązania tych nakładających się podproblemów, technika ta jest powszechnie znana jako zapamiętywanie . Podążając do granic możliwości, prowadzi to do oddolnych algorytmów dziel i zwyciężaj, takich jak programowanie dynamiczne i parsowanie wykresów .

Languages

In other projects