Rozděl a panuj (informatika)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. ledna 2021; kontroly vyžadují 22 úprav .

Rozděl a panuj v informatice je paradigma vývoje algoritmu , které spočívá v rekurzivním rozdělování řešeného problému do dvou nebo více dílčích úkolů stejného typu, ale menší velikosti, a kombinování jejich řešení za účelem získání odpovědi na původní problém; oddíly se provádějí, dokud nejsou všechny dílčí úkoly základní.

Pochopení a navrhování algoritmů Divide and Conquer je komplexní dovednost, která vyžaduje dobré porozumění povaze základního problému, který má být vyřešen. Stejně jako u dokazování věty matematickou indukcí je často nutné nahradit původní problém obecnějším nebo složitějším problémem pro inicializaci rekurze a neexistuje žádná systematická metoda pro nalezení správného zobecnění. Takové složitosti metody rozděl a panuj jsou vidět při optimalizaci výpočtu Fibonacciho čísla s účinnou dvojitou rekurzí.

Správnost algoritmu podle paradigmatu "Rozděl a panuj" se nejčastěji dokazuje metodou matematické indukce a doba běhu se určuje buď přímo řešením odpovídající rekurentní rovnice , nebo aplikací věty o hlavním rekurentním vztahu .

Rozděl a panuj

Paradigma rozděl a panuj se často používá k nalezení optimálního řešení konkrétního problému. Jeho hlavní myšlenkou je rozložit daný problém na dva nebo více podobných, ale jednodušších podproblémů, jeden po druhém je vyřešit a poskládat jejich řešení. Chcete-li například seřadit daný seznam n přirozených čísel, musíte jej rozdělit na dva seznamy po n /2 číslech, každý z nich postupně seřadit a oba výsledky podle toho uspořádat, abyste získali seřazenou verzi tohoto seznamu ( viz obrázek). Tento přístup je známý jako algoritmus řazení sloučení .

Název "Divide and Conquer" se někdy používá pro algoritmy, které redukují každý problém pouze na jeden dílčí problém, jako je binární vyhledávací algoritmus pro nalezení položky v seřazeném seznamu (nebo jeho speciální případ, algoritmus bisekce pro nalezení kořenů). [1] Tyto algoritmy lze implementovat efektivněji než obecné algoritmy Divide and Conquer; zejména, pokud používají rekurzi ocasu , mohou být převedeny na jednoduché smyčky . Nicméně, podle této široké definice, každý algoritmus, který používá rekurzi nebo smyčky, může být považován za „algoritmus rozděl a panuj“. Někteří autoři se proto domnívají, že název „Divide and Conquer“ by se měl používat pouze tehdy, když každý úkol může způsobit dva nebo více dílčích úkolů. [2] Místo toho bylo pro třídu jednotlivých problémů navrženo jméno redukovat a dobýt . [3]

Příklady

Rané příklady takových algoritmů jsou primárně "Reduce and Conquer" - původní problém je postupně rozdělen na samostatné dílčí problémy a ve skutečnosti může být řešen iterativně.

Binární vyhledávání, algoritmus „Reduce and Conquer“, ve kterém jsou dílčí problémy zhruba poloviční oproti původní velikosti, má dlouhou historii. I když jasný popis algoritmu na počítačích se objevil již v roce 1946 v článku Johna Mauchlyho . Myšlenka použít setříděný seznam položek pro usnadnění vyhledávání sahá přinejmenším do Babylonie v roce 200 před naším letopočtem. [4] Dalším starověkým algoritmem redukce-a-dobýt je Euklidův algoritmus pro výpočet největšího společného dělitele dvou čísel redukcí čísel na menší a menší ekvivalentní dílčí problémy, který se datuje několik století před naším letopočtem.

Raným příkladem algoritmu Divide and Conquer s více dílčími problémy je Gaussův (1805) popis toho, co se nyní nazývá Cooley-Tukey Fast Fourier Transform [5] .

Raný algoritmus Divide and Conquer se dvěma dílčími problémy, který byl speciálně navržen pro počítače a řádně analyzován, je algoritmus slučovacího řazení, který vynalezl John von Neumann v roce 1945. [6]

Typickým příkladem je slučovací třídicí algoritmus . Chcete-li seřadit pole čísel ve vzestupném pořadí, rozdělí se na dvě stejné části, každá se seřadí a poté se seřazené části sloučí do jedné. Tento postup se aplikuje na každou z částí, pokud část pole, která má být seřazena, obsahuje alespoň dva prvky (aby bylo možné ji rozdělit na dvě části). Doba běhu tohoto algoritmu jsou operace, zatímco jednodušší algoritmy vyžadují čas, kde je velikost původního pole. $O(n\log n)$ $O(n^{2})$ $n$

Dalším pozoruhodným příkladem je algoritmus, který vynalezl Anatoly Aleksandrovich Karatsuba v roce 1960 [7] pro násobení dvou čísel z n číslic číslem operace ( velká notace O ). Tento algoritmus vyvrátil hypotézu Andreje Kolmogorova z roku 1956, že tento úkol bude vyžadovat operace. $O(n^{\log _{2}3})$ $O(n^{2})$

Jako další příklad algoritmu Divide and Conquer, který původně nepoužíval počítače. Donald Knuth uvádí metodu běžně používanou poštou pro směrování pošty: dopisy jsou tříděny do samostatných balíčků určených pro různé geografické oblasti, každý z těchto balíčků je sám roztříděn do dávek pro menší subregiony a tak dále, dokud nejsou doručeny. [4] Souvisí to s radix sort , popsaným pro stroje na třídění děrných štítků již v roce 1929. [čtyři]

Výhody

Řešení složitých problémů

Divide and Conquer je mocný nástroj pro řešení koncepčně složitých problémů: vše, co je potřeba, je najít případ rozdělení problému na dílčí problémy, řešení triviálních případů a zkombinování dílčích problémů do původního problému. Podobně, Reduce and Conquer vyžaduje pouze redukci problému na jeden menší problém, jako je klasická Hanojská věž , která redukuje řešení přesunutí věže o výšce n na přesun věže o výšce n − 1.

Účinnost algoritmu

Paradigma rozděl a panuj často pomáhá při objevování účinných algoritmů. To bylo klíčem například k rychlé metodě násobení Karatsuba, algoritmům quicksort a mergesort , Strassenovu algoritmu pro maticové násobení a rychlým Fourierovým transformacím.

Ve všech těchto příkladech vedl přístup Divide and Conquer ke zlepšení asymptotických nákladů na řešení v samotném řešení. Například, pokud (a) má základní případ velikost ohraničenou konstantou, pak práce na rozdělení problému a kombinování dílčích řešení je úměrná velikosti problému n, a (b) existuje omezený počet p podproblémů velikost ~n/p v každé fázi, pak účinnost algoritmu je "Rozděl a panuj bude O( n  log p n ).

Souběh

Algoritmy Divide and Conquer jsou přirozeně přizpůsobeny pro běh na víceprocesorových strojích, zejména na systémech se sdílenou pamětí , ve kterých není třeba přenosy dat mezi procesory plánovat předem, protože jednotlivé dílčí úlohy mohou běžet na různých procesorech.

Přístup do paměti

Algoritmy Divide and Conquer přirozeně inklinují k efektivnímu využití mezipaměti . Důvodem je, že jakmile je dílčí úkol dostatečně malý, lze jej a všechny jeho dílčí úkoly v zásadě vyřešit v mezipaměti bez přístupu k pomalejší hlavní paměti. Algoritmus pro použití mezipaměti tímto způsobem se nazývá cache-oblivious , protože nezahrnuje velikost mezipaměti jako explicitní parametr. [8] Algoritmy Divide and Conquer mohou být navíc navrženy pro důležité algoritmy (např. třídění, FFT a násobení matic), aby se staly optimálními algoritmy, které nezapomínají na vyrovnávací paměť – používají mezipaměť pravděpodobně optimálním způsobem, v asymptotickém smyslu, bez ohledu na velikosti mezipaměti. Naproti tomu tradičním přístupem k použití mezipaměti je blokování, jako je tomu u optimalizace vnořené smyčky , kde je úloha explicitně rozdělena na části vhodné velikosti - to může také optimálně využít mezipaměť, ale pouze v případě, že je algoritmus vyladěn pro konkrétní velikost mezipaměti. konkrétního stroje.

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

Problémy s aplikací

Rekurze

Algoritmy dělení a panování jsou přirozeně aplikovány ve formě rekurzivních metod . V tomto případě jsou soukromé dílčí úkoly vedoucí k právě řešenému úkolu automaticky uloženy do zásobníku volání procedury . Rekurzivní funkce je numerická funkce numerického argumentu, která obsahuje sama sebe ve svém zápisu.

Explicitní zásobník

Algoritmy dělení a panování mohou být také aplikovány nerekurzivním programem, který ukládá soukromé 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ší svobodu ve výběru, který dílčí problém musí být vyřešen jako další. Funkce, která je v některých aplikacích důležitá – například ve způsobu větvení a propojování pro optimalizaci funkcí. Tento přístup je také standardní v programovacích jazycích, které nepodporují rekurzivní procedury.

Velikost zásobníku

V rekurzivních implementacích algoritmů Divide and Conquer je třeba zajistit, aby bylo pro zásobník rekurze alokováno dostatek paměti, jinak může provádění selhat kvůli přetečení zásobníku . Algoritmy dělení a panování, které jsou časově efektivní, mají často relativně malou hloubku rekurze. Například algoritmus quicksort lze implementovat tak, že nikdy nevyžaduje více než log2 n vnořených rekurzivních volání pro třídění n prvků.

Při použití rekurzivních rutin může být obtížné vyhnout se přetečení zásobníku, protože mnoho kompilátorů předpokládá, že zásobník rekurze je v paměti souvislý, a některé mu přidělují pevné množství místa. Kompilátory mohou také uložit více informací na rekurzním zásobníku, než je nezbytně nutné, jako je návratová adresa, neměnné parametry a vnitřní proměnné procedur. Riziko přetečení zásobníku lze tedy snížit minimalizací parametrů a vnitřních proměnných rekurzivní procedury nebo použitím explicitní struktury zásobníku.

Výběr ze základních možností

V každém rekurzivním algoritmu existuje značná volnost ve výběru základních případů, malých dílčích problémů, které se řeší přímo k dokončení rekurze.

Volba 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 potřeba uvažovat méně případů a snáze se řeší. Například FFT může zastavit rekurzi, když je vstupem jeden vzorek, a algoritmus rychlého třídění pro seznam se může zastavit, když je vstupem prázdný seznam; v obou příkladech je k uvážení pouze jeden základní případ a není třeba jej zpracovávat.

Na druhé straně se efektivita často zlepší, pokud se rekurze zastaví na relativně velkých základních případech a ty se řeší nerekurzivně, což vede k hybridnímu algoritmu . Tato strategie se vyhýbá překrývajícím se rekurzivním voláním, která dělají jen 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 efektivnější než explicitní rekurze. Obecným postupem pro jednoduchý hybridní rekurzivní algoritmus je zkratování základního případu, známého také jako rekurze ramenní délky . V tomto případě se před voláním funkce zkontroluje, zda další krok povede do základního registru, čímž se zabrání zbytečnému volání funkce. Protože algoritmus Divide and Conquer nakonec redukuje každou instanci problému nebo dílčího problému na velký počet základních instancí, často dominuje celkové efektivitě algoritmu, zvláště když je režie rozdělení/spojení nízká. Navíc tyto úvahy nezávisí na tom, zda je rekurze implementována kompilátorem nebo explicitním zásobníkem.

Tak se například mnoho knihovních aplikací quicksortu změní na jednoduchý algoritmus řazení na bázi smyčky (nebo podobný), jakmile bude počet prvků, které mají být tříděny, dostatečně malý. Pokud by navíc byl prázdný seznam jediným základním případem, pak by třídění seznamu s n položkami vedlo k maximálně n počtu volání rychlého třídění, která by nedělala nic jiného, než že by se okamžitě vrátila. Zvýšení základních případů na seznamy velikosti 2 nebo menší odstraní většinu těchto volání „nedělat nic“ a obecněji se základní případ větší než 2 obvykle používá ke snížení podílu času stráveného úklidem nebo manipulací se zásobníky.

Alternativně lze použít velké základní případy, které stále používají algoritmus Divide and Conquer, ale implementují algoritmus pro předdefinovanou sadu pevných velikostí, kde lze algoritmus plně rozšířit do kódu , který nemá rekurzi, smyčky nebo konvence (s tím spojené s metodou částečného hodnocení ). Tento přístup se například používá v některých efektivních aplikacích FFT, kde jsou základními případy rozšířené implementace algoritmů FFT Divide and Conquer pro sadu pevných velikostí. [9] Techniky generování zdrojového kódu lze použít ke generování velkého počtu odlišných základních případů požadovaných pro efektivní implementaci této strategie.

Zobecněná verze této myšlenky je známá jako „rozšiřovat“ nebo „růst“ rekurze a byly navrženy různé metody pro automatizaci postupu rozšiřování základního případu. [9]

Sdílení opakujících se dílčích úkolů

U některých úloh může mít větvená rekurze za následek více vyhodnocení stejné dílčí úlohy. 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 dílčích problémů, což je technika běžně známá jako memoizace . Po dosažení limitu to vede k algoritmům rozdělování a panování zdola nahoru, jako je dynamické programování a analýza diagramů .

Viz také

Poznámky

↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Úvod do algoritmů (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
↑ Brassard, G. a Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
↑ Anany V. Levitin, Úvod do návrhu a analýzy algoritmů (Addison Wesley, 2002).
↑ 1 2 3 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching , druhé vydání (Addison-Wesley, 1998).
↑ Heideman, MT, DH Johnson a CS Burrus, „ Gauss a historie rychlé Fourierovy transformace Archivováno 31. července 2020 na Wayback Machine “, IEEE ASSP Magazine, 1, (4), 14–21 (1984).
↑ Donald Knuth . Umění počítačového programování : 3. díl Třídění a vyhledávání . - 1998. - S. 159. - ISBN 0-201-89685-0 .
↑ Karatsuba, Anatolii A. ; Jurij P. Ofman . Násobení vícehodnotových čísel na automatech (neopr.) // Zprávy Akademie věd . - 1962. - T. 146 . - S. 293-294 . Přeloženo v Násobení víceciferných čísel na automatech // Sovětské fyziky Doklady : deník. - 1963. - Sv. 7 . - str. 595-596 .
↑ M. Frigo; CE Leiserson; H. Prokop. Algoritmy nezapomínající na vyrovnávací paměť (neopr.) // Proc. 40. Symp. o základech informatiky. — 1999.
↑ 1 2 Frigo, M.; Johnson, SG Návrh a implementace FFTW3 // Proceedings of the IEEE : deník. - 2005. - únor ( roč. 93 , č. 2 ). - str. 216-231 . - doi : 10.1109/JPROC.2004.840301 .

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .