Optimalizációs stratégiák 1

Optimalizációs stratégiák 1. Nyers erő, Oszd meg és uralkodj, Feljegyzéses, Dinamikus, Mohó

Programozás II. előadás http://nik.uni-obuda.hu/prog2 Szénási Sándor

[email protected]

Óbudai Egyetem,Neumann János Informatikai Kar

A megoldandó feladat • 0-1 hátizsák probléma – Bemenete • Wmax: hátizsák mérete • N: rendelkezésre álló tárgyak száma • wi: i. tárgy súlya • pi: i. tárgy értéke – Kimenete • Pmax: egy optimális pakolás értéke

• Pakolás: tárgyanként meghatározzuk, hogy bekerül-e a zsákba vagy sem (pl. N elemű logikai tömb) • Pakolás összsúlya/összértéke: a pakolás által a hátizsákba választott tárgyak súlyának/értékének összege • Érvényes pakolás: olyan pakolás, amelynek összsúlya nem nagyobb mint a hátizsák mérete • Optimális pakolás: olyan érvényes pakolás, amelyiknél nincs nagyobb összértékű érvényes pakolás [email protected]

Programozás II.

2

Optimalizációs stratégiák 1. Nyers erő módszere Oszd meg és uralkodj Feljegyzéses módszer Dinamikus programozás Mohó algoritmusok

Nyers erő módszere (brute force) • Alapelv: egyszerűen végigpróbálgatjuk az összes lehetséges megoldást • A 0-1 hátizsák probléma megoldása függvény HátizsákBF OPT  [hamis,hamis, … ,hamis] ciklus i  1-től 2N-1-ig ciklus j  0-től N-1-ig K[j]  i / 2j mod 2 = 1 ciklus vége ha (ÖsszSúly(K)≤Wmax)˄(ÖsszÉrték(K)>ÖsszÉrték(OPT)) akkor OPT  K elágazás vége ciklus vége vissza ÖsszÉrték(OPT) függvény vége

• Amennyiben érvényes pakolást találunk, akkor ellenőrizzük, hogy jobb-e, mint az eddig talált legjobb • Ha igen, akkor ezt követően ezt tekintjük a legjobbnak [email protected]

Programozás II.

4

Nyers erő módszerének értékelése • Előnyei – – – – –

Egyszerűen megérthető Egyszerűen implementálható Gyakran csak ez használható Tárhelyigénye nem jelentős Jól párhuzamosítható

• Hátrányai – Futásideje nem kedvező (jelen esetben 2N lépés)

[email protected]

Programozás II.

5


Oszd meg és uralkodj (divide and conqueror) • Programozás I tárgyban már tanult módszer – – – –

Összefésülő rendezés Quicksort K-adik legkisebb elem kiválasztása Stb.

• Általában rekurzív megközelítést használ: – Amennyiben a megoldandó probléma egyszerű, akkor • Megoldás – Amennyiben a megoldandó probléma ehhez túl bonyolult, akkor • Felosztás több kisebb részproblémára • Az így kapott kisebb részproblémák megoldása (tipikusan rekurzív hívás(ok) segítségével) • Az így kapott részeredmények egyesítése, azok alapján a megoldandó probléma eredményének előállítása

• A fenti alapelv optimalizációra is használható

[email protected]

Programozás II.

7

0-1 hátizsák probléma rekurzív megközelítésben • Egy részprobléma esetén van – t darab tárgyunk (az eredeti feladat 1..t-ig indexű tárgyai) – h szabad helyünk (ez értelemszerűen nem nagyobb mint Wmax)

• Rekurzívan megfogalmazva egy optimális pakolás értéke: 0 ℎ𝑎 ℎ = 0 0 ℎ𝑎 𝑡 = 0 𝐹𝑡,ℎ = 𝐹 ℎ𝑎 ℎ > 0 ˄ 𝑡 > 0 ˄ ℎ < 𝑤𝑡 𝑡−1,ℎ max 𝐹𝑡−1,ℎ , 𝐹𝑡−1,ℎ−𝑤𝑡 + 𝑝𝑡

ℎ𝑎 ℎ > 0 ˄ 𝑡 > 0 ˄ ℎ ≥ 𝑤𝑡

• Tehát – ha a tárgyak száma vagy a szabad hely 0, akkor az optimális pakolás értéke 0 – ha az utolsó tárgy nem fér bele a zsákba, akkor az optimális pakolás értéke annyi, mint amennyi az előtte lévő tárgyakkal elérhető ugyanekkora helyen – ha befér, akkor az alábbiak közül a nagyobbik érték • az előtte lévő tárgyakkal elérhető optimális érték ugyanekkora helyen (nem rakjuk be) • az előtte lévő tárgyakkal elérhető érték az utolsó tárgy méretével csökkentett helyen + az utolsó tárgy értéke (berakjuk) [email protected]

Programozás II.

8

0-1 hátizsák probléma megoldása „oszd meg és uralkodj” módszerrel függvény LegjobbRészMegoldás(t, h) ha (t = 0) ˅ (h = 0) akkor vissza 0 különben Pnem  LegjobbRészMegoldás(t-1, h) ha h ≥ wt akkor Pigen  pt + LegjobbRészMegoldás(t-1, h-wt) Popt  max(Pigen, Pnem) különben Popt  Pnem elágazás vége vissza Popt elágazás vége függvény vége függvény HátizsákDnC vissza LegjobbRészMegoldás(N, Wmax) függvény vége

[email protected]

Programozás II.

9

Az „oszd meg és uralkodj” módszer értékelése • Előnyei – A keresés jobban irányítható mint az előző esetben, nem vizsgál meg eleve reménytelen útvonalakat – Gyakran nagyon jól párhuzamosítható – A lépésszáma alacsonyabb lehet mint a „nyers erő” módszer esetén

• Hátrányai – Csak bizonyos szerkezetű megoldásoknál hatékony ez a technika – Amennyiben az egyes részproblémák egymást átfedik, akkor nagyon sok felesleges számítást végez. Lásd Fibonacci számok rekurzív számítása

[email protected]

Programozás II.

10


Feljegyzéses módszer (Memoization) • Oszd meg és uralkodj módszert így szeretjük elképzelni

• A valóságban azonban gyakran inkább így néz ki

• A részproblémák gyakran átfedik egymást: – A részproblémákra bontásnál nem foglalkoztunk azzal, hogy esetleg ugyanazt a részproblémát többször is megkapjuk – Ha már úgy alakult, hogy ugyanazt a problémát többször kell megoldani, akkor nem használjuk fel az előző megoldás eredményeit

• A futásidő tehát jelentősen javítható egy egyszerű módszerrel: – A már kiszámított részeredményeket tároljuk el valahogy – Ha egy már megoldott részproblémához jutunk újra, akkor használjuk ezeket [email protected]

Programozás II.

12

0-1 hátizsák probléma megoldása „feljegyzéses módszer”-rel függvény LegjobbRészMegoldás(t, h) ha (t = 0) ˅ (h = 0) akkor vissza 0 különben ha RészMegoldásTárolóbanKeres([t, h]) ≠  akkor vissza RészMegoldásTárolóbanKeres([t, h]) különben Pnem  LegjobbRészMegoldás(t-1, h) ha h ≥ wt akkor Pigen  pt + LegjobbRészMegoldás(t-1, h-wt) Popt  max(Pigen, Pnem) különben Popt  Pnem elágazás vége RészMegoldásTárolóbaFeljegyez([t, h], Popt) vissza Popt elágazás vége elágazás vége függvény vége függvény HátizsákMemo vissza LegjobbRészMegoldás(N, Wmax) függvény vége [email protected]

Programozás II.

13

A „feljegyzéses” módszer értékelése • Előnyei – A megoldás alapelve pontosan ugyanaz, mint az „oszd meg és uralkodj” módszer esetében, ezért azt nem is vizsgáltuk meg újra – Jelentősen tudja csökkenteni a lépésszámot, ha sok egymást átfedő részproblémát kell megoldani – Egyszerűen implementálható. A pontos feladat ismerete nélkül is adható egy általános séma a használatára (persze annak hatékonysága előre nem tudható)

• Hátrányai – Csak bizonyos szerkezetű megoldásoknál hatékony ez a technika – Jelentős többlet tárhelyigényt jelent – Tulajdonképpen jobb futásidőt kapunk nagyobb tárhelyért cserébe

• Kiegészítés – Amennyiben a triviális megoldások száma véges (és kevés), akkor azt is megtehetjük, hogy ezeket már a rekurzió hívása előtt betöltjük a részmegoldás tárolóba. Ilyenkor a triviális megoldás ellenőrzés el is hagyható a rekurzív algoritmusból

[email protected]

Programozás II.

14


Dinamikus programozás alapjai • Az „oszd meg és uralkodj” módszer felülről lefelé haladva próbálja megoldani a feladatot: – A komplex problémát felbontja kisebb részproblémákra – Majd ezek megoldása alapján adja meg az összetett probléma megoldását

• A gyakorlatban a rekurzív függvény először csak hívogatja magát, amíg el nem jut valamelyik triviális megoldásig. Ezt követően ez alapján elkezdi el felépíteni a teljes megoldást • A „feljegyzéses módszer” esetében ez jól látható, ha megvizsgáljuk, hogy a részmegoldás tárolóba milyen sorrendbe érkeznek az adatok. Először a legegyszerűbb részproblémák adatai kerülnek bele, majd ezek alapján épülnek fel a komplexebb részproblémák eredményei • A fentiek alapján próbáljuk meg eleve ezt az alulról felfelé való építkezést megvalósítani. Egy tárhelyen tároljuk el a triviális megoldásokat, majd ezek alapján kezdjük el felépíteni az egyre összetettebbeket, amíg el nem jutunk a teljes probléma megoldásáig [email protected]

Programozás II.

16

Hátizsákpakolási feladat megoldása • Az algoritmus egy T tömböt tölt fel – ennek mérete (N+1) × (Wmax+1) – T[t,h] értéke azt mutatja, hogy az első t darab tárgy elhelyezése h szabad helyre milyen optimális pakolási összértékkel járhat

• A feltöltés menete – Triviális esetek előre beírhatók a tömbbe: • ha nincs szabad hely, az érték 0 • ha nincs tárgy, az érték 0 – Ezt követően a már megismert képlettel feltöltjük a többi elemet

• Mivel a rekurzív képlet a T(t,h) elem kiszámításához csak a t-nél és hnál kisebb elemeket igényli, így könnyen belátható, hogy a táblázat T[t,h] elemének kiszámításához a t-t és h-t növelő ciklusok mindig már ismert részeredményeket fognak csak felhasználni • Így nincs szükség rekurzióra, a feltöltés egyszerűen megoldható • A feltöltött táblázat T[N, Wmax] eleme tartalmazza a teljes feladat megoldását (tehát egy optimális pakolás értékét) [email protected]

Programozás II.

17

0-1 hátizsák probléma megoldása „dinamikus programozás”-sal függvény HátizsákDP ciklus t  0-tól N-ig F[t,0]  0 ciklus vége ciklus h  1-től Wmax-ig F[0,h]  0 ciklus vége ciklus t  1-től N-ig ciklus h  1-től Wmax-ig ha h ≥ wt akkor F[t,h]  max(F[t-1,h], F[t-1,h-wt] + pt) különben F[t,h]  F[t-1,h] elágazás vége ciklus vége ciklus vége vissza F[N,Wmax] függvény vége

Megjegyzés: a tömböket kivételesen 0-tól indexeljük

[email protected]

Programozás II.

18

0-1 hátizsák probléma megoldásának előállítása • Egy optimális pakolást állít elő az alábbi algoritmus: függvény HátizsákDPEredmény(F) OPT  [hamis,hamis, … ,hamis] t  N h  Wmax ciklus amíg (t > 0) ˄ (h > 0) ha F[t,h] ≠ F[t-1,h] akkor OPT[t]  igaz h  h - wj elágazás vége t  t - 1 ciklus vége vissza OPT függvény vége

• Elindulunk a (t=N, h=Wmax) elemtől, majd – Ha F[t,h] = F[t-1,h] az azt jelenti, hogy a t. elem nincs benne a zsákban (hiszen ugyanakkora helyen nélküle ugyanakkora az optimális pakolás értéke) – Ha a két érték nem egyezik, akkor a t. elem benne van a zsákban

• Ezt követően vizsgáljuk a megelőző tárgyakból elérhető optimális pakolást (a fentiek alapján korrigált szabad hellyel) [email protected]

Programozás II.

19

A „dinamikus programozás” módszere általánosan • A módszer hatékony használatának előkövetelményei: – A feladat legyen optimális részstruktúrájú: a feladat optimális megoldása önmagán belül a részfeladatok optimális megoldásait is tartalmazza – Legyenek a részfeladatok átfedőek: a részfeladatokra bontás során többször is merüljön fel ugyanannak a részfeladatnak a megoldása

• A módszerrel minden, a fenti feltételeknek megfelelő probléma egyszerűen megoldható • Amennyiben ezek teljesülnek, a megoldás lépései: – Az optimális megoldás szerkezetének jellemzése – A megoldás értékének (jóságának) rekurzív módon való definiálása – Az optimális megoldás értékének (jóságának) kiszámítása alulról felfelé történő módon – Amennyiben szükséges, magának az optimális megoldásnak a magadása

• Az utolsó lépés csak akkor szükséges, ha nem elég egy optimális megoldás értéke, hanem magát a megoldást is tudni szeretnénk

[email protected]

Programozás II.

20

A „dinamikus programozás” értékelése • Előnyei – – – – –

Futásideje általában kedvező Nincs szükség egy részprobléma többszöri megoldására Nem rekurzív Minden, az előfeltételeknek megfelelő feladat megoldható vele Tárigénye és lépésszáma előre tudható

• Hátrányai – Az alulról felfelé való megoldás miatt néha felesleges részproblémákat is megold – A többi megoldáshoz viszonyítva a tárigénye magasabb lehet

• Megjegyzés – A tárigény csökkenthető, ha a már szükségtelen részmegoldások eredményeit töröljük (hátizsáknál pl. mindig csak az előző sorra van szükségünk) – További klasszikus dinamikus programozáson alapuló megoldások: • Mátrixok láncszorzása • Leghosszabb közös részsorozat • Stb. [email protected]

Programozás II.

21


Mohó algoritmusok • Mohó algoritmus: a feladat megoldása során felmerülő részproblémák megoldásakor mindig az aktuálisan legjobbnak tűnő részeredményt választja • Legjobbnak tűnő: a rendelkezésre álló (általában hiányos) információk alapján próbálja megbecsülni, hogy mit érdemes választani. Ebből adódóan a futásideje általában nagyon jó • A mohó stratégia általában az alábbi két előfeltételt igényli – Optimális részproblémák: az optimális megoldás felépíthető a részproblémák optimális megoldásából – Mohó választás: a globális optimális megoldás elérhető lokális optimumok választásán keresztül

• Mohó algoritmusok típusai – Az előzőeknek megfelelő problémák esetén mindig optimális megoldást ad – Bizonyos feladatoknál nem mindig ad optimális megoldást, csak egy közel optimálisat (bár általában itt is bizonyítható, hogy ez mennyire van közel az optimálishoz) [email protected]

Programozás II.

23

0-1 hátizsák probléma megoldása mohó algoritmussal • Egy közel optimális pakolást állít elő az alábbi algoritmus: függvény HátizsákMohó TárgyakRendezése(w, p) OPT  [hamis,hamis, … ,hamis] t  1 ciklus amíg (ÖsszSúly(OPT) < Wmax) ˄ (t ≤ N) ha ÖsszSúly(OPT) + wt ≤ Wmax akkor OPT[t]  igaz elágazás vége t  t + 1 ciklus vége vissza ÖsszÉrték(OPT) függvény vége

• Először rendezzük a tárgyakat valamilyen szempont szerint, pl. – Súly szerint növekvő sorrend – Érték szerint csökkenő sorrend – Érték/súly szerint csökkenő sorrend

• Ezt követően a fenti sorrendben kezdjük vizsgálni a tárgyakat – Ha még belefér a zsákba, akkor belerakjuk, egyébként nem – Megállunk ha tele a zsák, vagy elfogytak a tárgyak [email protected]

Programozás II.

24

A „mohó” módszer értékelése • Előnyei – Futásideje nagyon jó (gyakran lineáris) – Ha nem ad optimális megoldást, akkor is egy közel optimálisat nyújt (ez alapja lehet egy másik, lassabb de pontosabb módszernek)

• Hátrányai – Csak a feladatok egy szűk körénél használható

• Megjegyzés – A 0-1 hátizsákproblémára nem ismert mohó algoritmus, a töredékes hátizsákproblémára (amikor egy tárgy egy részét is berakhatjuk a zsákba) viszont könnyen belátható, hogy működik az általunk megadott módszer a harmadik rendezést használva – A későbbiek során még számos mohó algoritmussal találkozunk, amelyek bizonyítottan mindig optimális megoldást adnak • Dijkstra algoritmusa • Prim algoritmusa • Kruskal algoritmusa • Stb. [email protected]

Programozás II.

25

Irodalomjegyzék • Javasolt/felhasznált irodalom – – – – –

Rónyai, Ivanyos, Szabó: Algoritmusok, Typotex, 2005 Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997 Mehlhorn, Sanders: Algorithms and Data Structures, Springer, 2008 Skiena: The Algorithm Design Manual, Springer, 2008 Szénási: Algoritmusok, adatszerkezetek II., Óbudai Egyetem, 2014

[email protected]

Programozás II.

26

Optimalizációs stratégiák 1

Recommend Documents