Del-og-erobre-algoritmen- Divide-and-conquer algorithm

I informatikk er divisjon og erobring et algoritmedesign -paradigme . En divider-og-erobre- algoritme bryter et problem rekursivt ned i to eller flere delproblemer av samme eller beslektede type, til disse blir enkle nok til å kunne løses direkte. Løsningene på delproblemene kombineres deretter for å gi en løsning på det opprinnelige problemet.

Del-og-erobre-teknikken er grunnlaget for effektive algoritmer for mange problemer, for eksempel sortering (f.eks. Quicksort , merge sort ), multiplisere store tall (f.eks. Karatsuba-algoritmen ), finne det nærmeste parpunktet , syntaktisk analyse ( f.eks. top-down parsere ), og beregning av den diskrete Fourier-transformasjonen ( FFT ).

Å designe effektive dele-og-erobre-algoritmer kan være vanskelig. Som ved matematisk induksjon er det ofte nødvendig å generalisere problemet for å gjøre det tilgjengelig for en rekursiv løsning. Korrektheten til en divider-og-erobre-algoritme er vanligvis bevist ved matematisk induksjon, og beregningskostnaden bestemmes ofte ved å løse gjentakelsesrelasjoner .

Splitt og hersk

Del-og-erobre-tilnærmingen for å sortere listen (38, 27, 43, 3, 9, 82, 10) i økende rekkefølge. Øvre halvdel: deling i sublister; midt: en ett-element liste er trivielt sortert; nedre halvdel: komponere sorterte sublister.

Del-og-erobre-paradigmet brukes ofte for å finne en optimal løsning på et problem. Den grunnleggende ideen er å dekomponere et gitt problem i to eller flere like, men enklere, delproblemer, å løse dem etter tur og å komponere løsningene sine for å løse det gitte problemet. Problemer med tilstrekkelig enkelhet løses direkte. For eksempel, for å sortere en gitt liste over n naturlige tall, del den i to lister med omtrent n /2 tall hver, sorter hver av dem etter tur, og bla begge resultatene inn på riktig måte for å få den sorterte versjonen av den gitte listen (se bilde). Denne tilnærmingen er kjent som sammenslåingssorteringsalgoritmen .

Navnet "dele og erobre" brukes noen ganger på algoritmer som reduserer hvert problem til bare ett delproblem, for eksempel den binære søkealgoritmen for å finne en post i en sortert liste (eller dens analog i numerisk databehandling , biseksjonsalgoritmen for rot å finne ). Disse algoritmene kan implementeres mer effektivt enn generelle del-og-erobre-algoritmer; spesielt hvis de bruker halerekurs , kan de konverteres til enkle sløyfer . Under denne brede definisjonen kan imidlertid hver algoritme som bruker rekursjon eller sløyfer bli sett på som en "divider-og-erobre-algoritme". Derfor mener noen forfattere at navnet "dele og erobre" bare skal brukes når hvert problem kan generere to eller flere delproblemer. Navnet nedgang og erobring er foreslått i stedet for enkelt deloppgave klasse.

En viktig anvendelse av dele og erobre er optimalisering, der hvis søkeområdet reduseres ("beskjæres") med en konstant faktor i hvert trinn, har den generelle algoritmen den samme asymptotiske kompleksiteten som beskjæringstrinnet, med konstanten avhengig av beskjæringsfaktor (ved å summere den geometriske serien ); dette er kjent som sviske og søk .

Tidlige historiske eksempler

Tidlige eksempler på disse algoritmene blir først og fremst redusert og erobret - det opprinnelige problemet blir suksessivt delt inn i enkelt delproblemer, og kan faktisk løses iterativt.

Binært søk, en reduksjons-og-erobre-algoritme der delproblemene er omtrent halvparten av den opprinnelige størrelsen, har en lang historie. Mens en klar beskrivelse av algoritmen på datamaskiner dukket opp i 1946 i en artikkel av John Mauchly , stammer ideen om å bruke en sortert liste over elementer for å lette søket tilbake minst så langt som Babylonia i 200 f.Kr. En annen gammel reduksjons-og-erobre-algoritme er den euklidiske algoritmen for å beregne den største vanlige deleren av to tall ved å redusere tallene til mindre og mindre likeverdige delproblemer, som dateres til flere århundrer f.Kr.

Et tidlig eksempel på en divider-og-erobre-algoritme med flere delproblemer er Gauss 'beskrivelse fra 1805 av det som nå kalles Cooley-Tukey fast Fourier transform (FFT) algoritme, selv om han ikke analyserte driftstellingen kvantitativt, og FFTs gjorde det ikke blitt utbredt før de ble gjenoppdaget over et århundre senere.

En tidlig D-C-algoritme med to problemer som ble spesielt utviklet for datamaskiner og riktig analysert, er sammenslåingssorteringsalgoritmen som ble oppfunnet av John von Neumann i 1945.

Et annet bemerkelsesverdig eksempel er algoritmen som ble oppfunnet av Anatolii A. Karatsuba i 1960 som kan multiplisere to n -sifrede tall i operasjoner (i Big O -notasjon ). Denne algoritmen motbeviste Andrey Kolmogorovs formodning fra 1956 om at det ville være nødvendig med operasjoner for denne oppgaven. ${\ displaystyle O (n^{\ log _ {2} 3})}$ ${\ displaystyle \ Omega (n^{2})}$

Som et annet eksempel på en divider-og-erobre-algoritme som opprinnelig ikke involverte datamaskiner, gir Donald Knuth metoden et postkontor vanligvis bruker for å dirigere post: brev sorteres i separate poser for forskjellige geografiske områder, hver av disse posene er sortert i seg selv i grupper for mindre delregioner, og så videre til de er levert. Dette er relatert til en radix-sortering , beskrevet for slagkort-sorteringsmaskiner allerede i 1929.

Fordeler

Løse vanskelige problemer

Del og erobre er et kraftig verktøy for å løse konseptuelt vanskelige problemer: alt det krever er en måte å dele problemet opp i delproblemer, løse de bagatellmessige sakene og kombinere delproblemer med det opprinnelige problemet. På samme måte krever reduksjon og erobring bare å redusere problemet til et enkelt mindre problem, for eksempel det klassiske Tower of Hanoi -puslespillet, som reduserer flytting av et høyttårn for å flytte et høyttårn . ${\ displaystyle n}$ ${\ displaystyle n-1}$

Algoritme effektivitet

Del-og-erobre-paradigmet hjelper ofte med å finne effektive algoritmer. Det var for eksempel nøkkelen til Karatsubas hurtige multiplikasjonsmetode, kvikksort- og sammenslåingsalgoritmene, Strassen -algoritmen for matrisemultiplikasjon og raske Fourier -transformasjoner.

I alle disse eksemplene førte D & C -tilnærmingen til en forbedring i den asymptotiske kostnaden for løsningen. For eksempel, hvis (a) basistilfellene har konstant begrenset størrelse, er arbeidet med å dele problemet og kombinere delløsningene proporsjonalt med problemets størrelse , og (b) det er et begrenset antall delproblemer av størrelse ~ på hvert trinn, så vil kostnaden for del-og-erobre-algoritmen være . ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle n/p}$ ${\ displaystyle O (n \ log _ {p} n)}$

Parallellisme

Del-og-erobre-algoritmer er naturlig tilpasset for utførelse i maskiner med flere prosessorer, spesielt systemer med delt minne der kommunikasjon av data mellom prosessorer ikke trenger å planlegges på forhånd fordi forskjellige delproblemer kan utføres på forskjellige prosessorer.

Minnetilgang

Del-og-erobre-algoritmer har en naturlig tendens til å utnytte minnebuffer effektivt . Årsaken er at når et delproblem er lite nok, kan det og alle dets delproblemer i prinsippet løses i hurtigbufferen uten å få tilgang til det langsommere hovedminnet. En algoritme designet for å utnytte hurtigbufferen på denne måten kalles cache-oblivious , fordi den ikke inneholder bufferstørrelsen som en eksplisitt parameter. Videre kan D & C-algoritmer utformes for viktige algoritmer (f.eks. Sortering, FFT og matrisemultiplikasjon) for å være optimale cache-uvitende algoritmer-de bruker hurtigbufferen på en sannsynligvis optimal måte, i asymptotisk forstand, uavhengig av bufferstørrelsen. Derimot blokkerer den tradisjonelle tilnærmingen for å utnytte hurtigbufferen , som i sløyfeoptimalisering , der problemet eksplisitt er delt inn i biter av passende størrelse - dette kan også bruke hurtigbufferen optimalt, men bare når algoritmen er innstilt for den spesifikke bufferstørrelser på en bestemt maskin.

Den samme fordelen eksisterer med hensyn til andre hierarkiske lagringssystemer, for eksempel NUMA eller virtuelt minne , så vel som for flere cache-nivåer: Når et delproblem er lite nok, kan det løses innenfor et gitt nivå i hierarkiet, uten tilgang til de høyere (langsommere) nivåene.

Avrundingskontroll

I beregninger med avrundet aritmetikk, f.eks. Med flytende tall, kan en divider-og-erobre-algoritme gi mer nøyaktige resultater enn en overfladisk ekvivalent iterativ metode. For eksempel kan man legge til N -tall enten ved en enkel sløyfe som legger hvert nullpunkt til en enkelt variabel, eller ved en D & C -algoritme kalt parvis summering som bryter datasettet i to halvdeler, beregner summen av hver halvdel rekursivt og legger deretter til de to summene. Mens den andre metoden utfører samme antall tillegg som den første og betaler overhead for de rekursive samtalene, er den vanligvis mer nøyaktig.

Gjennomføringsproblemer

Rekursjon

Del-og-erobre-algoritmer er naturlig implementert som rekursive prosedyrer . I så fall lagres de delvise delproblemene som fører til at problemet for øyeblikket blir løst automatisk i prosedyreanropsstakken . En rekursiv funksjon er en funksjon som kaller seg innenfor definisjonen.

Eksplisitt stabel

Del-og-erobre-algoritmer kan også implementeres av et ikke-rekursivt program som lagrer de delvise delproblemene i en eksplisitt datastruktur, for eksempel en stabel , kø eller prioritetskø . Denne tilnærmingen gir større frihet i valget av delproblemet som skal løses neste gang, en funksjon som er viktig i noen applikasjoner-f.eks. I bredde-første rekursjon og gren-og-bundet metode for funksjonsoptimalisering. Denne tilnærmingen er også standardløsningen i programmeringsspråk som ikke gir støtte for rekursive prosedyrer.

Stabelstørrelse

I rekursive implementeringer av D & C -algoritmer må man sørge for at det er tilstrekkelig med minne tildelt for rekursjonsstakken, ellers kan utførelsen mislykkes på grunn av stabeloverløp . D & C-algoritmer som er tidseffektive har ofte relativt liten rekursjonsdybde. For eksempel kan quicksort -algoritmen implementeres slik at den aldri krever mer enn nestede rekursive anrop for å sortere elementer. ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle n}$

Stackoverløp kan være vanskelig å unngå når du bruker rekursive prosedyrer siden mange kompilatorer antar at rekursjonsstakken er et sammenhengende område med minne, og noen tildeler en bestemt mengde plass til den. Kompilatorer kan også lagre mer informasjon i rekursjonsbunken enn det som er strengt nødvendig, for eksempel returadresse, uendrede parametere og de interne variablene i prosedyren. Dermed kan risikoen for stabeloverløp reduseres ved å minimere parametrene og interne variablene i den rekursive prosedyren eller ved å bruke en eksplisitt stabelstruktur.

Velge basistilfeller

I enhver rekursiv algoritme er det stor frihet i valget av basistilfeller , de små delproblemene som løses direkte for å avslutte rekursjonen.

Å velge de minste eller enkleste mulige basissakene er mer elegant og fører vanligvis til enklere programmer, fordi det er færre saker å vurdere og de er lettere å løse. For eksempel kan en FFT-algoritme stoppe rekursjonen når inngangen er en enkelt prøve, og kvikksorteringssorteringsalgoritmen kan stoppe når inngangen er den tomme listen; i begge eksemplene er det bare ett grunnleggende tilfelle å vurdere, og det krever ingen behandling.

På den annen side forbedres effektiviteten ofte hvis rekursjonen stoppes ved relativt store basistilfeller, og disse løses ikke-rekursivt, noe som resulterer i en hybridalgoritme . Denne strategien unngår overhead av rekursive samtaler som gjør lite eller ingen arbeid, og kan også tillate bruk av spesialiserte ikke-rekursive algoritmer som, for de basistilfellene, er mer effektive enn eksplisitt rekursjon. En generell prosedyre for en enkel hybrid rekursiv algoritme er å kortslutte basiskassen , også kjent som rekursjon i armlengde . I dette tilfellet blir det sjekket om det neste trinnet vil føre til at hovedtilfellet er før funksjonssamtalen, og unødvendig funksjonsanrop unngås. For eksempel i et tre, i stedet for å gjenta seg til en barneknute og deretter kontrollere om det er null, sjekke null før det gjentas; unngår halve funksjonsanropene i noen algoritmer på binære trær. Siden en D & C-algoritme til slutt reduserer hvert problem eller delproblemforekomst til et stort antall basisforekomster, dominerer disse ofte den totale kostnaden for algoritmen, spesielt når delingen/sammenkoblingen er lav. Vær oppmerksom på at disse hensynene ikke avhenger av om rekursjon implementeres av kompilatoren eller av en eksplisitt stabel.

Således vil for eksempel mange bibliotekimplementeringer av quicksort bytte til en enkel sløyfebasert innsettingssorteringsalgoritme (eller lignende) når antallet elementer som skal sorteres er tilstrekkelig lite. Vær oppmerksom på at hvis den tomme listen var det eneste grunnleggende tilfellet, ville sortering av en liste med oppføringer innebære maksimalt quicksort -anrop som ikke ville gjøre annet enn å returnere umiddelbart. Hvis du øker basistilfellene til lister med størrelse 2 eller mindre, elimineres de fleste av de ikke-gjør-anropene, og mer generelt brukes vanligvis en hovedkasse større enn 2 for å redusere brøkdelen av tid brukt til funksjonsanrop overhead eller stabling. ${\ displaystyle n}$ ${\ displaystyle n}$

Alternativt kan man bruke store basistilfeller som fremdeles bruker en divider-og-erobre-algoritme, men implementerer algoritmen for forhåndsbestemte sett med faste størrelser der algoritmen kan rulles helt ut til kode som ikke har rekursjon, sløyfer eller betingelser (relatert til teknikken for delvis evaluering ). For eksempel brukes denne tilnærmingen i noen effektive FFT-implementeringer, der basistilfellene er avrullede implementeringer av divider-og-erobre FFT-algoritmer for et sett med faste størrelser. Kildekodegenereringsmetoder kan brukes til å produsere det store antallet separate basissaker som er ønskelige for å implementere denne strategien effektivt.

Den generaliserte versjonen av denne ideen er kjent som rekursjon "avrulling" eller "grovning", og forskjellige teknikker har blitt foreslått for å automatisere prosedyren for å forstørre basiskassen.

Deler gjentatte delproblemer

For noen problemer kan den forgrenede rekursjonen ende opp med å evaluere det samme delproblemet mange ganger. I slike tilfeller kan det være verdt å identifisere og lagre løsningene på disse overlappende delproblemene, en teknikk er kjent som memoisering . Følgt til det ytterste, fører det til bunn-opp- del-og-erobre-algoritmer som dynamisk programmering og kartanalyse .

Languages

In other projects