Optimalizációs stratégiák 2. Visszalépéses keresés, szétválasztás és korlátozás
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
Optimalizációs stratégiák 2. Visszalépéses keresés Visszalépéses kereséssel optimalizálás Szétválasztás és korlátozás
Bevezető feladat • Egy építkezésen több egymástól független munkafázist kell elvégezni. Osszuk szét a munkákat az arra alkalmas személyek között (úgy, hogy mindenki csak egyet vállalhat)! Géza Miklós
Miklós
András
Zsolt
Géza
Miklós
Klaudia
András
Zsolt
Palika
András
Géza
Szponzor
Irányítás
Alap
Fal
Engedély
Lefizetés
• Végigpróbálgathatjuk az összes lehetséges változatot, (amelyekből összesen 2×2×2×3×2×2 = 96 db van), ezek túlnyomó többsége azonban nem megoldása a feladatnak • Olyan algoritmust keresünk, ami a megoldás keresése során eleve nem folytat olyan utakat, amelyek láthatóan nem vezethetnek megoldáshoz
[email protected]
Programozás II.
3
Feladat általánosítása • N darab részeredményt keresünk (E1, E2 ... EN) • Mindegyikhez ismerjük a véges értékkészletet (pl. E1-hez ennek mérete M1, elemei: R1,1, R1,2, ... R1,M1) M4=3 M1=2
M2=2
M3=2
R4,1
M5=2
M6=2
R1,1
R2,1
R3,1
R4,2
R5,1
R6,1
R1,2
R2,2
R3,2
R4,3
R5,2
R6,2
E1
E2
E3
E4
E5
E6
N=6
• A visszalépéses keresés olyan feladat típusoknál alkalmazható hatékonyan, ahol – A megoldandó feladat több, egymástól csak közvetve függő részfeladat megoldásából áll – Már a részfeladatok egy részéből is lehet arra következtetni, hogy az azokra adott részmegoldásokkal biztosan nem érhető el a teljes megoldás
[email protected]
Programozás II.
4
Visszalépéses keresés paraméterei • Keresés bemenete: – N – megoldandó részfeladatok száma – Mszint – szint-edik részfeladat lehetséges részmegoldásainak a száma – Rszint,i – szint-edik részfeladat i. lehetséges részmegoldása
• Keresés kimenete: – van – van-e teljes megoldás? – E – részmegoldásokat tartalmazó vektor (Ei – az i. részmegoldás értéke)
• A feladattól függő szabályokat általában két függvény segítségével adjuk meg: – Ft(szint, s) – Egy függvény, ami azt határozza meg, hogy a szint-edik részfeladat esetében lehetséges megoldás-e az s? – Fk(szint, s, E) – Azt határozza meg, hogy a szint-edik részfeladat esetében választhatjuk-e az s részmegoldást, amennyiben az előző szinteken az E vektorban található részmegoldásokat választottuk?
• Az előző példa esetében az Ft mindig igaz (hiszen csak olyanokat soroltunk fel, akik megfelelnek az adott feladatra), az Fk pedig akkor igaz, ha a megadott embert még nem választottuk más munkára
[email protected]
Programozás II.
5
Rekurzív visszalépéses keresés • Visszalépéses keresés egy lehetséges megvalósítása eljárás VisszalépésesKeresés(szint, címsz. E, címsz. van) i 0 ciklus amíg ¬van ∧ i < Mszint i i + 1 ha Ft(szint, Rszint,i) akkor ha Fk(szint, Rszint,i, E) akkor Eszint Rszint,i ha szint = N akkor van igaz különben VisszalépésesKeresés(szint + 1, E, van) elágazás vége elágazás vége elágazás vége ciklus vége eljárás vége van hamis VisszalépésesKeresés(1, E, van)
[email protected]
Programozás II.
6
Rekurzív visszalépéses keresés egymást kizáró részmegoldásokkal • Amennyiben az egyes részeredmények páronként kizáróak eljárás VisszalépésesKeresés(szint, címsz. E, címsz. van) i 0 ciklus amíg ¬van ∧ i < Mszint i i + 1 ha Ft(szint, Rszint,i) akkor k 1 ciklus amíg k < szint ∧ Fk(szint, Rszint,i, k, Ek) k k + 1 ciklus vége ha k = szint akkor Eszint Rszint,i ha szint = N akkor van igaz különben VisszalépésesKeresés(szint + 1, E, van) elágazás vége elágazás vége elágazás vége ciklus vége eljárás vége van hamis VisszalépésesKeresés(1, E, van)
[email protected]
Programozás II.
7
Visszalépéses kereséssel kezelhető problémák osztályozása • Részfeladatok egymást kizárják – igen (ilyenkor használható az általános algoritmus) – nem (erre láttuk a második algoritmust)
• Részmegoldások száma – logikai változók – minden részfeladatnál két lehetőség közül választhatunk – M darab – több előre rögzített feltétel közül választhatunk – előzményfüggő – egy adott helyen a lehetséges választások száma attól függ, hogy az előző szinteken milyen értékeket választottunk (ilyenkor úgy kell az Ft függvényt módosítani, hogy az is hozzáférjen az eddigi részeredményekhez)
Kölcsönösen kizáró
Logikai
átfedések, időzítés
M darab
8 királynő, sudoku, feladat kioszt.
Előzményfüggő
szólánc
Logikai
hátizsák pakolás
M darab
összetett feladatkiosztás
Előzményfüggő
optimális útkeresés, huszár útja
Backtrack Összetett feltétel
[email protected]
Programozás II.
8
Problématér átalakítása • A visszalépéses keresés általunk vizsgált algoritmusa egy vektor elemeinek keresi az értékét • A feladatok azonban gyakran több dimenzióban vannak meghatározva, pl. – töltsünk ki egy sudoku táblát – helyezzünk el egy sakktáblán királynőket – járjunk be egy sakktáblát egy huszárral
• Megoldási lehetőségek – algoritmus módosítása: az i ciklus cseréje egy két vagy többdimenziós teret bejáró egymásba ágyazott ciklusokkal – problématér átalakítása: az eredetileg többdimenziós problémát felírjuk egydimenziós formában (erre látunk példákat a következő diákon) 1,1
1,2
1,3
szint
2,1
2,2
2,3
1,1
3,1
3,2
3,3
[email protected]
N=6 1,2
1,3
Programozás II.
2,1
2,2
2,3
3,1
3,2
3,3
9
8 királynő a sakktáblán • Klasszikus feladat: helyezzünk el úgy 8 királynőt a sakktáblán, hogy azok ne üssék egymást • A lehetséges elhelyezések száma meglehetősen nagy: 64×63×62×61×60×59×58×57 1,78 * 1014 • A visszalépéses keresés jól használható, mivel ha bármelyik két már lerakott királynő üti egymást, akkor nem is kell vizsgálni a többieket • Problématér átalakítása: minden oszlopba pontosan egy királynőt kell elhelyeznünk, így valójában 8 darab 1..8 közötti számot keresünk, ez már egyszerű egydimenziós probléma • A kölcsönösen kizáró algoritmus így már alkalmazható: – – – –
N=8 Mi = 8 ; Ri,j = j (i=1..8 ; j = 1..8) Ft(i, r) = igaz Fk(i, r, j, q) = akkor igaz, ha a sakk szabályai szerint az i,r és a j,q pozícióban lévő királynők nem ütik egymást
[email protected]
Programozás II.
10
8 királynő a sakktáblán (2) • Egy lehetséges elhelyezés Fk megvalósítása: (x1,y1) és (x2, y2) helyen álló királynők akkor ütik egymást, ha az alábbiak közül bármelyik teljesül: • x1 = x2 • y1 = y2 • │x1 - x2│ = │y1 - y2│
[email protected]
Programozás II.
11
Huszár útja a sakktáblán • Klasszikus feladat: egy fix kezdőpontból be lehet járni egy huszárral az egész táblát úgy, hogy minden mezőt pontosan egyszer érintünk? • Egy huszár 8 irányba tud lépni, így az ellenőrizendő kombinációk száma: kb. 863 7,84 * 1056 • Visszalépéses keresés jól használható, mivel egy n-edik rossz lépés után nem kell foglalkozni az utána következő (63-n) darabbal • Problématér átalakítása: tudjuk, hogy 63 lépésünk lesz, így a feladat valójában a 63 megfelelő irány megtalálása (minden lépésnél 8 lehetőség közül választhatunk) • Az algoritmus előzményfüggő változata használható: – N = 63 – Mi = 8 ; Ri,j = a j. lehetséges lépés iránya (pl. 2 fel+1 balra, 2 fel+1 jobbra, stb.) – Ft – megadott helyre léphet-e a huszár (táblán belül marad?). Mivel ez egy előzményfüggő feladat, itt az Ft is megkapja az előző lépések értékét (E vektor), ami alapján tudja hogy épp hol jár, és ez alapján tud dönteni – Fk – az előző lépések nem zárják-e ki az új helyet? (járt már ott?)
[email protected]
Programozás II.
12
Sudoku feladat megoldó • Egy 9x9-es táblázat tartalmaz előre beírt és üres mezőket. Az n darab üres mezőt kell kitölteni az alábbi szabályok szerint – minden üres helyre egy szám írható 1..9 között – egy sorban, illetve egy oszlopban nem szerepelhet kétszer ugyanaz a szám – a tábla 3x3-as blokkokra oszlik, egy blokkon belül nem lehet kétszer ugyanaz
• Lineáris kereséssel a lépésszám: kb. n9 • Visszalépéses keresés jól használható, mivel ha két mezőbe beírt érték kizárja egymást, akkor a többi mezőt nem is kell vizsgálni • Problématér átalakítása: maga a tábla kétdimenziós, azonban egy listába felsorolhatjuk az üres mezőket. Így megfelelően n darab részfeladatunk lesz, amelyekbe 1..9 közötti értéket keresünk • Az algoritmus előzményfüggő változata használható: – – – –
N = üres mezők száma Mi = 9 ; Ri,j = j (i=1..N ; j = 1..9) Ft(i, j) – az i. számú üres mezőbe beírható-e a j érték (a fix mezők alapján) Fk(i,r,j,q)– az i. üres mezőbe írt r szám nem zárja ki a j. üres mezőbe írt q-t
[email protected]
Programozás II.
13
Sudoku feladat megoldó • Kétdimenziós tábla átalakítása egydimenziós szerkezetté • Ezzel a módszerrel jelentősen kibővíthető a visszalépéses kereséssel megoldható feladatok köre 1
3
2
3
5
2
4 2
4 3
1
8
1
1
8 3
Fix mezők: (0,0) (0,2) (0,3) (1,0) … Üres mezők: (0,1) (0,4) (1,2) (1,3) …
• Az egyes szinteknek az egyes üres mezők felelnek meg, ezek között kell keresni megfelelő számokat 1..9 között
[email protected]
Programozás II.
14
Optimalizációs stratégiák 2. Visszalépéses keresés Visszalépéses kereséssel optimalizálás Szétválasztás és korlátozás
Minden megoldás kiválogatása • Az első megoldás után nem állunk meg, keressük a többit eljárás VisszalépésesKeresés(szint, címsz. E, címsz. van, címsz. MIND) i 0 ciklus amíg ¬van ∧ i < Mszint i i + 1 ha Ft(szint, Rszint,i) akkor ha Fk(szint, Rszint,i, E) akkor Eszint Rszint,i ha szint = N akkor van igaz MIND MIND E különben VisszalépésesKeresés(szint + 1, E, van, MIND) elágazás vége elágazás vége elágazás vége ciklus vége eljárás vége van hamis MIND ∅ VisszalépésesKeresés(1, E, van, MIND)
[email protected]
Programozás II.
16
Optimális megoldás keresése • Keresés helyett tulajdonképpen minimumkiválasztás eljárás VisszalépésesKeresés(szint, címsz. E, címsz. van, címsz. OPT) i 0 ciklus amíg ¬van ∧ i < Mszint i i + 1 ha Ft(szint, Rszint,i) akkor ha Fk(szint, Rszint,i, E) akkor Eszint Rszint,i ha szint = N akkor ha ¬van ∨ Jóság(E) > Jóság(OPT) akkor OPT E elágazás vége van igaz különben VisszalépésesKeresés(szint + 1, E, van, OPT) elágazás vége elágazás vége elágazás vége ciklus vége eljárás vége van hamis VisszalépésesKeresés(1, E, van, OPT)
[email protected]
Programozás II.
17
Hátizsák probléma • 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.
18
Hátizsákba pakolás • A visszalépéses keresés használható: ha néhány tárgy együtt nem fér a hátizsákba, akkor az ezen az úton nem kell tovább vizsgálódni • Az algoritmus előzményfüggő változata használható: – – – –
N = tárgyak száma Mi = 2 ; Ri,1 = igaz (adott tárgy bekerül), Ri,2 = hamis (adott tárgy nem kerül be) Ft – igaz, ha a tárgy önmagában belefér a zsákba Fk– igaz, ha az előző tárgyakkal együtt sem lépte túl a maximális méretet
• Az összehasonlíthatóság érdekében egyszerűsített algoritmust írunk – Nincs külön Mi és Ri, hiszen minden szinten két részmegoldás van csak – Az Ft-t mindig igaznak tekintjük így el is hagyhatjuk (ha egy tárgy mégse férne be a zsákba, akkor az Fk úgyis hamis lesz) – A VAN változóra sincs szükség, mivel a kiinduló állapot (semmit se rakunk a zsákba) egy biztosan érvényes pakolást tartalmaz. Megállási feltételre pedig nincs szükség az optimalizáció miatt.
[email protected]
Programozás II.
19
0-1 hátizsák probléma megoldása „visszalépéses keresés” segítségével függvény Fk(szint, E) vissza ÖsszSúly(E) ≤ Wmax függvény vége eljárás Backtrack(szint, címsz. E, címsz. OPT) ciklus i 0-tól 1-ig E[szint] (i = 0) ha Fk(szint, E) akkor ha szint = N akkor ha ÖsszÉrték(E) > ÖsszÉrték(OPT) akkor OPT E elágazás vége különben Backtrack(szint + 1, E, OPT) elágazás vége elágazás vége ciklus vége eljárás vége függvény HátizsákBT E [hamis,hamis, … ,hamis]; OPT [hamis,hamis, … ,hamis] Backtrack(1, E, OPT) vissza ÖsszÉrték(OPT) függvény vége
[email protected]
Programozás II.
20
A „visszalépéses keresés” módszer értékelése • Előnyei – Jól áttekinthető, általánosan használható módszer – Az „oszd meg és uralkodj” módszerhez hasonlóan a nyilvánvalóan felesleges részfeladatok vizsgálatát elkerüli
• Hátrányai – A rekurzív hívások miatt az erőforrásigénye nagy lehet (persze megírható a backtrack iteratív formában is) – Az átfedő részfeladatok esetén elképzelhető, hogy többször megoldja ugyanazt a részfeladatot – Bizonyos feladatokra találhatunk jobb megoldást is
[email protected]
Programozás II.
21
Optimalizációs stratégiák 2. Visszalépéses keresés Visszalépéses kereséssel optimalizálás Szétválasztás és korlátozás
Szétválasztás és korlátozás (branch and bound) • Bizonyos feladatoknál a keresés közben nem csak azt tudjuk megállapítani, hogy egy úton lehet-e megoldás, hanem azt is, hogy ez a megoldás lehet-e jobb mint az eddig talált legjobb • Ilyenkor használható jól a „szétválasztás és korlátozás” technika, amely során az alábbi két függvényre van szükség: – Szétválasztási függvény: ennek szerepe, hogy egy bonyolult feladatot szétbontson egyszerűbb részfeladatokra (ez már ismerős lehet az eddigi technikákból) – Korlátozó függvény: ez próbálja megmondani, hogy egy részfeladat megoldásának érdemes-e nekiállni. Általában egy felső becslést ad arra, hogy a megadott részfeladatnak mi lehet a legjobb eredménye. Ha még ezzel se járunk jobban, mint az eddigi optimum, akkor nem is kezd bele a vizsgálatba
• A hátizsákpakolásnál pl. megnézhetjük, hogy ha az összes hátralévő tárgyat bele tudjuk rakni a megmaradt szabad helyre, akkor jobb megoldást kapunk-e mint az eddigi legjobb – ez egy felső becslés, ha már ez se igaz, akkor nem is érdemes vizsgálódni erre – ha nem, akkor folytatni kell a rekurziót, hogy mi a tényleges részmegoldás erre
[email protected]
Programozás II.
23
0-1 hátizsák probléma megoldása „szétválasztás és korlátozás”-sal függvény Fb(szint, E) pfk 0 ciklus i szint + 1-től N-ig ha ÖsszSúly(E) + wi < Wmax akkor pfk pfk + pi elágazás vége ciklus vége vissza pfk függvény vége eljárás Backtrack(szint, címsz. E, címsz. OPT) ciklus i 0-tól 1-ig E[szint] (i = 0) ha Fk(szint, E) akkor ha szint = N akkor ha ÖsszÉrték(E) > ÖsszÉrték(OPT) akkor OPT E elágazás vége különben ha ÖsszÉrték(E) + Fb(szint,E) > ÖsszÉrték(OPT) akkor Backtrack(szint + 1, E, OPT) elágazás vége elágazás vége elágazás vége ciklus vége eljárás vége
• Az algoritmus többi része megegyezik az előző megoldással
[email protected]
Programozás II.
24
A „szétválasztás és korlátozás” módszer értékelése • Előnyei – A fentieknek megfelelően egy kellőképpen finomhangolt algoritmus nagyon sok felesleges lépést meg tud spórolni – Nem csak a már rögzített részeredményeken alapul a továbblépés, hanem a még fel nem dolgozott részproblémákat is figyelembe veszi
• Hátrányai – Csak megfelelően kiválasztott szétválasztó és korlátozó függvények esetében működik
• Megjegyzés – A példaprogramban a „visszalépéses” keresés által adott algoritmust módosítottuk úgy, hogy egy korlátozó függvény is legyen benne. Ez természetesen más technikáknál is lehetséges – Bár nehéz egyértelműen összehasonlítani az egyes technikákat, talán ezt tekinthetjük a leghatékonyabbnak, hiszen ez előrefele is néz a keresés során
[email protected]
Programozás II.
25
Irodalomjegyzék • Javasolt/felhasznált irodalom – – – – –
Pap, Szlávi, Zsakó: μlógia4 – Módszeres programozás: Rekurzió, ELTE TTK, 2004 Rónyai, Ivanyos, Szabó: Algoritmusok, Typotex, 2005 Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997 Mehlhorn, Sanders: Algorithms and Data Structures, Springer, 2008 Szénási: Algoritmusok, adatszerkezetek II., Óbudai Egyetem, 2014
[email protected]
Programozás II.
26
