Category: Számítógép és internet


Ugorjunk rögtön a közepébe. A módosítható keresés azt jelenti, hogy ha alkalmazunk egy valamilyen állapotra egy arra alkalmazható valamilyen operátort, akkor annak az eredménye egy új állapot. Ezt az állapotot később vissza tudjuk vonni és vissza tudunk ugorni arra az állapotra amire az előbb alkalmaztuk az operátort. Ezt úgyjük el, hogy módosítunk a keresőrendszer adatbázisán. Lássuk akkor, hogy ez hogyan is működik a gyakorlatban:
  • Adatbázis: Az adatbázis egyetlen a startcsúcsból kiiunduló aktuális csúcsban végződő irányított utat tartalmaz amelyet csomópontok tartanak nylván. Ahhoz, hogy ezt az irányított utat nevezzük most listának be tudjuk járni ahhoz a csomópontokban nyilván kell tartani az alábbi információkat:
    • A csúcs által reprezentált állapotot.
    • Egy mutatót amely az aktuális csúcs szülőjét címzi meg.
    • Azt az operátort amellyel előállt az aktuális állapot.
    • Az alkalmazható operátorok listája / A már alkalmazott operátorok listája
  • Műveletek: A műveletek itt már bonyolódnak egy kicsit. Kötelesek vagyunk masszívan elkülöníteni a technikai műveleteket az operátorokból származtatott műveletektől.
    • Operátorokból származtatott műveletek: Ahhoz, hogy alkalmazhassuk az operátorokat lennie kell legalább egy csomóponmtnak az adatbázisban. Enélkül nincs semmi. Ha már van legalább egy csomópont akkor arra már tudunk keresni alkalmazható operátort amelyet ha alkalmazunk akkor ennek hatásaként létrehozunk egy új csomópontot amelyet befűzünk az adatbázisba.
    • Technikai műveletek: Nos mivel most éppen a Backtrack azaz a visszalépéses keresőt kívánom bemutatni, ezért a technikai művelet nagyon szellemesen a visszalépés lesz. A visszalépéshez szintén elengedhetetlen, hogy legyen legalább egy csúcs az adatbázisban de hatásaként az utolsónak befűzött csomópont törlődik.
  • Vezérlő: A vezérlő feladata, hogy figyelje elértünk-e egy terminális csúcsot, illetve amennyiben nem eldönti, hogy mely produkciós szabályt alkalmazza. A produkciós szabály itt együttesen jelenti az operátorokból származtatott műveleteket és a technikai műveleteket is.

Na de a kérdés gondolom ekkorra már mindenkiben felvetődik. Mikor kell használni a visszalépést? Nos a dolog rendkívül egyszerű, de érdemes előre leszögezni, hogy backtrack algoritmus esetében is használhatunk heurisztikát. Nos hogy ezt tisztáztuk lássuk mikor is használunk visszalépést:

  1. Ha zsákutcába futunk: Ezt arról tudjuk felismerni, hogy még nem teljesül a célfeltétel de az adott csúcs által reprezentált állapotra nincs egyetlen alkalmazható operátor sem.
  2. Ha a zsákutca torkolatában vagyunk: Ez akkor áll elő, ha már egyszer visszaléptünk egy zsákutcából is ismét erre az állapotra csak azt az egy operátort tudjuk alkalmazni, amellyel ismét zsákutcába jutunk. Erre a célra a csomópontban szükséges letárolni mind az alkalmazható mint a már alkalmazott operátorok listáját, különben a backtrack beragad.
  3. Ha valamilyen heurisztika segítségével úgy találjuk, hogy az adott utat fölösleges tovább vizsgálni.
  4. Ha elfogytak az alkalmazható operátorok: Ha nincs több alkalmazható operátor akkor a csúcsból nemtudunk tovább menni. Mondjuk erről csak a szakirodalmakban olvastam, szerintem teljesen fölösleges mert ez totál ugyanazt jelenti, mint az első pont azaz zsákutcában vagyunk. Szóval én ezt figyelmen kívül szoktam hagyni, illetve ezzel szoktam megnézni, hogy na vaj zsákutcában vagyunk-e avagy sem.

És akkor lássunk valamicske kódot a backtrack algoritmus ezen változatához:

  1.  Procedure BackTrack(<A, kezdo, c, O>)
  2.     Műveletek <- Inicializál(O)
  3.     Terminálisok <- Inicializál(c)
  4.     Adatbázis <- Inicializál(kezdo) 
  5.     WHILE(IGAZ) LOOP
  6.                 IF Adatbázis.Top IS IN Terminálisok THEN
  7.                         STOP
  8.                 ENDIF
  9.         o <- SELECT * FROM Műveletek WHERE alkalmazási_előfeltétel(Adatbázis.Top)  AND Adatbázis.Top->Alkalmazott_Operátorok(this) IS NULL
  10.         IF o IS NOT NULL THEN
  11.             új_állapot->állapot <- o.Alkalmaz(Adatbázis.Top)
  12.             új_állapot->szülő <- Adatbázis.Top
  13.             új_állapot->operátor <- o
  14.             új_állapot->alkalmazott_operátorok <- NULL
  15.             Adatbázis.Top->alkalmazott_operátorok.Add(o)
  16.             Adatbázis.Push(új_állapot)
  17.         ELSE
  18.             Adatbázis.Pop
  19.         ENDIF
  20.     END LOOP
  21.     IF Adatbázis IS NOT NULL THEN
  22.         KiírMegoldás(Adatbázis)
  23.     ENDIF
  24. END

A dolog meglehetősen önmagáért beszél az egyetlen dolog ami talán magyarázatra szorul az operátorok összegyűjtése. A lényeg a következő. Össze kell gyűjteni minden alkalmazható operátort amelyet alkalmazhatunk az Adatbázis utolsó elemére és arra a csomópontra még nem alkalmaztuk az éppen vizsgált operátort. Szóval ez implementáció szinten kőkemény 1db for ciklust foglal magában. Aztán a következő érdekes dolog az, hogy itt már azt is megnézzük, hogy volt e egyáltalán ilyen kritériumokkal rendelkező operátor. Ha van akkor alkalmazzuk ha nincs akkor viszont visszalépünk. A visszalépés annyira egyszerű, hogy azt már ragozni sem lehet. Az utolsó csomópontot kitöröljük az adatbázisból. Ennyi lenne a visszalépéses megoldáskereső.

Fontos továbbá megjegyezni azt, hogy ebben a formában a backtrack nem nevezhető éppen hatékonynak. Hogy miért?

  1. Nem fogja észrevenni ha talált egy kört, azaz az új állapot már szerepel az adatbázisban.
  2. Ha végtelen hosszú a gráf akkor az életben nem fog terminálni.

Ezen hiányosságok kiküszöbölésére létezik még két variánsa a backtrack algoritmusnak. A körfigyeléses backtrack algoritmus és a mélységi korlátos backtrack algoritmus. Mindkettő koncepciója rendkívül egyszerű! A körfigyeléses algoritmusnál mielőtt létrehoznánk az új csomópontot és hozzáadnánk azt az adatbázishoz megnézzük, hogy az adatbázisban volt e már olyan csomópont amely által nyilvántartott állapot megegyezik az aktuálissal. Ha igen akkor nem foglalkozunk vele újrakezdjük a ciklust. Ezzel a rendkívül egyszerű 1db IF szerkezettel garantáltuk azt, hogy véges akár köröket is tartalmazó gráfban amennyiben létezik megoldás akkor az algoritmusunk körmentes megoldást fog találni. A mélységi korlátos backtrack algoritmus koncepciója mégegyszerűbb mint a körfigyeléses társáé. A lényege az, hogy fel kell venni egy számlálót, és meg kell neki adni egy maximális úthosszkorlátot. Amikor beszúrunk egy csomópontot az adatbázisba akkor növeljük egyel a számlálót. Amennyiben a számláló eléri a korlátot akkor az adott gráfban nincs megoldás vagy van de az a korlátnál hoszabb.

És ha a fenti két koncepciót összeöntjük egy algoritmusba azaz, kört is figyelünk és mélységi korlátot is megadunk, akkor eljutunk az ág és korlát algoritmushoz. Jó ez nem igaz mert ehhez az egészet egy ciklusba kell tenni, azaz minden megoldást kell keresni nem csak egyet de csak azt tároljuk amelyik megoldás hossza kevesebb vagy egyenlő mint a korábban tárolt megoldás hossza. Ezzel nem, hogy körmentes megoldást találunk egy általános akár végtelen gráfban de az a megoldás optimális megoldás lesz.

Eljutottunk ezen lecke végéhez is, lássuk akkor a fenti három algoritmus elemzésést.

  1. Teljesség:
    • Backtrack algoritmus: Véges gráfban ha létezik megoldás akkor talál egyet azok közül.
    • Körfigyeléses backtrack: Szintén véges gráfban ha léteznek megoldások akkor ez egy körmentes megoldást fog találni.
    • Mélységi korlátos (Úthossz-korlátos) backtrack: Tetszőleges gráfban ha létezik az úthosszkorlátnál rövidebb megoldás akkor azok közül egyet meg fog találni.
    • Ág-és-Korlát algoritmus: Tetszőleges gráfban optimális megoldást talál.
  2. Optimalitás: Egyedül az Ág-és-Korlát algoritmus garantálja az optimális megoldás megtalálását.
  3. Időigény:
    • Backtrack: Az időigényének java részét az alkalmazható operátorok összegyűjtése teszi ki.
    • Körfigyeléses backtrack: Itt már nem csak arról van szó, hogy össze kell gyűjteni az operátorokat amiket tudunk alkalmazni az adott állapotra de ha jó nagy a kör a gráfban amire sikeresen ráfut a kereső akkor az elég kritikus tud lenni. Akkor vissza kell lépkedni ám elég rendesen azon a szép kis körön és hát azért ez elég időigényes.
    • Úthosszkorlátos backtrack: Ennél nincs probléma az időigénnyel, az egyik leggyorsabb backtrack variáns. Az időigényét a  megadott korlát szabályozza. Minél hoszabb korlátot engedünk meg neki annál tovább tart a keresés de annál nagyobb eséllyel talál megoldást véges gráfban, illetve minél kisebb korlátot adunk meg annál gyorsabb de annál kétségesebb az, hogy akár véges gráfban is talál megoldást.
    • Ág-és-Korlát algoritmus: Rendkívül időigényes. Nincs megadva implicit úthosszkorlát mindenképpen az első megoldás hossza adja az első korlátot majd ezután minden újabb megtalál megoldás akkor kerül letárolásra ha ezen megoldások hossza kisebb vagy egyenlő mint az előzőleg letárolt megoldásé. Ekkor a korlát is felülíródik és indul megint az egész előről. Ettől időigényesebb backrack variáns egyszerűen nincs. De cserébe tuti biztos, hogy akármilyen is a gráfunk a kapott megoldástól jobb megoldás nem létezik.
  4. Tárigény: Az első két backtrack variáns tárigénye nagyban függ a kiinduló robléma állapottér-gráfjától. Ha nagy méretű a gráf és hosszú megoldások vannak benne akkor a nyilvántartandó út is hosszú ezért nyilván több emóriát fog lefoglalni.
    • Úthosszkorlátos backtrack: Fix méretű az adatbázisa, ami az úthosszkorlátnyi csomópontot tárol.
    • Ág-és-Korlát algoritmus: Teljesen változó méretű az adatbázisa. Maximum a leghoszabb megoldás lépéseinek számányi csomópont lesz az adatbázisban de végül az adatbázis mérete pont az optimális megoldás hosszától függ.

Ennyi lenne a módosítható megoldáskeresők bevezetése és a backtrack algoritmus. A következő téma már egy kicsit elvontabb: Keresőfával kereső rendszerek és azon belül helyet kapnak a Szélességi és Mélységi keresők, Best-First és Optimális algoritmusok valamint az A algoritmus és az A* algoritmus alapjai.

Na szóval, akkor lássuk mit takar a nem módosítható keresőrendszerek általános felépítése. Azt már tudjuk, hogy egy keresőrendszer három fő komponense, az adatbázis, az ezen végezhető műveletek és az egészet irányító vezérlő. De, hogy is néz ki ez a három komponens ebben az esetben?
  1. Adatbázis: A nem módosítható keresőrendszerek adatbázisa egyetlen állapotot reprezentáló csúcsot tárol. Itt máris szembetűnik, hogy miért is nem tudunk mihez kezdeni ha zsákutcába jutottunk. Nincs letárolva semmi információ arról, hogy honnan kerültünk az aktuális csúcsba. A nem módosíthatóság szóval annyit takar, hogy nincs lehetőségünk visszavonni egy tetszőleges operátor hatását.
  2. Műveletek: No ettől egyszerűbb nem is jöhetne. A nem módosítható keresőrendszerek műveletei az állapottér-reprezentáció operátoraiból származtatott műveletek. Egyetlen feltétele van egy művelet alkalmazásának, mégpedig az, hogy az adatbázisban tárolt aktuális állapotra teljesüljön az operátor alkalmazási előfeltétele. Az operátor alkalmazásaként előálló új állapot felülírja az adatbázisban korábban tárolt állapotot és ismét lehet alkalmazni egy műveletet.
  3. Vezérlő: A vezérlő feladata rendkívül egyszerű! Az adatbázisban tárolt állapotra választania kell az alkalmazható operátorok közül egyet és alkalmazni azt. A választás lehet szisztematikus vagy heurisztikus. Ezen kívül a vezérlőne figyelnie kell arra, hogy az éppen előállított állapot megfelel e a célfeltételeknek avagy sem. Ezen a ponton könnyen belátható, hogy eze az algoritmusok nem adja meg a probléma konkrét megoldását, csak annyit tud elmondani, hogy létezik -e megoldás avagy sem.

A nem módosítható keresőrendszerek is alkalmazhatnak heurisztikát. Azt már tudjuk mi a heurisztika de milyen hatással is van ez a keresés kimenetelére? A heurisztika kifejezetten a problémához kapcsolódik amit azért adunk meg, hogy jobb minőségű megoldást kapjunk és lehetőleg gyorsabban. De megvannak a negatív hatásai is. Pontosan mit is takarnak ezek a negatív hatások? Minél több ilyen információt adunk meg a keresőrendszernek annál jobban meggárgyul… Mit is takar ez?

  • Csökkenti a szabályok alkalmazásának számát a keresés során.
  • Mivel a heurisztika a szabályok kiválasztásában "segítkezik" ezért ezt ugye minden műveletválasztásnál ki kell értékelni. Úgyértem minden heurisztikát amit pluszban megadunk ki kell értékelni ahhoz, hogy az algoritmus választani tudjon. Vagyis Ugyan csökken a szabályok alkalmazásának mennyisége de növekszik a szabály kiválasztásának nehézsége.
  • Mivel növekszik a szabályok kiválasztásának bonyolultsága ezért növekszik a keresés időigénye.

Szóval akkorminél több és minél pontosabb heurisztikát adunk meg a keresőrendszernek annál lassabb lesz?! Akkor minek használjuk? Mert van egy szép kis aranyközépút. Aki ismeri a függvényeket annak elképzelni ezt most elég egyszerű lesz. Exponenciális függvény szerint csökken a szabályalkalmazások száma, de exponenciálisan nő egy szabály kiválasztásának ideje. A futásidő pedig egy parabolikus függvény amely minimumát pont az előbbi két exponencális függvény metszéspontjában veszi fel. Vagyis akkor az aranyközépút pont itt van, egy "közepes" erősségű heurisztika esetében.

  • Szisztematikus
    • Rögzített operátorsorrendet alkalmazó kereső
    • Véletlenszerűen operátor választó kereső: Próba-Hiba módszerHeurisztikus
  • Heurisztikus: Hegymászó algoritmus

Rendkívül egyszerű az értelmezésük az első két szisztematikus keresőrendszer magáért beszél. A heurisztikus kereső már inkább érdekesen működik. A hegymászó algoritmus heurisztikája egy olyan függvény amely minden állapothoz egy valós számot rendel hozzá. Az algormtus ezek után olyan operátort választ amely eredményeként előálló állapot heurisztikája kisebb mint a szóbajöhető összes többi operátor hatásaként előálló állapot heurisztikája. Ez nem más mint egy minimalizációs eljárás lényegében. Lássuk, hogy is néz ki ez kód ügyileg:

  1.  Procedure Hegymaszo_Kereso(<A, kezdo, c, O>, heurisztika)
  2.     Műveletek <- Inicializál(O)
  3.     Terminálisok <- Inicializál(c)
  4.     VanMegoldás <- False
  5.     aktuális <- kezdo
  6.         h <- heurisztika
  7.     WHILE(IGAZ) LOOP
  8.         o <- SELECT * FROM Műveletek WHERE alkalmazási_előfeltétel(aktuális) ORDER BY h(o.alkalmaz(aktualis)) ASC
  9.         aktuális <- o.alkalmaz(aktuális)
  10.         IF aktuális IS IN Terminálisok THEN 
  11.             VanMegoldás <- True
  12.             STOP
  13.         ENDIF
  14.     END LOOP
  15.     IF VanMegoldás IS True THEN
  16.         KiírMegoldás(aktuális)
  17.     ENDIF
  18. END

Nem is olyan szörnyű igaz? Összesen kőkemény egy sorban kellett módosítani az általános keresőhöz képest. Az operátorok kiválasztásán a lényeg. Lekéri az összes olyan operátort amelyet alkalmazhatunk az adott állapotra és ezeket növekvő sorba rendezi aszerint, hogy az alkalmazásként előállapot heuriszikája milyen. Ezután a szokásos módon az elsőt alkalmazza és előáll az új állapot és indul a ciklus előről egészen addig amíg el nem ér egy terminális csúcsot.

A Próba-Hiba módszert már mindenki fantáziájára fogom bízni de az is összesen ennyire bonyolult. Azt az egy darab sort kell átvariálni és készen áll az egész. Akkor elérkeztünk ezen lecke végére is; lássuk ezen algoritmusok elemzését:

  • Teljesség:
    • Próba-hiba módszer: Ha a gráf véges és nem tartalmaz köröket és tuti, hogy ellehet jutni a startcsúcsból a terminális csúcsokba akkor találni fog egy megoldást.
    • Hegymászó-algoritmus: Teljes mértékben a heurisztika jóságától függ az, hogy talál-e megoldást avagy sem, egyébként nem lehet megjósolni.
  • Optimalitás: Egyik keresőnél sem garantált, hogy optimális megoldást találna. Kivéve ha egyetlen megoldás létezik mert akkor az az optimális ugyebár.
  • Tárigény: Tárigényre ezek az algoritmusok a legjobbak. Hát ugye egyetlen csúcsot kell letárolni ettől kevesebbet már nagyon nehéz lenne mert akkor mi alapján keresne?!
  • Időigény: A szisztematikus próba-hiba módszer gyorsabb mint a hegymászó algoritmus, sőt én megkockáztatom azt is, hogy a lehető leggyorsabb és egyben leggagyibb keresőalgoritmus is ^^. A hegymászó-algoritmus sebessége nagyban függ az alkalmazott heurisztika összetettségétől, mert ugye ezt minden alkalmazható operátorra ki fogja értékelni és ez lehet bizony időigényes is.

Nos ennyi lenne a mára szentelt evangéliumok sorozata, a következő leckében már egy érdekesebb téma következik: Módosítható keresőrendszerek és a Backtrack algoritmus!

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ó.