Archive for június, 2010


Komolyan mondom ha nem lennék, engem ki kéne találni. Egy rohadt fél napot görnyedtem a játékelméletből ismert minimax algoritmus fölött és egyszerűen kénytelen voltam felfogni, hogy mi a hóhért akar ez tőlem… A dolog rendkívül egyszerű, számomra értelmezhetetlen volt a kapott pszeudo kód, ami pontosan így fest:
  1. function Minimax-Lépés(<A, kezdő, V, O>, állapot, korlát, h)
  2.     max <- -Inf
  3.     operátor <- NIL
  4.     for all o in O do
  5.         if ELŐFELTÉTEL(állapot, o) then
  6.             új-állapot <- ALKALMAZ(állapot, o)
  7.             v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, korlát – 1, h)
  8.             if v > max then
  9.                 max <- v
  10.                 operátor <- o
  11.             end if
  12.         end if
  13.     end for
  14.     return operátor
  15. end function

Hát ezzel önmagában semmi probléma nincs, az algoritmus lényege ugyanis az, hogy egy kétszemélyes véges determinisztikus stratégiai játékban egy játékos számára "elég jó" lépést ajánljon. Szóval visszaad egy operátort ami nem más mint egy lépés egy adott állásban, okké semmi gáz. És akkor jött az amin elszakadt minden cérnám és az istennek sem fért bele a fejembe, hogy mi a szent túrót szórakozik velem:

  1. function Minimax-Érték(<A, kezdő, V, OI>, állapot, mélység, h)
  2.     if állapot in V or mélység = 0 then
  3.         return h(állapot)
  4.     else if JÁTÉKOS[állapot] = J then
  5.         max <- -Inf
  6.         for all o in O do
  7.             if ELŐFELTÉTEL(állapot, o) then
  8.                 új-állapot <- ALKALMAZ(állapot, o)
  9.                 v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, mélység – 1, h)
  10.                 if v > max then
  11.                     max <- v
  12.                 end if
  13.             end if
  14.         end for
  15.         return max
  16.     else
  17.         min <- Inf
  18.         for all o in O do
  19.             if ELŐFELTÉTEL(állapot, o) then
  20.                 új-állapot <- ALKALMAZ(állapot, o)
  21.                 v <- Minimax-Érték(<A, kezdő, V, O>, új-állapot, mélység – 1, h)
  22.                 if v < min then
  23.                     min <- v
  24.                 end if
  25.             end if
  26.         end for
  27.         return min
  28.     end if
  29. end function

Na és, hogy ennek mit kellene csinálni? Hát nekem a kapott pszeudokódból minden kijön csak az nem aminek kéne. A dolog rendkívül egyszerű de az algoritmusa az számomra egy nulla. Szóval az algoritmus lényege a következő. Adott egy valamilyen játékgráf amelynek a csúcsait ki kell értékelni egy heurisztikus függvénnyel ami kb úgy működik, hogy:

  • Minél jobb az adott állás a pártfogolt játékos számára annál nagyobb pozitív értéket kap.
  • Minél jobb az adott állás az ellenfél számára annál kisebb negatív értéket fog kapni.
  • Döntetlen esetben meg egy nullához közeli értéket.

Szóval a heurisztika egy f: A -> R leképezés lenne, amivel totál semmi bajom nincs sőt nagyon jó ötletnek tartom. Az algoritmusnak meg úgy kéne működni, hogy először kiértékeli a játékgráf felépített részében a levélelemek heurisztikáit majd pedig halad tovább fölfelé a gyökér felé szintenként. Páros szinten az a játékos helyezkedik el amelynek lépést akarunk ajánlani páratlan szinten meg aki ellenünk van. A nem levél elemek heurisztikáinak kiértékelése meg szintén tök egyszerű. Egy tetszőleges n csúcs súlyának meghatározása páros szinten úgy zajlik, hogy a leszármazottai heurisztikáinak a maximumát vesszük, míg páratlan szinten pont a minimumát. Így szóba jöhet ugyan egy rekurzív függvény de ne úgy adjuk már meg környörgöm, hogy a rekurzív függvényhívás után nézzük meg, hogy na vajon az új érték milyen mer az életben rá nem kerül a vezérlés… Szóval ez betette nálam az ajtót elég rendesen, mire sikerült kibogarászni, hogy ki hol merre az nem 2 órámba telt. Vicces, hogy mikor totál feladtam, hogy ez egy marhaság akkor jöttem rá, hogy én jól gondolom de a kapott pszeudo már nem igazán. A rekurzív függvény hívás utáni if ágakkal szerette volna az oktató a maximumot illetve a minimumot keresni. Hát ez nem jött össze neki ráadásul jól megkeresrítette az életem.

Reklámok
Lássunk egy másik megközelítést is. Az lőzőekben tárgyalt algoritmusok nem túl hatákonyak mival vagy csak egy csúcsot vagy csak egy irányított utat figyeltek. Nekünk olyan kéne ami extra ciklus ezzel együtt lassítás nélkül hajlandó lenne figyelni minden lehetséges utat. Na erre adnak lehetőséget a keresőfával kereső rendszerek. A tárgyalásuk ugyanazon az elven történik mint eddig:
  1. Adatbázis: Az állapottér gráf adott most is mint minden eddigi esetben. No de, hogy fogunk ebben nyilvántartani minden lehetséges utat? Hát kicsit másként tároljuk a dolgot. Továbbra is csomópontok lesznek az adatbázisban egy hajszálnyi módosítással de a struktúrája az adatbázisnak egy csöppet más. Ketté fogjuk bontani az adatbázist de lássuk csak, hogy pontosín miért. Az adatbázisban a gráf már bejárt részét feszítő fát fogjuk eltárolni amit igen szellemesen keresőfának szokás nevezni. Ezt a keresőfát fogjuk nyilvántartani a csomópontokban de a csomópontokban most is variálunk egy kicsit.
    1. Az a állapot amelyet az adott csúcs reprezentál.
    2. Egy mutatót amely megmutatja, hogy az aktuális csúcs mely csúcsnak a leszármazottja.
    3. Azt az operátort amellyel előállt az aktuális állapot.
    4. Egy Státusz nevű jelzőt ami meg fogja osztani az adatbázisunkat. Pontosan két részre fogja osztani az adatbázist:
      • Nyílt: Ez azt jelenti, hogy az adott csúcs ugyan előállt már a keresés során valamilyen operátor alkalmazásának hatásaként, de arra még nem alkalmaztunk egy darab operátort sem. Ez azt jelenti, hogy annak még nem állítottuk elő egyik leszármazottját sem (ha van neki).
      • Zárt: Totál ellentettje az előzőnek, neki már előállítottuk az összes leszármazottját.
  2. Műveletek: A műveletek itt is két csoportba lesznek sorolva mint a backtrack algoritmusoknál. Bezony ennek van köze ahhoz, hogy az adatbázis megoszlik két csoportra.
    1. Operátorokból származtatott műveletek.
    2. Technikai műveletek: Nos szép és jó, hogy vannak nyílt csomópontok és zárt csomópontok de mire lesz ez nekünk jó? A dolog egyszerű de még nem lövöm le a poént. Azt máris ki lehet találni, hogy milyen technikai műveletünk lesz. A nyílt csomópontok azok amelyeknek még nem állítottuk elő egyik leszármazottját sem. Ez a keresőfában a levélelemeket jelenti. Ezesetben kizárásos alapon a zárt csomópontok a nem levél elemeket jelölik a keresőfánkban. Akkor ahhoz, hogy építhessük a keresőfát vagyis az adatbázist nyilván a csúcsoknak elő kell állítani a leszármazottjait. Ezt a folyamatot amikor egy nyílt csúcsnak előállítjuk az összes leszármazottját kiterjesztésnak nevezzük. Ez lenne a technikai műveletünk és nagyon hasznos és egyszerű dologról van szó.
        1. Procedure kiterjeszt(<A, kezdo, c, O>, Csúcs, Nyíltak, Zártak)
        2.     FOR EACH o IN O LOOP
        3.         IF o.alkalmazási_előfeltétel(Csúcs->Állapot) THEN
        4.             állapot <- o.alkalmaz(Csúcs->Állapot)
        5.             ny <- SELECT * FROM Nyíltak WHERE Állapot = állapot
        6.             z <- SELECT * FROM Zártak WHERE Állapot = állapot
        7.             IF ny IS NULL AND z IS NULL THEN
        8.                 új_csomópont->Állapot <- állapot
        9.                 új_csomópont->Szülő <- Csúcs
        10.                 új_csomópont->Operátor <- o
        11.                 új_csomópont->Státusz <- Nyílt
        12.                 Nyíltak.Add(új_csomópont)
        13.             ENDIF
        14.         ENDIF
        15.     END LOOP
        16.     Csúcs->Státusz <- Zárt
        17.     Zártak.Add(Csúcs)
        18.     Nyíltak.Remove(Csúcs)
        19. END
  3. Vezérlő: A vezérlő feladata ezúttal is az, hogy ellenőrizze előállt-e a célfeltételnek megfelelő állapot amely esetben megvan egy megoldás, valamint egy nyílt csomópont kiválasztása amelyet majd kiterjesztünk. Valamint itt bejön egy nagyon jó tulajdonsága ezen keresőknek. Ha elfogytak a nyílt csomópontok – ami azt jelenti, hogy bejártuk az egész gráfot ahová vezetett irányított út a startcsúcsból – de nem volt egy darab terminális csúcs sem, akkor nem létezik megoldása a problémának az adott reprezentációban. Bizony az algoritmus fölismeri, hogy van-e megoldás avagy sem. Ha van megoldás akkor véges sok lépés után talál egyet, de ha nincs akkor ezt felismeri azon jelenség bekövetkezésekor, hogy elfogynak a nyílt csomópontok. Az azonban, hogy milyen gráfban talál rá egy megoldásra nagyban függ az alkalmazott keresési stratégiától azaz attól, hogy mi alapján választja ki a kiterjesztendő csúcsot.

No és akkor lássunk egy általános sémát a keresőfával kereső algoritmusra is ha már korábban is adtam. A dolog ismételten rendkívül egyszerű mert a séma ugyanaz maradt mint eddig volt.

  1. Procedure Keresőfával_Kereső(<A, kezdo, c, O>)
  2.     Terminálisok <- Inicializál(c)
  3.     Csomópont->Állapot <- kezdő
  4.     Csomópont->Szülő <- NULL
  5.     Csomópont->Operátor <- NULL
  6.     Csomópont->Státusz <- Nyílt
  7.     Nyíltak.Add(Csomópont)
  8.     Zártak <- NULL
  9.     WHILE(TRUE) DO
  10.         IF Nyíltak IS NULL THEN
  11.             STOP
  12.         ENDIF
  13.         Csomópont <- SELECT * FROM Nyíltak
  14.         IF Csomópont IS IN Terminálisok THEN
  15.             STOP
  16.         ENDIF
  17.         Kiterjeszt(<A, kezdo, c, O>, Csomópont, Nyíltak, Zártak)
  18.     END DO
  19.     IF Nyíltak IS NOT NULL THEN
  20.         Kiír(Csomópont)
  21.     ELSE
  22.         Kiír("Nincs megoldás")
  23.     ENDIF
  24. END

Ennyi lenne a keresőfával megoldást keresők általános sémája. A következőkben tárgyalt algoritmusok mivel mindegyike ugyanerre a sémára épül, csak azt fogom elmondani ami másként van és kihagyom a szokásos Adatbázis/Műveletek/Vezérlő tárgyalását mert az mindegyiknél ugyanaz lesz.

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!

Van egy olyan spéci algoritmus-család amelyben minden algoritmust le lehet bontani három nagyon jól elkülöníthatő részre:
    • Adatbázis: Az adatbázis tárolja az állapottér-gráfnak a keresés során már előállított részét. Ezt áldalában csomópontokkal tartja nyilván de, hogy mit tárol egyy adott csomópont azt az adott algoritmus dönti el.
    • Műveletek: Ez trükkös mert két részből tevődik össze.
      • Operátorokból származtatott műveletek: Ez ismét visszaköszön mert mik is ezek?Hát az operátorok amiket bevezettünk a gráfban is. Ugye nekünk csak a gráf egyetlen csúcsa adott a startcsúcs, és a kereséssel építjük fel az adott operátorok segítségével. Miért is működik ez? Egy operátort egy állapotra alkalmazva egy másik állapotot kapunk, ami a gráfban úgy jelenik meg, hogy az adott állapotot reprezentálú csúcsból elindul egy nyilacska, valahol megáll; majd a nyíl végén megjelenik egy másik állapotot reprezentáló csúcs. Így szépen épül a fa, nade mikor érünk el egy terminális csúcsot?!
      • Technikai műveletek: Olykor-olykor nem elég nekünk, hogy van 288 alkalmazási előfeltétel és adott 324 kényszerfeltétel mert a keresés piszkosul lassú szépen lassan komótosan építgeti a gráfot de mindíg belefut egy körbe vagy zsákutcába aztán ott behal. A technikai műveleteket pont arra találták ki valamikor a ’60-as ’70-es években, hogy ne dögöljön már ki a keresés hanem akkor csináljon valamit és menjen tovább. Ilyen lehetne például a kezd előrről a keresést igaz nem sok értelme lenne.
    • Vezérlő: A vezérlő az a része az algoritmusnak ami figyeli, hogy az adatbázisban megjelent-e már a célfeltételeknek eleget tévő állapotok valamelyikét reprezentáló csúcsok valamelyike. Ha igen akkor leállítja a keresést mert lett egy megoldásunk, ha pedig nem akkor eldönti, hogy mely produkciós szabály legyen alkalmazva a gráf mely részére. Apropó produkciós szabály semmi extra dologra nem kell itt gondolni, a produkciós szabályok halmazát az összes művelet alkotja.

Azokat az algoritmusokat amelyek teljesítik ezt keresőrendszereknek nevezzük. A kereső rendszereket számos módon lehet osztályozgatni mint például:

  1. A keresés iránya szerint:
    • Előrehaladó: Ez azt jelenti, hogy a startcsúcsból indulva keres az algoritmus egészen addig amíg nem talál egy terminális csúcsot, vagy esetleg rájön, hogy nincs megoldás.
    • Visszafelé haladó: Ez nagyon szellemesen pont azt jelenti, hogy kap egy terminális csúcsot, és abból próbálja meg majd rekonstruálni azt az irányított utat amelyen a startcsúcsból eljuthatuunk a kapott terminális csúcsig. Igen erre nagyon jól tippeltetetk elég körülményes implementálni és amennyire én udom elég kevés helyen akalmazzák, nem úgy mint a harmadikat amin meglepődtem.
    • Kétirányú kereső: Ez elindul a startcsúcsból és egy terminális csúcsból is aztán majd találkozik egyszer valamikor.
  2. Módosíthatóság szerint:
    • Nem módosítható kereső: Akkor beszélünk nem módosítható keresőről, amikor egy operátor hatását nem tudjuk visszavonni. Vagyis egy csúcsból választunk egy élt és továbbmegyünk az élen a következő csúcshoz, de gőzünk nincs utánna arról, hogy honnan is kerültünk ide.
    • Módosítható kereső: Nagyon szellemesen pont az előző ellentettje ha lehet nem fejteném ki.
  3. Speciális ismeret áll-e a kereső rendelkezésére a keresés során: Itt nem árt először tisztázni, hogy mit is értünk speciális ismeret alatt. Nos az egész ott kezdődik, hogy a Vezérlő is lebontható két részre aszerint, hogy milyen vezérlési stratégiákat alkalmaz. Így megkülönböztetünk elsődleges vezérlési stratégiákat, amelyek lényegében adottak az állapottér-reprezentációból (minden perátor cakk-um-pakk); illetve a másik csoport a másodlagos vezérlési stratágiákat tartalmazza. Na most mik is tartoznak ide amiket nem írtunk bele az állapottér-reprezentációba? Nem-nem bizony, hogy nem felejtettük el! Ide olyan spéci ismeretek tartoznak amik problémaspecifikusak, azaz csak az adott problémára vonatkozva egyszerűsíthetik a keresést.
    • Szisztematikus: Ezt nem igazán szeretném ragozni szisztematikusan mindenki tud keresni, csak nem biztos, hogy talál. Hacsak nem tud valami spéci módszert amivel garantáltan találni fog megoldást. Igen igazad van bizony, hogy létezik ilyen módszer nem is egy!
    • Heurisztikus: Mi is az a heurisztika? Ha heurisztika, az egy olyan tipikusan másodlagos vezérlési stratégia amelyet pont azért építünk be, hogy:
      • Jobb "minőségű" megoldást kapjunk.
      • Gyorsabban találjunk megoldást

DE van a heurisztikának egy jó nagy hátránya is. Nem, hogy azt nem garantálja amit elvárnánk tőle, de még azt sem garantálja, hogy egyáltalán megoldást találunk. Ráadásul még bonyolítja az algoritmusunkat is (növeli a futiási idejét). Hát ez van ezt kell szeretni.

Aztán mint gondolni való volt, akárcsak minden algoritmust, úgy a keresőrendszereket is lehet osztályozni az alábbi szempontok alapján:

  1. Teljesség: Bármilyen esetben amikor egy adott problmának létezik megoldása, akkor az algoritmus azt meg is fogja találni.
  2. Optimalitás: Jobban szorítja az algoritmust általában ez az ún. Bottleneck, ugyanis itt nem elég az, hogy talál egy megoldást de ha egy adott problémának több megoldása is létezik akkor ő a legjobbat találja meg. Hogy miként értelmezett a legjobb azt, most hanyagoljuk, maradjunk annyiban, hogy a legrövidebb irányított út lesz a legjobb. De vannak más szempontok is amire nem szeretnék kitérni mert nem írtam bele az állapottér reprezentációba.
  3. Időigény: Nagyon szellemes értelmezés következik, az az idő ami alatt az algoritmus vagy sikeresen vagy sikerertelenül de befejezi a keresést. Magyarul tökmindegy, hogy talál e megoldást avagy sem csak áljon le!
  4. Tárigény: Ismét szellemes értelmezés, az a lényege, hogy a keresés során maximum mennyi memóriát zabbantott föl.

És ennyi lenne általánosan a keresőrendszerekről. A továbbiakban minden spéci kereőrendszer ezt a sémát fogja felvenni. Ja igen elfelejtettem megmutatni, hogy miként is fest egy ilyen algoritmus:

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

Ez lenne a lehető legegyszerűbb általános megoldáskereső rendszer formája.Amennyire lehet ragaszkodni fogok később is ehhez a formához főleg azért mert itt nincs lehetőségem logikai formulákat bevésni, ahhoz meg türelmem nincs, hogy mindet megrajzoljam és beillesztgessem a megfelelő helyre. Amint látható ez SQL sintaxist tartalmaz amit kiemeltem kékkel és szerintem ettől jobban magáért kitevő szintaxissal még nem találkoztam. Szinte ordít, hogy mit csinál.

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