Obsah:
Definice - Co znamená Greedy Algorithm?
Chamtivý algoritmus je algoritmická strategie, která dělá nejlepší optimální volbu v každé malé fázi s cílem toho nakonec vést k globálně optimálnímu řešení. To znamená, že algoritmus vybere nejlepší řešení v tuto chvíli bez ohledu na důsledky. Vybírá nejlepší okamžitý výstup, ale nebere v úvahu celkový obraz, proto je považován za chamtivý.
Techopedia vysvětluje Greedy Algorithm
Chamtivý algoritmus funguje tak, že v každém kroku vybere nejlepší možnou odpověď a poté přejde k dalšímu kroku, dokud nedosáhne konce, bez ohledu na celkové řešení. Doufá pouze, že cesta, kterou zvolí, je globálně optimální, ale jak se znovu a znovu osvědčuje, tato metoda často nepřichází s globálně optimálním řešením. Ve skutečnosti je zcela možné, že nejoptimálnější krátkodobá řešení vedou k nejhoršímu možnému celosvětovému výsledku.
Přemýšlejte o tom jako o převzetí mnoha zkratek ve výrobním podniku: v krátkodobém horizontu jsou ušetřeny velké částky ve výrobních nákladech, ale to nakonec vede k poklesu, protože kvalita je ohrožena, což vede k návratnosti produktů a nízkým prodejům, když se zákazníci seznamují s výrobkem „Levný“ produkt. Ale není tomu tak vždy, existuje spousta aplikací, kde chamtivý algoritmus pracuje nejlépe k nalezení nebo přibližování globálně optimálního řešení, například při konstrukci Huffmanova stromu nebo stromu učení rozhodnutí.
Například: Vydejte se s největší celkovou částkou. Chamtivý algoritmus by si vybral modrou cestu v důsledku krátkozrakosti, spíše než oranžovou cestu, která poskytne největší částku.
Komponenty:
- Kandidátská sada dat, která potřebuje řešení
- Funkce výběru, která vybere nejlepšího přispěvatele do konečného řešení
- Funkce proveditelnosti, která pomáhá výběrové funkci určením, zda kandidát může být přispěvatelem k řešení
- Objektivní funkce, která přiřazuje hodnotu částečnému řešení
- Funkce řešení, která ukazuje, že optimální řešení bylo objeveno
