Greedy (pažravé) algoritmy, problém change-making (rozmenenie sumy, mincovka), divide-and-conquer (rozdeľuj a panuj), dynamické programovanie (zhora-nadol, zdola-nahor), backtracking.
Typy algoritmov a spôsoby riešenia
Existujú rôzne spôsoby riešenia algoritmických problémov. Ak máme nejaký problém ktorý sa dá riešiť algoritmicky, môžeme ho riešiť viacerými spôsobmi. Niektoré spôsoby sú už zaužívané a dajú sa použiť pre riešenie viacero typov problémov:
Greedy (pažravé) algoritmy
Podľa môjho názoru jedny z najľahšie pochopiteľných algoritmov. Ak máme nejaký problém, snažíme sa vždy vyberať tú najlepšiu variantu (môže to byť napríklad vždy najväčšie číslo). Je to zároveň algoritmus, ktorý častokrát podvedome používame v reálnom živote a možno si to ani neuvedomujeme. Napríklad, ak máme usporiadať čísla od najväčšieho po najmenšie, ako by sme postupovali inštinktívne? Pravdepodobne by sme vybrali najväčšie číslo, potom druhé najväčšie, a tak ďalej... Princíp je taký, že vždy vyberieme najväčšie číslo. A práve takto fungujú pažravé algoritmy – vždy sa snažia vybrať tú možnosť, ktorá je v aktuálnom bode riešenia problému optimálna. Avšak, nie vždy to vyústi k tomu že záverečné riešenie je optimálne.
Change-making problém
Change-making problém (taktiež nazývaný v slovenčine aj ako "mincovka") je problém, kde máme danú určitú peňažnú sumu a pre túto sumu musíme nájsť minimálny počet mincí ktoré môžeme použiť pre rozmenenie tejto sumy. Napríklad, sumu 1,23 € by sme rozmenili ako: 1 € + 0,20 € + 0,02 € + 0,01 €.
Štandardne máme v tomto probléme k dispozícií ako platidlo mince so sumami: 2 €; 1 €; 0,50 €; 0,20 €; 0,10 €; 0,05 €; 0,02 € a 0,01 €, ale problém rozmenenia sumy dokáže nájsť minimálny počet mincí pre akúkoľvek množinu hodnôt mincí (platidiel, pretože ak je hodnota vyššia tak sú to bankovky).
Tento problém sa najľahšie (a intuitívne) rieši pomocou pažravého algoritmu, preto je aj vhodný príklad pre lepšie pochopenie pažravých algoritmov: jednoducho prechádzame množinou všetkých mincí a zakaždým od sumy pre rozmenenie odčítame túto sumu. Ak sa táto suma už nevmestí (výsledok je menej ako 0), prejdeme na ďalšiu mincu. Takto pokračujeme až dokým nevyčerpáme všetky mince.
Poďme si skúsiť naprogramovať riešenie mincovky v Pythone, za pomoci pažravého algoritmu:
Riešenie mincovky sa dá aplikovať v reálnom živote v bankomatoch alebo rôznych predajných, parkovacích a iných automatoch ktoré rozmieňajú peňažné sumy.
Optimálnosť riešenia
Aj napriek tomu, že pažravé algoritmy sú z hľadiska implementácie vcelku priamočiare a jednoduché, v niektorých prípadoch nenájdu vždy optimálne riešenie.
Povedzme, že by sme mali ako platidlá zvolené neštandardné hodnoty: 6 €, 5 € a 1 €. Máme rozmeniť sumu 10 € – ako by postupoval pažravý algoritmus? Vždy by sme použili mincu s najväčšou hodnotou, takže: 6 €, potom by nasledovalo 5 €. Lenže 6 + 5 = 11 €, a to sa už do našej sumy 10 € nevmestí. Pažravý algoritmus by teda rozmenil sumu ako: 6 € + 1 € + 1 € + 1 € + 1 € = 10 €. To je správne riešenie, avšak nie je optimálne. Predsa sumu 10 € môžeme rozmeniť oveľa efektívnejšie, iba ako 5 € + 5 €!
Tu sa stretávame s neoptimálnym algoritmom. Nie je garantované, že pažravý algoritmus nájde vždy optimálne riešenie (v niektorých prípadoch môžu byť vstupné hodnoty zadané tak, že algoritmus sa náhodou trafí a vráti optimálne riešenie, ale to nie je garantované).
Naopak, optimálne algoritmy prehľadávajú všetky možnosti tak, aby vrátili vždy optimálne riešenie (za cenu toho, že môžu byť časovo viacej náročné, keďže pracujú neintuitívne a musia prehľadať všetky alternatívy v ktorých by mohlo byť skryté správne riešenie). Pri voľbe vhodného algoritmu pre náš prípad použitia musíme tiež dbať na to, či je garantované že nájdu optimálne riešenie. Inými slovami, musíme voliť medzi rýchlosťou vs. presnosťou ktoré nám ponúkajú rôzne algoritmy.
Divide-and-conquer (rozdeľuj a panuj)
.
Dynamické programovanie
.
Dynamické programovanie zhora-nadol
.
Dynamické programovanie zdola-nahor
.
Backtracking
.