Divide and Conquer (datavetenskap)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 januari 2021; kontroller kräver 22 redigeringar .

Dela och erövra inom datavetenskap är ett  algoritmutvecklingsparadigm som består i att rekursivt dela upp problemet som ska lösas i två eller flera deluppgifter av samma typ, men av mindre storlek, och kombinera deras lösningar för att få ett svar på det ursprungliga problemet ; partitioner utförs tills alla deluppgifter är elementära.

Att förstå och designa Divide and Conquer-algoritmer är en komplex färdighet som kräver en god förståelse för arten av det underliggande problemet som ska lösas. Precis som med att bevisa ett teorem genom matematisk induktion , är det ofta nödvändigt att ersätta det ursprungliga problemet med ett mer allmänt eller komplext problem för att initiera rekursionen, och det finns ingen systematisk metod för att hitta den korrekta generaliseringen. Sådana komplexiteter av Divide and Conquer-metoden ses när man optimerar beräkningen av Fibonacci-talet med effektiv dubbelrekursion.

Korrektheten av algoritmen som följer "Dela och erövra"-paradigmet bevisas oftast med metoden för matematisk induktion , och körtiden bestäms antingen genom att direkt lösa motsvarande återkommande ekvation eller genom att tillämpa satsen för huvudsaklig återkommande relation .

Dela och erövra

Divide and Conquer-paradigmet används ofta för att hitta den optimala lösningen på ett visst problem. Dess huvudidé är att dekomponera ett givet problem i två eller flera liknande men enklare delproblem, lösa dem ett efter ett och komponera deras lösningar. Till exempel, för att sortera en given lista med n naturliga tal, måste du dela upp den i två listor med ungefär n /2 nummer vardera, sortera var och en av dem i tur och ordning och ordna båda resultaten därefter för att få en sorterad version av denna lista ( se figur). Detta tillvägagångssätt är känt som sammanslagningssorteringsalgoritmen .

Namnet "Dela och erövra" används ibland för algoritmer som reducerar varje problem till endast ett delproblem, till exempel den binära sökalgoritmen för att hitta en post i en sorterad lista (eller dess specialfall, halveringsalgoritmen för att hitta rötter). [1] Dessa algoritmer kan implementeras mer effektivt än de allmänna Divide and Conquer-algoritmerna; i synnerhet, om de använder svansrekursion , kan de konverteras till enkla loopar . Under denna breda definition kan dock varje algoritm som använder rekursion eller loopar betraktas som en "dela och erövra algoritm". Därför anser vissa författare att namnet "Dela och erövra" endast bör användas när varje uppgift kan skapa två eller flera deluppgifter. [2] Istället föreslogs namnet reducera och erövra för klassen av enstaka problem. [3]

Exempel

Tidiga exempel på sådana algoritmer är i första hand "Reduce and Conquer" - det ursprungliga problemet är sekventiellt uppdelat i separata delproblem, och kan faktiskt lösas iterativt.

Binär sökning, "Reduce and Conquer"-algoritmen där delproblem är ungefär hälften av den ursprungliga storleken, har en lång historia. Även om en tydlig beskrivning av algoritmen på datorer dök upp redan 1946 i en artikel av John Mauchly . Tanken på att använda en sorterad lista med föremål för att göra sökningen enklare går tillbaka åtminstone till Babylonien år 200 f.Kr. [4] En annan gammal reducera-och-erövra-algoritm är Euklids algoritm för att beräkna den största gemensamma divisorn  av två tal genom att reducera talen till mindre och mindre ekvivalenta delproblem, som går tillbaka flera århundraden f.Kr.

Ett tidigt exempel på en Divide and Conquer-algoritm med flera delproblem är den Gaussiska (1805) beskrivningen av vad som nu kallas Cooley-Tukey Fast Fourier Transform [5] .

En tidig algoritm med två delproblem Divide and Conquer som designades specifikt för datorer och analyserades ordentligt är algoritmen för sammanslagning som uppfanns   av John von Neumann 1945. [6]

Ett typiskt exempel är sammanslagningssorteringsalgoritmen . För att sortera en matris med siffror i stigande ordning delas den upp i två lika stora delar, var och en sorteras, sedan slås de sorterade delarna samman till en. Denna procedur tillämpas på var och en av delarna så länge som den del av arrayen som ska sorteras innehåller minst två element (så att den kan delas upp i två delar). Körtiden för denna algoritm är operationer, medan enklare algoritmer tar tid, där  är storleken på den ursprungliga arrayen.

Ett annat anmärkningsvärt exempel är algoritmen som uppfanns av Anatolij Aleksandrovich Karatsuba 1960 [7] för att multiplicera två tal från n siffror med  operationsnumret ( stor notation O ). Denna algoritm motbevisade Andrey Kolmogorovs hypotes från 1956 att denna uppgift skulle kräva operationer.

Som ett annat exempel på en Divide and Conquer-algoritm som inte ursprungligen använde datorer. Donald Knuth ger en metod som vanligen används av postkontoret för att dirigera post: brev sorteras i separata paket avsedda för olika geografiska områden, vart och ett av dessa paket sorteras i sig själv i partier för mindre underregioner, och så vidare tills de levereras. [4] Detta är relaterat till radix sort , beskrivet för hålkortssorteringsmaskiner redan 1929. [fyra]

Fördelar

Lösa komplexa problem

Divide and Conquer är ett kraftfullt verktyg för att lösa begreppsmässigt komplexa problem: allt som krävs är att hitta ett fall av att dela upp problemet i delproblem, lösa triviala fall och kombinera delproblemen till det ursprungliga problemet. På samma sätt kräver Reduce and Conquer bara att problemet reduceras till ett mindre problem, såsom det klassiska tornet i Hanoi , som reducerar lösningen för att flytta ett torn på höjden n till att flytta ett torn på höjden n − 1.

Algoritmeffektivitet

Divide and Conquer-paradigmet hjälper ofta till att upptäcka effektiva algoritmer. Detta har varit nyckeln till till exempel Karatsubas snabba multiplikationsmetod, quicksort och mergesort- algoritmer, Strassens algoritm för matrismultiplikation och snabba Fourier-transformers.

I alla dessa exempel resulterade Divide and Conquer-metoden i en förbättring av den asymptotiska kostnaden för lösningen i själva lösningen. Till exempel, om (a) basfallet har en storlek som begränsas av en konstant, då är arbetet med att partitionera problemet och kombinera dellösningar proportionellt mot problemstorleken n, och (b) det finns ett begränsat antal p av delproblem av storlek ~n/p i varje steg, då är effektiviteten för algoritmen " Divide and Conquer kommer att vara O( n  log p n ).

Samtidighet

Divide and Conquer-algoritmer är naturligtvis anpassade för att köras på flerprocessormaskiner, särskilt delade minnessystem , där dataöverföringar mellan processorer inte behöver schemaläggas i förväg, eftersom individuella deluppgifter kan köras på olika processorer.

Minnesåtkomst

Divide and Conquer-algoritmer tenderar naturligtvis att använda cacheminnet effektivt . Anledningen är att när en deluppgift väl är tillräckligt liten kan den och alla dess deluppgifter i princip lösas i cachen utan att komma åt det långsammare huvudminnet. Algoritmen för att använda cachen på detta sätt kallas cache-oblivious eftersom den inte inkluderar storleken på cachen som en explicit parameter. [8] Dessutom kan Divide and Conquer-algoritmer designas för att viktiga algoritmer (t.ex. sortering, FFT och matrismultiplikation) ska bli optimala cache-omedvetna algoritmer - de använder cachen på ett förmodligen optimalt sätt, i asymptotisk mening, oavsett av cachestorlek. Däremot är det traditionella tillvägagångssättet för cacheanvändning blockering, som i kapslad loopoptimering , där uppgiften explicit är uppdelad i bitar av lämplig storlek - detta kan också använda cachen optimalt, men bara när algoritmen är inställd för en specifik cachestorlek av en viss maskin.

Samma fördel finns för andra hierarkiska lagringssystem som NUMA eller virtuellt minne , och för flera nivåer av cache: när ett delproblem är tillräckligt litet kan det lösas inom den nivån i hierarkin, utan tillgång till högre (högre långsamma) nivåer .

Programproblem

Rekursion

Divide and Conquer-algoritmer tillämpas naturligt i form av rekursiva metoder . I det här fallet lagras de privata deluppgifterna som leder till den som för närvarande löses automatiskt i procedurenropstacken . En rekursiv funktion är en numerisk funktion av ett numeriskt argument som innehåller sig själv i dess notation.

Explicit stack

Divide and Conquer-algoritmer kan också tillämpas av ett icke-rekursivt program som lagrar privata delproblem i någon explicit datastruktur som en stack , kö eller prioritetskö . Detta tillvägagångssätt ger större frihet att välja vilket delproblem som måste lösas härnäst. En funktion som är viktig i vissa applikationer - till exempel i metoden att förgrena och länka för att optimera funktioner. Detta tillvägagångssätt är också standard i programmeringsspråk som inte ger stöd för rekursiva procedurer.

Stackstorlek

I rekursiva implementeringar av Divide and Conquer-algoritmer måste man se till att tillräckligt med minne allokeras för rekursionsstacken, annars kan exekveringen misslyckas på grund av stackoverflow . Divide and Conquer-algoritmer som är tidseffektiva har ofta relativt grunda rekursionsdjup. Till exempel kan en snabbsorteringsalgoritm implementeras på ett sådant sätt att den aldrig kräver mer än log2 n kapslade rekursiva anrop för att sortera n element.

Stackoverflows kan vara svåra att undvika när man använder rekursiva rutiner eftersom många kompilatorer antar att rekursionsstacken är sammanhängande i minnet, och vissa allokerar en fast mängd utrymme för den. Kompilatorer kan också lagra mer information om rekursionsstacken än vad som är absolut nödvändigt, såsom returadressen, oföränderliga parametrar och interna variabler för procedurer. Således kan risken för stackspill minskas genom att minimera parametrarna och interna variabler för den rekursiva proceduren, eller genom att använda en explicit stackstruktur.

Val av grundläggande alternativ

I vilken rekursiv algoritm som helst finns det stor frihet i valet av basfall, små delproblem som löses direkt för att fullborda rekursionen.

Att välja minsta eller enklast möjliga basfall är mer elegant och resulterar oftast i enklare program eftersom det finns färre fall att ta hänsyn till och lättare att lösa. Till exempel kan FFT stoppa rekursion när ingången är ett enda sampel, och snabbsorteringsalgoritmen för en lista kan stoppa när inmatningen är en tom lista; i båda exemplen finns det bara ett basfall att beakta och det behöver inte behandlas.

Å andra sidan förbättras effektiviteten ofta om rekursionen stannar vid relativt stora basfall och dessa löses icke-rekursivt, vilket resulterar i en hybridalgoritm . Denna strategi undviker överlappande rekursiva anrop som gör lite eller inget arbete, och kan också tillåta användning av specialiserade icke-rekursiva algoritmer som, för dessa grundläggande fall, är mer effektiva än explicit rekursion. Den allmänna proceduren för en enkel hybridrekursiv algoritm är att kortsluta basfallet, även känt som armlängdsrekursion . I detta fall kontrolleras det innan funktionen anropas om nästa steg kommer att leda till basregistret, vilket undviker ett onödigt funktionsanrop. Eftersom Divide and Conquer-algoritmen så småningom reducerar varje instans av ett problem eller delproblem till ett stort antal basinstanser, dominerar de ofta den övergripande effektiviteten av algoritmen, speciellt när split/join-overheaden är låg. Dessutom beror dessa överväganden inte på om rekursion implementeras av kompilatorn eller av en explicit stack.

Således kommer till exempel många biblioteksapplikationer av quicksort att förvandlas till en enkel loop-baserad insättningssorteringsalgoritm (eller liknande) så snart antalet element som ska sorteras är tillräckligt litet. Dessutom, om en tom lista var det enda basfallet, skulle sortering av en lista med n poster resultera i maximalt n antal snabbsorteringsanrop som inte skulle göra något annat än att återvända omedelbart. Att öka basfallen till listor med storlek 2 eller mindre kommer att eliminera de flesta av dessa "gör ingenting"-anrop, och mer generellt används basfall större än 2 för att minska andelen tid som ägnas åt hushållning eller stackmanipulation.

Alternativt kan stora basfall användas, som fortfarande använder Divide and Conquer-algoritmen men implementerar algoritmen för en fördefinierad uppsättning fasta storlekar, där algoritmen helt kan expanderas till kod som inte har rekursion, loopar eller konventioner (associerade med metod för partiell utvärdering ). Till exempel används detta tillvägagångssätt i vissa effektiva FFT-applikationer, där basfallen är utökade implementeringar av Divide and Conquer FFT-algoritmer för en uppsättning fasta storlekar. [9] Tekniker för generering av källkod kan användas för att generera det stora antalet distinkta basfall som önskas för att effektivt implementera denna strategi.

En generaliserad version av denna idé är känd som "expandera" eller "växa"-rekursion, och olika metoder har föreslagits för att automatisera basfallsexpansionsproceduren. [9]

Dela återkommande deluppgifter

För vissa uppgifter kan förgreningsrekursion resultera i flera utvärderingar av samma deluppgift. I sådana fall kan det vara värt att identifiera och lagra lösningar på dessa överlappande delproblem, en teknik som vanligtvis kallas memoization . Följande till det yttersta leder detta till algoritmer för dela och erövra nerifrån och upp som dynamisk programmering och diagramparsning .

Se även

Anteckningar

  1. ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduktion till  algoritmer (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
  2. ↑ Brassard, G. och Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ↑ Anany V. Levitin, Introduktion till design och analys av algoritmer (Addison Wesley, 2002).
  4. ↑ 1 2 3 Donald E. Knuth, Konsten att programmera datorer: Volym 3, Sortering och sökning , andra upplagan (Addison-Wesley, 1998).
  5. ↑ Heideman, MT, DH Johnson och CS Burrus, " Gauss and the history of the fast Fourier transform Archived July 31, 2020 at the Wayback Machine ", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
  6. ↑ Donald Knuth . Konsten att programmera : Volym 3 Sortering och sökning  . - 1998. - S. 159. - ISBN 0-201-89685-0 .
  7. ↑ Karatsuba, Anatolii A. ; Yuri P. Ofman . Multiplikation av flervärdiga tal på automater  (neopr.)  // Vetenskapsakademiens rapporter . - 1962. - T. 146 . - S. 293-294 . Översatt till multiplikation av flersiffriga tal på automater   // Soviet Physics Doklady : journal. - 1963. - Vol. 7 . - s. 595-596 .
  8. ↑ M. Frigo; CE Leiserson; H. Prokop. Cache-omedvetna algoritmer  (neopr.)  // Proc. 40:e Symp. om datavetenskapens grunder. — 1999.
  9. ↑ 1 2 Frigo, M.; Johnson, SG  Utformningen och implementeringen av FFTW3  // Proceedings of the IEEE : journal. - 2005. - Februari ( vol. 93 , nr 2 ). - S. 216-231 . - doi : 10.1109/JPROC.2004.840301 .

Litteratur

Länkar