Mohó algoritmus

A Wikipédiából, a szabad enciklopédiából
Mohó algoritmussal meghatározható a legkevesebb pénzérme, amivel ki lehet az aprót fizetni. A legnagyobb értékű érme, amivel ki lehet fizetni a megmaradt összeget, a helyi optimum.

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.

Alkalmazásai[szerkesztés | forrásszöveg szerkesztése]

Példák[szerkesztés | forrásszöveg szerkesztése]

  • 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 algoritmusa: 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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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.
  • 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.

További információk[szerkesztés | forrásszöveg szerkesztése]