A mohó módszer az egyik olyan stratégia, mint az Oszd meg és uralkodj a problémák megoldására. Ez a módszer az optimalizálási problémák megoldására szolgál. Az optimalizálási probléma olyan probléma, amely maximális vagy minimális eredményt igényel. Értsük meg néhány kifejezésen keresztül.

A Greedy módszer a legegyszerűbb és legegyszerűbb megközelítés. Ez nem egy algoritmus, hanem egy technika. Ennek a megközelítésnek a fő funkciója, hogy a döntést a jelenleg rendelkezésre álló információk alapján hozzák meg. Bármi legyen is a jelenlegi információ, a döntést anélkül hozzuk meg, hogy aggódnánk a jelenlegi döntés jövőbeli hatásai miatt.

java enums

Ezt a technikát alapvetően arra használják, hogy meghatározzák a megvalósítható megoldást, amely lehet vagy nem optimális. A megvalósítható megoldás egy olyan részhalmaz, amely megfelel a megadott kritériumoknak. Az optimális megoldás az a megoldás, amelyik a részhalmaz legjobb és legkedvezőbb megoldása. Megvalósítható esetben, ha több megoldás is megfelel a megadott kritériumoknak, akkor azokat a megoldásokat tekintjük megvalósíthatónak, míg az összes megoldás közül az optimális megoldás a legjobb megoldás.

A Greedy módszer jellemzői

A mohó módszer jellemzői a következők:

• A megoldás optimális felépítéséhez ez az algoritmus két halmazt hoz létre, ahol az egyik halmaz tartalmazza az összes kiválasztott elemet, a másik pedig az elutasított elemeket.
• A Greedy algoritmus jó helyi döntéseket hoz abban a reményben, hogy a megoldás megvalósítható vagy optimális lesz.

A mohó algoritmus összetevői

A mohó algoritmusban használható komponensek a következők:

aes vs des

Jelölt készlet:A halmazból létrehozott megoldást jelölthalmaznak nevezzük.Kiválasztási funkció:Ezzel a funkcióval kiválasztható a megoldáshoz hozzáadható jelölt vagy részhalmaz.Megvalósíthatósági funkció:Egy függvény, amely annak meghatározására szolgál, hogy a jelölt vagy részhalmaz felhasználható-e a megoldáshoz való hozzájárulásra.Objektív funkció:Egy függvény segítségével hozzárendeljük az értéket a megoldáshoz vagy a részmegoldáshoz.Megoldás funkció:Ez a funkció annak meghatározására szolgál, hogy a teljes funkciót elérte-e vagy sem.

A mohó algoritmus alkalmazásai

• A legrövidebb út megtalálására használják.
• A minimális feszítőfa megkeresésére szolgál a prím vagy a Kruskal-algoritmus segítségével.
• Határidős munkasorrendben használják.
• Ezt az algoritmust használják a tört hátizsák probléma megoldására is.

A Greedy Algorithm pszeudo kódja

 Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 

A fenti a mohó algoritmus. Kezdetben a megoldás nulla értékkel van rendelve. A mohó algoritmusban átadjuk a tömböt és az elemek számát. A for cikluson belül egyenként kiválasztjuk az elemet, és ellenőrizzük, hogy a megoldás megvalósítható-e vagy sem. Ha a megoldás megvalósítható, akkor végrehajtjuk az egyesülést.

Értsük meg egy példán keresztül.

Tegyük fel, hogy 'P' probléma van. Szeretnék A-ból B-be utazni az alábbiak szerint:

P: A → B

A probléma az, hogy ezt az utat A-ból B-be kell utaznunk. A-ból B-be többféle megoldás létezik. A-ból B-be mehetünk úgy, hogy séta, autó, bicikli, vonat, repülőgép , stb. Az útnak van egy megkötése, hogy ezt az utat 12 órán belül meg kell utaznunk. Ha vonattal vagy repülővel megyek, akkor csak 12 órán belül tudom megtenni ezt a távolságot. Számos megoldás létezik erre a problémára, de csak két megoldás van, amely megfelel a megszorításnak.

Ha azt mondjuk, hogy minimális költséggel kell fedeznünk az utat. Ez azt jelenti, hogy ezt a távolságot a lehető legkevesebbet kell megtennünk, ezért ezt a problémát minimalizálási problémaként ismerjük. Eddig két megvalósítható megoldásunk van, az egyik vonattal, a másik légi úton. Mivel a vonatozás minimális költséggel jár, ezért ez egy optimális megoldás. Az optimális megoldás egyben a megvalósítható, de a legjobb eredményt nyújtó megoldás, hogy a megoldás legyen az optimális megoldás minimális költséggel. Egyetlen optimális megoldás lenne.

Azt a problémát, amelyhez minimális vagy maximális eredmény szükséges, ezt a problémát optimalizálási feladatnak nevezzük. A mohó módszer az optimalizálási problémák megoldására használt egyik stratégia.

tkinter gomb

A Greedy algoritmus használatának hátrányai

A mohó algoritmus az egyes fázisokban rendelkezésre álló információk alapján hoz döntéseket anélkül, hogy figyelembe venné a tágabb problémát. Így előfordulhat, hogy a mohó megoldás nem minden problémára adja a legjobb megoldást.

Minden szakaszban követi a helyi optimumot, azzal a szándékkal, hogy megtalálja a globális optimumot. Értsük meg egy példán keresztül.

Tekintsük az alábbi grafikont:

Minimális költséggel kell utaznunk a forrástól a célig. Mivel három megvalósítható megoldásunk van, amelyek költségútvonalai 10, 20 és 5, ezért az 5 a minimális költségút, így ez az optimális megoldás. Ez a lokális optimum, és így minden szakaszban megtaláljuk a lokális optimumot a globális optimális megoldás kiszámításához.

python // operátor