Hladový algoritmus: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
Thijs!bot (diskuse | příspěvky)
ZéroBot (diskuse | příspěvky)
m robot přidal: sk:Pažravý algoritmus
Řádek 37: Řádek 37:
[[pt:Algoritmo guloso]]
[[pt:Algoritmo guloso]]
[[ru:Жадный алгоритм]]
[[ru:Жадный алгоритм]]
[[sk:Pažravý algoritmus]]
[[sl:Požrešna metoda]]
[[sl:Požrešna metoda]]
[[sr:Похлепни алгоритам]]
[[sr:Похлепни алгоритам]]

Verze z 3. 9. 2010, 15:40

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í)

Příklady

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

  • hledání minimální kostry grafuKruskalů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 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.

Související články