Algoritmus rozděl a panuj- Divide-and-conquer algorithm

Ve vědě o počítačích , rozděl a panuj je návrh algoritmu paradigma . Algoritmus rozděl a panuj rekurzivně rozděluje problém na dva nebo více dílčích problémů stejného nebo příbuzného typu, dokud nejsou dostatečně jednoduché, aby je bylo možné přímo vyřešit. Řešení dílčích problémů se pak spojí, aby poskytlo řešení původního problému.

Technika rozděl a panuj je základem efektivních algoritmů pro mnoho problémů, jako je třídění (např. Quicksort , merge sort ), násobení velkých čísel (např. Algoritmus Karatsuba ), hledání nejbližší dvojice bodů , syntaktická analýza ( např top-down analyzátory ) a výpočtem z diskrétní Fourierova transformace ( FFT ).

Navrhování efektivních algoritmů rozděl a panuj může být obtížné. Stejně jako v matematické indukci je často nutné problém zobecnit, aby byl přístupný rekurzivnímu řešení. Správnost algoritmu rozděl a panuj je obvykle prokázána matematickou indukcí a jeho výpočetní náklady jsou často určeny řešením relací opakování .

Rozděl a panuj

Přístup rozděl a panuj k seřazení seznamu (38, 27, 43, 3, 9, 82, 10) ve vzrůstajícím pořadí. Horní polovina: rozdělení do dílčích seznamů; mid: jednoprvkový seznam je triviálně seřazen; dolní polovina: skládání seřazených podseznamů.

Paradigma rozděl a panuj se často používá k nalezení optimálního řešení problému. Jeho základní myšlenkou je rozložit daný problém na dva nebo více podobných, ale jednodušších, podproblémů, postupně je vyřešit a sestavit jejich řešení k vyřešení daného problému. Problémy dostatečné jednoduchosti jsou řešeny přímo. Chcete -li například setřídit daný seznam n přirozených čísel, rozdělte jej na dva seznamy po přibližně n /2 číslech, postupně je seřaďte a oba výsledky vhodně prokládejte, abyste získali seřazenou verzi daného seznamu (viz obrázek). Tento přístup je známý jako algoritmus sloučení řazení .

Název „rozděl a panuj“ je někdy používán pro algoritmy, které redukují každý problém pouze na jeden dílčí problém, jako je algoritmus binárního vyhledávání pro nalezení záznamu v seřazeném seznamu (nebo jeho analog v numerickém počítání , půlící algoritmus pro root) nález ). Tyto algoritmy lze implementovat efektivněji než obecné algoritmy rozděl a panuj; zejména pokud používají rekurzi ocasu , lze je převést na jednoduché smyčky . Podle této široké definice by však každý algoritmus, který používá rekurzi nebo smyčky, mohl být považován za „algoritmus rozděl a panuj“. Někteří autoři se proto domnívají, že název „rozděl a panuj“ by měl být používán pouze tehdy, když každý problém může generovat dva nebo více podproblémů. Místo toho bylo pro třídu s jedním podproblémem navrženo snížení názvu a dobytí .

Důležitá aplikace rozděl a panuj je v optimalizaci, kde pokud je vyhledávací prostor zmenšen („ořezán“) konstantním faktorem v každém kroku, má celkový algoritmus stejnou asymptotickou složitost jako krok prořezávání, přičemž konstanta závisí na faktor prořezávání (součtem geometrických řad ); toto je známé jako švestka a hledání .

Rané historické příklady

Počáteční příklady těchto algoritmů jsou primárně omezeny a dobývány - původní problém je postupně rozdělen na jednotlivé dílčí problémy a lze jej skutečně vyřešit iterativně.

Binární vyhledávání, algoritmus snižování a dobývání, kde dílčí problémy mají zhruba polovinu původní velikosti, má dlouhou historii. Zatímco v roce 1946 se v článku Johna Mauchlyho objevil jasný popis algoritmu na počítačích , myšlenka použít seřazený seznam položek k usnadnění vyhledávání sahá přinejmenším až do Babylonie v roce 200 př. N. L. Dalším starověkým algoritmem snižování a dobývání je euklidovský algoritmus pro výpočet největšího společného dělitele dvou čísel snížením čísel na menší a menší ekvivalentní podproblémy, které se datují do několika století před naším letopočtem.

Časným příkladem algoritmu rozděl a panuj s více podproblémy je Gaussův popis 1805 toho, co se nyní nazývá algoritmus Cooley-Tukeyovy rychlé Fourierovy transformace (FFT), ačkoli kvantitativně neanalyzoval počet jeho operací a FFT ano se nerozšířily, dokud nebyly znovu objeveny o více než století později.

Časný algoritmus D & C se dvěma podproblémy, který byl speciálně vyvinut pro počítače a řádně analyzován, je algoritmus sloučení , který vynalezl John von Neumann v roce 1945.

Dalším pozoruhodným příkladem je algoritmus vynalezený Anatolii A. Karatsubou v roce 1960, který by mohl znásobit dvě n -číselná čísla v operacích (v notaci Big O ). Tento algoritmus vyvrátil dohady Andrey Kolmogorova z roku 1956, že pro tento úkol budou nutné operace. ${\ displaystyle O (n^{\ log _ {2} 3})}$ ${\ displaystyle \ Omega (n^{2})}$

Jako další příklad algoritmu rozděl a panuj, který původně nezahrnoval počítače, uvádí Donald Knuth metodu, kterou pošta obvykle používá ke směrování pošty: dopisy jsou tříděny do samostatných pytlů pro různé geografické oblasti, přičemž každý z těchto pytlů je tříděn sám do dávek pro menší podoblasti a tak dále, dokud nejsou dodány. To souvisí s radixovým tříděním , popsaným pro stroje na třídění děrných karet již v roce 1929.

Výhody

Řešení obtížných problémů

Divide and conquer je účinný nástroj pro řešení koncepčně obtížných problémů: vše, co vyžaduje, je způsob rozdělení problému na dílčí problémy, řešení triviálních případů a kombinace dílčích problémů s původním problémem. Podobně snížení a dobytí vyžaduje pouze snížení problému na jeden menší problém, jako je například klasická hádanka Tower of Hanoi , která redukuje přesun výškové věže na přesun výškové věže . ${\ displaystyle n}$ ${\ displaystyle n-1}$

Účinnost algoritmu

Paradigma rozděl a panuj často pomáhá při objevování efektivních algoritmů. Byl to klíč například pro rychlou multiplikační metodu Karatsuba, algoritmy quicksort a mergesort, Strassenův algoritmus pro maticové násobení a rychlé Fourierovy transformace.

Ve všech těchto příkladech vedl přístup D&C ke zlepšení asymptotických nákladů na řešení. Například pokud (a) základní případy mají velikost s konstantním ohraničením, práce na rozdělení problému a kombinování dílčích řešení je úměrná velikosti problému a (b) existuje omezený počet dílčích problémů velikosti ~ v každé fázi pak budou náklady na algoritmus rozděl a panuj . ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle n/p}$ ${\ Displaystyle O (n \ log _ {p} n)}$

Rovnoběžnost

Algoritmy Divide-and-Conquer jsou přirozeně přizpůsobeny pro provádění na víceprocesorových strojích, zejména v systémech se sdílenou pamětí, kde komunikaci dat mezi procesory není třeba předem plánovat, protože na různých procesorech lze provádět odlišné dílčí problémy.

Přístup do paměti

Algoritmy rozděl a panuj přirozeně obvykle efektivně využívají paměťové mezipaměti . Důvodem je, že jakmile je dílčí problém dostatečně malý, lze jej i všechny jeho dílčí problémy v zásadě vyřešit v mezipaměti, aniž by se přistupovalo k pomalejší hlavní paměti. Algoritmus navržený k využití mezipaměti tímto způsobem se nazývá zapomnění na mezipaměť , protože jako explicitní parametr neobsahuje velikost mezipaměti. Algoritmy D&C mohou být navíc navrženy tak, aby důležité algoritmy (např. Třídění, FFT a násobení matic) byly optimálními algoritmy bez paměti cache-používají mezipaměť pravděpodobně optimálním způsobem, v asymptotickém smyslu, bez ohledu na velikost mezipaměti. Naproti tomu tradiční přístup k využívání mezipaměti je blokování , jako při optimalizaci smyčkového hnízda , kde je problém výslovně rozdělen na bloky příslušné velikosti - to může také mezipaměť optimálně využívat, ale pouze tehdy, když je algoritmus vyladěn pro konkrétní velikosti mezipaměti konkrétního počítače.

Stejná výhoda existuje s ohledem na další hierarchické úložné systémy, jako je NUMA nebo virtuální paměť , a také pro více úrovní mezipaměti: jakmile je dílčí problém dostatečně malý, lze jej vyřešit v rámci dané úrovně hierarchie, bez přístup k vyšším (pomalejším) úrovním.

Zaokrouhlení ovládání

Při výpočtech se zaoblenou aritmetikou, např. S čísly s plovoucí desetinnou čárkou , může algoritmus rozděl a panuj získat přesnější výsledky než povrchně ekvivalentní iterační metoda. Například lze přidat N čísel buď jednoduchou smyčkou, která přidá každý vztažný bod k jedné proměnné, nebo algoritmem D & C nazývaným párová sumace, která rozbije datovou sadu na dvě poloviny, rekurzivně vypočítá součet každé poloviny a poté sečte ty dvě částky. Zatímco druhá metoda provádí stejný počet přírůstků jako první a platí režii rekurzivních hovorů, je obvykle přesnější.

Problémy s implementací

Rekurze

Algoritmy rozděl a panuj jsou přirozeně implementovány jako rekurzivní procedury . V takovém případě se dílčí dílčí problémy vedoucí k aktuálně řešenému automaticky ukládají do zásobníku volání procedur . Rekurzivní funkce je funkce, která se sama volá v rámci své definice.

Explicitní zásobník

Algoritmy rozděl a chyť lze také implementovat nerekurzivním programem, který ukládá dílčí dílčí problémy do nějaké explicitní datové struktury, jako je zásobník , fronta nebo prioritní fronta . Tento přístup umožňuje větší volnost při výběru dílčího problému, který je třeba řešit další, což je funkce, která je důležitá v některých aplikacích - například v šířky první rekurze a větví a vázané metoda pro optimalizaci funkce. Tento přístup je také standardním řešením v programovacích jazycích, které neposkytují podporu rekurzivních procedur.

Velikost zásobníku

V rekurzivních implementacích algoritmů D & C je třeba se ujistit, že pro rekurzivní zásobník je přidělena dostatečná paměť, v opačném případě může spuštění selhat kvůli přetečení zásobníku . Algoritmy D&C, které jsou časově efektivní, mají často relativně malou hloubku rekurze. Algoritmus quicksort lze například implementovat tak, že k třídění položek nikdy nevyžaduje více než vnořená rekurzivní volání . ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle n}$

Přetečení zásobníku může být obtížné vyhnout se při použití rekurzivních procedur, protože mnoho kompilátorů předpokládá, že rekurzivní zásobník je souvislou oblastí paměti a někteří pro něj přidělují pevné množství místa. Kompilátory mohou také ukládat do rekurzivního zásobníku více informací, než je nezbytně nutné, například návratovou adresu, neměnné parametry a interní proměnné procedury. Riziko přetečení zásobníku lze tedy snížit minimalizací parametrů a interních proměnných rekurzivní procedury nebo použitím explicitní struktury zásobníku.

Výběr základních případů

V každém rekurzivním algoritmu existuje značná volnost při výběru základních případů , malých podproblémů, které jsou řešeny přímo za účelem ukončení rekurze.

Výběr nejmenších nebo nejjednodušších možných základních případů je elegantnější a obvykle vede k jednodušším programům, protože je třeba zvážit méně případů a jejich řešení je snazší. Algoritmus FFT by například mohl zastavit rekurzi, pokud je vstupem jeden vzorek, a algoritmus řazení v rychlém řazení by se mohl zastavit, pokud je vstup prázdný seznam; v obou příkladech je třeba vzít v úvahu pouze jeden základní případ a nevyžaduje žádné zpracování.

Na druhou stranu se účinnost často zlepšuje, pokud je rekurze zastavena v relativně velkých základních případech, a ty jsou řešeny nerekurzivně, což vede k hybridnímu algoritmu . Tato strategie se vyhýbá režii rekurzivních hovorů, které dělají malou nebo žádnou práci, a může také umožnit použití specializovaných nerekurzivních algoritmů, které jsou v těchto základních případech účinnější než explicitní rekurze. Obecným postupem pro jednoduchý hybridní rekurzivní algoritmus je zkratování základního případu , známé také jako rekurze na délku paže . V tomto případě se před voláním funkce zkontroluje, zda další krok bude mít za následek základní případ, čímž se vyhnete zbytečnému volání funkce. Například ve stromu, místo aby se opakoval na podřízený uzel a poté zkontroloval, zda je null, kontroluje null před opakováním; vyhýbá se polovině volání funkcí v některých algoritmech na binárních stromech. Protože algoritmus D&C nakonec redukuje každou instanci problému nebo dílčího problému na velký počet základních instancí, často dominují celkovým nákladům na algoritmus, zvláště když režie rozdělení/spojování je nízká. Všimněte si, že tyto úvahy nezávisí na tom, zda je rekurze implementována kompilátorem nebo explicitním zásobníkem.

Například například mnoho knihovních implementací quicksortu přejde na jednoduchý algoritmus řazení (nebo podobný) na základě smyčky, jakmile bude počet položek, které mají být tříděny, dostatečně malý. Všimněte si, že pokud by byl prázdný seznam jediným základním případem, třídění seznamu podle záznamů by znamenalo maximálně rychlé řazení, které by neudělalo nic jiného než okamžité vrácení. Zvětšení základních případů na seznamy velikosti 2 nebo menší odstraní většinu těchto volání typu „nic nedělat“ a obecněji se základní případ větší než 2 obvykle používá ke snížení zlomku času stráveného při režijním volání nebo manipulaci s funkcemi volání funkcí. ${\ displaystyle n}$ ${\ displaystyle n}$

Alternativně lze použít velké základní případy, které stále používají algoritmus rozděl a panuj, ale implementujte algoritmus pro předem stanovenou sadu pevných velikostí, kde lze algoritmus zcela rozvinout do kódu, který nemá žádnou rekurzi, smyčky nebo podmíněné (související s technika dílčího hodnocení ). Tento přístup se například používá v některých efektivních implementacích FFT, kde jsou základními případy rozvinuté implementace algoritmů FFT typu rozděl a panuj pro sadu pevných velikostí. Metody generování zdrojového kódu mohou být použity k vytvoření velkého počtu samostatných základních případů, které jsou žádoucí k efektivní implementaci této strategie.

Zobecněná verze této myšlenky je známá jako rekurzivní „odvíjení“ nebo „hrubnutí“ a byly navrženy různé techniky pro automatizaci postupu zvětšování základní skříně.

Sdílení opakovaných podproblémů

U některých problémů může rozvětvená rekurze skončit hodnocením stejného dílčího problému mnohokrát. V takových případech může být užitečné identifikovat a uložit řešení těchto překrývajících se podproblémů, technika je běžně známá jako memoizace . Následováno limitem vede k algoritmům rozděl a panuj zdola nahoru, jako je dynamické programování a analýza grafů .

Languages

In other projects