Obsah:
Definícia - Čo znamená Greedyov algoritmus?
Chamtivý algoritmus je algoritmická stratégia, ktorá robí najlepšiu optimálnu voľbu v každej malej etape s cieľom nakoniec viesť ku globálne optimálnemu riešeniu. To znamená, že algoritmus v súčasnosti vyberá najlepšie riešenie bez ohľadu na dôsledky. Vyberá najlepší okamžitý výstup, ale nezohľadňuje celkový obraz, preto sa považuje za chamtivý.
Techopedia vysvetľuje Greedyho algoritmus
Chamtivý algoritmus funguje tak, že v každom kroku vyberie najlepšiu možnú odpoveď a potom prejde na ďalší krok, až kým nedosiahne koniec, bez ohľadu na celkové riešenie. Dúfa len, že cesta, po ktorej sa vydá, je globálne optimálna, ale ako sa znovu a znovu preukazuje, táto metóda často neprichádza s globálne optimálnym riešením. V skutočnosti je úplne možné, že najoptimálnejšie krátkodobé riešenia vedú k najhoršiemu možnému globálnemu výsledku.
Zamyslite sa nad tým, ako by ste vo výrobnom podniku brali veľa skratiek: z krátkodobého hľadiska sa ušetria veľké množstvá výrobných nákladov, ale to nakoniec vedie k poklesu, pretože kvalita je znížená, čo vedie k návratnosti produktu a nízkemu predaju, keď sa zákazníci oboznámia s výrobkom. „Lacný“ produkt. Nie je to však vždy tak, existuje veľa aplikácií, v ktorých chamtivý algoritmus pracuje najlepšie na nájdenie alebo aproximácii globálne optimálneho riešenia, napríklad pri konštrukcii Huffmanovho stromu alebo stromu rozhodovania.
Napríklad: Choďte po ceste s najväčšou celkovou sumou. Chamtivý algoritmus by si vybral modrú cestu v dôsledku krátkozrakosti, a nie oranžovej cesty, ktorá poskytne najväčšiu sumu.
komponenty:
- Kandidátska sada údajov, ktorá potrebuje riešenie
- Funkcia výberu, ktorá vyberie najlepšieho prispievateľa do konečného riešenia
- Funkcia uskutočniteľnosti, ktorá pomáha výberovej funkcii určením, či kandidát môže byť prispievateľom k riešeniu
- Objektívna funkcia, ktorá priradí hodnotu čiastočnému riešeniu
- Funkcia riešenia, ktorá naznačuje, že bolo nájdené optimálne riešenie
