1 of 63

Mohó algoritmusok�2024.10.09

2 of 63

Ismétlés

3 of 63

Dinamikus programozás

Az eddigiekben egy-egy összetett feladat megoldására oszd-meg-és-uralkodj megoldást használtunk.

A rekurzív megoldás legnagyobb hátránya azonban az, hogy legtöbb esetben, ahogy növekszik az elemszámunk, vele együtt hatványozottan növekszik a megoldáshoz szükséges idő hossza és a lépések száma is.

4 of 63

Dinamikus programozás

A dinamikus programozás a részproblémákra bontás gyengeségeit két fő módszerrel próbálja orvosolni:

Az egyik módszer lényege, hogy programunk futása alatt

a megoldott rész problémák (optimális) megoldását eltároljuk,
ha ugyanezen részprobléma megoldására szükségünk lenne később, csak kiolvassuk a megoldást,
nem oldjuk meg újra a részfeladatot

(TÁBLÁZATKITÖLTÉS módszere)

5 of 63

def fib( n, memo ) :

if memo[n] != null:

return memo[n]

if (( n == 2 ) || (n == 1)):

result = 1

else

result = fib(n-1) + fib(n-2)

memo[n] = result

return result

Nézzük meg, hogyan nézne ki a példánk, ha eltárolnánk az értékeket.

memo = 1 1 2 3

T(n) = 2n + 1 …… O(n)

Fibonacci

6 of 63

Dinamikus programozás

A második módszer:

Általában amikor a részproblémákat többször is szükséges megoldani, akkor az összes lehetséges „kis” részproblémát ki kell számolni, hogy az eredeti nagy probléma megoldása kiszámítható legyen.

7 of 63

Dinamikus programozás

Vegyük észre, hogy ez ellentétes az oszd-meg-és-uralkodj algoritmusok filozófiájával, ahol mindig az eredeti problémát bontjuk kisebb és kisebb problémákra

(FELÖLRŐL LEFELÉ ÉPÍTKEZÉS módszere)

8 of 63

Lépcső

Az előző órán a rekurzív algoritmushoz megadtuk az összefüggéseket:

Alapeset:

P(1) = 1 (ha egy lépcső van, egyféleképpen mehetünk)
P(2) = 2 (ha két lépcső van, vagy kétszer egyet lépünk, vagy egyszer kettőt)

Rekurzív eset:

P(n) = P(n − 1) + P(n − 2), ha n ≥ 3 (utolsó lépésként egyet vagy kettőt léphetünk)

9 of 63

Lépcső

Ezek alapján a következő dinamikus programozási eljárást adhatjuk meg, ahol egy T tömböt töltünk ki, T[i] a P(i) értékét tartalmazza:

10 of 63

Sakk

Megoldás:

Az előző órán megadtuk a rekurzív algoritmusokhoz az összefüggéseket.

A következő összefüggések állnak fent:

Alapeset:

R(k, 1) = 1 (csak felfelé mehetünk)
R(1, n) = 1 (csak jobbra mehetünk)

Rekurzív eset:

R(k, n) = R(k, n−1)+R(k−1, n), ha n, k ≥ 2 (az első lépés jobbra vagy felfelé történhet)

11 of 63

Sakk

Ezek alapján a következő dinamikus programozási eljárást adhatjuk meg, T[i, j] az R(i, j) értékét tartalmazza:

12 of 63

Mohó algoritmusok

13 of 63

Mohó algoritmusok

Egy mohó algoritmus minden lépésben egy lokálisan legjobb döntést hoz, de figyelmen kívül hagyja ennek a döntésnek a hatását a későbbi eseményekre.

14 of 63

Mohó algoritmusok

,,optimálisnak tűnő döntés”

Nem minden probléma oldható meg mohó algoritmussal és nem mindig ad optimális megoldást.

15 of 63

Mohó algoritmusok

Ha valami mohó módon megoldható, akkor 2 tulajdonságot biztosan el tudunk róla mondani:

• Optimális részstruktúra: Egy feladat optimális részstruktúrájú, ha a probléma egy optimális megoldása önmagán belül a részfeladatok optimális megoldásait tartalmazza.

• Mohó választás tulajdonság: lokálisan optimális választások a globálisan optimális megoldáshoz vezetnek

16 of 63

Mohó algoritmusok

Egy mohó algoritmus tervezésének lépései:

Fogalmazzuk meg az optimalizációs feladatot úgy, hogy minden egyes döntés hatására egy megoldandó részprobléma keletkezzen.

2. Bizonyítsuk be, hogy mindig van olyan optimális megoldása az eredeti problémának, amely tartalmazza a mohó választást, tehát a mohó választás mindig biztonságos

17 of 63

Mohó algoritmusok

Egy mohó algoritmus tervezésének lépései:

3. Mutassuk meg, hogy a mohó választással olyan részprobléma keletkezik, amelynek egy optimális megoldásához hozzávéve a mohó választást, az eredeti probléma egy optimális megoldását kapjuk.

18 of 63

Mohó algoritmusok

Nézzünk egy példát.
Amennyiben elakarunk jutni A-ból B-be, ezt számtalan módon megtehetjük.
Gyalog, Autóval, Kerékpárral.. Stb.

19 of 63

Mohó algoritmusok

Ám ha egy kritériumot adunk a képlethez, akkor sok eddigi megoldás értelmetlenné válik. (12óra alatt -> repülő, vonat)

20 of 63

Mohó algoritmusok

Tovább szűkítve a dolog, átalakíthatjuk egy minimumkereső problémává. (12óra -> a legolcsóbb módszerrel)

21 of 63

Mohó algoritmusok

A célunk, hogy megtaláljuk az (az egyetlen) optimális megoldást.

A min/max keresése alatt értjük az optimalizációt.

22 of 63

Mohó algoritmusok

A mohó algoritmus a problémát lépésekben oldja meg, és az megvalósítható (feasible) akkor az hozzáadódik a megoldás halmazhoz

23 of 63

Mohó algoritmusok

Példa: Autót akarunk venni, és ehhez keressük az optimális megoldást.
Algoritmus nélkül a világ összes autóját össze kellene írnunk.
Algoritmussal viszont:

Szűrhetjük a márka neveket
Legjobb modellek
A legmegbízhatóbb
Az akciónk lévők
Stb.

24 of 63

Pénzváltás probléma

25 of 63

Pénzváltás probléma

Egy nyugdíjas elmegy a postára, hogy felvegye 79.845 Ft-os nyugdíját. Hogyan tudja a postai pénztáros kifizetni neki ezt az összeget úgy, hogy a kifizetéshez a lehető legkevesebb darab címletet használja?

26 of 63

Pénzváltás probléma

Rendelkezésre álló címletek: 20.000, 10.000, 5.000, 2.000, 1.000, 500, 200, 100, 50, 20, 10 és 5 Ft-os.

Tegyük fel, hogy minden címletből korlátlan mennyiség van a postán.

Az nem tekinthető megoldásnak, ha a nyugdíjasnak vissza kell adnia.

(Pl.: a pénztáros ad 80.000 Ft-ot 4 db 20.000 Ft-os címlettel, majd a nyugdíjas visszaad 155 Ft-ot.)

27 of 63

Pénzváltás probléma

Megoldás:

Vegyünk a legnagyobb címletű pénzjegyből, amennyi szükséges, majd a maradék összeget fizessük ki a nála kisebb pénz-jegyekkel!

28 of 63

Pénzváltás probléma

A pénztáros az alábbi címleteket fogja adni:

3 db 20.000 Ft-os = 60.000 Ft

1 db 10.000 Ft-os = 10.000 Ft

1 db 5.000 Ft-os = 5.000 Ft

2 db 2.000 Ft-os = 4.000 Ft

1 db 500 Ft-os = 500 Ft

1 db 200 Ft-os = 200 Ft

1 db 100 Ft-os = 100Ft

2 db 20 Ft-os = 40 Ft

1 db 5 Ft-os = 5 Ft 79.845 Ft

Ez összesen 13 db papír pénzt, illetve pénzérmét jelent.

29 of 63

Pénzváltás probléma

def findMin(V):

ermek = [ 5, 10, 20, 50,100,200,500,1000,2000 ,5000,10000,20000]

n = len(ermek)

ans = []

i = n - 1

while(i >= 0):

#Keresse meg a címleteket

while (V >= ermek[i]):

V -= ermek[i]

ans.append(ermek[i])

i -= 1

for i in range(len(ans)):

print(ans[i], end = " ")

30 of 63

Levélfeladás

31 of 63

Levélfeladás

Nyugdíjasunk szeretne feladni egy levelet, mely 1400 Ft-ba kerül. Hogyan lehet ezt megtenni, ha a lehető legkevesebb számú bélyeget szeretnénk a borítékra tenni.

Rendelkezésre álló bélyegcímletek:

3.500 Ft

1.000 Ft

700 Ft

340 Ft

210 Ft

100 Ft

10 Ft

32 of 63

Ha a mohó algoritmust használjuk oly módon, hogy mindig a lehető legnagyobb címletű bélyeget ragasztjuk fel, akkor az alábbi megoldást kapjuk:

0 db 3.500 Ft-os = 0 Ft

1 db 1.000 Ft-os = 1.000 Ft

0 db 700 Ft-os = 0 Ft

1 db 340 Ft-os = 340 Ft

0 db 210 Ft-os = 0 Ft

0 db 100 Ft-os = 0 Ft

6 db 10 Ft-os = 60 Ft

1.400 Ft-os

Az algoritmus szerint 8 db bélyegre van szükségünk.

33 of 63

Könnyen látható, hogy a mohó algoritmus által adott megoldás most nem optimális.

Az optimális megoldás 2 db 700 Ft-os bélyeg választása lenne.

34 of 63

Hátizsák pakoló probléma

35 of 63

Hátizsák pakoló probléma

Egy adott hátizsákba tárgyakat akarunk pakolni.
Adott n tárgy minden tárgynak van egy fontossági értéke (e [i]), és egy súlya (s[i]), a hátizsákba maximum összesen S súlyt pakolhatunk. Az s[i] és S értékek egészek.
Szeretnénk úgy választani tárgyakat, hogy az összfontosság(profit) maximális legyen.
Tehát feladatunk, hogy kiválasszuk a tárgyaknak olyan halmazai közül, amelyekre az összsúly nem haladja meg S-t azt, amelyre maximális az összfontosság.

36 of 63

Hátizsák pakoló probléma

Egy maximum keresési probléma.

37 of 63

Hátizsák pakoló probléma

Első lépésben meg kell határozni, hogy mi kerül a táskába.
Hogyan kezdjünk ehhez?

38 of 63

Hátizsák pakoló probléma

Egy jó megoldás, ha kiszámítjuk a profit/súly hányadosát.

Ez egy jó mutató lesz a helyes elemek kiválasztásához.

39 of 63

Hátizsák pakoló probléma

Most nézzük meg, hogy hogyan oldjuk ezt meg MOHÓ algoritmussal
Első lépésben kiválasztjuk a legnagyobb profit hányadosú elemet és megnézzük mekkora súlyúnk maradt.

40 of 63

Hátizsák pakoló probléma

Majd kiválasszuk a 2. legjobbat.

És a 3.-at

41 of 63

Hátizsák pakoló probléma

Majd 4.-et. (Fontos most nem a súlyokat, hanem a hányados figyeljük)

42 of 63

Hátizsák pakoló probléma

5. lépésben ismét egy 3-as értéket választunk…

43 of 63

Hátizsák pakoló probléma

A következő lépésben viszont már nem tudjuk az egész „elemet” bepakolni, ezért annak csak egy részét tesszük bele.

44 of 63

Hátizsák pakoló probléma

Az utolsó elemet pedig nem akarjuk felhasználni.

45 of 63

Hátizsák pakoló probléma

Következő lépés, a profit/súly kalkulációja és az algoritmus igazolása.

46 of 63

Munkavégzés sorrendje

47 of 63