Hladový algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: sk:Pažravý algoritmus |
|||
Řádek 12: | Řádek 12: | ||
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]] |
||
*[[problém obchodního cestujícího]] |
*[[problém obchodního cestujícího]] (to by som chcel vidiet) |
||
*[[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]]: 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. |
||
Verze z 11. 4. 2011, 17:04
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
- 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í)
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
- problém obchodního cestujícího (to by som chcel vidiet)
- problém batohu: 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 ř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.