Hladový algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
To chce klid (a trochu rozumu); |
hladový ve dvou významech |
||
Řádek 8:
#*jinak <math>A_i = A_{i-1}</math>
#projdeme-li takto celou původní množinu, obsahuje množina <math>A_n</math> 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 [[Huffmanův strom|Huffmanova stromu]] v [[Huffmanovo kódování|Huffmanově kódování]].
Teorie je založena na [[matroid]]ech.
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ů, pro které není znám efektivní způsob přesného řešení. Hladovou heuristiku lze použít v [[aproximační algoritmus|aproximačních algoritmech]] anebo s nima skombinovat, 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í prohledávání|lokálního prohledávání]].
== Příklady ==
| |||