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
Powered by Facebook Comments