21. Mohó algoritmusok I

Mohó algoritmusok általános jellemzői:

Á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énz visszaadás lehető legkevesebb címlettel:

Feladat: Egy nyugdíjas elmegy felvenni a nyugdíját(79.845 Ft). Hogyan tudja a pénztáros úgy kifizetni, hogy a legkevesebb papír és érme pénzt adja.

Megjegyzések:

• Rendelkezésre álló papír és érme címletek: 20.000, 10.000, 5.000, 2.000, 1.000, 500, 200, 100, 50, 20, 10, 5 Ft-os
• Tételezzük fel, hogy minden címlet korlátlan
• Nem számít megoldásnak, ha a nyugdíjasnak vissza kell adnia!

Pszeudokód:

Függvény Pénzkifizetés(x)

S<-Ø

Ciklus amíg x!=0

k<- a legnagyobb egész, melyre Ck<=x

Ha k=0 akkor

return nincs megoldás

Elágazás vége

x<-x-Ck

S<-S U {k}

Ciklus vége

return S

Függvény vége

 

Tankolási pontok meghatározása:

Madridból szeretnénk Moszkvába utazni, az útvonalat ismerjük, nem feladat a módosítás. Tudjuk, hogy út közben hol találhatóak benzinkutak, és autónk tankjának méretét és fogyasztását is ismerjük. Határozzuk meg, hogy hol kell megállni tankolni, ha minimális megállásszámmal szeretnénk célba érni.

A kiindulási ponttól menjünk addig amíg a benzinkútig, ameddig elegendő az üzemanyagunk, és ott tankoljuk tele. Ezt ismételjük míg célba nem érünk. Ha két benzinkút között nagyobb a távolság mint amit egy tankkal megtehetünk, akkor nem teljesíthető az utazás.

• L jelöli az utunk hosszát
• A benzinkutak távolságát bi-k jelölik a kiindulási ponttól növekvő sorrendben.
• S jelöli az algoritmus által kijelölt megállási pontok halmazát
• x jelöli az aktuális helyünket(Távolságunk a kiindulási ponttól)
• C jelöli a teli tankkal megtehető maximális távolságot

Algoritmus:

S<-{0}

x<-0

Ciklus amíg x!=bn

p<- a legnagyobb index amelyre bp<=x+c

Ha bp=x akkor

return “nincs megoldás”

Elágazás vége

x<-bp

S<- S U {p}

Ciklus vége

0-1 hátizsák probléma mohó megvalósítása:

Adott n darab tárgy. Az i-edik tárgy értéke pi és az i-edik tárgy súlya wi. A tárgyak azon részhalmazát kell kiválasztanunk, mellyel a legtöbb értéket rakjuk a táskába, és nem haladjuk meg a táska kapacitását(c).

Először el kell döntenünk, hogy melyik jellemző alapján akarunk mohó stratégiát folytatni:

• Érték
• Súly
• Érték/súly arány alapján

Válasszuk az érték/súly arány alapú megközelítést.
Legyenek a tárgyak érték/súly alapján növekvően rendezettek.

Pszeudokód(Bemenet: n-tárgyak darabszáma, p-tárgyak értékeinek tömbje, w-tárgyak súlyainak tömbje, c-táska kapacitása Kimenet: A-kiválasztott tárgyak sorszámainak halmaza):

Függvény Mohó0_1HátizsákProbléma(n,p,w,c)

u<-c

A<-Ø

i<-1

Ciklus amíg u>0 és i<=n

Ha wi <=u akkor

A<-A U {i}

u<-u-wi

Elágazás vége

i<-i+1

Ciklus vége

return(A)

Függvény vége

Sajnos a mohó stratégi ebben az esetben nem az optimális megoldást.

Forrás:

• Wikipédia
• Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 12. előadás diasor

Kommentek

comments

Powered by Facebook Comments