Hladový algoritmus: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
m →‎Hladová heuristika: ylepseni formulace
m →‎Příklady: h. alg . x heuristika
Řádek 31: Řádek 31:
Hladové algoritmy se uplatňují například v následujících úlohách:
Hladové algoritmy se uplatňují například v následujících úlohách:
*hledání [[kostra grafu|minimální kostry]] [[Graf (teorie grafů)|grafu]] — [[Kruskalův algoritmus]], [[Jarníkův algoritmus]] a [[Borůvkův algoritmus]]
*hledání [[kostra grafu|minimální kostry]] [[Graf (teorie grafů)|grafu]] — [[Kruskalův algoritmus]], [[Jarníkův algoritmus]] a [[Borůvkův algoritmus]]
*budování Huffmannova stromu v [[Huffmannovo kódování|Huffmannově kódování]]
*[[problém batohu]] pro dělitelné předměty (zlatý písek, diamantový prach a pod.)

Hladovou heuristiku lze použít např. pro
*[[problém obchodního cestujícího]]
*[[problém obchodního cestujícího]]
*[[problém batohu]]: máme dáno ''n'' předmětů. Pro každý předmět <math>i = 1, \ldots, n</math> 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í <math>\sum_{i = 1}^{n} x[i]\cdot W[i] \le C</math> a zároveň je celková cena batohu <math>\sum_{i = 1}^{n} x[i]\cdot P[i]</math> 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ěr]]u cena/hmotnost, podmínka na množinu je, že součet hmotností předmětů musí být menší nebo roven C.
*[[problém batohu]] pro nedělitelné předměty: máme dáno ''n'' předmětů. Pro každý předmět <math>i = 1, \ldots, n</math> 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í <math>\sum_{i = 1}^{n} x[i]\cdot W[i] \le C</math> a zároveň je celková cena batohu <math>\sum_{i = 1}^{n} x[i]\cdot P[i]</math> 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ěr]]u 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 ==
== Související články ==

Verze z 5. 2. 2013, 22:50

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 .

Algoritmus

  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
  3. postupně procházíme posloupnost a vytváříme množiny
    • splňuje-li množina danou podmínku, položíme
    • jinak
  4. 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:

Hladovou heuristiku lze 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