Algoritmide tüübid

Algoritmide klassifitseerimiseks on erinevaid viise, millest igaühel on oma eelised.

Rakendusmeetodi alusel muuda

Üks viis algoritmide klassifitseerimiseks on rakendusmeetodi alusel.

Rekursiivne algoritm

Rekursiivne algoritm on algoritm, mis kutsub ennast välja (viitab endale) korduvalt, kuni teatud tingimus (tuntud ka kui lõpetamise tingimus) on täidetud. See on levinud meetod funktsionaalses programmeerimises. Iteratiivsed algoritmid kasutavad ette antud ülesannete lahendamiseks korduvaid konstruktsioone (nt tsükleid) ja mõnikord täiendavaid andmestruktuure (nt pinud). Mõned ülesanded sobivad loomult paremini ühe või teise rakendusmeetodi abil lahendatavaks. Näiteks Hanoi tornid on rekursiivse rakendamise abil hästi mõistetavad. Igal rekursiivsel versioonil on samaväärne (kuid võib-olla rohkem või vähem keerukas) iteratiivne versioon ja vastupidi.

Loogiline algoritm

Algoritmi võib vaadelda kui kontrollitud loogilist deduktsiooni. Seda mõistet võib väljendada järgmiselt: Algoritm = loogika + juhtimine.^[1] Loogikakomponent väljendab aksioome, mida võib arvutamisel kasutada ja juhtkomponent määrab viisi, kuidas aksioomidele deduktsiooni rakendatakse. See on loogilise programmeerimise paradigma aluseks. Puhastes loogilistes programmeerimiskeeltes on juhtkomponent fikseeritud ja algoritmid määratakse ainult loogikakomponendiga. Selle lähenemisviisi võlu seisneb elegantses semantikas: aksioomide muutus toob algoritmis kaasa täpselt määratletud muutuse.

Jada-, paralleel- või hajutatud algoritm

Algoritme käsitletakse tavaliselt eeldusel, et arvutid täidavad korraga ühte algoritmi käsku. Neid arvuteid nimetatakse mõnikord jadaarvutiteks. Jadaarvutite jaoks loodud algoritmi nimetatakse jadaalgoritmiks. Jadaalgoritmid on sisuliselt erinevalt paralleelalgoritmidest või hajutatud algoritmidest. Paralleelsed algoritmid kasutavad ära arvutiarhitektuure, kus mitu protsessorit võimaldavad arvutil mitme erineva ülesandega samaaegselt tegeleda, samas kui hajutatud algoritmid kasutavad mitut ühte arvutivõrku ühendatud arvutit. Paralleelsed või hajutatud algoritmid jagavad ülesande sümmeetrilisteks või asümmeetrilisteks alamülesanneteks ja koguvad hiljem tulemused kokku. Selliste algoritmide ressursikulu ei seisne ainult protsessori tsüklites igas protsessoris, vaid ka protsessorite vahelises suhtluses. Mõningaid sorteerimisalgoritme saab tõhusalt paralleliseerida, kuid nende omavaheline suhtlus on kulukas. Iteratiivsed algoritmid on üldiselt paralleliseeritavad. Mõnel ülesandel pole paralleelseid algoritme ja neid nimetatakse oma olemuselt jadaülesanneteks.

Deterministlik või mittedeterministlik algoritm

Deterministlikud algoritmid lahendavad ülesande täpse otsusega algoritmi igal sammul, samas kui mittedeterministlikud algoritmid lahendavad ülesandeid arvamise teel, kuigi tüüpilisi oletusi muudetakse täpsemaks heuristika abil.

Täpne või ligikaudne algoritm

Kui paljud algoritmid jõuavad täpse lahenduseni, siis ligikaudsed algoritmid otsivad ligikaudsust, mis on tõelisele lahendusele lähemal. Ligikaudsuse saab saavutada kas deterministliku või juhusliku strateegia abil. Sellistel algoritmidel on paljude keeruliste ülesannete jaoks praktiline väärtus. Üks ligikaudse algoritmi näidetest on "seljakoti ülesanne" (knapsack problem), kus on ette antud hulk asju ja eesmärk on pakkida seljakott nii, et see oleks maksimaalse koguväärtusega. Igal esemel on teatud kaal ja väärtus ning kogukaal, mida kaasas kanda saab, ei ole suurem kui mingi kindel arv X. Seega peab lahendus arvestama nii esemete kaalu kui ka väärtust.^[2]

Kvant-algoritm

Sellised algoritmid töötavad realistliku kvantarvutuse mudeli alusel. Seda terminit kasutatakse tavaliselt selliste algoritmide kohta, mis tunduvad oma olemuselt kvantidena või kasutavad mõnda kvantarvutuse olulist omadust nagu kvantsuperpositsioon või kvantpõimumine.

Disaini paradigma alusel muuda

Teine viis algoritmide klassifitseerimiseks on nende disainimetoodika või paradigma alusel. On teatud arv paradigmasid, millest igaüks on erinev. Lisaks sisaldab igaüks neist kategooriatest palju erinevaid tüüpe algoritme. Mõned levinumad paradigmad on järgmised:

Jõumeetod (Brute-force) või põhjaliku otsingu meetod (exhaustive search)

See on naiivne meetod proovida kõiki võimalikke lahendusi, et näha, milline on parim.^[3]

Jaga-ja-valitse algoritm (Divide and conquer)

Jaga-ja-valitse algoritm jagab ülesande korduvalt kaheks või rohkemaks alamülesandeks (tavaliselt rekursiivselt), kuni alamülesanded on piisavalt väikesed, et neid lihtsalt lahendada. Üks selline jaga-ja-valitse näide on mestimissortimine. Sortida saab igat andmesegmenti pärast andmete segmentideks jagamist ja kogu andmete sortimist saab teha valitsemise faasis segmentide mestimise teel. Lihtsamat varianti jaga-ja-valitse algoritmist nimetatakse vähenda-ja-valitse algoritmiks, mis lahendab identse alamülesande ja kasutab selle alamülesande lahendust suurema ülesande lahendamiseks. Jaga-ja-valitse jagab ülesande mitmeks alamülesandeks ja seega on valitsemise etapp keerulisem kui vähenda-ja-valitse algoritmide puhul. Näide vähenda-ja-valitse algoritmist on binaarotsingu algoritm.

Otsingu- ja loendusalgoritmid

Paljusid ülesandeid (näiteks malemängu) saab modelleerida ülesannetena graafidel. Graafi uurimisalgoritm määrab graafil ringi liikumise reeglid ja on kasulik selliste ülesannete korral. Sellesse kategooriasse kuuluvad ka otsingualgoritmid, haru- ja piiranguloendusalgoritmid ning tagurdusalgoritmid.

Juhuslik algoritm

Sellised algoritmid teevad mõned valikud juhuslikult (või pseudojuhuslikult). Need võivad olla väga kasulikud ligikaudsete lahenduste leidmisel ülesannetele, kus täpsete lahenduste leidmine võib olla ebapraktiline (vt allpool heuristlikku meetodit). Mõnede selliste ülesannete puhul on teada, et kiireimad lähendused peavad hõlmama teatud juhuslikkust.^[4] See, kas polünoomilise aja keerukusega randomiseeritud algoritmid võivad olla mõne ülesande lahendamiseks kiireimad algoritmid, on lahtine küsimus, mida tuntakse P versus NP ülesandena. Sellised algoritmid jagunevad kaheks suureks klassiks:

Monte Carlo algoritmid tagastavad õige vastuse suure tõenäosusega. Nt RP on nende alamklass, mis töötavad polünoomilises ajas.
Las Vegase algoritmid tagastavad alati õige vastuse, kuid nende tööaeg on ainult tõenäosuslikult seotud, nt ZPP.

Keerukuse vähendamise meetod

See meetod hõlmab keerulise ülesande lahendamist, muutes selle paremini tuntud ülesandeks, mille jaoks on meil (loodetavasti) asümptootiliselt optimaalsed algoritmid. Eesmärk on leida redutseeriv algoritm, mille keerukuses ei domineeriks saadud redutseeritud algoritmid. Näiteks üks valikualgoritm sortimata loendist mediaani leidmiseks hõlmab esmalt loendi sortimist (kulukas osa) ja seejärel sorteeritud loendi keskmise elemendi välja toomist (odav osa). Seda tehnikat tuntakse ka kui teisenda-ja-valitse algoritm.

Tagurdusmeetod (Back tracking)

Selle lähenemisviisi puhul ehitatakse mitu lahendust järk-järgult ja loobutakse, kui saab kindlaks tehtud, et need ei saa viia kehtiva täislahenduseni.

Optimeerimise ülesanded muuda

Optimeerimise ülesannete jaoks on olemas spetsiifilisem algoritmide klassifikatsioon; algoritm selliste ülesannete jaoks võib kuuluda ühte või mitmesse ülalkirjeldatud üldkategooriasse, samuti ühte järgmistest:

Lineaarprogrammeerimine

Lineaarse võrdsuse ja ebavõrdsuse piirangutega seotud lineaarfunktsioonile optimaalsete lahenduste otsimisel saab ülesande piiranguid kasutada vahetult optimaalsete lahenduste loomisel. On algoritme, mis suudavad lahendada selle kategooria mis tahes ülesande, näiteks populaarne simpleksalgoritm.^[5] Lineaarprogrammeerimise abil lahendatavate ülesannete alla kuulub ka näiteks suunatud graafide maksimaalse voolu ülesanne. Kui ülesanne nõuab lisaks, et üks või mitu tundmatut peavad olema täisarvud, klassifitseeritakse see täisarvulise programmeerimise alla. Lineaarprogrammeerimise algoritm suudab sellise ülesande lahendada, kui suudetakse tõestada, et kõik täisarvuliste väärtuste piirangud on pealiskaudsed, st lahendused vastavad neile piirangutele nagunii. Üldjuhul kasutatakse olenevalt ülesande raskusastmest kas spetsiaalset algoritmi või ligikaudseid lahendusi leidvat algoritmi.

Dünaamiline programmeerimine

Kui ülesanne näitab optimaalseid alamstruktuure – mis tähendab, et ülesande optimaalse lahenduse saab koostada alamülesannete optimaalsetest lahendustest – ja kattuvaid alamülesandeid, mis tähendab, et samu alamülesandeid kasutatakse paljude erinevate ülesannete lahendamiseks, väldib kiirem lähenemine, mida nimetatakse dünaamiliseks programmeerimiseks, lahenduste uuesti arvutamist, kui need on juba välja arvutatud. Näiteks Floydi-Warshalli algoritm, mille abil saab leida lühima tee eesmärgini kaalutud graafi tipust, kasutades kõigist külgnevatest tippudest eesmärgini viivat lühimat teed. Dünaamiline programmeerimine ja memoiseerimine käivad käsikäes. Peamine erinevus dünaamilise programmeerimise ja jaga-ja-valitse algoritmi vahel on see, et jaga-ja-valitse algoritmi alamülesanded on vähem või rohkem sõltumatud, samas kui dünaamilises programmeerimises alamülesanded kattuvad. Dünaamilise programmeerimise ja otsese rekursiooni erinevus seisneb rekursiivsete väljakutsete vahemällu salvestamises või memoiseerimises. Kui alamülesanded on sõltumatud ja kordusi ei esine, siis pole memoiseerimisest kasu, seega ei ole dünaamiline programmeerimine kõigi keeruliste ülesannete lahendus. Memoiseerimise või juba lahendatud alamülesannete kohta tabeli pidamise abil vähendab dünaamiline programmeerimine paljude ülesannete eksponentsiaalset olemust polünoomilise keerukusega.

Ahne meetod (The greedy method)

Ahne algoritm sarnaneb dünaamilise programmeerimise algoritmiga selle poolest, et see uurib alamstruktuure, antud juhul mitte ülesande omi, vaid etteantud lahenduse alamstruktuure. Sellised algoritmid saavad alguse mingist lahendusest, mis võib olla ette antud või on mingil moel konstrueeritud, ja täiustavad seda väikeste muudatuste tegemisega. Mõne ülesande puhul leiavad nad optimaalse lahenduse, teiste puhul aga peatuvad lokaalsel optimumil, st lahendustel, mida algoritm ei saa parandada, kuid mis ei ole optimaalsed. Ahnete algoritmide levinuim kasutusala on minimaalse täispuu leidmine, kus selle meetodi abil on võimalik leida optimaalne lahendus. Huffmani puu, Kruskal, Prim, Sollin on ahned algoritmid, mis suudavad selle optimeerimise ülesannet lahendada.

Heuristiline meetod

Optimeerimise ülesannetes saab heuristiliste algoritmide abil leida optimaalsele lahendusele lähedase lahenduse juhtudel, kui optimaalse lahenduse leidmine on ebapraktiline. Nende algoritmide tööpõhimõte on jõuda edenedes optimaalsele lahendusele aina lähemale. Põhimõtteliselt kui neid lõpmatult kaua jooksutada, siis jõuavad nad lõpuks ka optimaalse lahenduseni. Nende eelis seisneb aga selles, et nad suudavad suhteliselt lühikese aja jooksul leida optimaalsele lahendusele väga lähedase lahenduse. Sellised algoritmid on näiteks lokaalne otsing, tabuotsing, simuleeritud anniilimine ja geneetilised algoritmid. Mõned neist, nagu simuleeritud anniilimine, on mittedeterministlikud algoritmid, samas kui teised, nagu tabuotsing, on deterministlikud. Kui mitteoptimaalse lahenduse vea piir on teada, liigitatakse algoritm veelgi täpsemalt ligikaudseks algoritmiks.

Teadusvaldkonna alusel muuda

Vaata ka: Algoritmide loend

Igal teadusvaldkonnal on oma ülesanded, mis vajavad tõhusaid algoritme. Ühe valdkonna seotud ülesandeid uuritakse sageli koos. Mõned näited klassidest on otsingualgoritmid, sortimisalgoritmid, mestimisalgoritmid, numbrilised algoritmid, graafialgoritmid, sõnealgoritmid, arvutuslikud geomeetrilised algoritmid, kombinatoorsed algoritmid, meditsiinilised algoritmid, masinõpe, krüptograafia, andmete tihendamise algoritmid ja parsimistehnikad.

Valdkonnad kipuvad üksteisega kattuma ja algoritmide edusammud ühes valdkonnas võivad parandada teiste, mõnikord täiesti mitteseotud valdkondade tulemusi. Näiteks dünaamiline programmeerimine leiutati tööstuse ressursside tarbimise optimeerimiseks, kuid nüüd kasutatakse seda paljudes valdkondades paljude ülesannete lahendamiseks.

Keerukuse alusel muuda

Algoritme saab klassifitseerida nende täitmiseks kuluva aja järgi, võrreldes nende sisendi suurusega:

Konstantne aeg: kui algoritmi täitmiseks kuluv aeg on sama, olenemata sisendi suurusest. Nt juurdepääs massiivi elemendile.
Logaritmiline aeg: kui aeg on sisendi suuruse logaritmiline funktsioon. Nt binaarotsingu algoritm.
Lineaarne aeg: kui aeg on võrdeline sisendi suurusega. Nt nimekirja traavers.
Polünoomaeg: kui aeg on sisendi suuruse aste. Nt mullsortimise algoritmil on ruutkeskne ajaline keerukus.
Eksponentaeg: kui aeg on sisendi suuruse eksponentsiaalne funktsioon. Nt jõumeetodil otsing.

Mõnel ülesandel võib olla mitu erineva keerukusega algoritmi, samas kui teistel ülesannetel ei pruugi olla ühtegi algoritmi või puuduvad teadaolevad tõhusad algoritmid. Samuti on mõnest ülesandest olemas kaardistused teistele ülesannetele. Tänu sellele leiti, et algoritmide asemel on sobivam liigitada ülesanded endid ekvivalentsusklassidesse, lähtudes nende jaoks parimate võimalike algoritmide keerukusest.

Pidevad algoritmid muuda

Omadussõna "pidev", kui see on lisatud sõnale "algoritm", võib tähendada kas:

Algoritmi, mis töötab andmetel, mis esindavad pidevaid suurusi, kuigi need andmed on esitatud diskreetsete ligikaudsuste kaudu – selliseid algoritme uuritakse numbrilises analüüsis; või
Algoritmi diferentsiaalvõrrandi kujul, mis, töötades analoogarvutis, tegutseb pidevalt andmetega.^[6]

Viited muuda

↑ Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. 22 (7): 424–436. DOI:10.1145/359131.359136. S2CID 2509896.
↑ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems | Hans Kellerer | Springer (inglise). Springer. DOI:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID 28836720. Originaali arhiivikoopia seisuga 18. oktoober 2017.
↑ Carroll, Sue; Daughtrey, Taz (4. juuli 2007). Fundamental Concepts for the Software Quality Engineer. American Society for Quality. Lk 282 et seq. ISBN 978-0-87389-720-4.
↑ Näiteks kumera polütoobi ruumala saab suure täpsusega lähendada randomiseeritud polünoomilise aja algoritmi abil, kuid mitte deterministliku algoritmiga: Dyer, Martin; Frieze, Alan; Kannan, Ravi (jaanuar 1991), "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies", J. ACM, 38 (1): 1–17, CiteSeerX 10.1.1.145.4600, DOI:10.1145/102782.102783, S2CID 13268711.
↑ George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
↑ Tsypkin (1971). Adaptation and learning in automatic systems. Academic Press. Lk 54. ISBN 978-0-08-095582-7.

[1] Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. 22 (7): 424–436. DOI:10.1145/359131.359136. S2CID 2509896.

[2] Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems | Hans Kellerer | Springer (inglise). Springer. DOI:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID 28836720. Originaali arhiivikoopia seisuga 18. oktoober 2017.

[3] Carroll, Sue; Daughtrey, Taz (4. juuli 2007). Fundamental Concepts for the Software Quality Engineer. American Society for Quality. Lk 282 et seq. ISBN 978-0-87389-720-4.

[4] Näiteks kumera polütoobi ruumala saab suure täpsusega lähendada randomiseeritud polünoomilise aja algoritmi abil, kuid mitte deterministliku algoritmiga: Dyer, Martin; Frieze, Alan; Kannan, Ravi (jaanuar 1991), "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies", J. ACM, 38 (1): 1–17, CiteSeerX 10.1.1.145.4600, DOI:10.1145/102782.102783, S2CID 13268711.

[5] George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.

[6] Tsypkin (1971). Adaptation and learning in automatic systems. Academic Press. Lk 54. ISBN 978-0-08-095582-7.

[1]

[2]

[3]

[4]

[5]

[6]