Bevezetés a mesterséges intelligencia alapjaiba - 3. rész

 

Az optimális út

 

Ahogy ígértem a mostani részben megnézünk más algoritmusokat is. Olyanokat, amelyek kiküszöbölik a hegymászó módszer hibáját, amely mint láttuk még oly rövidtávon, mint amit a mi állapot terünkön kellet bejárnia is képes volt eltévedni. Először tisztázzunk néhány kérdést arról, hogy mikor fontos megtalálni az optimális utat. Mielőtt kijelentenénk, hogy ez egy igen egyszerű kérdés, gondoljunk bele, hogy az optimális út megtalálása, nem biztos, hogy a leggyorsabb. Lehet, hogy előbb akadna a rendszerünk egy nem optimális megoldásra, mint az optimálisra. Vannak esetek, amikor az optimális út megtalálása kötelező, máskor, pedig a gyors eredmény a fontos. Gondoljuk el, hogy ha a szomszéd faluba akarunk eljutni, akkor rossz néven vennénk, ha az útvonal optimalizáló rendszerünk azt tanácsolná, hogy a London, Párizs, Róma útvonalat válasszuk. Viszont egy pilóta, aki zuhan a repülőjével, valószínűleg nehezményezné, ha a rendszer azt mondaná, hogy a megoldás már megvan, de türelem, mert keresek optimálisabbat. Egyszóval az optimális út megtalálása csak bizonyos rendszerek esetén fontos követelmény. Most pedig végre lássuk, hogy milyen lehetőségek vannak.

 

Heurisztika


Már az előző részben szó esett arról, hogy a hanoi torony probléma megoldása a tiszta hegymászó módszer alkalmazásával négy korong esetén lehetetlen, mert a folyamat körbejárásba torkollik. Ezen, ha valaki megnézi az applett lényegi részét, láthatja, hogy két az algoritmusba épített heurisztikus ismerettel segítettünk Felmerülhet a kérdés, hogy ha a programunk futását itt-ott helyre billentenénk, akkor nem térne le a helyes útról. Ez igaz is ott ahol előre látjuk az állapot teret, annak minden csomópontjával, és a program által bejárt utat, illetve azt, hogy hol kell beavatkoznunk. Viszont az is látható, mind a háromkorongos mind a négykorongos alkalmazásból, hogy a cél az, hogy minél kevesebb konkrét ismeretet, és minél több szabályt alkalmazzunk. Nos tehát a heurisztika alkalmazása minden probléma megoldására nem a helyes megközelítés, hiszen végletes esetben a starttól a célig tartó összes lépést meg kellene adnunk, és az már nem mesterséges intelligencia alkalmazás lenne. A legtöbb feladatban nem is rendelkezünk ilyen konkrét ismeretekkel az adott feladat kapcsán.

 

Visszalépéses keresés


Mint a hegymászó módszernél láttuk, ha egy döntést meghozott a gép. Akkor onnan nem volt visszaút. Szemben ezzel a módszerrel, ha a megtett utat tároljuk. Akár egy tömb elemeként, vagy mérettől függően akár adatbázisban is, akkor egy sikertelen választás után visszamehetünk egy lépéssel és, ha ott sem érünk el eredményt, akkor még eggyel … stb. Természetesen a keresés ezzel a módszerrel feltételezhetően lelassul (a megoldandó feladattól függ, hiszen a visszalépés csak lehetőség, ami nem mindig következik be). Van azonban ennek a módszernek még egy fontos eleme. Meg kell határoznunk, hogy a rendszer mikor lépjen visszafelé. Erre 3 esetben van szükség.

 

  1. ha az adatbázisunkban az egyik elem megismétlődik. Ilyenkor ugyanis körbejárás alakult ki, tehát a rendszer eltévedt.
  2. ha meg tudunk határozni egy lépésszámot, ami alatt biztosan találnunk kell egy célcsúcsot, akkor ezzel a maximális lépésszámmal megakadályozhatjuk, hogy a rendszer hosszabb utat járjon be, mint amit érdemes. Ha ez a maximális lépésszám egybe esik az optimális útban szereplő lépések számával, akkor a rendszer addig keres, míg meg nem találja az optimális utat.
  3. ha egy állapotból nem tudunk tovább lépni, mert nincsenek szomszédos csúcsok, vagy már mindegyiket bejártuk. Ezt nevezzük zsákutcának, amiből ki kell hátrálnia a rendszernek.


A keresés algoritmusa a következő képen néz ki:

a.       Válasszuk ki a kezdő állapotot, és helyezzük el az adatbázis( vagy tömb) első elemeként

b.      While az adatbázis utolsó eleme nem egyenlő a célcsúccsal {

c.         Válasszunk a szabályok szerint az útra alkalmazható műveletek segítségével egy következő állapotot

d.         Helyezzük el ezt az állapotot az adatbázis (tömb) utolsó elemeként

 

4.  } eljárás vége.


Láthatjuk, hogy ez az eljárás sem bonyolult. Viszont ha valaki végignézi a példánkban szereplő állapottéren megtett utat, és a választott utat láthatja, hogy, ha maximális lépésszámnak a hegymászó módszer által kijelölt útvonal lépésszámát adjuk meg a programunk, ugyanúgy eltéved, ha pedig az optimális út lépésszámát, akkor addig keres, amíg megtalálja azt. Ha a kettő közötti értéket adunk meg akkor újra eltéved a keresés közben.

 

Gráfkeresés

 

Megtehetnénk, hogy az adott csúcsra alkalmazható összes műveletet végrehajtjuk, azaz kiterjesztjük az adott állapotot. Ekkor felvesszük az adatbázisba ezeket a gyermekcsúcsokat is, majd választunk egyet valamilyen szabály szerint és azt is kiterjesztjük. Ily módon nyilvántartjuk a teljes gráf egy részgráfját. A keresés addig tart, amíg ebben a nyilvántartott részgráfban meg nem jelenik a célcsúcs. Amennyiben egy meghatározott mélység után sem jelentkezik a célcsúcs akkor a gráfnak azt a részét kidobjuk és helyette egy másikat bontunk ki. Ez az eljárás a legrövidebb azaz az optimális utat találja meg, viszont cserében a legtöbb csúcsot bontja ki. (Ez természetesen erre a feladatra érvényes megállapítás. Elképzelhető olyan feladat is, amelyben a fent említett három módszer erőforrás igénye másképpen alakul. Érdekes szellemi torna lenne ilyen feladatok kreálása.)


Íme a keresés algoritmusa:

1.      Az adatbázisban elhelyezzük a kiindulópontot, azaz a startcsúcsot.

2.      Amíg az adatbázisban meg nem jelenik a célcsúcs ismételgetjük a következőket{

3.      Megállapítjuk, hogy az adott csúcsból mely csúcsokat lehet elérni, és elhelyezzük őket az adatbázisban.

4.      Kiválasztjuk közülük, azt, amelyiket a következő körben ki fogunk terjeszteni.

5.   } ciklus vége

program vége.


Mint már írtam lehet keresni optimális megoldást, lehet igény az, hogy a keresés gyors legyen, lehet igény az is, hogy a szűkös erőforrásokhoz igazodjon az algoritmus. Mint a három példából láttuk Ezek a kívánalmak általában egymásnak ellent mondanak. A következő részben megnézünk néhány olyan algoritmust, amelyik a gyorsaság, és az optimális út meghatározásának minél közelebb hozatalát célozzák meg.


Ezen kívül látni fogunk példákat, amelyek ennek ellenére csak az egyik, vagy csak a másik esetben alkalmazhatóak sikeresen.
Aki hajlandó időt áldozni arra, hogy az eredeti hanoi probléma megoldását (amely a CD-n megtalálható) átalakítsa az ebben a cikkben leírt út és gráf kereső algoritmusokká, azok bizonyára jobban érzékelni tudják az itt leírtak lényegét. Például, ha kiegészítik a programot egy számlálóval, amely megmutatja a kezdő és befejezési időt, akkor láthatják belőle, hogy melyik mennyire terheli le a rendszert. Ebből pedig messzemenő következtetéseket lehet levonni, egy ennél a problémánál sokkal bonyolultabb probléma megoldásához szükséges idő mennyiségére. Ezek a tapasztalatok fontosak lehetnek a későbbiekben egy komolyabb rendszer fejlesztése esetén, ahol igen fontos tényező, hogy a felhasználó szeretne választ kapni a kérdésére, és ha ez záros határidőn bellül nem történik meg, akkor vagy a rendszert fogja használhatatlannak tartani, vagy azt hiszi, hogy a gépe fagyott le. A különböző algoritmusok futási idejének meghatározása, számtalan dolgozat tárgya volt már. Ilyen munkák mind az irodalomban, mind a BME és az ELTE diploma munkái között megtalálhatóak. Sok sikert a böngészésükhöz, és a kódok megírásához.

 

Horváth Richárd - hricsih@icqmail.com