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!

Reklámok