náhled|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 .
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
Kategorie:Kombinatorické algoritmy Kategorie:Optimalizační algoritmy a metody Kategorie:Teorie matroidů