Hladový algoritmus

Příklad selhání hladového algoritmu v optimalizační úloze (nalezení největšího součtu v grafu).

Hladový algoritmus (anglicky greedy search) 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}=\emptyset$
postupně procházíme posloupnost a vytváříme množiny $A_{i}$ $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ř. 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 $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]\leq 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

Související články