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