Hladový algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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 Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle \mathit{w(A)} = \sum_{a \in A} w(a)} .

Algoritmus[editovat | editovat zdroj]

  1. 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
  2. položíme Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle A_0 = \empty}
  3. postupně procházíme posloupnost a vytváříme množiny Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): A_{i}
    • splňuje-li množina Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle A_{i-1}\cup \{i\}} danou podmínku, položíme Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle A_i = A_{i-1} \cup \{i\}}
    • jinak Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle A_i = A_{i-1}}
  4. projdeme-li takto celou původní množinu, obsahuje množina Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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

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 Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle 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í Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle \sum_{i = 1}^{n} x[i]\cdot W[i] \le C} 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[editovat | editovat zdroj]