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