II. Állapottér-reprezentáció

II. Állapottér-reprezentáció

Gregorics Tibor

Mesterséges intelligencia

1

Állapottér-reprezentáció elemei 



 

Állapottér: a feladat homlokterében álló adategyüttes (objektum) lehetséges értékeinek (állapotainak) halmaza  lényegében egyetlen típusérték-halmaz és annak összetett szerkezetű reprezentációja a típus invariánssal Műveletek: állapotból állapotba vezetnek  megadásukhoz: előfeltétel és hatás-leírás Kezdő állapot(ok) vagy azokat leíró kezdőfeltétel Célállapot(ok) vagy célfeltétel

Gregorics Tibor


2

Megjegyzés 

Megoldás: műveletek sorozata



Az állapottér általában nem azonos a problématérrel, mert a problématér elemei, azaz a lehetséges válaszok többnyire a kezdőállapotból induló műveletsorozatok, nem pedig az állapotok. – A kiinduló válasz a kezdő állapotból induló nulla hosszú műveletsorozat – Egy műveletsorozatnak (válasznak) szomszédjai azok a sorozatok, amelyek egy művelettel hosszabbak.

Gregorics Tibor


3

Hanoi tornyai probléma 1

3 Kezdőállapot

2

[3,3,3]

3 Állapottér:

2

1

Célállapot 1 [1,1,1]

2

1

2

3

3

Állás ={1,2,3}n

megjegyzés : a rudakon lentről felfelé csökkenő méret szerint helyezkednek el a korongok. Egydimenziós , 1..n intervallummal indexelt n elemű tömb, amely elemeit az {1,2,3}-ból veszi

Művelet:

Gregorics Tibor

Rak(honnan, hová):ÁllásÁllás HA a-ban (a:Állás) a honnan nem üres, és a hová üres vagy a legfelső korongja nagyobb, mint honnan legfelső korongja AKKOR a[honnan legfelső korongja] := hová Mesterséges intelligencia

4

Implementáció Művelet: Rak(honnan, hová):ÁllásÁllás (a:Állás)

l1,i=search i1..n (a[i]=honnan) i-t akarjuk mozgatni l2,j=search j1..n (a[j]=hová) j-re akarunk rakni HA l1 és (l2 vagy i<j) AKKOR a[i] := hová

Gregorics Tibor


5

[3,3,3] start

Hanoi tornyai [2,3,3]

állapot-gráf

[1,3,3] [1,2,3]

[2,1,3]

[2,2,3]

[1,1,3] [3,1,3] [3,2,3]

[2,2,1]

[1,1,2] [3,1,2] [3,2,2]

[2,1,2]

[1,2,1]

[3,2,1]

[2,3,2] [1,3,1]

[3,1,1]

[2,2,2] [1,2,2] [1,3,2] [3,3,2] [3,3,1]

[2,3,1] [2,1,1]

[1,1,1] cél

Állapottér-reprezentáció állapot-gráfja 

Állapot-gráf az állapottér-repr. reprezentációs gráfja   

  



állapot művelet hatása művelet költsége kezdő állapot célállapotok műveletsorozat hatása

csúcs irányított él élköltség startcsúcs célcsúcsok irányított út

Az útkeresés hatékonysága a problématér bonyolultságán múlik, ami az állapot-gráf bonyolultságától függ   

csúcsok és élek száma (3n csúcs, 1 csúcsból kivezető él max: 3) utak száma, hossza (adott csúcsból kivezető k hosszú utak száma, ha a közvetlen visszalépést kizárjuk: 2k) körök gyakorisága és hossza

Gregorics Tibor


7

n-királynő probléma 1. általános állapot

célfeltételnek megfelelő állapot

♛

♛ ♛♛

♛ ♛

♛

♛

kétdimenziós tömb (n×n-es mátrix) Állapottér: Tábla = {♛, _ }n×n amely elemeit a {♛, _ }-ból veszi invariáns: egy állapotban a királynők (♛ jelű mezők) száma = n

Művelet: Áthelyez(x,y,u,v):TáblaTábla HA (a[x,y]=♛) és (a[u,v]=_ ) AKKOR a[x,y]  a[u,v] Gregorics Tibor

(a:Tábla)


8

Problématér mérete 

Sok modellje lehet ugyanannak a feladatnak: keressük meg a legkisebb problématerűt o

Most annyi állapot van, ahányféleképpen n királynőt elhelyezhetünk. Ennél jóval nagyobb a problématér, azaz egy adott állapotból kiinduló utak halmaza, hiszen egy állapotból n*(n2n) féleképpen lehet továbblépni, és egymás után végtelen sok ilyen lépést lehet tenni.

o

Bővítsük az állapotteret az n-nél kevesebb királynőt tartalmazó állásokkal, de használjunk új műveletet : a királynő-felhelyezést. A problématér a legfeljebb n hosszú utakból áll majd, és a megoldást a pontosan n hosszúak között találjuk. Ezek száma:

o

A műveletek előfeltételének szigorításával csökkenhet a problématér: Sorról sorra csak egy-egy királynőt helyezzünk fel a táblára! Ekkor az n hosszú utak száma: nn Ez tovább csökkenthető, ha ütést tartalmazó állásra nem rakunk fel újabb királynőt!

Gregorics Tibor


9

n-királynő probléma 2. kezdőállapot

közbülső állapot

♛ Állapottér: Tábla = {♛, _ }n×n

♛

célállapot

♛

♛

♛

♛

invariáns: a királynők (♛ jelű mezők) száma  n csak az első valahány sorban van egy-egy királynő

Művelet: Helyez(oszlop):TáblaTábla HA a táblán (a:Tábla) a királynők száma < n és nincs ütés és a „sor” a soron következő üres sort jelöli AKKOR a[sor,oszlop] := ♛ Gregorics Tibor


10

Állapot-gráf ♛

♛

♛ ♛

♛ ♛

♛ ♛

♛

♛

♛ ♛

♛

♛

♛ ♛ ♛ Gregorics Tibor

♛ ♛

♛

♛

♛

♛ ♛ ♛

♛

♛ ♛♛

♛

♛

♛

♛

♛ ♛

♛ ♛

♛

♛ ♛

♛

♛ ♛

♛ ♛

♛

♛

♛

♛ ♛

♛ ♛

♛ ♛ ♛

♛ ♛

♛

♛ ♛ ♛

♛

♛ ♛


♛

♛

♛

♛

♛

♛

♛

♛ 11

Művelet végrehajtásának hatékonysága 

A művelet előfeltételének kiszámítási bonyolultsága csökkenthető, ha az állapotteret (vagy annak invariánsát) szigorítjuk és o a művelet hatását ennek megfelelően módosítjuk (ugyanaz a megszorítás „vándorol” a specifikáción belül) o



Például o o

o

A királynők számát eltároljuk az állapotban (ebből ismert lesz a következő üres sor is) ahelyett, hogy mindig kiszámolnánk. Ha tároljuk, hogy mely üres mezőket tartanak ütés alatt a királynők, (ezeket a művelet végrehajtásakor, egy újabb királynő elhelyezésekor kell bejelölni, akkor konstans időben eldönthető, hogy egy új királynő üti-e az előzőeket, és ezt a tényt egy logikai változóban rögzíthetnénk, amiből látni, hogy további királynőt nem szabad elhelyezni. Sőt (és ez már új megszorítás) ne is legyen ütés a táblán.

Gregorics Tibor


12

n-királynő probléma 3. kezdőállapot: db = 0

közbülső állapot: db = 2 ♛    ♛       

célállapot : db = 4 ♛    ♛ ♛    ♛

Állapottér: Tábla = rec(m :{♛,  , _ }n×n, db : ℕ) invariáns: csak az első db sorban van egy-egy királynő (♛), db  n, királynők nem ütik egymást,  egy királynő által ütésben álló (foglalt) üres mezőt, _ az ütésben nem álló szabad mezőt jelöli Gregorics Tibor


13

n-királynő probléma 3. Művelet: új királynő elhelyezése a soron következő üres sor szabad mezőjére (invariáns tartó művelet) Helyez(oszlop):TáblaTábla

HA AKKOR

(a:Tábla)

a. db < n és a.m[a.db+1,oszlop]= _ a.db:=a.db+1 a.m[a.db,oszlop] := ♛ minden megfelelő i,j -re: a.m[i,j] := 

Kezdőállapot: a.m üres mátrix, a.db=0 Célállapot: a.db=n Gregorics Tibor


14

állapot gráf

4-királynő ♛     

 ♛    

♛     ♛    

♛    ♛   

 ♛ ♛     

  ♛ ♛      

♛     ♛ ♛  

♛    ♛ ♛    

 ♛ ♛     ♛  

  ♛ ♛    ♛ 

♛    ♛ ♛    ♛

 ♛ ♛     ♛ ♛ 

♛        ♛    ♛   

Gregorics Tibor

  ♛        ♛ ♛    


17

Tologató játék (8-as, 15-ös) kezdőállapot: tetszőleges

2 8 3 1 6 4 7 5

1 2 3 8 4 7 6 5

célállapot: szokásos

Állapottér: Tábla=rec(m :{0..8}3×3, ü :{1..3}×{1..3}) invariáns: a mátrix sorfolytonos kiterítése a 0 .. 8 számok permutációja, az üreshely a 0 elem sor és oszlopindexe.

Művelet: Tol(irány):TáblaTábla (irány∊*(1,0),(0,1),(-1,0),(0,-1)}) HA a.ü+irány egy érvényes pozíció (a:Tábla) AKKOR a.m[a.ü]  a.m[a.ü+irány] a.ü := a.ü+irány a.ü+irány koordinátánként értendő

Gregorics Tibor


19

Mit lát egy keresés a problématérből? 

A keresés szempontjából egy reprezentációs gráfnak csak a startcsúcsból elérhető része érdekes (9!/2), ugyanis ez az, amit egy keresés „felfedhet” a gráfból. Ráadásul ezt a felfedett részt is sokszor csak torzultan látja a keresés: (keresési tér) •

• •

Ha a keresés nem ellenőrzi, hogy egy általa elért állapotot már korábban felfedezett-e, akkor nem az eredeti reprezentációs gráfot, hanem annak fává kiegyenesített változatát látja. Nem feltétlenül baj, ha emiatt a keresési tér végtelen nagy lesz, ha cserébe nincsenek már benne körök. A szülőcsúcsba való visszalépést viszont érdemes direkt módon kizárni, hiszen ez egy egyszerű vizsgálat, amellyel a felesleges éleket, oda-vissza köröket hagyhatjuk el a keresési térből.

Gregorics Tibor


20

Keresési tér

2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5

2 8 3 1 4 7 6 5

2 8 3 6 4 1 7 5 8 3 2 6 4 1 7 5

2 8 3 1 4 7 6 5

2 8 3 6 4 1 7 5

2 3 1 8 4 7 6 5

8 3 2 1 4 7 6 5

2 8 3 7 1 4 6 5

2 3 1 8 4 7 6 5

2 3 1 8 4 7 6 5

8 3 2 1 4 7 6 5

2 8 3 7 1 4 6 5

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

8 3 2 1 4 7 6 5

8 1 3 2 4 7 6 5

1 2 3 8 4 7 6 5

1 2 3 7 8 4 6 5

2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 1 4 3 7 6 5

2 8 3 1 6 7 5 4

2 8 3 1 4 5 7 6

2 8 3 1 6 7 5 4

2 8 3 1 4 5 7 6 2 8 3 1 4 5 7 6

2 8 3 1 5 6 7 4 2 8 3 1 5 6 7 4

2 8 3 5 1 7 4 6 2 8 3 1 5 7 4 6

1 2 3 8 4 7 6 5

célállapotok

2 8 1 6 3 7 5 4

2 8 3 1 5 7 4 6

duplikátumok

Fekete-fehér kirakó Egy n+m+1 hosszú sínen n fekete és m fehér lapka és egy üres hely van. Egy lapkát szomszédos üres helyre tolhatunk vagy a szomszéd felett üres helyre ugrathatunk. Kezdetben a feketék után jönnek a fehérek, majd az üres hely. Kerüljenek a fehérek a feketék elé! Állapottér: Sín=rec(v : {B, W,_}n+m+1, poz : [1.. n+m+1]) invariáns: egy üres hely, poz az üres hely indexe, n darab B és m darab W

Műveletek: TolBal, TolJobb, UgrikBal, UgrikJobb: Sín  Sín Például: TolBal (üres helyet toljuk balra) HA a.poz1 (a : Sín) AKKOR a.v[a.poz-1]  a.v[a.poz] ; a.poz :=a.poz-1 Kezdőállapot: [B, … , B, W, … , W, _ ] Célállapot: i,j [1.. n+m+1], i<j : (a.v[i]=B  a.v[j]=W) Gregorics Tibor


22

Fekete-fehér kirakó állapot gráfja start

cél cél

cél Gregorics Tibor

cél Mesterséges intelligencia

23

C A B

Kockavilág probléma

Egy asztalon van néhány kocka (A,B,C,…), amelyeket egy robotkar mozgat: felemel, rátesz, levesz, lerak. Építsünk fel egy meghatározott alakzatot egy rögzített helyzetből kiindulva! Állapottér: Kockák= set(Alapliterálok) Alapliterálok={az ontable(x), on(x,y), clear(x), handempty, holding(x) összes alapelőfordulása, azaz ontable(A), ontable(B), … } invariáns: egy állapot ellentmondás mentes (pl.: nincs on(C,B) és clear(B)), de lehet hiányos (lásd célállapot)

Például: Kezdőállapot: ontable(A), clear(A), ontable(B), on(C,B), clear(C),handempty Célállapot: on(A,B), on(B,C) Gregorics Tibor


24

C A B

Kockavilág probléma műveletei

Teljes leírású állapotból teljes leírású állapotba vezetnek, de lehet alkalmazni hiányos állapotra is, Műveletek: sőt nemcsak alapliterálokkal leírt állapotokra is. Pickup(x): Kockák  Kockák (h : Kockák) HA ontable(x),clear(x),handempty  h AKKOR h := h {ontable(x),clear(x),handempty }{holding(x)} Putdown(x): Kockák  Kockák (h : Kockák) HA holding(x) h AKKOR h := h {holding(x)}{ontable(x),clear(x),handempty} Stack(x,y): Kockák  Kockák (h : Kockák) HA holding(x), clear(y) h AKKOR h := h {holding(x), clear(y)}{on(x,y),clear(x),handempty} Unstack(x,y): Kockák  Kockák (h : Kockák) HA on(x,y),clear(x),handempty  h AKKOR h := h {on(x,y),clear(x),handempty}{holding(x), clear(y)} Gregorics Tibor


25

Kancsók problémája Három kancsóban, egy öt, egy három és egy két literesben, együttesen 5 liter bor van. Kezdetben az öt literes kancsó van tele. Töltögetéssel érjük el, hogy a két literesbe pontosan 1 liter bor kerüljön! Állapottér: Kancsók= vektor( [5,3,2];{0..5} ) invariáns: i [5,3,2] v[i] = 5 i[5,3,2]: v[i]i

Kezdő állapotból elérhető állásokban egyik kancsó üres vagy teli.

Művelet: Tölt(i,j): Kancsók  Kancsók (v : Kancsók) HA i,j[5,3,2]  ij  min(v[i], j-v[j])>0 AKKOR v[i],v[j] := v[i]-min(v[i], j-v[j]),v[j]+min(v[i], j-v[j]) Kezdőállapot: [5, 0, 0] Célállapot: [x, y, 1] Gregorics Tibor


26

Kancsók-probléma állapot gráfja

032

122

cél 1 3 1

221

230

320

Gregorics Tibor

212

cél

311

410

302

cél

401

500

cél

start


27

Misszionárius - kannibál probléma Elég csak a bal partot jegyezni az átkelés nem külön állapot

n misszionárius és n kannibál át akar kelni egy folyón egy h személyes csónakban … Ha a bal parton nincs emberevés, akkor a jobb parton sincs

Állapottér: Part = rec(m : [0..n], k : [0..n], c : 𝕃) invariáns: nincs emberevés, azaz I(m,k)  m=k  m=0  m=n Kezdőállapot: (n,n,igaz) (0,0,hamis) Ha Célállapot: az átevezés előtt és után nincs emberevés, akkor a csónakban sincs. Műveletek: Oda(x,y):PartPart és Vissza(x,y):PartPart (a:Part) HA a.c  xa.m  ya.k HA a.c  xn–a.m  yn–a.k  0<x+yh  I(a.m–x, a.k–y)  0<x+yh  I(a.m+x, a.k+y) AKKOR a.c:=hamis : AKKOR a.c:=igaz : a.m:=a.m–x: a.k:=a.k–y a.m:=a.m+x: a.k:=a.k+y Gregorics Tibor


29

Feladatok 1. 2. 3.

4. 5. 6.

7. 8. 9.

Utazó ügynök probléma Gráf színezési probléma Sakktábla bejárása lóval Rubik kocka Bűvös négyzet 5×5-ös mátrix 0,1-esekkel úgy, hogy minden 2×2-es más Ábrarajzolás egy vonallal Útvonal tervezés városban (egyirányú utcák) Nagypapa játéka

Gregorics Tibor


34

II. Állapottér-reprezentáció

Recommend Documents