A valós világ egy marha összetett dolog, így teljes szépségében esélyünk nincs a számítógépes környezetben való tanulmányozására. Ennek megoldása végett, csak a számunkra funtos tulajdonságaival foglalkozunk. Jelölje T1,T2,…,Tm (m>0) az általunk fontosnak tartott tulajdonságait a valós világnak. Belátható, hogy egy-egy tulajdonság több értéket is felvehet, tehát az értékek változnak. Minden Ti tulajdonság tehát egy halmaz, amely halmazok descartes-féle szorzathalmazaként (t1,t2, …, tm) elem m-eseket kapunk, amelyeket egy halmazban gyűjtünk össze. Ezt a halmazt az állapotok halmazának nevezzük:
(t1, t2, …, tm) := { a | a eleme T1 x T2 x T3 x … x Tm && kényszerfeltétel(a) }
A kényszerfeltételek azok a feltételek amelyek eldöntik egy tetszőleges (t1, t2, t3, …, tm) elem m-esről, hogy az állapota e az általunk vizsgált problémának. A kényszerfeltételeket a matematikai logika segítségével tudjuk formalizálni. Az állapotok halmazának egy elemét rendkívül szellemesen állapotnak nevezzük. Létezik két kitüntett állapot:
  1. Kezdőállapot: Az általunk megfigyelt tulajdonságok kezdeti értékei által meghatározott állapot.
  2. Célállapot: A célfeltételek által meghatározott állapot.

Nade mik is azok a célfeltételek? A célfeltételek, hogy a nevük is sugalja megmondják egy valamilyen úton megkapott állapotról, hogy azt kerestük e? Nyilván valamilyen állapotot szeretnénk elérni de nem azzal az állapottal kezdünk. Nézzünk egy példát:

kezdo: ( {0,0,0}; {0,0,0}; {0,0,0} ) => Kezdőállapot. Valahol valamikor ezeket az értékeket mértük valamire.

cel: ( {-1, 5, 7}; {9, 9, 9}; {3, -2, 8} ) => Ezt az állapotot akarjuk valahogyan elérni a kezdo állapotból.

Rögtön látható, hogy az állapotoknak változnuk kell valahogyan mert különben folyamatosan a kezdo állapotot látnánk és tuti biztos, hogy az életben nem érnénk el a célállapotunkat. Azokat a speciális műveleteket amelyek megváltoztatják egy tetszőleges állapot által hordozott információkat, operátoroknak nevezzük. Itt érdemes megjegyezni, hogy az operátor egy olyan n dimenziós függvény amely egy tetszőleges állapotoz egy állapotot rendel hozzá. Miért mondom, ogy n-dimenziós? Mert az állapotok tetszőleges bonyolultságúak lehetnek. Egy állapot lehet egy egyszerű szám is de akár lehet egy n*m -es mátrix is. Az gondolom rögtön leesik mindenkinek, hogy az operátorokat nem tudjuk vakon felhasználni, mert különben elég lenne 1 operátor (vannak olyan problémák ahol megoldható a dolog 1 operátorral de akkor meg az operátor paramétereire kell megszorításokat kimondani). Azok a speciális feltételek, amelyek megmondják, hogy egy adott a állapotra alkalmazható-e egy o operátor, az operátor alkalmazási előfeltételei. Az operátor ugye egy állapothoz egy újabb állapotot rendel: o(a) = b. Ezt nevezzük az operátor hatásának.

Amennyiben megadtuk az Állapotok nem üres halmazát, valamint ennek a halmaznak kitüntetett jelentőséggel bíró 1db elemét illetve egy részhalmazát; a kezdőállapotot és a célállapotokat; valamint egy újabb halmazban összegyűjtöttük a probléma állapotaira alkalmazható operátorokat, akkor a problémánkat állapottér-reprezentáltuk.

p: <A, kezdo, c, O> – jelöli a p probléma állapottér-reprezentációját.

Legyen adott p: <A, kezdo, c, O> állapottér-reprezentáció, továbbá a és b tetszőleges állapotai a problémának. Ekkor definiáltak a következő relációk a és b között:

    • a-ból közvetlenül elérhető b ( a => b) ha létezik olyan o operátor, amely alkalmazható az a állapotra, és amelynek hatásaként előáll a b állapot: o.alkalmazási_előfeltétel(a) && o.alkalaz(a) = b.
    • a-ból elérhető b (a =*> b), ha létezik a <c0, c1, c2, …, cn> állapotoknak egy olyan sorozata amelyre teljesül, hogy: c0 = a && cn = b && ci => ci+1 minden i < n-re.

A p problémát megoldhatónak tekintjük, ha kezdő =*> c (itt c eleme a célállapotok halmazának).

Állapottér-gráf

Az állapottér-reprezentáció szép és jó de nem szemléletes. A szemléletesség az ott kezdődik, hogy felírjuk az összes előforduló állapotot és nyilacskát húzunk közéjük akkor, ha van olyan operátor amely alkalmazható a arra az állapotra amelyből a nyíl indul és a hatása az az állapot ahová a nyíl mutat. Na ezt nevezzük állapottér-gráfnak; ezt használjuk programok írásakor. Miből is áll egy gráf?

  1. Csúcsok: N := { ta | a eleme az A-nak }
    • s := kezdőállapot
    • T := { tc | c eleme a c-nek }
  2. Élek: E := { (na, nb) | Létezik o operátor amelyre: o.alkalmazási_előfeltétel(a) && o.alkalmaz(a) = b }

Az így megadott gráfot <N, s, T, E> a p probléma állapottér-gráfjának nevezzük. Legyen most adott ez az állapottér-gráf és legyen még adott két tetszőleges p és q csúcsok. Ekkor definiálhatóak az alábbi fogalmak:

  • p-ből közvetlenül elérhető q (p => q), ha Létezik olyan (nx, ny) eleme az E-nek, hogy az nx által reprezentált állapot megeggyezik a p által reprezentált állapottal, és az ny által reprezentált állapot megegyezik a q által reprezentált állapottal. Vagyis él van közöttük magyarul…
  • p-ből elérhető q (p =*> q), ha létezik olyan <c0, c1, c2, …, cn> csúcsokból álló sorozat, amelyre teljesül, hogy c0 = p && cn = q && ci => ci+1 minden i<n -re.

Amit itt nagyon észre kell venni az az, hogy az élek nem mások mint az operátorok, és irányított élekről van szó. Ergó a p =*> q egy irányított utat definiál p-től q-ig. Vagyis állapottér-gráf szemszögéből nézve a dolgokat az adott problémát akkor tekintjük megoldhatónak ha a startcsúcsból vezet irányított út valamelyik terminális csúcsba (T egy eleme a terminális csúcs).

Hasonlóan ahogy a matematikai gráfelméletből ismerős, úgy az állapottér-gráfban is értelmezve vannak a sztenderd gráfelméleti topológiák így például:

  • Kör: Olyan speciális irányított út az állapottér-gráfban amelynek a kezdőcsúcsa által reprezentált állapot megegyezik egy másik csúcs által reprezentált állapottal: c0, c1, c2, c3, …., cn-2, cn-1, cn, c0
  • Hurok: Adott két csúcs között egy irányított út, ez már tiszta sor. A hurok lényege az, hogy létezik a két csúcs között egy másik irányított út is: c0, c1, c2, c3, c4, c5, …, cn-2, cn-1, cn && c0, d0, d1, d2, …, dn, cn

Vagyis mit is jelent egy MI feladat megoldása? Egy ilyen állapottér gráfban kell keresni egy startcsúcsból induló és terminális csúcsban végződő irányított utat vagy csak el kell érni egy terminális csúcsot. Nehezíti a dolgot, hogy általában a gráfokban van bőven kör is és hurok is. Ezek ugye kiegyenesíthetőek fa struktúrájú gráffá de ennek eredménye az lehet, hogy az amúgy addig tökéletes véges gráf paff végtelenné válik és akkor ezt valahogy fel kell tudni dolgozni. Azok a speciális keresők amelyek egy állapottér gráfban megoldást keresnek a keresőrendszerek. De ezekről majd később, kellemes csemegézést .

Ennyi lenne az állapottér reprezentáció.

Advertisements