Cesko.wiki Hladový algoritmus
Author
Albert FloresHladový algoritmus je heuristický algoritmus používaný v informatice a matematice pro řešení problémů optimalizace. Jeho základní myšlenkou je vybírat v každém kroku nejlepší možnou volbu na základě aktuálního stavu. Hladový algoritmus je založen na egoistickém principu, který se snaží najít řešení, jež v daném kroku vypadá jako nejlepší, aniž by se zabýval dlouhodobou optimálností. Hladový algoritmus je jednoduchý a rychlý, avšak není vždy schopen nalézt globálně optimální řešení. Jeho výhodou je, že dokáže rychle vypočítat přibližné řešení, což ho činí vhodným pro problémy s velkým množstvím dat. Příkladem použití hladového algoritmu je problém obchodního cestujícího, kdy je cílem najít nejkratší trasu pro návštěvu určitého počtu měst. Hladový algoritmus by ve svém kroku vybral vždy nejbližší dostupné město, aniž by se zabýval celkovou délkou trasy. Výsledné řešení nebude nejkratší možné, ale bude přijatelné ve velkém měřítku. Hladový algoritmus lze upravit nebo kombinovat s jinými algoritmy a technikami, aby se dosáhlo lepších výsledků. Přestože nemusí být nejlepší volbou pro všechny problémy, je hladový algoritmus cenným nástrojem pro rychlou a přibližnou optimalizaci.
Příklad selhání hladového algoritmu v optimalizační úloze (nalezení největšího součtu v grafu). Hladový algoritmus je jedním z možných způsobů řešení optimalizačních úloh v matematice a informatice. V každém svém kroku vybírá lokální minimum, přičemž existuje šance, že takto nalezne minimum globální. Hladový algoritmus se uplatní v případě, kdy je třeba z množiny určitých objektů vybrat takovou podmnožinu, která splňuje jistou předem danou vlastnost a navíc má minimální (případně maximální) ohodnocení. Ohodnocení je obvykle reálné číslo w, přiřazené každému objektu dané množiny, ohodnocení množiny A je definováno jako \mathit{w(A)} = \sum_{a \in A} w(a).
Algoritmus
# všechny prvky původní množiny setřídíme do posloupnosti podle rostoucí nebo klesající váhy podle toho, zda chceme výsledek minimalizovat nebo maximalizovat # položíme A_0 = \empty # postupně procházíme posloupnost a vytváříme množiny A_i #* splňuje-li množina A_{i-1} \cup \{i\} danou podmínku, položíme A_i = A_{i-1} \cup \{i\} #* jinak A_i = A_{i-1} # projdeme-li takto celou původní množinu, obsahuje množina A_n prvky, splňující danou vlastnost, a to takové, že součet jejich ohodnocení je minimální (maximální)
Různé významy hladového algoritmu
Pojem hladový algoritmus se (i zde) používá ve dvou významech: * 1) druh (optimalizačních) problémů, které jsou správně řešeny hladovým algoritmem * 2) hladová heuristika
Problémy řešitelné hladovým algoritmem
Některé optimalizační problémy jsou řešitelné hladovým algoritmem (popsaným výše), přičemž je zaručeno, že takový algoritmus najde globálně optimální řešení. Z níže popsaných mezi ně patří hledání kostry grafu, problém batohu pro dělitelné předměty a dále např. +more stavba Huffmanova stromu v Huffmanově kódování.
Teorie je založena na matroidech.
Obecnější přístup použitelný na víc problémů je dynamické programování.
Hladová heuristika
I když hladový algoritmus nevede ke globálně optimálnímu řešení, můžeme hladový výběr z přípustných možností použít jako heuristiku, která snad vrátí dostatečně dobré řešení. Například v problému obchodního cestujícího lze jako prodloužení cesty vybírat nejbližší ještě nenavštívené město.
Takto se hladová heuristika používá pro řešení NP-těžkých problémů, protože pro ně není znám efektivní způsob přesného řešení. Hladovou heuristiku lze použít v aproximačních algoritmech anebo ji s nimi zkombinovat, tj. +more jednou se vyřeší problém aproximačně se zárukou chyby a pak mnohokrát heuristicky.
Z hlediska prohledávání stavového prostoru hladový výběr změn je způsob lokálního prohledávání.
Příklady
Hladové algoritmy se uplatňují například v následujících úlohách: * hledání minimální kostry grafu - Kruskalův algoritmus, Jarníkův algoritmus a Borůvkův algoritmus * budování Huffmanova stromu v Huffmanově kódování * problém batohu pro dělitelné předměty (zlatý písek, diamantový prach apod.)
Hladovou heuristiku nelze použít např. pro * problém obchodního cestujícího * problém batohu pro nedělitelné předměty: máme dáno n předmětů. +more Pro každý předmět i = 1, \ldots, n máme dánu hmotnost W[i] a cenu P[i]. Je dána kapacita C. Úkolem je najít takovou podmnožinu množiny předmětů, pro niž platí \sum_{i = 1}^{n} x[i]\cdot W[i] \le C a zároveň je celková cena batohu \sum_{i = 1}^{n} x[i]\cdot P[i] je co největší (x je vektor; je-li x[i] = 1, pak i-tý předmět do dané podmnožiny patří, je-li x[i] = 0, pak do ní nepatří). Pro nepřesné (suboptimální) řešení této úlohy pomocí hladového algoritmu stačí setřídit předměty podle rostoucího poměru cena/hmotnost, podmínka na množinu je, že součet hmotností předmětů musí být menší nebo roven C. * pro problém vrcholového pokrytí dává hladová heuristika pro některé grafy libovolněkrát horší výsledky než aproximační algoritmus.