Hladový algoritmus: Porovnání verzí

Přidáno 1 705 bajtů ,  před 10 lety
hladový ve dvou významech
(To chce klid (a trochu rozumu);)
(hladový ve dvou významech)
#*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 ==