Mohó algoritmus
olyan algoritmus, amely lépések sorozatában helyileg optimális döntéseket hoz a globális optimum elérése érdekében
A mohó algoritmus vagy greedy algoritmus az a problémamegoldó algoritmus, amely helyi optimumok megvalósításával próbálja megtalálni a globális optimumot. Ez például az utazó ügynök problémájaként ismert feladatban azt jelenti, hogy minden állomásról a legközelebbi, addig még nem látogatott városba fog utazni az ügynök.



Általánosan öt pillérre támaszkodik:
- egy halmazból veszi a jelölteket, amelyekkel felállítja a megoldáshalmazt
- egy kiválasztó függvény, amely a legjobb jelöltet választja ki a megoldás reményében
- egy lehetőségvizsgáló függvény, amely megnézi, hogy egy jelölt alkalmas-e a megoldásra
- egy célfüggvény, amely egy értéket megoldásnak, vagy részleges megoldásnak jelöl
- egy megoldásfüggvény, amely jelzi, ha megtaláltuk a teljes megoldást.
A módszer jól alkalmazható néhány matematikai probléma megoldásában, de nem garantálja sok probléma megoldását.
Példák
szerkesztés- Az utazó ügynök problémájaként ismert feladat: Minden állomásról a legközelebbi, addig még nem látogatott városba utazva bejárni a városokat a legrövidebb útvonalon.
- Kruskal-algoritmus: Egy összefüggő gráf éleihez hozzárendelnek egy szigorúan pozitív számot, az úgynevezett költséget. Meg kell határozni a minimális feszítőfát a csúcsok között.
- Dijkstra-algoritmus: egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva.
Alkalmazásai
szerkesztésA mohó algoritmusok igen jól teljesítenek, ahol gyors és kis számítási kapacitású keresést kell megvalósítani, ellenben egyetlen megoldást adnak alternatívák nélkül. Bonyolult állapotterek esetén minimális javulást eredményezhetnek.
- Huffman-kódolás az adattömörítésben
- Erdős–Straus-sejtés a matematikában
Források
szerkesztés- Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, 17. fejezet Greedy Algorithms 329. old.
- Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001, 16. fejezet Greedy Algorithms.
- G. Gutin, A. Yeo és A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
- J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
- G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.
Fordítás
szerkesztés- Ez a szócikk részben vagy egészben a Greedy algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.