FIGYELEM!
Szeretsz programozni? Szereted a kihívásokat? Szeretnél pénzt is keresni?
Az új CodeX ForeX minderre ITT lehetoséget ad!




Bevezetés a mesterséges inteligencia alapjaiba

Bevezetés a mesterséges intelligenciába - 2. rész

Az előző részben röviden áttekintettünk a mesterséges intelligenciával kapcsolatos néhány ismeretet (sajnos igen felületesen, mert egyébként szakkönyvek tucatjait tölti meg a téma). Most néhány régebbi, de alap algoritmust ismerünk meg. Ehhez azonban először meg kell ismernünk néhány alapfogalmat. Tudnunk kell azt, hogy mikor mire használjuk őket, mert ezek a fogalmak végigkísérnek minket a befejezésig. Az alap algoritmusokra pedig azért van szükségünk, hogy gyorsabban lehessen megérteni, miről is van szó. Az algoritmusokat nem kódoljuk és nem magyarázom el részletesen, feltételezve, hogy aki programozott már, az kisebb nagyobb ráfordítással értelmezni tudja azokat. Ha nem ezt tennénk talán sohasem érnénk a sorozat végére. Aki azonban szeretne részletesebb leírást olvasni, annak ajánlom a Futó Iván szerkesztésében megjelent Mesterséges intelligencia (Aula kiadó 1999) c. munkát. Ennek okán mi is a kezdetekben a Hanoi tornyai probléma megoldásával foglalkozunk.

Tehát az alapfogalmak:

Reprezentációs modell:  Az a mód ahogyan a feladattal kapcsolatos ismereteket ábrázoljuk. Ez igen sokféle lehet, a lényeg az, hogy a lehető leghatékonyabban tegyük.

Kereső rendszer: Olyan alap algoritmus, ami a reprezentációs modellben keresi egy irányított gráf egyik csúcsából a másik csúcsába vezető utat.

A keresés stratégiája: Ez a stratégia alapvetően meghatározza, hogy milyen módon találjuk meg az utat. Később látni fogjuk, hogy vannak stratégiák, amelyek jobbak, mások gyorsabbak ... stb. Hogy melyiket válasszuk, az a megoldandó feladattól és az igényektől függ. Példaként említhetnénk az útvonal tervezés problémáját. Itt nem az a fontos, hogy másodpercek alatt döntés szülessen egy kamion útvonaláról, hanem, hogy optimális eredmény szülessen.

Egy kereső rendszert a reprezentációs modell és a keresés stratégiája határozza meg alapvetően. De vannak a hatékonyságot befolyásoló más tényezők is. Ilyen például a heurisztika. A heurisztika, más néven vezérlési ismeretek, arra szolgálnak, hogy olyan feladatspecifikus ismereteket tudjunk a stratégiánkba beépíteni, amivel optimalizálhatjuk az eredményt, vagy mint a cd-n látható, a hanoi tornyai demó első verziója egy három karika három rúd elrendezés. Itt nem igényelte az alkalmazott stratégia (amit később részletezni fogok) heurisztikus ismeret beépítését az algoritmusba. Ezzel ellentétben a feladat olyan verziója, amiben négy korong van, már olyan megnövekedett állapotteret eredményez, amelyben körbenjárás alakulhat ki. Ez - mint fejlesztéskor tapasztaltam - ki is alakult (ezt a verziót applet formájában lehet megtalálni a cd-n).

Az előbb említettem még egy fontos alapkifejezést. Ez az állapottér. Ha egy problémát ábrázolni akarunk, akkor arra a legjobb módszer, hogy egy gráfban felvesszük az adott probléma során létrejövő összes állapotot. Majd ebben a gráfban keressük meg azt az útvonalat, amely a start csúcsból a cél csúcsba megy. Tehát az állapottér nem más mint a probléma kapcsán felmerülő összes lehetséges állapot együttese. Természetesen komolyabb feladatok esetén ez az állapottér nem reprezentálható. Gráfban biztosan nem. Ha csak a sakkra gondolunk, akkor egy játszma lehetséges állásai megfelelnek a gráf egyes csomópontjainak. Az egyik csomópontból a másikba vezető út az adott lépés, a start csúcs ismert, hiszen az a játék kiinduló állapota, de a célcsúcsok egy halmazt alkotnak, hiszen a játék számtalan módon befejeződhet. Tehát ha elképzeljük a sakk állapotterét, láthatjuk, hogy az egy végtelen tér, amiben egy végtelen gráfot tudunk létrehozni.

Az állapottér reprezentáció az a mód, ahogyan az állapottér elemeit, az állapotokat bemutatjuk, felvesszük.

Még természetesen menet közben rengeteg fogalmat kell majd tisztáznunk, de ahhoz, hogy a legegyszerűbb algoritmusokat megértsük, ennyi elegendő. A többi fogalmat felmerülésük helyén fogjuk tisztázni.

Alap algoritmusok

Ahhoz, hogy egy algoritmust bemutassunk, szükséges, hogy a feladatot ábrázolni tudjuk. Most a hanoi tornyai probléma egy lehetséges ábrázolásával tesszük meg ezt. Tisztázni kell, hogy bármilyen ábrázolása a feladatnak eredményes lehet. Ezért ha valaki más módon közelíti meg az ábrázolás kérdését az se követ el hibát.

A feladat:

Adott három rúd és a harmadikon elhelyezkedõ korongok csökkenõ átmérõvel. A feladat a korongokat az első rúdra áthelyezni úgy, hogy egyszerre csak egy korongot lehet elmozdítani és kisebb korongra nem szabad nagyobbat tenni.

A reprezentáció:

A rudakat egytől háromig sorszámozzuk. Kezdetben a korongok a harmadik rúdon helyezkednek el. A korongokat A, B, C betűkkel jelöljük. Az állapotokat úgy írjuk le, hogy meghatározzuk, melyik korong melyik rúdon helyezkedik el. Ezt legegyszerűbben egy rendezett számhármassal (vektor) tudjuk megadni. Tehát az állapot = (A,B,C) számhármas, ahol A,B,C a rúd száma, amelyiken a korong elhelyezkedik. A start csúcs ebből következően a (3,3,3) vektorral írható le a legkönnyebben. A cél is meg van határozva a feladatban, hiszen a feladat kimondja, hogy az első rúdra kell áthelyezni. Tehát a célcsúcsot az (1,1,1) vektor jellemzi.

Az állapottér minden csomópontja azt jelképezi, hogy egy korongot áthelyezünk. A szabályok ismeretében a startcsúcsból két áthelyezés lehetséges. A legkisebb korongot az egyes számú rúdra, vagy a legkisebb korongot a kettes számú rúdra helyezhetjük. Ezután ezeket a csomópontokat kibontva továbbiakat kapunk. Az állapotteret az 1. ábrán láthatjuk teljesen kifejtve, azonban meg kell jegyezni, hogy egy végtelen állapotteret elegendő csak a célcsúcs megjelenéséig kibontani. Így sem biztos, hogy az itt látható módon ábrázolható. Majd látjuk az algoritmusoknál, hogy a számítógép memóriájában különböző algoritmusokkal különböző módon jelenítjük meg az állapotteret, de sosem a teljeset, mindig csak azt a részét, amelyiket kibontjuk.


A hill climbing (hegymászó) módszer:

Ahhoz, hogy a számítógép értelmezni tudja, hogy melyik csomópontban áll és hogy merre léphet tovább, valamilyen módon azonosítani kell számára a csomópontot. Erre a legcélszerűbbnek az látszik, hogy a vektor elemeit össze adjuk (összeg függvény), és azt a következő lépést választjuk, amelyik a szabályok értelmében a pillanatnyi állapotból következik és legkisebb az összegfüggvény értéke. Azért célszerű ezt választani, mert amint megjelenik az (1,1,1) állapot az algoritmus végpontot ér el. Ennél kisebb összérték nem lehetséges.


Az algoritmus:

1. Pill_állapot = (3,3,3) „kezdő állapot”
2. While (Pill_állapot != (1,1,1){
3. Szabályok alapján következő lehetséges csomópontok meghatározása
4. Pill_Állapot = min_sum(lehetséges állapotok)
}

END

Látható, hogy a szabályokat addig alkalmazzuk a pillanatnyi állapotra, amíg minden elérhető csomópontot meg nem határoztunk, majd kiválasszuk közülük a legkisebb összegfüggvény értékűt, és a pillanatnyi állapotot felülírjuk ezzel az új csomóponttal. Addig ismételgetjük a műveletsort, amíg a célállapotot el nem érjük.

Ez a módszer igen egyszerű, de sajnos nem mindig ér el végpontot. Vannak olyan esetek, amelyekben nem találja meg a megoldást. Heurisztika hiányában például egy negyedik korong rendszerbe helyezésekor körbenjár, azaz három csomópont által meghatározott körből sosem talál ki. Fontos hibája, hogy nem az optimális utat találja meg (optimális út: az a megoldás, amelyik a legrövidebb (legkisebb költségű - ez később fontos lesz) útvonal a start és a cél között) Ha valaki az algoritmus alapján végigköveti a bejárt utat, maga is könnyedén meggyőződhet arról, hogy egy ponton a rendszer eltéved és felesleges csomópontokat érint. A szabályok között szerepel, hogy egy csomópontból nem léphetünk vissza a szülő objektumba, azaz a megelőző csomópontba. Így kizárjuk a két pont közötti ingázást.

Mint említettem, a CD-n megtalálható egy JAVA program, amelyik megoldja a fent nevezett módszerrel a hanoi tornyai problémát. Érdemes tanulmányozni a forráskódot. A cél nem az elegáns megoldás, hanem a módszer bemutatása volt, ezért könnyen értelmezhető. Az appletes megoldásban fellelhető az a heurisztika, melynek segítségével a négy korongos eset is megoldható.

Legközelebb megnézünk néhány olyan algoritmust, amelyik optimális megoldást eredményez.

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