Metoda hrubé síly (Brute Force Algorithm)
Zpravidla lze rychle navrhnout naivní řešení, které přímo vychází z definice problému. Toto řešení spočívá ve vyzkoušení všech variant řešení problému a vybrání nejlepšího z nich. Toto řešení, ale zpravidla nebývá příliš efektivní. Lze aplikovat pouze na malé datové soubory, zpravidla n ≤ 10.
Heuristické algoritmy
Vygenerováno velké množství potenciálních řešení. Na rozdíl od metody hrubé síly nikoliv všechny varianty. Z nich hledáno nejlepší možné řešení.
Použití heuristiky: NP úlohy, optimalizační problémy.
Základní techniky heuristiky:
- Iterativní algoritmy: Postupné hledání řešení nad zmenšující se množinou možných řešení, kvalita řešení se v každém dalším kroku zlepšuje.
- Hladové algoritmy: V každém dílčím kroku hledáno optimální řešení. Hledáním lokálního minima chceme nalézt globální minimum.
- Genetické algoritmy: Založeny na principech evoluční biologie. Do dalšího kroku přežívají pouze perspektivní řešení, která jsou dále zlepšována drobnou modifikací (křížením)
Kvalita řešení Cílem nalezení přípustného řešení.
Hodnocení kvality nalezeného řešení: Odchylka nalezeného řešení mA od optimálního mopt Hodnoceno pomerem k k = mA/mopt Nalezené řešení představuje k% optima (např. 90%). Jako optimální mu ̊že být posuzováno dosud nejlepší nalezené řešení. Počet kroků vedoucích k nalezení řešení Snaha o co nejrychlejší konvergenci algoritmu. Důležitá volba podmínky ukončující iteraci.
Metoda rozděl a panul (Divide and Conquer)
Metoda opakovaného rozdělování problému na menší a jednodušší podproblémy. Dělení prováděno dokud není řešení podproblému triviální (tj. většinou přímé). Hodí se pro dekomponovatelné úlohy, tj. úlohy které lze vůbec rozdělitit na podúlohy stejného nebo podobného typu.
Hodí se pro dekomponovatelné úlohy, tj. úlohy rozdělitelné na podúlohy stejného nebo podobného typu. Dělení prováděno dokud není řešení podproblému triviální (tj. většinou přímé). Takové řešení umíme zpravidla nalézt bez složitých výpočtů. Podproblémy řešeny nezávisle na sobě a poté jejich řešení spojena v celek, čímž získáme řešení původního problému.
Odhad složitosti: Θ(n log n), ale O(N2). Techniky řešení: Rekurze, iterace.
Příklady:
- třídí algoritmy ([Merge sort], [Quick Sort])
- výpočetní geometrie (Convex Hull, Voronoi Diagram, Delaunay Triangulace...)
- kartografická generalizace (Douglas Peucker Algorithm)
Inkrementální algoritmy
Druhy inkrementálních algoritmů
-
Inkrementální vkládání (Incremental Insertion) Při běhu nemusí být k dispozici celá vstupní množina dat (on-line metoda). Data vybírána ze vstupní množiny buď randomizovaně nebo dle určitých pravidel.
-
Inkrementální konstrukce (Incremental Construction) Většinou pomalejší než inkrementální vkládání. Není on-line. Data zpracovávána podle požadavků algoritmu, nemohou být přidávaná na vstup randomizovaně. Příklad algoritmů: Swepline, Delaunay triangulace
-
Inkrementální výběr. Příklad algoritmů: konvexní obálky, Voronoi Diagramy
Randomizované algoritmy
Výhody a nevýhody:
- snadnost implementace,
- vylepšení špatných vlastností algoritmů (špatný Worst Case, dobrý Average Case), - nelze použít pro NP problémy, Dělení randomizovaných algoritmů:
Randomizované inkrementální algoritmy: Zpravidla náhodný výběr prvku ze vstupní množiny, použití např. u triangulací.
Randomizované Divide & Conquer algoritmy: Náhodný výběr prvku majícího předpokládané statistické parametry. Např. [Quick Sort], náhodné stanovení mediánu.
Typy vzorkování Jednoduché vzorkování Všechny prvky vstupní množiny mají stejnou pravděpodobnost pro zařazení do vzorku. Položky vybrány náhodně, nemusí být rovnoměrně rozloženy.
Systematické vzorkování Výběr každé n-té položky, první položka vybrána náhodně. Výhodou lepší rozložení položek v souboru.
Shlukové vzorkování Ze vstupní množiny vybrán náhodný / předem daný počet vzorků. Zpracovány všechny prvky každého vybraného vzorku.
Použití: Třídící algoritmy, konvexní obálky, triangulace, hledání průsečíků.