Hladový algoritmus

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 .

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 
 postupně procházíme posloupnost a vytváříme množiny 
 splňuje-li množina  danou podmínku, položíme 
 jinak 
 projdeme-li takto celou původní množinu, obsahuje množina  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ř. 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. 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ů. Pro každý předmět  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í  a zároveň je celková cena batohu  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

Související články 
 matroidy
 prohledávání stavového prostoru

Externí odkazy 
 

Kombinatorické algoritmy
Optimalizační algoritmy a metody
Teorie matroidů