Divide and Conquer (datalogi)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. januar 2021; checks kræver 22 redigeringer .

Divide and conquer i datalogi er et algoritmeudviklingsparadigme ,  der består i rekursivt at opdele det problem, der skal løses, i to eller flere delopgaver af samme type, men af ​​en mindre størrelse, og kombinere deres løsninger for at opnå et svar på det oprindelige problem; partitioner udføres, indtil alle underopgaver er elementære.

Forståelse og design af Divide and Conquer-algoritmer er en kompleks færdighed, der kræver en god forståelse af arten af ​​det underliggende problem, der skal løses. Som med at bevise en sætning ved matematisk induktion , er det ofte nødvendigt at erstatte det oprindelige problem med et mere generelt eller komplekst problem for at initialisere rekursionen, og der er ingen systematisk metode til at finde den korrekte generalisering. Sådanne kompleksiteter af Divide and Conquer-metoden ses, når man optimerer beregningen af ​​Fibonacci-tallet med effektiv dobbeltrekursion.

Rigtigheden af ​​algoritmen efter "Del og hersk"-paradigmet bevises oftest ved hjælp af metoden til matematisk induktion , og køretiden bestemmes enten ved direkte at løse den tilsvarende tilbagevendende ligning eller ved at anvende den primære gentagelsesrelationssætning .

Del og hersk

Divide and Conquer-paradigmet bruges ofte til at finde den optimale løsning på et bestemt problem. Dens hovedidé er at dekomponere et givent problem i to eller flere ens, men enklere delproblemer, løse dem én efter én og sammensætte deres løsninger. For at sortere en given liste med n naturlige tal, skal du f.eks. opdele den i to lister med ca. n /2 tal hver, sortere hver af dem efter tur og arrangere begge resultater i overensstemmelse hermed for at få en sorteret version af denne liste ( se figur). Denne tilgang er kendt som flettesorteringsalgoritmen .

Navnet "Del og hersk" bruges nogle gange på algoritmer, der reducerer hvert problem til kun ét underproblem, såsom den binære søgealgoritme til at finde en post i en sorteret liste (eller dets specielle tilfælde, halveringsalgoritmen til at finde rødder). [1] Disse algoritmer kan implementeres mere effektivt end de generelle Divide and Conquer-algoritmer; især, hvis de bruger halerekursion , kan de konverteres til simple loops . Men under denne brede definition kan enhver algoritme, der bruger rekursion eller loops, betragtes som en "del og hersk-algoritme". Derfor mener nogle forfattere, at navnet "Del og erob" kun bør bruges, når hver opgave kan afføde to eller flere underopgaver. [2] I stedet blev navnet reducere og erobre foreslået for klassen af ​​enkeltproblemer. [3]

Eksempler

Tidlige eksempler på sådanne algoritmer er primært "Reduce and Conquer" - det oprindelige problem er sekventielt opdelt i separate delproblemer og kan faktisk løses iterativt.

Binær søgning, "Reducer and Conquer"-algoritmen, hvor underproblemer er omtrent halvdelen af ​​den oprindelige størrelse, har en lang historie. Selvom en klar beskrivelse af algoritmen på computere dukkede op allerede i 1946 i en artikel af John Mauchly . Ideen om at bruge en sorteret liste over genstande for at gøre søgningen lettere går tilbage i det mindste til Babylonien i 200 f.Kr. [4] En anden ældgammel reducer-og-erob-algoritme er Euklids algoritme til at beregne den største fælles divisor  af to tal ved at reducere tallene til mindre og mindre ækvivalente underproblemer, som går tilbage flere århundreder f.Kr.

Et tidligt eksempel på en Divide and Conquer-algoritme med flere underproblemer er den Gaussiske (1805) beskrivelse af det, der nu kaldes Cooley-Tukey Fast Fourier Transform [5] .

En tidlig to-underproblem Divide and Conquer-algoritme, der var specielt designet til computere og korrekt analyseret, er fusionssorteringsalgoritmen opfundet   af John von Neumann i 1945. [6]

Et typisk eksempel er flettesorteringsalgoritmen . For at sortere et array af tal i stigende rækkefølge opdeles det i to lige store dele, hver sorteres, hvorefter de sorterede dele flettes sammen til én. Denne procedure anvendes på hver af delene, så længe den del af arrayet, der skal sorteres, indeholder mindst to elementer (så den kan opdeles i to dele). Køretiden for denne algoritme er operationer, mens enklere algoritmer tager tid, hvor  er størrelsen af ​​det originale array.

Et andet bemærkelsesværdigt eksempel er algoritmen opfundet af Anatoly Aleksandrovich Karatsuba i 1960 [7] til at gange to tal fra n cifre med  operationsnummeret ( stor notation O ). Denne algoritme modbeviste Andrey Kolmogorovs hypotese fra 1956 om, at denne opgave ville kræve operationer.

Som endnu et eksempel på en Divide and Conquer-algoritme, der ikke oprindeligt brugte computere. Donald Knuth giver en metode, der almindeligvis bruges af postkontoret til at dirigere post: Breve sorteres i separate pakker, der er bestemt til forskellige geografiske områder, hver af disse pakker sorteres i sig selv i partier for mindre underregioner, og så videre, indtil de er leveret. [4] Dette er relateret til radix sort , beskrevet for hulkortsorteringsmaskiner allerede i 1929. [fire]

Fordele

Løsning af komplekse problemer

Divide and Conquer er et kraftfuldt værktøj til at løse konceptuelt komplekse problemer: alt, hvad der kræves, er at finde en sag om at opdele problemet i delproblemer, løse trivielle tilfælde og kombinere delproblemerne i det oprindelige problem. Ligeledes kræver Reduce and Conquer kun at reducere problemet til et mindre problem, såsom det klassiske Tower of Hanoi , som reducerer løsningen på at flytte et tårn i højden n til at flytte et tårn i højden n - 1.

Algoritmeeffektivitet

Divide and Conquer-paradigmet hjælper ofte med at opdage effektive algoritmer. Dette har været nøglen til for eksempel Karatsubas hurtige multiplikationsmetode, quicksort og mergesort algoritmer, Strassens algoritme til matrix multiplikation og hurtige Fourier transformationer.

I alle disse eksempler resulterede Divide and Conquer-tilgangen i en forbedring af de asymptotiske omkostninger ved løsningen i selve løsningen. For eksempel, hvis (a) basistilfældet har en størrelse afgrænset af en konstant, så er arbejdet med at opdele problemet og kombinere delløsninger proportionalt med problemstørrelsen n, og (b) der er et begrænset antal p af delproblemer af størrelse ~n/p på hvert trin, så er effektiviteten af ​​algoritmen " Divide and Conquer vil være O( n  log p n ).

Samtidighed

Divide and Conquer-algoritmer er naturligvis tilpasset til at køre på multiprocessor-maskiner, især delte hukommelsessystemer , hvor dataoverførsler mellem processorer ikke skal planlægges før tid, da individuelle underopgaver kan køre på forskellige processorer.

Hukommelsesadgang

Divide and Conquer-algoritmer har naturligvis en tendens til at bruge cachehukommelsen effektivt . Årsagen er, at når en underopgave er lille nok, kan den og alle dens underopgaver i princippet løses i cachen uden at få adgang til den langsommere hovedhukommelse. Algoritmen til at bruge cachen på denne måde kaldes cache-oblivious , fordi den ikke inkluderer størrelsen af ​​cachen som en eksplicit parameter. [8] Derudover kan Divide and Conquer-algoritmer designes til, at vigtige algoritmer (f.eks. sortering, FFT og matrixmultiplikation) bliver optimale cache-oblivious algoritmer - de bruger cachen på en sandsynligvis optimal måde, i asymptotisk forstand, uanset af cachestørrelse. I modsætning hertil er den traditionelle tilgang til cachebrug blokering, som i nested loop optimization , hvor opgaven eksplicit er opdelt i bidder af passende størrelse - dette kan også bruge cachen optimalt, men kun når algoritmen er tunet til en specifik cachestørrelse af en bestemt maskine.

Den samme fordel eksisterer for andre hierarkiske lagersystemer såsom NUMA eller virtuel hukommelse og for flere niveauer af cache: når et underproblem er lille nok, kan det løses inden for dette niveau af hierarkiet uden adgang til højere (højere langsomme) niveauer .

Applikationsproblemer

Rekursion

Divide and Conquer algoritmer anvendes naturligt i form af rekursive metoder . I dette tilfælde gemmes de private underopgaver, der fører til den, der i øjeblikket løses, automatisk på procedurekaldsstakken . En rekursiv funktion er en numerisk funktion af et numerisk argument, der indeholder sig selv i sin notation.

Eksplicit stak

Divide and Conquer-algoritmer kan også anvendes af et ikke-rekursivt program, der gemmer private underproblemer i en eller anden eksplicit datastruktur, såsom en stak , kø eller prioritetskø . Denne tilgang giver større frihed til at vælge, hvilket underproblem, der skal løses næste gang. En funktion, der er vigtig i nogle applikationer - for eksempel i metoden til at forgrene og linke for at optimere funktioner. Denne tilgang er også standard i programmeringssprog, der ikke understøtter rekursive procedurer.

Stakstørrelse

I rekursive implementeringer af Divide and Conquer-algoritmer skal man sikre, at der er allokeret nok hukommelse til rekursionsstakken, ellers kan eksekveringen mislykkes på grund af stak-overløb . Divide and Conquer-algoritmer, der er tidseffektive, har ofte relativt lave rekursionsdybder. For eksempel kan en quicksort-algoritme implementeres på en sådan måde, at den aldrig kræver mere end log2 n indlejrede rekursive kald for at sortere n elementer.

Stack overflows kan være vanskelige at undgå, når du bruger rekursive rutiner, fordi mange compilere antager, at rekursionsstakken er sammenhængende i hukommelsen, og nogle tildeler en fast mængde plads til den. Kompilere kan også gemme mere information på rekursionsstakken, end det er strengt nødvendigt, såsom returadressen, uforanderlige parametre og interne procedurevariabler. Således kan risikoen for stakoverløb reduceres ved at minimere parametrene og interne variabler i den rekursive procedure eller ved at bruge en eksplicit stakstruktur.

Valg af grundlæggende muligheder

I enhver rekursiv algoritme er der stor frihed i valget af basistilfælde, små delproblemer, der løses direkte for at fuldende rekursionen.

At vælge de mindste eller enklest mulige basissager er mere elegant og resulterer normalt i enklere programmer, fordi der er færre sager at overveje og lettere at løse. FFT kan f.eks. stoppe rekursion, når inputtet er en enkelt prøve, og quicksort-sorteringsalgoritmen for en liste kan stoppe, når inputtet er en tom liste; i begge eksempler er der kun én basiscase at overveje, og den skal ikke behandles.

På den anden side forbedres effektiviteten ofte, hvis rekursionen stopper ved relativt store basistilfælde, og disse løses ikke-rekursivt, hvilket resulterer i en hybridalgoritme . Denne strategi undgår overlappende rekursive opkald, der gør lidt eller intet arbejde, og kan også tillade brugen af ​​specialiserede ikke-rekursive algoritmer, der i disse grundlæggende tilfælde er mere effektive end eksplicit rekursion. Den generelle procedure for en simpel hybrid rekursiv algoritme er at kortslutte basistilfældet, også kendt som armslængde-rekursion . I dette tilfælde kontrolleres det, før funktionen kaldes, om det næste trin fører til basisregistret, hvilket undgår et unødvendigt funktionskald. Fordi Divide and Conquer-algoritmen til sidst reducerer hver forekomst af et problem eller delproblem til et stort antal basisforekomster, dominerer de ofte den overordnede effektivitet af algoritmen, især når split/join-overheaden er lav. Desuden afhænger disse overvejelser ikke af, om rekursion er implementeret af compileren eller af en eksplicit stack.

Således vil for eksempel mange biblioteksapplikationer af quicksort blive til en simpel loop-baseret indsættelsessorteringsalgoritme (eller lignende), så snart antallet af elementer, der skal sorteres, er tilstrækkeligt lille. Desuden, hvis en tom liste var det eneste grundtilfælde, ville sortering af en liste med n poster resultere i et maksimalt n antal quicksort-kald, der ikke ville gøre andet end at vende tilbage med det samme. Forøgelse af basiscases til lister med størrelse 2 eller mindre vil eliminere de fleste af disse "gør ingenting"-opkald, og mere generelt bruges basiscases større end 2 til at reducere andelen af ​​tid brugt på husholdning eller stakmanipulation.

Alternativt kan der bruges store basiscases, som stadig bruger Divide and Conquer-algoritmen, men implementerer algoritmen til et foruddefineret sæt af faste størrelser, hvor algoritmen kan udvides fuldt ud til kode , der ikke har rekursion, loops eller konventioner (tilknyttet med metode til delvis evaluering ). For eksempel bruges denne tilgang i nogle effektive FFT-applikationer, hvor basissagen er udvidede implementeringer af Divide and Conquer FFT-algoritmer for et sæt faste størrelser. [9] Teknikker til generering af kildekode kan bruges til at generere det store antal forskellige basistilfælde, der ønskes for effektivt at implementere denne strategi.

En generaliseret version af denne idé er kendt som "expand" eller "grow" rekursion, og forskellige metoder er blevet foreslået til at automatisere basiscase-udvidelsesproceduren. [9]

Deling af tilbagevendende underopgaver

For nogle opgaver kan forgreningsrekursion resultere i flere evalueringer af den samme delopgave. I sådanne tilfælde kan det være umagen værd at identificere og gemme løsninger på disse overlappende underproblemer, en teknik almindeligvis kendt som memoization . Følgende til det yderste fører dette til bottom-up Divide and Conquer-algoritmer såsom dynamisk programmering og diagramparsing .

Se også

Noter

  1. ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduktion til algoritmer  (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
  2. ↑ Brassard, G. og Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ↑ Anany V. Levitin, Introduktion til design og analyse af algoritmer (Addison Wesley, 2002).
  4. ↑ 1 2 3 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching , anden udgave (Addison-Wesley, 1998).
  5. ↑ Heideman, MT, DH Johnson og CS Burrus, " Gauss og historien om den hurtige Fourier-transformation Arkiveret 31. juli 2020 på Wayback Machine ", IEEE ASSP Magazine, 1, (4), 14-21 (1984).
  6. ↑ Donald Knuth . The Art of Computer Programming : Bind 3 Sortering og søgning  . - 1998. - S. 159. - ISBN 0-201-89685-0 .
  7. ↑ Karatsuba, Anatolii A. ; Yuri P. Ofman . Multiplikation af tal med flere værdier på automater  (neopr.)  // Videnskabsakademiets rapporter . - 1962. - T. 146 . - S. 293-294 . Oversat til multiplikation af flercifrede tal på automater   // Sovjetisk fysik Doklady : journal. - 1963. - Bd. 7 . - S. 595-596 .
  8. ↑ M. Frigo; CE Leiserson; H. Prokop. Cache-oblivious algoritmer  (neopr.)  // Proc. 40. Symp. om Datalogiens Grundlag. – 1999.
  9. ↑ 1 2 Frigo, M.; Johnson, SG  Designet og implementeringen af ​​FFTW3  // Proceedings of IEEE : journal. - 2005. - Februar ( bind 93 , nr. 2 ). - S. 216-231 . - doi : 10.1109/JPROC.2004.840301 .

Litteratur

Links