Hladový algoritmus: Porovnání verzí
To chce klid (a trochu rozumu); |
hladový ve dvou významech |
||
Řádek 8: | Řádek 8: | ||
#*jinak <math>A_i = A_{i-1}</math> |
#*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í) |
#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 == |
== Příklady == |
Verze z 7. 6. 2011, 19:20
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
- 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
- položíme
- postupně procházíme posloupnost a vytváříme množiny
- splňuje-li množina danou podmínku, položíme
- jinak
- 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í)
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 Huffmanova stromu v Huffmanově kódování.
Teorie je založena na matroidech.
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í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ího prohledávání.
Příklady
Hladové algoritmy se uplatňují například v následujících úlohách:
- hledání minimální kostry grafu — Kruskalů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.