Tartalomjegyzék:
Meghatározás - Mit jelent a kapzsi algoritmus?
A kapzsi algoritmus egy algoritmikus stratégia, amely minden kis szakaszban meghozza a legjobb optimális választást azzal a céllal, hogy ez végül globálisan optimális megoldást eredményezzen. Ez azt jelenti, hogy az algoritmus a legjobb megoldást választja ki a pillanatban, a következmények figyelembevétele nélkül. Kiválasztja a legjobb azonnali kimenetet, de nem veszi figyelembe a nagy képet, ezért kapzsinak tekintik.
A Techopedia magyarázza a kapzsi algoritmust
Egy kapzsi algoritmus úgy működik, hogy az egyes lépésekben kiválasztja a lehető legjobb választ, majd a következő lépésre halad, amíg a végére nem ér, a teljes megoldást figyelembe véve. Csak azt reméli, hogy a megtett út a globálisan optimális, de mint újra és újra bebizonyosodott, ez a módszer gyakran nem talál globálisan optimális megoldást. Valójában teljesen lehetséges, hogy az optimális rövid távú megoldások a lehető legrosszabb globális eredményhez vezetnek.
Gondolj úgy, mintha sok hivatkozás lenne a gyártó üzletben: rövid távon nagy összegeket takarítanak meg a gyártási költségekben, de ez végül visszaesést eredményez, mivel a minőség sérül, ami termék visszatérést és alacsony eladásokat eredményez, amikor az ügyfelek megismerik a „Olcsó” termék. De nem mindig ez a helyzet, sok olyan alkalmazás van, ahol a kapzsi algoritmus a legjobban működik a globálisan optimális megoldás megtalálásakor vagy közelítésében, például Huffman-fa vagy döntéshozó fa felépítésekor.
Például: Távolítsa el az utat a legnagyobb összeggel. Egy kapzsi algoritmus a rövidlátás eredményeként a kék utat választja, nem pedig a narancssárga utat, amely a legnagyobb összeget hozza.
Alkatrészek:
- Jelölt adatkészlet, amely megoldást igényel
- Kiválasztási funkció, amely a legjobb megoldást választja a végső megoldáshoz
- Egy megvalósíthatósági funkció, amely elősegíti a kiválasztási funkciót annak meghatározásával, hogy a jelölt hozzájárulhat-e a megoldáshoz
- Objektív funkció, amely értéket rendel hozzá egy részleges megoldáshoz
- Megoldás funkció, amely jelzi, hogy az optimális megoldást felfedezték
