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:
Divide-and-conquer (rozdeľuj a panuj)
.
Dynamické programovanie
.
Dynamické programovanie zhora-nadol
.
Dynamické programovanie zdola-nahor
.
Backtracking
.