Hladový algoritmus

Z Wikipedie, otevřené encyklopedie

Hladový algoritmus je jedním z možných způsobů řešení optimalizačních úloh v 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)$ .

[editovat] 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í)

[editovat] Příklady

Hladové algoritmy se uplatňují například v následujích úlohách:

hledání minimální kostry grafu — Kruskalův algoritmus, Jarníkův algoritmus a Borůvkův algoritmus
problém obchodního cestujícího
problém batohu: 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 úkolů, 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 ř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.