Jaga-ja-valitse algoritm

Jaga-ja-valitse algoritmid on klass algoritme arvutiteaduses mis põhinevad mitmeharulisel rekursioonil. Jaga-ja-valitse algoritmid põhinevad probleemi kaheks või rohkemaks sarnaseks alamprobleemiks jagamisel, kuni need muutuvad piisavalt lihtsaks, et otseselt lahendada. Seejärel alamprobleemide lahendid kombineeritakse, et saada algse probleemi lahend.

See tehnika on alus efektiivsetele algoritmitele erinevate probleemide jaoks, näiteks sortimine (kiirsortimine, mestimissortimine), suurte arvude korrutamine (Karatsuba algoritm), lähima punktipaari leidmine ja lauseanalüüs.

Jaga-ja-valitse algoritmide põhimõte on sarnane matemaatilise induktsiooniga; viimane on ka viis nende algoritmide korrektsuse tõestamiseks. Jaga-ja-valitse algoritmide algoritmilist keerukust määratakse sageli rekurentsusseoste arvutamise teel.

 Jaga-ja-valitse 
Nime "jaga-ja-valitse" kasutatakse mõnikord algoritmide kohta, mis jagab iga probleemi vaid üheks alamprobleemiks, näiteks kahendotsingu algoritm sorditud loendis kirje leidmiseksThomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).. Neid algoritme saab implementeerida efektiivsemalt kui jaga-ja-valitse algoritme üldiselt; täpsemalt, kui need kasutavad sabarekursiooni, saab neid teisendada lihtsateks tsükliteks. Sellise laia definitsiooni korral aga võiks iga algorirmi, mis kasutab rekursiooni või tsükleid lugeda jaga-ja-valitse algoritmideks. Seetõttu osad autorid arvavad, et nime "jaga-ja-valitse" peaks kasutama vaid siis, kui iga probleem võib jaguneda kaheks või rohkemaks alamprobleemiksBrassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.. Ühe alamjuhuga klassi nimeks pakutakse "vähenda-ja-valitse."Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

Oluline rakendus jaga-ja-valitse algoritmidele on optimeerimine, kus, kui igal sammul otsinguruumi vähendatakse (pügatakse) konstantse teguri korda, siis algoritmil üldiselt on sama asümptootiline keerukus kui pügamissammul; keerukuse konstant sõltub pügamistegurist. Sellist algoritmi tuntakse ka kui püga-ja-jaga algoritmi.

 Varajased ajaloolised näited 
Varajased näited on peamiselt vähenda-ja-valitse: algprobleem vähendatakse üheks alamprobleemiks, ja on lahendatava iteratiivselt.

Kahendotsingul, kus alamprobleemid on ligikaudu pool algsest probleemist, on pikk ajalugu. Kuigi selge kirjeldus sellest algoritmist arvutitele avaldati 1946. aastal John Mauchly artiklis, siis idee sorteeritud loendite kasutamisest otsimise lihtsustamiseks on pärit hiljemalt Babülooniast 200 aastat eKrDonald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).. Veel üks varajane näide on Eukleidese algoritm suurima ühisteguri leidmiseks, mis jääb ajaliselt mitu sajandit eKr.

 Eelised 

 Keeruliste probleemide lahendamine 
Jaga-ja-valitse algoritmid on võimas tööriist ideeliselt keeruliste probleemide lahendamiseks: vaja on vaid viise probleemi alamprobleemideks jagamiseks, lihtsate juhtude lahendamiseks ja alamprobleemide lahendite kombineerimiseks. Sarnaselt, vähenda-ja-valitse vajab vaid probleemi üheks lihtsamaks alamjuhuks vähendamist, näiteks klassikalise Hanoi torni probleemi korral vähendatakse torni kõrgusega  liigutamine torni kõrgusega  liigutamiseks.

 Algoritmi efektiivsus 
Jaga-ja-valitse lähenemine sageli aitab leida kiireid algoritme. See oli võtmetähtsusega näiteks Karatsuba kiire korrutamise meetodi, kiirsortimise ja mestimissortimise, Strasseni algoritmi maatriksite korrutamise ja kiirete Fourier' teisenduste jaoks.

Kõikides nendes juhtudes viis jaga-ja-valitse lähenemise kasutamine parema asümptootilise keerukuseni. Näiteks, kui
 baasjuhul on konstandiga piiratud suurus
 töö probleemi alamprobleemideks jagamiseks ja lahendite kombineerimiseks on lineaarselt sõltuv probleemi suurusest 
 Leidub piiratud arv  alamprobleeme suurusega 
siis selle jaga-ja-valitse algoritmi keerukus on .

 Paralleelsus 
Jaga-ja-valitse algoritmid on loomupäraselt sobilikud paralleelarvutuseks,eriti jagatud mäluga süsteemides, kus andmevahetust protsessorite vahel ei ole vaja ette plaanida, sest eri alamprobleeme saab lahendata rööbiti.

 Mälukasutus 
Jaga-ja-valitse algoritmid loomupäraselt kipuvad efektiivselt kasutama protsessori vahemälusid, sest kui alamprobleem on piisavalt väike, siis selle ja kõik selle alamprobleemid saab, põhimõtteliselt, lahendada vahemälus, kasutamata aeglast põhimälu. Algoritmid, mis on disainitud kasutama vahemälu sel viisil, on vahemälu suurusest sõltumatud. Lisaks saab jaga-ja-valitse algoritme oluliste probleemide jaoks (näiteks sortimine) disainida olema vahemälu suurusest sõltumatult optimaalsed: nad kasutavad vahemälu tõenäosuslikult optimaalsel viisil, asümptootilises tähenduses, sõltumata vahemälu suurusest. Vastupidi, traditsiooniline lähenemine vahemälu kasutamisele on tükeldamine, kus probleem jagatakse sobiva suurusega tükkideks – ka see kasutab vahemälu optimaalselt, kuid vaid siis, kui algoritm on optimeeritud antud masina spetsiifilisele vahemälu suurusele.

Sama eelis kehtib ka muude hierarhiliste hoiusüsteemide korral, nagu näiteks NUMA ja virtuaalmälu, ning ka mitme vahemälu taseme korral: kui alamprobleem on piisavalt väike, saab seda lahendada antud hierarhiataseme sees, puutumata kõrgemaid (aeglasemaid) tasemeid.

 Ümardamine 
Arvutustes, kus kasutatakse ümardamist, näiteks ujukomaarvudega, võib jaga-ja-valitse algoritm anda täpsemaid tulemusi kui pealtnäha samaväärne iteratiivne algoritm. Näiteks, N arvu saab kokku liita kas lihtsa tsükliga, mis liidab iga andmepunkti ühele summamuutujale, või jaga-ja-valitse kaskaadliitmise algoritmiga, mis jagab andmed kaheks pooleks, rekursiivselt arvutab mõlema summa ja siis liidab need summad kokku. Kuigi teine algoritm teeb sama palju arvutusi kui teine, ja on rekursiooni tõttu aeglasem, on see tavaliselt täpsem.Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

 Implementeerimine 

 Rekursioon 
Jaga-ja-valitse algoritmide loomulik implementatsioon on rekursiooniga. Sel juhul parajasti lahendatava alamprobleemi ülemprobleemid hoitakse automaatselt kutsepinus.

 Eraldi pinu 
Jaga-ja-valitse algorime saab implementeerida ka mitte-rekursiivse programmiga, mis hoiab osalisi alamprobleeme mõnes eraldi andmestruktuuris, nagu näiteks pinus või riviloendis (queue). See lähenemine lubab rohkem valikut järgmise alamprobleemi valimisel, mis on osade rakenduste, nagu näiteks laiuti otsingu, korral oluline. See on ka standardne lähenemine programmeerimiskeeltes, mis ei toeta rekursiooni.

 Pinu suurus 
Rekursiivsetes jaga-ja-valitse algoritmide implementatsioonides on oluline jälgida, et kutsepinule on eraldatud piisavalt mälu, muul juhul võib jooksutamine ebaõnnestuda pinu ületäitumise tõttu. Enamikul aja suhtes efektiivsetel algoritmidel on siiski üsna väike rekursioonisügavus. Näiteks on võimalik kiirsortimist implementeerida nii, et see ei vaja kunagi rohkem kui  rekursioonisügavust  elemendi sortimiseks.

Pinu ületäitumist võib rekursiivsete implementatsioonide korral olla raske vältida, sest paljud kompilaatorid eeldavad, et kutsepinu on pidev mäluplokk ja osad eraldavad sellele konstantse hulga mälu. Lisaks võivad kompilaatorid pinus hoida rohkem andmeid kui on rangelt vajalik, nagu näiteks tagastusaadress, muutumatud parameetrid ja protseduuri sisemised muutujad. Seega saab pinu ületäitumise riski vähendada minimeerides rekursiivse protseduuri parameetreid ja sisemisi muutujaid või kasutades eraldi pinu struktuuri.

 Baasjuhtude valimine 
Iga rekursiivse algoritmi korral saab vabalt valida baasjuhud, rekursiooni lõpetamiseks otse lahendatavad väikesed alamprobleemid.

Väikseimate või lihtsaimate võimalike baasjuhtude valimine on elegantsem ja tavaliselt viib lihtsamate programmideni, sest on vaja arvestada väiksema hulga juhtudega ja neid on lihtsam lahendada. Näiteks kiirsortimise võib lõpetada, kui sisendiks on tühi loend, mispuhul on vaid üks baasjuht ja see ei vaja töötlemist.

Samas suureneb sageli efektiivsus, kui suhteliselt suurte baasjuhtude korral rekursioon lõpetada ja need juhud lahendada mitte-rekursiivelt; selline algoritm on hübriidalgoritm. See strateegia väldib rekursiivsete kutsete, mis teevad vähe või mitte üldse tööd, lisakulu ja võimaldab kasutada spetsiaalseid mitte-rekursiivseid algoritme, mis on nende kindlate baasjuhtude korral efektiivsemad.

Seega näiteks paljude teekide kiirsortimise implementatsioon lülitab ümber lihtsale tsüklipõhisele pistemeetodile (või sarnasele algoritmile), kui sorditavaid elemente on piisavalt vähe. Tuleb tähele panna, et kui tühi loend oleks ainus baasjuht, siis  elemendiga loendi sortimine nõuaks  kutset, mis ei tee midagi muud kui tagastavad kohe. Baasjuhtude suurendamine loenditeks kahe või vähema elemendiga eemaldab enamiku neist juhtudest ja üldisemalt baasjuhte suuremaid kui kaks kasutatakse, et vähendada ajakulu funktsioonikutsetele või pinu kasutusele.

 Korduvate alamprobleemide jagamine 
Osade probleemide korral võib naiivne rekursioon viia samade alamprobleemide mitu korda lahendamiseni. Sellistel juhtudel võib olla kasulik hoida alles lahendused nendele kattuvatele alamprobleemidele. Seda tehnikat nimetatakse mäluga rekursiooniks. Keerukam, aga veel efektiivsem lähenemine kattuvate alamprobleemiga probleemide lahendamiseks on dünaamiline programmeerimine.

 Viited 

 Välislingid 
 Ahto Truu korduvatest alamprobleemidest
 Algoritmide koostamise strateegiad (Tallinna Ülikool)

Kategooria:Algoritmid