Hladový algoritmus: Porovnání verzí

Odebráno 20 bajtů ,  před 1 rokem
m
Robot: vhodnější šablona dle žádosti ze dne 25. 4. 2020; kosmetické úpravy
m (+Kategorie:Optimalizační algoritmy a metody, -Kategorie:Algoritmy, +Kategorie:Kombinatorické algoritmy, +Kategorie:Teorie matroidů)
m (Robot: vhodnější šablona dle žádosti ze dne 25. 4. 2020; kosmetické úpravy)
[[Soubor:Greedy-search-path-example.gif|thumbnáhled|Příklad selhání hladového algoritmu v optimalizační úloze (nalezení největšího součtu v grafu).]]
'''Hladový algoritmus''' ({{Vjazyce|en}} {{CizojazyčněVjazyce2|en|'''greedy search'''}}) je jedním z možných způsobů řešení [[optimalizace (matematika)|optimalizačních]] úloh v [[Matematika|matematice]] a [[Informatika|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žina|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 <math>\mathit{w(A)} = \sum_{a \in A} w(a)</math>.
 
== Algoritmus ==
 
== 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
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í Huffmanova stromu v [[Huffmanovo kódování|Huffmanově kódování]]
* [[problém batohu]] pro dělitelné předměty (zlatý písek, diamantový prach apod.)
 
421 379

editací