Heuristické algoritmy

Heuristické algoritmy jsou takové algoritmy, které při svém výpočtu používají heuristiku. Algoritmus typicky obsahuje možnost volby pokračování výpočtu, tj. která data, v jakém pořadí a jak se budou zpracovávat. Tato konkrétní volba, tzv. strategie, je pak heuristická (viz návrhový vzor strategy).

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.

Pojem heuristický algoritmus se obvykle používá pro algoritmy, které neposkytují (matematické) záruky kvality řešení, případně kdy nevíme, zda heuristika uspěje. Viz část Souvislosti.

• 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ý

Vlastnosti

Je vhodné si uvědomit, že heuristika může selhat. Podle druhu problému a použité heuristiky to znamená, že algoritmus nevydá správné řešení, žádné řešení, optimální řešení, běží déle, ...

Algoritmus, který obsahuje rozhodování, ale neurčuje konkrétní použitou heuristiku/strategii, se nazývá generický algoritmus (neplést s generickým programováním). Jádro tohoto přístupu vystihuje návrhový vzor strategie.

Pro konkrétní problém může existovat víc heuristik. Například jsou vhodné nebo přímo navrženy pro určité druhy dat anebo mají jiný poměr cena/výkon (tj. rychlost/kvalita). Pokud známe typická data, lze navrhnout heuristiku tak, aby dobře zpracovala tato typická data.

Výběr pokračování výpočtu může být náhodný místo heuristický, případně kombinovaný, tj. většinou se řídí heuristikou a s malou pravděpodobností náhodou (s použitím generátoru pseudonáhodných čísel). Podobně lze kombinovat několik heuristik v rámci jednoho výpočtu, například deterministicky nebo náhodně.

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 způsobů. Buď jako kladný výsledek (odpověď), nebo jako výrok neurčitosti.

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ě (...zpochybněno). Naopak výhodou je oproti heuristickým algoritmům nalezení přesného, optimálního řešení, které lze dokázat. Lépe řečeno, o algoritmu se dokáže, že vrací optimální řešení. O výsledném řešení se už nic nedokazuje.

Velmi často se setkáváme s metodami kombinujícími heuristické algoritmy s deterministickými.

Č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 zužující oblasti řešení (postupně se z dobrého řešení dopracovává k ještě lepšímu řešení).
• použití "hladové heuristiky" (viz Hladový algoritmus) na prohledávací problém, který není řešitelný hladově. Heuristika při prohledávání určí nejslibnější z možných pokračování a to 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í, typicky rychleji než u přesných algoritmů. Mezi zápory dobu, která je k provedení algoritmu potřeba, případně množství upřesňujících parametrů. (zpochybněno: heuristické alg. používáme tam, kde přesný výpočet trvá dlouho. Některé heuristiky jsou proto navrhovány s ohledem na rychlost provedení)

Kromě obecných heuristik (a metaheuristik) se heuristiky navrhují speciálně pro jeden konkrétní problém, resp. algoritmus, anebo dokonce jen pro určitou třídu vstupních dat (např. pouze pro rovinné grafy místo obecných grafů)

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. Aby se jednotlivé běhy heuristiky neopakovaly, lze použít náhodná čísla anebo různé počáteční konfigurace.

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 (''zpochybněno'': spíš pravděpodobnostní výpočty, i když mohou vypadat jak alchymie), 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í...).

Souvislosti

Pro optimalizační problémy, teda hledání minima anebo maxima funkce na nějaké množině, aproximační algoritmy na rozdíl od heuristických obvykle poskytují odhad kvality vydaného řešení. Pokud pro problém existuje aproximační algoritmus, pak je vhodné spustit aproximační algoritmus jednou a heuristický případně opakovaně. Takto dostaneme dobré výsledky od heuristiky se zárukou, protože pokud heuristika i opakovaně selže, máme výsledek se zárukou od aproximačního algoritmu.

Pro rozhodovací problémy, na které se odpovídá ANO/NE, se mluví o pravděpodobnostním algoritmu, pokud poskytuje záruky na pravděpodobnost špatné odpovědi. Pravděpodobnostní algoritmus může odpovídat taky NEVÍM, občas.

Externí odkazy

• Obrázky, zvuky či videa k tématu heuristické algoritmy na Wikimedia Commons
• Aproximativní a heuristické metody řešení NP-těžkých problémů
• www.unitime.org/~muller/heurist02_present.pdf
• dsp.vscht.cz/konference_matlab/matlab00/matousra.pdf
• www.bakal06.chytrak.cz/2006_K48.pdf Archivováno 30. 12. 2008 na Wayback Machine.