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.
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.