Bevezetés a kapzsi algoritmusba
A problémák megoldására használt stratégia. A kapzsi algoritmust a problémák megoldására alkalmazott egyik megközelítésnek tekintik. Ez a problémamegoldó eretnekség abban a pillanatban a legmegfelelőbbnek tűnő döntés meghozatalával jár. Ezt a megközelítést lehet az optimális problémák megoldására a legjobban használni. Az optimalizálási problémák meghatározhatók olyan problémákként, amelyek minimális vagy maximális eredményt igényelnek. A Greedy algoritmus egy legegyszerűbb és legegyszerűbb megközelítés, amely felhasználható az optimális megoldás elérésére.
Mi az a kapzsi algoritmus?
A Greedy Algorithm egy olyan algoritmikus stratégia, amelyet egy nagyon kicsi szakaszban a lehető legjobb választás meghozatalához használnak, miközben végül egy globálisan optimális megoldást hoznak létre. Ez az algoritmus kiválasztja az adott pillanatban megvalósítható legjobb megoldást, tekintet nélkül a következményekre. A kapzsi módszer szerint a problémát fokozatosan kell megoldani, ahol mindegyik bemenetet figyelembe veszik, mivel ez a bemenet megvalósítható. Mivel ez a megközelítés csak az azonnali eredményre összpontosít, a nagyobb képet figyelembe véve, kapzsinak tekinthető.
A központi koncepció meghatározása
Mostanáig tudjuk, mi a kapzsi algoritmus, és miért nevezték el így. Az alábbi mutatók segítenek jobban megérteni a kapzsi algoritmust. Mára nagyon világos volt, hogy a kapzsi algoritmus csak akkor működik, ha probléma merül fel; mindazonáltal ez a megközelítés csak akkor alkalmazható, ha van egy feltétel vagy korlátozás erre a problémára.
A problémák típusai
- Minimalizálási probléma: A probléma megoldása egyszerű, mivel minden feltétel teljesül. Ha azonban ez a probléma minimális eredményt igényel, akkor azt Minimalizációs problémának nevezik.
- Maximalizálási probléma: A maximális eredményt igénylő problémát maximalizálási problémának nevezzük.
- Optimalizálási probléma: A problémát akkor nevezzük optimalizálási problémának, amikor minimális vagy maximális eredményt igényel.
A megoldások típusai
- Megfelelő megoldás: Ha egy probléma merül fel, sok valószínű megoldást kínálunk erre a problémára. Mindazonáltal, figyelembe véve a probléma feltételeit, olyan megoldásokat választunk, amelyek megfelelnek az adott feltételnek. Azokat a megoldásokat, amelyek segítenek elérni az adott feltételnek megfelelő eredményeket, megvalósítható megoldásnak nevezzük .
- Optimális megoldás: Az a megoldás, amelyet akkor lehet optimálisnak hívni, ha ez már megvalósítható, és megvalósítja a probléma célját; a legjobb eredmény. Ez a cél lehet a minimális vagy a maximális eredmény. Itt érdemes észrevenni, hogy minden problémára csak egy optimális megoldás lesz.
A következő példa megkönnyíti a kapzsi módszer megértését. Mondjuk, meg akarja vásárolni a piacon elérhető legjobb autót. Az autó kiválasztásának egyik módja a piacon lévő összes autó elemzése. Most, hogy ez időigényes, megkönnyíti a gépkocsi kiválasztását azokból a konkrét márkákból, amelyekbe érdekli őket befektetni. Ezt tovább kategorizálva ismét a kívánt modelleket választanánk annak jellemzői alapján. Ezért az itt alkalmazott megközelítés kapzsi, mivel ez a megoldás volt az optimális megoldás az Ön számára, miközben az összes tényező kedvező volt.
A kapzsi algoritmus alapvető alkotóelemei
Most, amikor jobban megértjük ezt a mechanizmust, vizsgáljuk meg egy mohó algoritmus alapvető alkotóelemeit, amely különbözteti meg más folyamatoktól:
- Jelöltkészlet: Válasz jön létre ebből a készletből.
- Kiválasztási funkció: Kiválasztja a legjobb jelöltet, amelyet be kell vonni a megoldásba.
- Megvalósíthatósági funkció: Ez a szakasz kiszámítja, hogy a jelölt felhasználható-e a megoldáshoz való hozzájárulásra.
- Objektív funkció: Értéket rendel teljes vagy részleges megoldáshoz.
- Megoldás funkció: Ez azt jelzi, hogy a megfelelő megoldás teljesült-e.
Hol működik a legjobban a kapzsi algoritmus?
A kapzsi algoritmus alkalmazható az alábbiakban említett problémákra.
- A Greedy megközelítés felhasználható a minimális átfogó fa gráf megtalálására Prim vagy Kruskal algoritmusa segítségével
- A két csúcs közötti legrövidebb út megkeresése egy újabb probléma, amelyet kapzsi algoritmus segítségével lehet megoldani. A Dijkstra algoritmusának és a kapzsi algoritmusnak az alkalmazása optimális megoldást kínál.
- Huffman Coding
Előnyök
A Greedy algoritmus legnagyobb előnye másokkal szemben az, hogy könnyen megvalósítható és a legtöbb esetben nagyon hatékony.
hátrányok
A kapzsi algoritmus alapvetően részlegesen épít megoldást, és a következő részt úgy választja meg, hogy az a jelenlegi probléma legjobb megoldására szolgáljon azonnal. Ennek eredményeként a jelenlegi döntés következményeit nem kell figyelembe venni vagy aggódni. A Greedy Algorithm soha nem mérlegelte korábban a választásokat, nem sikerül optimális megoldást hoznia, bár szinte optimális megoldást kínál . A hátizsákos probléma és az utazó eladó problémája olyan problémákra mutat példákat, amelyekben a kapzsi algoritmus nem hoz létre optimális megoldást.
- Hátizsákos probléma: A hátizsák-probléma néven ismert, mindennapi probléma, amellyel sok ember szembesül. Mondjuk, hogy elemeket állítottunk össze, és mindegyiküknek különbözõ súlya és értéke (nyeresége) van ahhoz, hogy egy tartályba töltsük be, vagy oly módon kell összegyûjteni, hogy a teljes tömeg kevesebb vagy egyenlõ legyen a tartály tömegével, miközben a teljes profit maximális .
Következtetés
A kapzsi algoritmus akkor a legjobban alkalmazható, ha valós idejű megoldásra van szükség, és a hozzávetőleges válaszok „elég jó”. Nyilvánvaló, hogy egy kapzsi algoritmus minimalizálja az időt, miközben biztosítja az optimális megoldás előállítását, ennélfogva inkább alkalmazható olyan helyzetekben, ahol kevesebb idő szükséges. A cikk elolvasása után jó ötlet alakulhat ki a kapzsi algoritmusokról. Ezenkívül ez a bejegyzés megmagyarázza, hogy miért tekintik a legjobb keretnek, amely szinte minden programozási kihívást megválaszol, és segít abban, hogy egy adott időpontban meghozza a legoptimálisabb megoldást.
Durva oldalon azonban a kapzsi algoritmus elméletének alkalmazásához keményebben kell dolgozni a helyes kérdések ismeretében. Bár ez egy tudományos koncepció, amelynek logikája van, a kreativitás lényege is.
Ajánlott cikkek
Ez egy útmutató a Mi a kapzsi algoritmus számára. Itt tárgyaltuk a kapzsi algoritmus alapvető koncepcióját, összetevőit, előnyeit és hátrányait. A további javasolt cikkeken keresztül további információkat is megtudhat -
- Algoritmus a programozásban
- Mi az a Perl?
- Bevezetés az algoritmusba
- Mi az Agile Sprint?