Visszalépéses keresés Backtracking
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
Visszalépéses keresés Alapvető működése Továbbfejlesztési lehetőségek Gyakorlati példák
Egy megoldásra váró 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
Visszalépéses keresés Alapvető működése Továbbfejlesztési lehetőségek Gyakorlati példák
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.
8
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.
9
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.
10
Vágás • Az optimális megoldás keresése során a visszalépéses keresés is átvizsgálja a problématér jelentős részét • Bizonyos feladatoknál a keresés közben nem csak azt tudjuk megállapítani, hogy egy úton lehet-e jó teljes megoldás, hanem azt is, hogy ez a megoldás lehet-e jobb mint az eddig talált legjobb • A vágás lépései: – Minden megtalált végeredmény esetén eltároljuk annak értékét – Minden továbblépés előtt adunk egy felső becslést arra vonatkozóan, hogy ha azon úton minden a legjobban alakul, akkor mi lehet a maximális érték – Amennyiben ez kisebb, mint az eddig talált legjobb megoldás, akkor felesleges tovább haladni ezen az úton
• Pl. hátizsák pakolási probléma esetén a továbblépéskor megnézhetjük, hogy ha az üresen maradt helyre el tudnánk helyezni az összes abba önmagában beleférő tárgyat, akkor milyen végeredményhez jutunk. Ha ez rosszabb mint az eddig talált legjobb, akkor nem is kell keresni tovább ezen az úton
[email protected]
Programozás II.
11
Visszalépéses keresés Alapvető működése Továbbfejlesztési lehetőségek Gyakorlati példák
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.
13
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
14
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.
15
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.
16
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.
17
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.
18
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.
19
Hátizsákba pakolás • Adott egy megadott méretű hátizsák és n darab tárgy, amelyeknek ismert a méretük és az értékük. Keressük a tárgyak azon halmazát, amelyek összmérete kisebb mint a hátizsák mérete, és a tárgyak összértéke maximális • 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 • A feladat egyszerűen leírható logikai típusú részeredményekkel. A részfeladatok száma egyenlő a tárgyak darabszámával, és minden részeredmény azt mutatja, hogy az adott tárgy bekerül a zsákba (igaz) vagy nem (hamis) • 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 optimális megoldás keresést gyorsíthatjuk vágással
[email protected]
Programozás II.
20
További ötletek • Logikai értékkészlet használata – egymást (nem) kizáró esetek kezelése – egy tartományból elemek kigyűjtése – stb.
• Előre nem ismert értékkészlet használata – síkbeli/térbeli pozíciók meghatározása
• Előre nem ismert részfeladatszám használata – útkeresés
[email protected]
Programozás II.
21
Irodalomjegyzék • Javasolt/felhasznált irodalom – Pap, Szlávi, Zsakó: μlógia4 – Módszeres programozás: Rekurzió ELTE TTK, 2004 – Szénási: Algoritmusok, adatszerkezetek II., Óbudai Egyetem, 2014 – Wikipedia.org megfelelő szócikkek http://en.wikipedia.org/wiki/Backtracking
[email protected]
Programozás II.
22
