Kasutaja:Aetella/Algoritmide tüübid
Algoritmi tüüpi saab määrata selle järgi, millise lähenemisega antud probleemi lahendatakse.
1. Jaga ja valitse algoritmid[muuda | muuda lähteteksti]
Jaga ja valitse algoritm (inglise keeles "divide-and-conquer algorithm") aga ka põhineb mitmeharulisel rekursioonil, kus algoritm kutsub ennast ise välja lihtsama juhu jaoks ehk probleemi lahendus sõltub sama probleemi lihtsama juhu lahendusest. Probleem jagatakse alaprobleemideks, mis omakorda lahendatakse ning kombineeritakse, et lahendada algne probleem.[1][2] Sarnaselt matemaatilisele induktsioonile saab eristada baasi ja sammu.[3] Kombineerides sellist algoritmi otsingutabeliga, kuhu salvestatakse alaprobleemide lahendused (et vältida nende korduvat lahendamist ja hoida nii kokku arvutusaega), võib seda meetodit nimetada dünaamiliseks programmeerimiseks.
2. Tagurdusmeetodil põhinevad algoritmid[muuda | muuda lähteteksti]
Tagurusmeetodil pannakse algoritmi alguses paika esimene element, siis teine jne. Kui mingil etapil ei saa panna kirja järgmist element, siis liigutakse tagasi eelmise elemendi juurde ning proovitakse uut elementi.
Tagurdusmeetodit on hea kasutada näiteks Sudokude lahendamisel. Igas etapis täidetakse üks kast numbriga. Kui mingil hetkel jõuab lahendaja olukorrani, kus kasti ei saa midagi panna, siis minnakse eelmise kasti juurde asendatakse seal olev element muu sobiva elemendiga. Kui sellist asendus pole võimalik teha, siis liigutakse sellest eelmise kasti.[4]
3. Ahned algoritmid[muuda | muuda lähteteksti]
Ahne algoritm valib igas etapis antud valikute hulgast välja kõige optimaalsema. Protsess kordub nii kaua kuni ülesanne on täidetud. Sellised algoritmid on efektiivsed, kuid sageli ei anna kogu programmi mõttes optimaalseimat tulemust.
Olgu antud väärtused 1, 3 ja 4 ning ülesandeks on leida vähim kogus elemente, mille summa on 6. Ahne algoritm valib esimeses etapis 4, teises etapis 1 ning kolmandas etapis 1. Tagastab, et vaja on kolme elementi. Samas on võimalik moodustada summa vaid kahe elemendiga(3+3).
Tuntud ahned algoritmid on näiteks Dijkstra algoritm ja Primi algoritm.
4. Toore jõu algoritmid[muuda | muuda lähteteksti]
5. Dünaamilise programmeerimise algoritmid[muuda | muuda lähteteksti]
- ↑ Sanjoy Dasqupta, Christos Papadimitriou, Umesh Vazirani (2008). Algorithms. Lk 45.
{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link) - ↑ Graham Ronald. "Concrete Mathematics" (inglise). Vaadatud 30.01.2020.
- ↑ Jaanus Pöial. "Programmeerimise algkursus Java baasil". Vaadatud 30.01.2020.
- ↑ Targo Tennisberg, Katrin Babrel (2017). Võistlusprogrammeerimine, 1.osa. Lk 70,192.