Hladový algoritmus: Porovnání verzí

Přidáno 434 bajtů ,  před 8 lety
m
→‎Příklady: h. alg . x heuristika
m (→‎Hladová heuristika: ylepseni formulace)
m (→‎Příklady: h. alg . x heuristika)
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]]
*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 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 ==