V tomto výukovém programu se dozvíte, co je to chamtivý algoritmus. Najdete také příklad chamtivého přístupu.
Chamtivý algoritmus je přístup k řešení problému výběrem nejlepší možnosti, která je v danou chvíli k dispozici, bez obav z budoucího výsledku, který přinese. Jinými slovy, lokálně nejlepší volby se zaměřují na dosažení globálně nejlepších výsledků.
Tento algoritmus nemusí být nejlepší volbou pro všechny problémy. V některých případech může způsobit nesprávné výsledky.
Tento algoritmus se nikdy nevrátí, aby zvrátil učiněné rozhodnutí. Tento algoritmus pracuje v přístupu shora dolů.
Hlavní výhodou tohoto algoritmu je:
- Algoritmus je snazší popsat .
- Tento algoritmus může fungovat lépe než jiné algoritmy (ale ne ve všech případech).
Proveditelné řešení
Proveditelné řešení je takové, které poskytuje optimální řešení problému.
Chamtivý algoritmus
- Pro začátek je sada řešení (obsahující odpovědi) prázdná.
- V každém kroku je do sady řešení přidána položka.
- Pokud je sada řešení proveditelná, aktuální položka se uchová.
- Jinak je položka odmítnuta a nikdy znovu zvážena.
Příklad - chamtivý přístup
Problém: Musíte provést změnu částky pomocí co nejmenšího počtu mincí. Částka: $ 28 Dostupné mince: $ 5 coin $ 2 coin $ 1 coin
Řešení:
- Vytvořte prázdnou sadu řešení = ().
- coiny = (5, 2, 1)
- součet = 0
- Zatímco součet ≠ 28, proveďte následující.
- Vyberte si minci C z mincí tak, aby součet + C <28.
- Pokud C + součet> 28, nevrátí žádné řešení.
- Jinak součet = součet + C.
- Přidejte C do sady řešení.
Až do prvních 5 iterací obsahuje sada řešení 5 $ 5 coinů. Poté získáme 1 $ 2 coiny a nakonec 1 $ 1 coin.
Greedy Algorithm Applications
- Výběr řazení
- Problém s batohem
- Minimum Spanning Tree
- Problém s nejkratší cestou jednoho zdroje
- Problém s plánováním úloh
- Primův algoritmus minimálního rozpětí stromu
- Kruskalův algoritmus minimálního rozpětí stromů
- Dijkstrův algoritmus minimálního rozpětí stromů
- Huffman kódování
- Ford-Fulkersonův algoritmus
