Podeli pa vladaj (informatika)

U informatici, podeli pa vladaj je strategija dizajniranja algoritama zasnovana na rekurziji sa višestrukim grananjem. Ovakvi algoritmi se zasnivaju na rekurzivnom razlaganju problema na dva ili više podproblema istog (ili sličnog) tipa (podeli), sve dok problem ne postane dovoljno jednostavan da se može direktno rešiti (vladaj). Rešenja tih podproblema se nakon toga sjedinjavaju i daju rešenje polaznog problema.

Ova strategija je osnova efikasnih algoritama za rešavanje raznolikih problema, kao što je problem sortiranja (npr. Algoritam brzog sortiranja, Algoritam sortiranja objedinjavanjem, problem množenja velikih brojeva (npr. Karacubin aloritam), problem pronalaženja dve najbliže tačke, sintaksna analiza (npr. analiza naniže i izračunavanje diskretne Furijeove transformacije.

Shvatanje i dizajn algoritama zasnovanih na ovoj strategiji je složena veština koja zahteva dobro razumevanje prirode problema koji treba da se reši, kao što pri dokazivanju teoreme matematičkom indukcijom početni problem treba zameniti opštijim ili komplikovanijim problemom, kako bi se krenulo u rekurzivno rešavanje, pri čemu ne postoji opšti metod za pronalaženje prave generalizacije. Ovakve komplikacije se izražavaju pri optimizaciji izračunavanja Fibonačijevog broja efikasnom dvostrukom rekurzijom.

Ispravnost algoritama zasnovanih na razlaganju se obično dokazuje matematičkom indukcijom, a složenost izračunavanja se određuje rešavanjem rekurentnih jednačina.

Pojednostavi pa vladaj

Naziv podeli pa vladaj se ponekad koristi i za algoritme koji smanjuju početni problem na samo jedan podproblem, kao kod algoritma binarne pretrage za pronalaženje vrednosti u povezanoj listi ili numeričkom izračunavanju algoritmom bisekcije za pronalaženje korena. Ovakvi algoritmi se mogu implementirati efikasnije drugim strategijama, na primer ako je u pitanju repna rekurzija, ona se može zameniti jednostavnim petljama. Po definiciji, u širem smislu, svaki algoritam koji je zasnovan na petljama i rekurziji se može smatrati Podeli pa vladaj algoritmom, stoga neki autori smatraju da ovaj naziv treba koristiti samo kada se početni problem razlaže na dva ili više podproblema. Naziv koji oni predlažu za algoritme koji početni problem razlažu na samo jedan podproblem je Pojednostavi pa vladaj.

Važna primena pojednostavi pa vladaj algoritama je optimizacija, gde ako se prostor pretrage smanjuje za konstantan faktor u svakom koraku, celokupan algoritam ima istu asimptotsku složenost kao i korak odsecanja, pri čemu konstanta zavisi od faktora odsecanja (od sume geometrijskog reda). Na ovaj način se dobija algoritam koji se naziva Pretraga odsecanjem (en. prune and search).

Primer: Maksimalna vrednost niza

Neka je dat niz a = {2, 3, -2, 5, 12, 15, 100, 22, -5}, u kojem treba pronaći maksimalnu vrednost. Rekurzivno rešenje po ovom principu bi glasilo:

Pretpoziv:
0. Pozovi algoritam max za niz a, u granicama od prvog do poslednjeg elementa (označavamo ih, redom, sa l i r).

Algoritam:
1. Ukoliko je l > r, završilo se sa pretragom niza ili je niz bio prazan.
   Vrati najmanju moguću vrednost.
2. Ukoliko je l = r, to znači da više nema elemenata za
   poređenje. Rezultat je a[l], odnosno a[r].
3. Ukoliko je razlika između l i r samo 1, uporediti a[l] i a[r]
   i vratiti veći od njih.

4. U ostalim slučajevima izračunati p = (l+r)/2 i pozvati ovaj isti
   algoritam dva puta:
      1. Za niz a u granicama od l do p
      2. Za niz a u granicama od p+1 do r

   Rezultate oba poziva uporediti i vratiti veći broj.

Pojednostavljenje, koje se postiže ovim algoritmom, je da se uvek porede dva elementa ili vrati samo jedan preostali broj; tj. kada niz ima dužinu veću od 2, u jednom pozivu algoritma se ne porede svi elementi. Sledi šematski prikaz na kome se može videti na koji način algoritam deli i obrađuje niz:

Legenda:        - Prosleđene granice (pod)nizova        - Vraćeni maksimumi (pod)nizova        - Numeracija podnizova

Treba primetiti da se obrada podnizova I i VI može paralelizovati, jer bi se radilo o pozivima istog algoritma nad dva podniza. Ovi pozivi ne moraju da znaju ništa o drugim pozivima, već samo da pozivu u kome su pozvani vrate svoje rezultate koje će on obraditi.

Pod uslovom da se svi potrebni pozivi mogu paralelizovati, složenost ovakvog algoritma je određena visinom nacrtanog grafa. Konkretno, pošto se niz stalno deli na dva dela, složenost ovog algoritma pri obradi niza od n elemenata će biti O(log₂n), što je manje od O(n), koliko bi iznosila složenost linearne pretrage.

Rani istorijski primeri

Rani primeri ovakvih algoritama su prvenstveno Pojednostavi pa vladaj, odnosno bazni problem koji se sukcesivno razlaže na jedan podproblem se zaista može rešiti iterativno.

Algoritam binarne pretrage, odnosno pojednostavi pa vladaj algoritam u kome je veličina podproblema polovina početnog ima dugu istoriju. Iako se celokupan opis algoritma pojavio 1946. godine u članku Džona Moučlija, ideja upotrebe sortirane liste predmeta radi olakšavanja pretrage datira još iz Vavilona, oko 200. godine p.n.e. . Euklidov algoritam koji je opisan oko 300. godine p.n.e. je još jedan primer starih pojednostavi pa vladaj algoritama.

Rani primer podeli pa vladaj algoritama sa većim brojem podproblema je Gausov opis iz 1805. godine, koji je danas poznat kao algoritam Koli-Tukejeve brze Furijeove transformacije. Kako Gaus nije analizirao broj operacija potrebnih za njegovo izvršavanje, ovaj algoritam nije postao široko rasprostranjen sve do njegovog ponovnog otkrića, više od jednog veka kasnije.

Drugi primer je algoritam sortiranja objedinjavanjem, koji početni problem deli na dva podproblema. Ovaj podeli pa vladaj algoritam je razvio Džon fon Nojman 1945. godine.

Još jedan značajan primer je algoritam Anatolija Karacube iz 1960. godine kojim bi se dva n-tocifrena broja mogla pomnožiti u $O(n^{\log _{2}3})$ operacija (izraženo u veliko O notaciji). Ovaj aloritam je opovrgao Andrej Kolmogorov 1956. godine hipotezom da bi bilo potrebno $\Omega {(n^{2})}$ operacija za izvršavanje algoritma.

Kao još jedan primer podeli pa vladaj algoritama, koji nije izvorno razvijen za računare, je Knutov metod koji pošta obično koristi za usmeravanje pošiljki: pisma se sortiraju u različite džakove za različita geografska područja, a zatim se sadržaj svakog džaka sortira u pakete za manja područja i slično, sve dok ne budu isporučena. Ovaj metod je povezan i sa radiks sortiranjem, opisanim za sortiranje bušenih kartica još 1929. godine.

Prednosti

Rešavanje teških problema

Strategija podeli pa vladaj je posebno pogodna za rešavanje konceptualno teških problema: sve što je potrebno je da se pronađe način da se polazni problem podeli na podprobleme, kao i da se reše trivijalni slučajevi i iskombinuju rešenja podproblema. Slično, strategija pojednostavi pa vladaj zahteva jedino da se problem pojednostavi, čime se dobija "manji" problem. Klasičan primer je problem kula Hanoja u kome se početni broj, odnosno n, diskova svodi na podproblem veličine n-1.

Efikasnost algoritama

Paradigma podeli pa vladaj često vodi otkrivanju efikasnih algoritama. Neki problemi za koje je ova paradigma bila ključna su Karacubin metod brzog množenja brojeva, algoritmi brzog sortiranja i sortiranja objedinjavanjem, Štrasenov algoritam za množenje matrica, kao i brze Furijeove transformacije.

U ovim primerima, pristup podeli pa vladaj je doveo do poboljšanja asimptotske složenosti rešenja. Na primer, ako je veličina baznih slučajeva konstantna, podela problema i kombinovanje parcijalnih problema je proporcionalna veličini polaznog problema n, i ako postoji p potproblema približne veličine n/p u svakom koraku, tada je asimptotska složenost podli pa vladaj algoritma $O(n\log _{p}{n})$ .

Paralelizam

Algoritmi zasnovani na strategiji podeli pa vladaj su prirodno pogodni za izvršavanje na višeprocesorskim mašinama, pogotovo na sistemima sa deljenom memorijom, gde tok podataka između više procesora ne mora da bude unapred isplaniran jer zasebni podproblemi mogu da se izvršavaju na različitim procesorima.

Pristup memoriji

Podeli pa vladaj algoritmi prirodno efikasno upotrebljavaju keš memoriju jer kada je podproblem dovoljno mali, on i svi njegovi podproblemi mogu, u principu, da budu rešeni u okviru keša, bez potrebe za pristupom sporijoj glavnoj memoriji. Algoritam koji je dizajniran tako da keš memoriju koristi na ovako opisan način se naziva algoritam koji nije svestan keš memorije, zbog toga što ne sadrži eksplicitno veličinu (ili veličine) keša kao parametar. Štaviše, ova strategija se može upotrebiti za konstrukciju važnih algoritama (npr. sortiranje, brze Furijeove transformacije, množenje matrica) tako da koristi keš memoriju na optimalan način, u asimptotskom smislu, bez obzira na njenu veličinu, za razliku od tradicionalnog pristupa koji blokira keš. Primer blokiranja keš memorije bi bila optimizacija ugnježdenosti petlje, gde se polazni problem eksplicitno deli na "parčiće" odgovarajuće veličine. Ipak, treba napomenuti da i pored toga, keš može biti optimalno iskorišćen, ali samo u slučaju da je algoritam konstruisan za specifičnu veličinu keša konkretne mašine na kojoj se izvršava algoritam.

Pored keš memorije, iste pogodnosti postoje i za ostale vrste memorije (hijerarhijski), kao što su virtuelna memorija, ali i različiti nivoi keš memorije (kada je podproblem dovoljno mali), u datom nivou hijerarhije bez pristupa višim (i sporijim) nivoima.

Kontrola zaokruživanja

Pri izračunavanju sa "zaokruživom" aritmetikom, npr. sa brojevima u pokretnom zarezu, podeli pa vladaj algoritam može dati tačnije rezultate od površnih ekvivalentnih iterativnih metoda. Na primer, N brojeva se mogu sabrati pomoću jednostavne petlje koja dodaje svaki broj na tekuću sumu, ili pomoću podeli pa vladaj algoritma sume parova koji deli skup vrednosti na dve polovine, rekurzivno izračunava sumu za obe polovine, posle čega sabira te dve vrednosti i tako daje konačan rezultat. Iako drugi metod izvršava isti broj operacija sabiranja kao i prvi, pri čemu postoji i cena rekurzivnih poziva, on je obično tačniji.

Problemi sa implementacijom

Rekurzija

Podeli pa vladaj algoritmi se prirodno impelentiraju rekurzivno. U tom slučaju, parcijalni podproblemi koji vode do rešenja početnog problema, se automatski smeštaju na stek poziva. Rekurzivna funkcija je zapravo ona funkcija koja poziva samu sebe u okviru svoje definicije.

Eksplicitan stek

Podeli pa vladaj algoritmi se takođe mogu implementirati nerekurzivno, kao program koji skladišti parcijalne podprobleme u neku strukturu podataka kao što su: stek, red, ili red sa prioritetom. Ovakav pristup daje više slobode u izboru podproblema koji treba da bude rešen sledeći, što je važna osobina u nekim primenama, npr. kod pretrage grafa u širinu ili metoda separacije i evaluacije za optimizaciju. Ovaj pristup je takođe standardno rešenje programskih jezika koji ne podržavaju rekurzivne procedure.

Veličina steka

U rekurzivnoj implementaciji podeli pa vladaj algoritama, treba voditi računa da postoji dovoljno alocirane memorije za stek rekurzivnih poziva, u suprotnom izvršavanje algoritma može da zakaže zbog prekoračenja kapaciteta steka. Na svu sreću, podeli pa vladaj algoritmi koji su vremenski efikasni često nemaju veliki broj rekurzivnih poziva. Na primer, algoritam brzog sortiranja se može implementirati tako da nikada ne zahteva više od $\log _{2}{n}$ ugnježdenih rekurzivnih poziva za sortiranje n članova niza.

Prekoračenje kapaciteta steka može biti teško za izbegavanje pri korišćenju rekurzivnih procedura, pošto mnogi kompilatori pretpostavljaju da rekurzivni stek zauzima neki memorijski prostor koji se lako može proširiti, a mnogi drugi alociraju fiksan memorijski prostor za stek. Kompilatori, takođe, mogu imati više informacija u steku nego što je zaista potrebno, kao što su adresa povratka iz tekućeg poziva, parametri koji se ne menjaju u toku poziva, ili lokalne promenljive procedure. Odatle sledi da se rizik od prekoračenja kapaciteta se može smanjiti korišćenjem manjeg broja parametara i lokalnih promenljivih u okviru rekurzivne procedure, i/ili korišćenjem neke od struktura podataka opisanih ranije.

Izbor baznih slučajeva

U okviru bilo kog rekurzivnog algoritma, postoji određena sloboda u izboru baznih slučajeva, manjih podproblema koji se direktno rešavaju da bi se izašlo iz rekurzivnog poziva.

Izbor manjih ili jednostavnijih mogućih baznih slučajeva je elegantniji i obično vodi do jednostavnijih programa, jer postoji manje slučajeva koje treba razmotriti i koji su lakši za rešavanje. Na primer, algoritam brze Furijeove transformacije može zaustaviti rekurziju kada ulaz predstavlja jedan uzorak, a algoritam brzog sortiranja se može zaustaviti kada na ulazu nema više elemenata. U oba primera postoji samo jedan bazni slučaj za razmatranje, i on ne zahteva dalju obradu.

Sa druge strane, efikasnost se često poboljšava ukoliko se rekurzija zaustavi sa relativno velikim baznim slučajevima, koji se rešavaju nerekurzivno, čime se dobija hibridni algoritam. Korišćenjem ove strategije izbegavaju se rekurzivni pozivi koji obavljaju malo ili ne obavljaju nimalo posla, dopušta se upotreba specijalizovanih nerekurzivnih algoritama, koji su za te bazne slučajeve efikasniji od klasične rekurzije. Uobičajna procedura za jednostavni hibridno rekurzivni algoritam je kratko spajanje baznog slučaja (arm's-length rekurzija). U ovom slučaju, provera da li će sledeći korak predstavljati bazni slučaj za sledeći rekurzivni poziv se izvršava pre poziva funkcije, čime se izbegava nepotreban poziv. Na primer, u stablu, pre ulaska u novi rekurzivni poziv za sledeći čvor treba proveriti da li za trenutni čvor uopšte postoji sledeći, umesto provere tek nakon ulaska u novi poziv, čime se izbegava polovina rekurzivnih poziva kod nekih algoritama za binarna stabla. Kako podeli pa vladaj algoritam na kraju redukuje svaki problem ili podproblem na veliki broj novih baznih instanci, koje dosta utiču na ukupnu cenu algoritma, naročito kada postoji mali broj spajanja/razdvajanja u prethodnom pozivu. Važno je uzeti u obzir da ova razmatranja ne zavise od toga da li rekurziju implementira kompilator ili je implementirana eksplicitnim korišćenjem steka.

Odatle, na primer, mnoge bibliotečke implementacije algoritma brzog sortiranja (kviksort algoritma) će rekurzivni poziv zameniti sortiranjem umetanjem ili nekim sličnim algoritmom koji je zasnovan na iteracijama, kada broj preostalih elemenata postane dovoljno mali. Važno je napomenuti i da ako bi prazan skup elemenata bio jedini bazni slučaj, sortiranje skupa od n elemenata bi rezultovalo sa maksimalno n rekurzivnih poziva kviksort algoritma, koji ne bi imali da izvršavaju ništa, osim momentalnog povratka iz poziva. Povećavanje baze ima za posledicu da se za skupove veličine 2 ili manje eliminiše većina poziva u kojima se ništa ne radi. Opštije, baza veća od 2 se obično koristi za smanjenje vremena potrošenog u prethodnim rekurzivnim pozivima ili smanjenje eksplicitno kreiranog steka.

Alternativno, mogu se napraviti veliki bazni slučajevi koji bi još uvek koristili podeli pa vladaj algoritam, ali bi implementirali algoritam za pre-određivanje skupa fiksnih veličina za koje bi rekurzivni algoritam prešao u nerekurzivni, algoritam bez petlje, ili u algoritam bez uslova. Na primer, ovaj pristup se koristi u nekim efikasnim implementacijama brzih Furijeovih transformacija, u kojima bazni slučajevi predstavljaju razvijene implementacije podeli pa vladaj algoritama brzih Furijeovih transformacija za skup fiksne veličine. Metode za generisanje koda se mogu koristiti za pronalaženje velikog broja različitih baznih slučajeva, koje su poželjne za efikasnu implementaciju ove strategije.

Generalizovana verzija ove ideje je poznata kao "razvijanje" rekurzije i različite tehnike su predložene za automatizaciju procedure ukrupnjavanja baznog slučaja.

Ponavljanje podproblema

Za neke probleme, u okviru rekurzivnog grananja, neki podproblemi se mogu izračunavati i po nekoliko puta. U takvim slučajevima, može biti korisno odrediti i sačuvati rešenja ovih preklapajućih podproblema. Ova tehnika je poznata kao memorizacija, i njenim doslovnim praćenjem se dolazi do bottom-up podeli pa vladaj algoritama, kao što je slučaj kod dinamičkog programiranja.

Vidi još

• Hipsort
• Kviksort
• Merdžsort
• Binarna pretraga