Heuristické algoritmy
Heuristické algoritmy mohou být nazývány též jako stochastické algoritmy.
- algoritmus – posloupnost konečného počtu elementárních kroků vedoucí k vyřešení úlohy
- heuristika – teorie řešení problémů, neobvyklé řešení
- stochastický – náhodný
Obsah |
[editovat] Definice
Informatika jako věda o informacích a jejich zpracování chápe heuristiku jako postup získání řešení problému, které však není přesné a nemusí být nalezeno v krátkém čase. Slouží však nejčastěji jako metoda rychle poskytující dostatečné a dosti přesné řešení, které však nelze obecně dokázat. Nejčastější použití heuristického algoritmu nalezneme v případech, kde není možné použít jiného lepšího algoritmu, poskytujícího přesné řešení s obecným důkazem.
[editovat] Jiný, avšak podobný pohled na heuristiku
Heuristikou nazýváme postup, který, i když neprobere všechny možnosti, je schopný v některých případech podat výsledek. Výsledek je podáván zpravidla jedním ze dvou možných stavů. Buď jako kladný výsledek (odpověď) nebo jako výrok neurčitosti.
[editovat] Použití algoritmu
Heuristické algoritmy se začaly používat s příchodem výpočetní techniky, kde jsou rozvíjeny a často používány pro řešení složitých problémů. Jsou vhodné zejména pro řešení složitých funkcí s mnoha parametry a složitým průběhem s mnoha extrémy.
Například algoritmy deterministické jsou v řešení složitých problémů velmi špatně použitelné, protože jejich náročnost (zejména časová) roste, s lineárně rostoucím rozsahem problému, exponenciálně. Naopak výhodou je oproti heuristickým algoritmům nalezení přesného, optimálního řešení, které lze dokázat.
Velmi často se setkáváme s metodami kombinujícími heuristické algoritmy s deterministickými.
[editovat] Často používané metody heuristiky
- Genetický algoritmus – algoritmus založený na principu přirozené selekce. S úspěchem se využívá jako počítačový heuristický algoritmus schopný nalézt kvalitní řešení i složitého problému. v oblasti IT ho využijeme pro řešení mnoha technických a matematických problémů.
- Metoda lokálního hledání – jedná se o jednu z nejjednodušších metod. Dobře použitelná pro řešení matematických problémů.
- Iterativní metoda – využívá postupného hledání řešení ve stále se zúžující oblasti řešení (postupně se z dobrého řešení dopracovává k ještě lepšímu řešení).
- Hladový algoritmus – heuristika při prohledávání určí, které z možných pokračování si vybereme.
Metod je celá řada a každá má své klady a zápory. Mezi klady řadíme možnost nalezení přesného řešení. Mezi zápory dobu která je k provedení algoritmu potřeba, případně množství upřesňujících parametrů.
Větší jistotu, že nalezený výsledek je přesný, můžeme u některých metod zvýšit opakováním heuristického algoritmu.
Použití heuristických algoritmů je velmi dobře použitelné při řešení tzv. "Problému obchodního cestujícího", který má nejkratší cestou projít města vyznačená na mapě.
Běžně používané algoritmy využívající heuristiku, jejichž služeb využíváme každodenně, jsou algoritmy pro heuristickou analýzu integrované v antivirových software. Dále se heuristické algoritmy využívají pro odhalení e-mailového spamu, ve specializovaném vývojovém a simulačním software určeném pro různé oblastí použití (od strojírenství, přes oblast IT až po lékařství...).
