V tomto tutoriáli sa dozviete, čo je to chamtivý algoritmus. Nájdete tiež príklad chamtivého prístupu.
Chamtivý algoritmus je prístup k riešeniu problému výberom najlepšej možnosti, ktorá je momentálne k dispozícii, bez obáv z budúceho výsledku, ktorý prinesie. Inými slovami, lokálne najlepšie možnosti sú zamerané na dosiahnutie globálne najlepších výsledkov.
Tento algoritmus nemusí byť najlepšou voľbou pre všetky problémy. V niektorých prípadoch môže spôsobiť nesprávne výsledky.
Tento algoritmus sa nikdy nevráti späť, aby zmenil prijaté rozhodnutie. Tento algoritmus funguje zhora nadol.
Hlavnou výhodou tohto algoritmu je:
- Algoritmus je ľahšie opísať .
- Tento algoritmus môže fungovať lepšie ako iné algoritmy (ale nie vo všetkých prípadoch).
Realizovateľné riešenie
Realizovateľné riešenie je riešenie, ktoré poskytuje optimálne riešenie problému.
Chamtivý algoritmus
- Na začiatok je sada riešení (obsahujúca odpovede) prázdna.
- V každom kroku sa do súpravy roztoku pridá položka.
- Ak je sada riešení možná, aktuálna položka sa uchová.
- V opačnom prípade je položka odmietnutá a už nikdy sa nezvažuje.
Príklad - chamtivý prístup
Problém: Musíte zmeniť sumu s použitím najmenšieho možného počtu mincí. Suma: 28 dolárov Dostupné mince: mince 5 dolárov, mince 2 doláre, mince 1 dolár
Riešenie:
- Vytvorte prázdnu množinu riešení = ().
- coiny = (5, 2, 1)
- súčet = 0
- Zatiaľ čo súčet ≠ 28, postupujte takto.
- Vyberte mincu C z mincí, ktorých súčet je + C <28.
- Ak C + súčet> 28, nevráti žiadne riešenie.
- Inak, súčet = súčet + C.
- Pridajte C do sady riešení.
Až do prvých 5 iterácií obsahuje sada riešení 5 coinov v hodnote 5 dolárov. Potom dostaneme 1 mincu 2 doláre a nakoniec 1 mincu 1 dolár.
Chamtivé algoritmické aplikácie
- Výber Zoradiť
- Problém s batohom
- Minimálny rozpätie stromu
- Problém s najkratšou cestou jedného zdroja
- Problém s plánovaním práce
- Algoritmus minimálneho rozpätia stromu Prim
- Kruskalov algoritmus minimálneho rozpätia stromov
- Dijkstraov algoritmus minimálneho rozpätia stromov
- Huffmanovo kódovanie
- Ford-Fulkersonov algoritmus