Bevezetés a mesterséges intelligencia alapjaiba – 4. rész

 

A mohók, a precízek, és az öszvérek

Nos itt az ideje, hogy döntsünk rendszerünk alapvető kérdéseiben. Az első ilyen kérdés, hogy mit várunk el a rendszerünktől. Ha optimális utat szeretnénk kapni eredményként, akkor ezért áldozatokat kell hozni. A későbbiek során erre fog példát mutatni a szélességi keresés. Ha gyorsak akarunk lenni, akkor kockáztatnunk kell. Erre jó példa lesz a mélységi keresés stratégiája. Végül pedig látni fogjuk, hogy ismét az arany középút az ami a legjobban alkalmazható. Persze nem tudom eleget hangsúlyozni, hogy mindent a konkrét feladat dönt el! Ezért is alakult ki a sokféle eljárás, az egyszerűektől a genetikus algoritmusokon át a Fuzzy logikai alkalmazásokig.

 

Szélességi keresés

 

A szélességi keresésről tudni kell, hogy mindig optimális eredményt ad (abban az esetben, ha két csúcs közötti élt egységnyinek tekintünk), amennyiben a feladatnak van megoldása, no és persze a számítógépnek elegendő kapacitása, a megoldás megtalálásához! Nos nézzük meg a szélességi keresés elméletét. A lényeg, ha egy állapot teret gráfként ábrázolunk, majd feloldjuk az esetleges hurkokat (amikor egy csúcshalmaz elemeiből kiinduló élek mentén haladva visszajutunk a halmazon belüli kiindulópontunkba), akkor egy fát kapunk. A startcsúcs a fa gyökéreleme, a levelei, pedig a zsákutcák. Persze köztük lehet a célcsúcs is, de előfordulhat olyan eset is, hogy a hurokmentesítés közben a célcsúcsból további élek indulnak ki, más csúcsok felé. Ezt a fát fogjuk feldolgozni, méghozzá a gráfkeresés módszerének speciális esetével. Csak emlékeztetőül, a gráfkeresés során, az adott csúcs, mint szülő csúcs minden gyermek csúcsát meghatároztuk, majd választunk egy csúcsot a gyermekek közül, és megismételjük az előző lépést. Az ötlet az, hogy ne válasszunk a gyermek csúcsok közül egyet sem, hanem bontsuk ki az összest. Így szintről szintre haladva előbb – utóbb megtaláljuk a célt. Ha több is van (hiszen egy feladatnak nem biztos, hogy egy megoldása van) akkor is a start csúcstól a legkevesebb lépésből elérhető megoldást találja meg. Ez a megfogalmazás fontos. Azért fontos, mert, ahogy már említettem a ez csak akkor igaz, ha a csúcsokat összekötő éleket egységnyinek tekintjük. Jó példa az útvonal optimalizálás. El szeretnénk jutni A pontból K pontba, a lehető legrövidebb út megtételével. A csúcsok az egyes állomások. Természetesen a szomszédos csúcsokat (pontokat) összekötjük élekkel. Majd az így nyert állapot teret próbáljuk fa struktúrába szervezni, úgy, hogy kigyomláljuk azokat az éleket, amelyek visszafelé vezetnek. Természetes, hogy az első szintje a fának (a gyökér után [A pont]) az A pontból egy él végig követésével elérhető pontok. A második szint az a pontból két él végigkövetésével, egy pont érintésével elérhető pontok… stb. Na de senki sem garantálhatja, hogy A ponttól B pont ugyan olyan távolságra található, mint C pont, pedig mindkettőt egyetlen közvetlen él köti össze A-val. Ez esetben tehát érdemes az éleket súlyozni. Ez esetben elképzelhető, hogy a szélességi keresés egy olyan megoldást talál, amelynek élsúlya nagyobb, mint ha több kisebb élsúlyú élen haladtunk volna végig. Ezért fontos, hogy a szélességi keresésnél feltételezzük, hogy az állapottéren a csúcsokat összekötő élek súlya egységnyi.

 

Mélységi keresés

 

Felmerül a kérdés, hogy mi történik, ha ezek az élsúlyok eltérőek?

Természetesen alkalmazhatjuk továbbra is a szélességi keresést, csak elveszítjük azt a tulajdonságát, amiért érdemes alkalmazni, nevezetesen, hogy megtalálja az optimális megoldást. Viszont megmarad az egyik legnagyobb hátránya, hogy nagy az erőforrás igénye. Ha viszont el kell veszni az optimalitásnak, akkor ne bánkódjunk, ha elveszítjük a hátrányokat is. Készítsünk olyan algoritmust, amelyik kiválasztja a soron következő gyermekobjektumok közül a legígéretesebbet (az élsúlyok vizsgálata alapján), majd a többivel nem törődve erre mohon lecsapva kiterjeszti ezt a csúcsot, és a kiterjesztés során elért csúcsok közül szintén kiválasztja a legígéretesebbet. Jól látszik azonban, hogy ez a megoldás nagyon mellé tud fogni, a keresés során. Elképzelhető, hogy simán elmegy a megoldás mellet, és esetleg nem is talál meg egyet sem, nem, hogy az optimálist. Természetesen ennek kivédésére alkalmas heurisztika beépítésével (ha rendelkezünk a feladatra jellemző megfelelő ismerettel) elkerülhetjük ezt az esetet. Ha pedig pontosan tudjuk, hogy hány lépésre van a célcsúcs, akkor az algoritmus rákényszeríthető az optimális megoldás megtalálására. Ezzel azonban, leszámítva a nagyon szerencsés eseteket, megnöveljük az erőforrás igényt. Ha tudunk egy olyan határt szabni, amin túl már biztosan nem találhatjuk meg a megoldást, akkor van értelme kombinálni a mélységi keresést és a visszalépéses algoritmust, hiszen az eltévedt keresést visszavezethetjük, és biztosan rálelhetünk előbb, vagy utóbb egy megoldásra.

 

Iteratív mélységi keresés

 

Mit tegyünk, ha nem áll rendelkezésünkre semmilyen adat a célcsúcs hollétéről? Tételezzük fel, hogy a megoldás megtalálása olyan nagy háttértár kapacitást igényel, ami nem áll rendelkezésünkre. Ráadásul időnk sem lenne egy esetlegesen hosszan elnyúló szélességi keresés végrehajtására, és a feladat jellegéből adódóan elveszítjük az optimalitását is egy ilyen típusú keresésnek. Viszont nem engedhetjük meg magunknak azt a blamát, hogy nem találunk megoldást. Tehát nem kockáztathatjuk meg azt sem, hogy a mélységi keresés elrobog a megoldás mellett, és mivel nem tudjuk előre, hány lépés után mondhatjuk ki, hogy eltévedt, ezért rengetegszer bejárjuk az állapot teret, addig amíg az összes zsákutcát (levélobjektumot) fel nem derítjük, és esetleg a keresés végén ki nem derül, hogy a megoldás egyetlen, (élsúly alapján) előre semmi jóval nem kecsegtető lépés bizonyult a nyerőnek. Ebben az esetben érdemes megpróbálkozni egy öszvér megoldással. AZ előbb említett eljárások előnyeit ötvözve, kialakítani egy eljárást.

Ez az eljárás a következő módon működik:

1., Beállítja a mélységi korlátot egynek.

A startcsúcsból a legígéretesebb irányba lép, ha nem célcsúcs, akkor a startcsúcsból a második legígéretesebb irányba lép, …stb. Ezt azért teszi, mert a mélységi korlát megakadályozza, hogy tovább menjen a fán lefelé. Kénytelen visszalépni, és új irányba elmozdulni.

2., Amennyiben nincs több lehetőség az adott szinten és a célcsúcsot nem találtuk meg, akkor a mélységi korlátot eggyel megnöveljük, és a startcsúcsból indulva kiterjesztjük a legígéretesebb csúcsot. Mivel már ez nem célcsúcs, és a mélységi korlát engedi a továbblépést, ezért innen továbblép az algoritmus a legígéretesebb irányba. Ha ez sem célcsúcs, és mivel elértük a mélységi korlátot, visszalépünk, és egy másik irányt választunk. Ha végignéztük az összes elérhető csúcsot, és nem volt célcsúcs, akkor visszalépünk a célcsúcsra, és új irányt választunk.

Tehát a mélységi korlátot növelve a keresést ciklikusan ismételgetjük. Ezzel elérjük, hogy a fa adott szintjét teljesen kiterjesztjük. Mivel az algoritmus alapvetően mindig a legígéretesebb irányba kezdi el a keresést, és ott a mélységi korlát által engedett mélységig keres, megvan az esély, hogy ott meg is találja a megoldást. Ha nem, akkor visszalépünk, és kezdjük, előröl. Az algoritmus biztosan megtalálja az optimális megoldást, ha létezik a problémának megoldása. Természetesen a keresési idő megnövekszik, mivel egy csúcsot sokszor kiterjesztünk. Az útvonal tárolásához szükséges kapacitás kisebb, mint a szélességi keresésé, és megegyezik a mélységi keresésével.

 

A most megismert három keresési eljárás mindegyike a gráfkeresési eljárásból indul ki, azt más, más módon valósítja meg. A mélységi keresési eljárás a későbbi mohó keresési eljárások alapjául szolgál. Azért nevezik ezeket az eljárásokat mohónak, mert rögtön a legígéretesebb irányba mozdulnak, és közben előfordulhat, hogy nem az a legjobb. A szélességi keresésnél láttuk, hogy precízen, minden csúcsot kiterjesztettünk, ez természetesen (egységnyi élsúly esetén) az optimális megoldást eredményezi, azonban nagyon nagy az erőforrás igénye, ami egy nagyobb állapottér esetén végzetes lehet. Végül ötvöztük a két megoldást és megszületett az iteratív mélységi keresés. Ez az öszvérmegoldás, minden szempontból jobb, mint az elődei. Azt azonban itt is el kell mondani, hogy a feladat határozza meg, hogy melyik keresési eljárást érdemes alkalmazni.

 

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