Rozdeľuj a panuj (Divide and Conquer)
Množstvo algoritmických problémov je, čo sa týka štruktúry, rekurzívnych a je teda možné rozdeliť ich na podproblémy, ktoré sa dajú riešiť
obdobným spôsobom. Riešenie takýchto problémov pomocou metódy divide & conquer pozostáva z nasledujúcich častí:
a) Rozdelenie problému na časti (divide).
b) Rekurzívne vyriešenie každého z podproblémov (conquer). Ak je problém dostatočne malý, vyriešime ho nerekurzívne.
c) Spojenie riešení podproblémov do riešenia pôvodného problému (combine).
Príkladom techniky divide & conquer sú algoritmy triedenia
Quicksort a Mergesort.
Jednoduchší variant divide & conquer sa nazýva decrease and conquer. Tento vyrieši identický podproblém
a výsledok použije na riešenie väčšieho problému. Príkladom tejto techniky je binárne vyhľadávanie.
Dynamické programovanie (Dynamic Programming)
Keď optimálne riešenie problému je možné zostrojiť pomocou optimálnych riešení jeho podproblémov a je nutné podproblémy riešiť opakovane
(keď je veľa rovnakých vetiev v algoritme prehľadávania s návratom), je možné ušetriť čas použitím techniky dynamického programovania.
Najprv sa vyrieši každý podproblém systémom „zdola“ - od najmenšieho po najväčší. Riešenie jednotlivých podproblémov sa ukladá do tabuľky.
Takto sa každý podproblém navštívi a rieši len raz.
Hlavný rozdiel medzi dynamickým programovaním a divide & conquer je, že podproblémy v divide & conquer sú relatívne nezávislé a v dynamickom
programovaní sa prekrývajú. Rozdiel medzi dynamickým programovaním a priamou rekurziou je v zapamätávaní si rekurzívnych volaní. Keď sú
podproblémy nezávislé a nie je tam žiadne opakovanie, pamätanie údajov nepomáha k nájdeniu riešenia. Ak však je problém vhodne riešiteľný
dynamickým programovaním, je možné zredukovať exponenciálnu časovú zložitosť na polynomiálnu.
Žravé algoritmy (Greedy Algorithms)
Greedy algoritmus je podobný dynamickému programovaniu s tým rozdielom, že nie je potrebné poznať riešenie všetkých podproblémov v
každom bode riešenia. Namiesto toho môže byť zvolená možnosť, ktorá je v danom okamihu najvýhodnejšia. Táto technika neskúma všetky
možnosti a pre veľa problémov nedáva správne výsledky. Ak však funguje, je to najrýchlejšia metóda. Naprogramovať algoritmus, ktorý
používa greedy techniku je ľahké. Dokázať jeho správnosť však býva zvyčajne omnoho ťažšie.
Najznámejší algoritmus používajúci greedy techniku je Kruskalov algoritmus
na nájdenie najlacnejšej kostry grafu.