Informatika | Mesterséges intelligencia » Mi a MI? - Mesterséges Intelligencia Könyv

Mi a MI? Avagy a mesterséges intelligencia témaköre, célkitûzései A mesterséges intelligencia (MI) a számítástudománynak az a része, amely intelligens rendszerek kifejlesztésével foglalkozik. Az MI pontos fogalmán, definiálhatóságán vitáznak a mesterséges intelligenciával foglalkozó szakemberek. A legtöbbjük más-mást ért rajta Általában a mesterséges intelligencia olyan feladatok számítógépes megoldását tûzi ki célul, amelyek - ha ember oldja meg õket, intelligenciát igényelnek. Olyan feladatok tartoznak ide, amelyek általában nem rendelkeznek fix megoldó mechanizmussal, hanem szerepet kap a próbálkozás és az azt irányító emberi szakértelem és intuíció. Ilyen problémák például a sakkozás, matematikai tételek bebizonyítása, fordítás egyik nyelvrõl a másikra, alakzatok és emberi beszéd felismerése, orvosi diagnózis kidolgozása, stb. Az MI fontosabb részterületei A mesterséges intelligencia két legalapvetõbb

témaköre a tudás-ábrázolás (tudásreprezentáció) és a keresés. Az elsõ témakör avval foglalkozik, hogy mi módon lehet egy adott tárgykörrõl szerzett ismereteket ábrázolni olyan szerkezetben, amely a tárgykörben felmerülõ feladatok számítógépes megoldását megkönnyíti. A keresés olyan problémamegoldó technika, amely szisztematikusan felderíti a probléma állapotainak terét, vagyis a probléma megoldása során adódó egymást követõ vagy alternatív lehetõséget nyújtó állomásokat. A feladat állapottere különbözõ játékállásokat tartalmazhat, ha valamely játékról van szó, vagy különbözõ következtetési lépéseket, ha egy következtetési eljárást vizsgálunk. Ebben a térben keressük a feladat végsõ megoldását Newell és Simon szerint lényegében ilyen az emberi problémamegoldás is. Valóban, amikor egy sakkozó végiggondolja a különbözõ lépések lehetséges hatását vagy egy orvos választ az alternatív

diagnózisok közül, akkor a szóba jöhetõ lehetõségek között keresnek. Ahogy más tudományterületeknek is, a mesterséges intelligenciának is különbözõ részterületei vannak. A következõkben ezekrõl adunk rövid áttekintést 1. Játékelmélet A korai MI kutatások nagy része a táblás játékokra (sakk, kirakós játék (“puzzle”), tic-tac-toe (amõba), stb.) irányult Amellett, hogy ezek intellektuális játékok, azért is váltak a kutatások fõ célpontjává, mert ezeket a játékokat jól definiált szabályok jellemzik, amelyek alapján könnyen fel lehet építeni a keresési teret. A különbözõ táblás játékok állásait könnyû számítógéppel ábrázolni, nem kellenek hozzá összetett formalizmusok. Az elkészült programok egyszerûen tesztelhetõek, így megvalósításuk nem jelent különösebb anyagi megterhelést. A játékokhoz sokszor hatalmas keresési tér tartozik. Ezért érdemes olyan technikák után kutatni, amelyek

hatékonyan tudnak keresni ebben a térben. Ezek az úgynevezett heurisztikus keresések. A heurisztika egy jó, vagy jónak tûnõ ötlet, amely segítségével a keresési térnek csak egy ígéretesnek tûnõ részét járjuk be, csökkentve evvel a keresések számát, vagyis növelve a keresés hatékonyságát. Az emberi problémamegoldás során is az intelligensnek tartott megoldások jó ötleteket, heurisztikákat tartalmaznak. Természetesen a heurisztika csak akkor növeli a hatékonyságot, ha valóban “jó ötlet” és segítségével valóban az ígéretes utakat járjuk be. Ahhoz, hogy ilyen ragyogó ötletek eszükbe jussanak, általában szükségünk van az adott tárgyterületen szerzett tapasztalatokra. Mivel a játékok terén a legtöbb ember rendelkezik valamicske tapasztalattal és a heurisztikák kialakítása nem igényel különleges szaktudást, ez a tény ismét választ ad arra, hogy miért is ezen a területen indult el elõször a heurisztikus

keresési stratégiák kutatása. 2. Automatikus következtetés és tételbizonyítás A mesterséges intelligencia másik legrégibb ága az automatikus tételbizonyítás. Alapötlete visszanyúlik egészen Russell és Whitehead század eleji munkásságáig, akik az egész matematikát úgy tekintették, mint tételek alapaxiómákból való formális levezetését. Az automatikus tételbizonyítások zöme a logika szigorán és általánosságán alapszik. Formalitásából eredõen a logika “kínálja” az automatizálást. Problémák széles köre oldható meg úgy, hogy a problémaleírást és a lényeges háttérinformációkat logikai axiómáknak tekintjük, a megoldandó feladatot pedig bizonyítandó tételnek. Sajnos, a komplikált problémákat következetesen megoldó rendszer megalkotására vonatkozó kísérletek nem érték el céljukat, mivel egy még ésszerûen komplex logikai rendszer is képes volt végtelen sok bizonyítandó tételt generálni. Mivel

nem voltak hatékony heurisztikus keresõ eljárások, ezért a tételbizonyító rengeteg fölösleges tételt bizonyított be, mielõtt végül belebotlott a ténylegesen bizonyítandó állításba. Ezek a tapasztalatok arra utaltak, hogy gyakorlatilag lehetetlen ilyen hatalmas teret pusztán formális, szintaktikus módszerekkel kezelni, és az egyetlen kivezetõ út, megtalálni azokat az informális, ad hoc stratégiákat, amelyeket úgy tûnik, az ember is használ a problémamegoldás során. Ezek az elképzelések vezettek a szakértõi rendszerek fejlesztéséhez. A fentiek ellenére a formális matematikai logikán alapuló következtetések elég erõsek ahhoz, hogy csak úgy egyszerûen mellõzhetnénk õket. Sok probléma - pl logikai áramkörök tervezése és tesztelése, számítógépes programok helyességének bizonyítása, komplex rendszerek ellenõrzése - kezelhetõ ilyen módon. Tovább menve, ma már a tételbizonyító eljárások rendelkeznek hatásos

heurisztikákkal, melyek gyorsítják az eljárást. Bõvebben pl. [FGN], [LS] 3. Szakértõi rendszerek A problémamegoldó módszerek kutatása hamar elvezetett annak felismerésére, mennyire fontos, hogy milyen területrõl származik a megoldandó probléma. Nem általános problémamegoldó módszerekre, hanem egy-egy konkrét szakterületre vonatkozó tudás, ismeret feldolgozására van szükség. Az emberi szakértõ is a saját szakterületén tud biztonságosan dolgozni. Egy orvos, vagy geológus nemcsak az adott szakterületre vonatkozó elméleti és gyakorlati tudással rendelkezik, hanem sok, a tapasztalatain alapuló intuícióval is. A szakértõi tudás a probléma elméleti feldolgozásának és heurisztikus problémamegoldó szabályok gyûjteményének kombinációja. A szakértõi rendszereket arra készítették, hogy az emberi szakértõtõl összegyûjtsék ezt a tudást, és olyan formában kódolják, hogy egy számítógép alkalmazni tudja hasonló

feladatok megoldására. A legelsõ - és a szakirodalomban legtöbbet tárgyalt - szakértõi rendszerek (DENDRAL, MYCIN) óta számtalan, a gyakorlatban is jól használható szakértõi rendszer született. 4. Beszédértelmezõ és fordítóprogramok A mesterséges intelligencia egyik hosszú távú célja olyan program készítése, amely megérti a természetes emberi nyelvet. Ugyancsak régi törekvés, hogy egyik nyelvrõl a másikra fordító programot készítsenek. Ezen feladatok esetén komoly problémát jelent a nyelv megértése - egyrészt a nyelv jelentésének megértése, másrészt, ha beszédfelismerõ rendszerekrõl van szó az, hogyan lehet a kiejtés alapján megérteni. A nyelv jelentésének felismeréséhez fontosak a nyelvi elemzõk - a grammatikai szabályok, mondatstruktúrák felismerése, alkalmazása. A nyelv grammatikája (nyelvtana) olyan szabályok együttese, amely megmutatja, hogy milyen mondatok megengedettek a nyelvben. Megadja azokat a

szintaktikai szabályokat, amelyek segítségével felépíthetõek az egyes állítások. Ezek kutatására alakította ki Chomsky a formális nyelvek elméletét A nyelvi elemzés, beszédfelépítés szempontjából nem egyforma nehézségûek az egyes nyelvek. Ilyen szempontból az angol az egyik legegyszerûbb nyelv (A magyar a “nehezek” közé tartozik.) Angol nyelven több “beszélgetõ” program is született. Leghíresebbek a DOCTOR és az ELIZA (Weizenbaum, 1966). Egy természetes nyelv megértése azonban nemcsak abból áll, hogy megnézzük a mondatokat alkotó szavakat a szótárban, illetve elemezzük a mondatstruktúrákat. Az igazi megértés függ attól a tudás-háttértõl, amellyel az adott témakörrel kapcsolatban rendelkezünk. Egy olyan ember például, aki jól tud angolul, de fogalma sincs pl. a baseball szabályairól, játékosairól, stb., lehet, hogy szavanként megért egy baseball-lal kapcsolatos mondatot, de valószínûleg nem érti meg a

mondat tényleges jelentését. Emiatt fontos kutatási témává vált az is, miképp lehet ezt a háttértudást hatékonyan ábrázolni. Ez vezetett a tudásreprezentációk vizsgálatához. Mivel egy szöveg megértéséhez szükséges ez a háttérismeret, több olyan program is készült, amelyekkel nem “általánosságban” lehet társalogni, hanem konkrét témában lehet neki kérdéseket feltenni vagy utasításokat adni. Az elsõre példa William Wood LUNAR nevû programja (1970-es évek eleje), amely a Holdról hozott kõzetminták vizsgálatában vett részt, evvel kapcsolatosan lehetett kérdéseket feltenni neki. A kérdések megértéséhez, illetve válaszai megadásához felhasználta az Amerika Nemzeti Repülési és Ûrkutatási Hivatal adatbázisát. Szintén a 70-es évek elején készült Terry Winograd SHRLDU nevû rendszere, amely olyan robotot szimulált, amely szóbeli utasítások alapján egy asztalon lévõ tárgyakkal végzett mûveleteket. Szûk

szókinccsel, egyértelmû szabályokkal felépítve tudtak tehát beszédfelismerõ-, illetve fordítóprogramokat csinálni, a teljesen általános beszédfelismerõ létrehozása azonban komoly nehézségekbe ütközik - hogy csak egy nehézséget említsek, meg kell tudni oldani pl. a többértelmûség kezelését. A beszédfelismerõ rendszereknek a nyelvi elemzésen kívül a kiejtés megértése is komoly problémát okoz. A szavakat megértõ rendszer megalkotása valamivel egyszerûbb, mint a folyamatos beszédfelismerõ, hiszen a szavak kiejtése változhat attól függõen, hogy milyen szövegkörnyezetben használják õket. A szavak felismerése leegyszerûsítve úgy történik, hogy bizonyos szavak akusztikai mintáiból létrehoznak egy szótárat, majd ennek a szótárnak a szavaival hasonlítja össze a rendszer a felismerendõ szavakat. Mivel a kiejtés egyénenként változhat, ezért egyszerûbb egy konkrét személy beszédét felismerõ rendszert készíteni. Az

egyéni beszédhangok felismerésére tréningként beolvastatják az illetõ személlyel az alapszótárt. Bõvebben pl. [LS] 5. Látásmodellezés A beszédfelismeréshez hasonlóan a képek felismerése is komoly kihívást jelent a számítógépes szakemberek számára. Olyan rendszereket próbálnak létrehozni, amelyek képesek egyes objektumok felismerésére, különbséget tudnak tenni kis eltéréssel rendelkezõ képek között. A kutatás már a 40-es években elkezdõdött, ebbõl fejlõdött ki a mintaillesztés, illetve az alakfelismerés elmélete. Bõvebben pl [W] 6. Robotika Komoly kutatások folynak olyan programok létrehozására, amelyek robotokat mûködtetnek. Külön vizsgálatokat végeznek arra vonatkozóan, hogyan lehet egy adott feladatban optimálisan mûködtetni (mozgatni) egy robotkart, illetve hogyan kell megtervezni a cél elérése érdekében végrehajtandó cselekvések sorozatát. A tervezés egyik emberi módszere a probléma-redukció, vagyis

a problémák részproblémákra bontása. Ezt a gondolkozásmódot azonban nem könnyû számítógépre vinni Ahhoz, hogy a feladatot egymástól független részproblémákra bonthassuk, sokszor heurisztikákat alkalmazunk, illetve felhasználjuk az adott területre vonatkozó tudásunkat. Ennek számítógépes megvalósítása nem egyszerû feladat. Napjainkban egyre több helyen használják fel a robotika eredményeit. Elsõsorban az iparban alkalmazzák a robotokat. A legtöbb robot “vak”, de vannak olyanok is, amelyeket kamerával szerelnek fel (azaz “látó” robotok), így a képi információkat is tudja továbbítani egy számítógépnek. A leglátványosabb alkalmazások közé tartoznak az ûrkutatás-beli alkalmazások, mint pl. a legfrissebbek egyike, a Mars-járó. Bõvebben pl. [LS], [Sch], [W] 7. Mesterséges intelligencia nyelvek A mesterséges intelligencia kutatások egyik legfontosabb “mellékterméke” a programozási nyelvek fejlesztése. A

mesterséges intelligenciát alkalmazó programok mérete, az a tendencia, hogy a keresõ algoritmusoknak hatalmas keresési tereket kell felderítenie, az az elvárás, hogy heurisztikákat lehessen beépíteni a programokba, mind-mind arra ösztönözte, az MI kutatókat, hogy hatékony programozási metódusokat fejlesszenek ki. Ezek a fejlesztések vezettek az MI nyelvek kialakításához, melyek közül a legismertebbek a LISP és a PROLOG. 8. Gépi tanulás Az emberi intelligencia egyik leglényegesebb jellemzõje, hogy képes új ismeretek befogadására, régebbi ismeretek korrigálására, vagyis tanulásra. Nagy jelentõségû lenne ennek számítógépes megvalósítása. Régóta célja a mesterséges intelligenciával foglalkozó kutatóknak, hogy olyan számítógépes rendszert fejlesszenek ki, amely tanítható a programozhatóság helyett. Több érdekes kísérletet ismerünk erre vonatkozóan, olyan rendszereket, amelyek példák alapján tanulnak, olyanokat,

amelyek külsõ tanító segítségét veszik igénybe, stb. Bõvebben ld pl [LS], [W] 9. Neurális hálózatok A “neurális hálózatok” elnevezés eredete az emberi agy idegsejtjeinek, neuronjainak hálózatos elrendezõdésébõl ered. Már az 50-es években, jórészt biológiai kutatások eredményeként merült fel az a gondolat, hogy a természetes, biológiai neurális hálózatok mintájára is létrehozhatók számítógépes rendszerek. Ezek a rendszerek a feladatot nem algoritmikusan oldják meg, hanem a természettõl ellesett módon mintákból, példákból nyert tapasztalatok felhasználásával, tanulás útján kialakított feladatmegoldó képességgel. E mesterséges neurális rendszerek felépítésükben is sok hasonlóságot mutatnak a biológiai rendszerekkel; sok, egymással nagymértékben összekötött elemi mûveletvégzõ egységbõl állnak, melyek párhuzamos mûködésük révén bonyolult feladatok gyors megoldására is képesek lehetnek. Az

ötvenes évek végén kezdõdött a neuronhálók modellezése, de a korabeli technikai feltételek nem tették lehetõvé a modellek hatékony felépítését, alkalmazását. (Bár már a korai kutatási eredményeket is alkalmazták a gyakorlatban - pl. a 60-as években a telefonkészülékek adaptív zajszûrésénél.) A technika gyors fejlõdése lehetõvé tette, hogy a 80-as évek végétõl újra elõtérbe kerüljön a neurális hálók kutatása. 1988-ban L.Chua és L Yang professzorok, a Berkeley egyetem kutató laboratóriumában felfedeztek egy új elektronikus számítási módot, a celluláris neurális hálózatot (CNN Cellular Neural Network). Ez egy olyan szabályos geometriai rács, amely kis analóg elemek elektronikus számoló áramkörök - lokálisan kis távolságban összekapcsolt hálózata Az elsõ CNN elvû chip 1 cm2-en 300 milliárd mûveletet végez másodpercenként. Felépítése hasonló a legtöbb érzékszerv anatómiájához. Eközben Roska

Tamás (MTA SZTAKI) Berkeley-ben azt kutatta, hogyan lehet két számítási diszciplínát, az idõközben kifejlesztett neuro- és a korábbi digitális számítógépeket analógdigitális átalakítás nélkül kombinálni. Chua és Roska professzorok 1992-ben megalkották a CNN univerzális és szuperszámítógép chip architektúrát, amely az elsõ tárolt programú tömbszámítógép. Ennek egy CNN egysége saját analóg memóriával és logikával rendelkezõ kis számítógép. Frank Werblin, a retina világhírû szakértõje vetette fel azt a gondolatot, hogy a CNN univerzális chippel utánozni lehetne a retinát, mégpedig programozható módon. Hámori József akadémikus - az MTA által támogatott neurobiológiai kutatócsoportjával - ki is dolgozott néhány CNN modellt a látórendszer egyes részeire. A neurális hálózatok modelljei “hagyományos” számítógépeken is futtathatók. Ezek olyan algoritmusok, amelyek a központi idegrendszer kutatása során

elért eredményeken alapulva a gépi tanulást teszik lehetõvé. Ez egy több egységbõl álló hálózat, amelyben mindegyik egység viszonylag egyszerû feladatot hajt végre: jeleket fogad szomszédos neuronoktól vagy külsõ forrásból, amiket felhasználva meghatározza aktivitását és továbbítja azt más neuronok felé. A rendszer párhuzamosan mûködik abban az értelemben, hogy több egység számításai készülnek el nagyjából egy idõben. A neurális hálózatokat ezért szokták PDP-ként (Parallel Distributed Processing - Párhuzamosan Elosztott Feldolgozású rendszerek) is emlegetni. Bõvebben ld. pl [LS] 10. Az emberi tevékenység modellezése Bár a legtöbb MI kutatási terület az emberi intelligenciát veszi kiindulási pontként, de a megvalósult programok nagy része nem “ember szerûen” mûködik, vagyis nem követi szorosan az emberi gondolkodásmódot, az emberi elme problémamegoldó gondolkodását. Ha csak az emberi tevékenység merev

követése lenne a cél, a legtöbb MI program nem lenne olyan hatékony, mint amilyen most. (A világbajnok sakkprogram is inkább az “erejével”, mint az “eszével” gyõzött.- ld a sakkvilágbajnok programról alkotott véleményt) Ugyanakkor az emberi problémamegoldást pontosan (vagy inkább minél pontosabban) követõ modellek tervezése termékeny kutatási területet jelent mind a mesterséges intelligencia, mind a pszichológia számára. Az emberi feladatmegoldás modellezése amellett, hogy az MI legtöbb alapvetõ módszertanának kialakulásához vezetett, nagyon hasznosnak bizonyult az emberi gondolkodás, megismerés folyamatának formalizálásában és tesztelésében, így nagy mértékben hozzájárult a kognitív pszichológia fejlõdéséhez. A számítógépes szakemberek által kifejlesztett problémamegoldó módszerek új lehetõséget adtak a pszichológusoknak arra, hogy az emberi agyat számítógépes kifejezések körébõl vett hasonlatokkal

próbálják leírni, modellezni. Ez nem csak arra jó, hogy újabb “szótárunk” legyen az emberi intelligencia leírásához, hanem arra is, hogy ezeket az elméleteket számítógépes implementációkkal lehet tesztelni, kritizálni, módosítani. Bõvebben ld. pl [A],[LS], [M1],[Pe],[SFG] A teljesség igénye nélkül soroltuk föl a legfontosabb részterületeket. Végezetül szeretném megemlíteni, hogy a mesterséges intelligencia fejlesztése filozófiai problémákat is felvet, így a filozófusokat sem hagyja munka nélkül. Ilyen kérdések például, hogy egyáltalán, mi is az intelligencia, mit tekintünk intelligens viselkedésnek és hogyan lehet leírni azt. Mi a tudás természete? Lehet reprezentálni a tudást? Mit jelent a gyakorlottság, tapasztalat? Hogyan kapcsolódik egy adott alkalmazási területre vonatkozó tudás az ezen a területen alkalmazott problémamegoldó “szokások”-kal? Az MI alkalmazási területek is felvetnek számos mély

filozófiai kérdést. Milyen értelemben mondhatjuk például azt, hogy egy számítógép megérti a természetes nyelvi kifejezéseket? Ahhoz, hogy egy nyelvet megérthessünk, szimbólumokat kell értelmeznünk. Nem elég azonban a formális értelmezés - a vizsgált szövegeknek jelentéstartalma is van. Mit értünk ezen? Mi a jel és a jelentés? Ilyen és számtalan hasonló kérdés foglalkoztatja az MI filozófiájával foglalkozó tudósokat, laikusokat. Bõvebben pl. [LS], [Pe], de ki-ki saját maga is elgondolkozhat hasonló kérdéseken Feladatreprezentáció Az ember nap mint nap valamilyen probléma megoldására kényszerül. Mit is jelent megoldani egy feladatot? A megoldandó probléma egy, az adott problémakörrel kapcsolatos “világot”, “környezetet” határoz meg az ember körül. Ez a világ minden pillanatban valamilyen állapotban van Az általunk elképzelt eredményt nevezzük célállapotnak. Ilyen megközelítésben a feladatot akkor

tekinthetjük megoldottnak, ha a pillanatnyi állapot és a célállapot megegyezik, vagy legalábbis nincs köztük számunkra fontos különbség. A feladatmegoldás pedig azt jelenti, hogy keressük azt a mûveletsorozatot, amely segítségével a kezdõállapotból a végállapotba juthatunk. Ezt a mûveletsort a probléma egy megoldásának nevezzük A mesterséges intelligenciában problémamegoldás alatt mindig ennek a mûveletsorozatnak a meghatározását értjük. Ahhoz azonban, hogy egy feladatot jól és hatékonyan tudjunk megoldani, fontos, hogy magát a feladatot, a feladathoz tartozó “világot” jól és pontosan tudjuk leírni. Ezt nevezzük a feladat specifikálásának. A hagyományos programozási feladatok megoldása is a feladatspecifikációval kezdõdik. Ha szabályosan járunk el, akkor elõször megadjuk a feladat állapotterét, amelyen általában az összes lényeges adatszerkezet elõforduló értékeinek halmazát értjük. Ezután megadjuk, hogy

ezen állapottér elemei közül melyek a kiinduló állapotok, majd definiáljuk a célállapotok halmazát. Az adatszerkezeteken értelmezett mûveleteket általában nem adjuk meg külön, mivel ezek a gyakran használt adattípusok szokásos mûveletei. Az MI feladatok megoldását is specifikációval kezdjük, itt azonban sokszor nagyon speciális mûveleteket használunk, ezért itt a specifikációban az állapottéren értelmezett mûveleteket is megadjuk. A specifikáció magában foglalja az értelmezési tartományokat, azaz a mûveletek végrehajthatóságának feltételeit is. Olyan is elõfordulhat, hogy a mûveletekhez különbözõ végrehajtási költségeket is rendelünk. Ebben az esetben ezeknek a költségeknek a megadása is a specifikáció része. Az elõzõekben vázolt feladatspecifikálást a mesterséges intelligenciában állapottérreprezentációnak nevezzük. Az állapottér-reprezentációt irányított gráfokkal szemléltetjük. A gráf csúcsai

az egyes állapotoknak, az irányított élek pedig az alkalmazható mûveleteknek felelnek meg. A kezdõállapotnak a gráf startcsúcsa, a célállapotoknak a célcsúcsok halmaza felel meg. Ezt a gráfot reprezentációs gráfnak nevezzük. Ez sokszor nagy méretû, esetleg végtelen, ezért vagy nem célszerû, vagy nem is lehet explicit módon fölrajzolni, hanem csak implicit módon megadni. A gráf azonban roppant szemléletes eszköz a megoldó algoritmusok létrehozásában Egy általános gráfban sokszor nehéz megtalálni a megoldást, egy fa gráfban azonban általában jóval könnyebb. Ezért a reprezentációs gráfot gyakran fává alakítják Ismerkedjünk meg az állapottér-reprezentáció pontosabb fogalmával! Az állapottér-reprezentáció A mesterséges intelligenciában ez az egyik legáltalánosabb és legrégebben használt fogalom. Az állapottér-reprezentáció komponensei a következõk: 1. A feladat állapottere 2. Az állapottéren értelmezett

mûveletek 3. A kezdõállapot vagy kezdõállapotok 4. A célállapotok halmazát leíró célfeltételek Az állapottér a feladat adatszerkezeteinek összes lehetséges értékét tartalmazza. Az egyes állapotokban a feladat minden adata képviselteti magát egy-egy értékkel, az állapottér pedig az összes lehetséges adat-kombinációt tartalmazza. Egy algoritmus végrehajtása egy állapotból egy másik állapotba vezetõ út végigjárásának felel meg, hiszen minden egyes lépés módosítja bizonyos adatok értékét, vagyis minden egyes lépés egy állapotból egy másik állapotba vezet. A mûveletek az állapottéren értelmezett transzformációk. A reprezentációban megadjuk az egyes mûveletek értelmezési tartományát, vagyis a végrehajthatóságuk feltételét. Ha a mûveletekhez végrehajtási költséget is rendelünk, akkor ezt is itt adjuk meg. Ha a feladatban nem szerepelnek költségek, akkor szokás egységnyinek tekinteni õket, így egységesen

kezelhetõek a feladatok. A továbbiakban mi is ezt tesszük A kezdõállapotok halmaza része az állapottérnek. A kezdõállapot megadásával kapcsolatban meg kell különböztetnünk egy feladat specifikálását az összes szóba jöhetõ kiinduló adatra és egy konkrét feladat kitûzését egy konkrét kiinduló adatra. A különbözõ feladatok reprezentálásakor lehet, hogy az állapottér bármely pontjából kiindulhatunk, lehet, hogy ennek csak egy részhalmazára értelmes a feladat, és az is lehet, hogy csak egyetlen kezdõállapot jöhet szóba. A célfeltétel leírja a célállapotok halmazát, amely szintén részhalmaza az állapottérnek. A feladatmegoldás célja egy ilyen állapot elérése. Célállapot lehet több is Elõfordulhat, hogy a célállapotokat explicit módon meg tudjuk adni, de az is, hogy nem ismerjük õket konkrétan, és csak feltételekkel tudjuk leírni ezeket. Egy feladat megoldásán egy olyan mûveletsorozatot értünk, amely adott

kezdõállapotból elvezet egy célállapotba. A lehetséges megoldások közül sokszor a minimális költségû mûveletsorozat megkeresése a cél, néha azonban megelégszünk avval, hogy valamilyen módon elérjünk egy célállapotot. A minimális költségû megoldási mûveletsorozatot optimális megoldásnak nevezzük. Olyan esetben, amikor a költségek egységnyiek, az optimális megoldás a legrövidebb megoldási út. Vannak olyan feladatok, ahol csak a célállapot elõállítása a fontos, az odavezetõ mûveletsorozat csak “mellékterméke” a feladatot megoldó algoritmusnak. Máskor, épp ellenkezõleg, a célállapotot már ismerjük, és az elõállítását végzõ mûveletsorozatot keressük. A reprezentációs gráf Az állapottér-reprezentációt irányított gráfok segítségével szemléltethetjük. Az állapottér elemei alkotják a gráf csúcsait. Egy csúcsból egy másikba akkor vezet irányított él, ha van olyan mûvelet, amely az ezen

csúcsoknak megfelelõ állapotokat összeköti. Az ily módon megadott gráfot nevezzük reprezentációs gráfnak. A gráfnak azt a csúcsát, amely a feladat kezdõállapotának felel meg, kezdõcsúcsnak, vagy startcsúcsnak nevezzük. A célfeltételt kielégítõ állapotok csúcsai a célcsúcsok. Ezek halmaza a terminális halmaz Egy feladat megoldásának sikerét, a megoldás megtalálásához szükséges idõt nagyban befolyásolja a reprezentációs gráf bonyolultsága. Olykor ügyes reprezentációval magát az állapotteret szûkíthetjük le, máskor a mûveletek értelmezési tartományának ügyes megválasztása vezet egyszerûsítéshez. A leggyakoribb egyszerûsítési lehetõség a reprezentációs gráf fává alakítása. Ennek lényege, hogy megengedjük ugyanannak az állapotnak több elõfordulását, azaz több, neki megfelelõ csúcsot a reprezentációs gráfban. Elképzelhetõ, hogy így véges gráfból egy végtelen sok csúcsot tartalmazó fához

jutunk. Ez azonban nem baj, mert a legtöbb keresõ eljárás sokkal inkább érzékeny arra, hogy fán keres-e vagy általános gráfon, mint arra, hogy ez a gráf véges vagy végtelen. A fává alakítás lépései: 1. Ha két csúcs között oda-vissza irányú él van, akkor töröljük a startcsúcs felé visszairányuló élet. Így az élek mindig a startcsúcs felõl a gráf egyre távolabbi csúcsai felé vezetnek Ezeket a köröket azért lehet elhagyni, mert ha egy megoldási útnak része egy kör, akkor azt elhagyva is megoldási utat kapunk, mégpedig ennél rövidebbet. 2. Minden állapotnak annyi különbözõ csúcsot feleltetünk meg, ahány különbözõ csúcsból érhetõ el a startcsúcsból. Ilyenkor újabb utakat nem veszítünk, viszont elérjük azt, hogy minden csúcsnak csak egy szülõje legyen. A reprezentációs gráf fává alakítása nem mindig célszerû. Ha az eredeti gráf sok rövid visszacsatolású kört tartalmaz, vagy az elõzõ módon

kialakított fában a csúcsok száma robbanásszerûen megnõ, akkor nem érdemes áttérni erre a szerkezetre. A továbbiakban nézzünk néhány példát az állapottér-reprezentációra! Példák A produkciós rendszer A produkciós rendszerek fontos szerepet játszanak a mesterséges intelligenciában. Tekinthetõek keresõ rendszereknek is, hiszen a feladatok megoldásának meghatározása általában keresést igényel, de ugyanakkor tekinthetjük az emberi problémamegoldás modelljének is. A produkciós rendszer sajátos problémamegoldó szemlélettel rendelkezik. Lényege, hogy egy feladat megoldása során egymástól függetlenül, elkülönítve kezeli a feladat adatait, az ezeken értelmezett mûveleteket, és mûveletek sorrendjét meghatározó vezérlést. A produkciós rendszer mûködését elsõsorban vezérlése határozza meg. Mint látni fogjuk, a különbözõ keresõ algoritmusok a produkciós rendszerbõl a vezérlés megadásával származnak. A

produkciós rendszer komponensei: 1. Globális adatbázis - a feladat reprezentációs gráfjának a megoldás során elõállított része. 2. Produkciós szabályok - a globális adatbázison értelmezett operátorok 3. Vezérlési stratégia - az alkalmazható produkciós szabályok sorrendjének meghatározása. A hagyományos programokban a változók mindig csak az állapottér egyetlen állapotát rögzítik. A globális adatbázis azonban lehetõséget ad a feladatról megszerezhetõ összes információ megõrzésére és így, egy korábbi állapothoz való visszatérésre. Legtöbbször tartalmazza a már bejárt állapotok egy részét, vagy akár az összes bejárt állapotot. Általában nemcsak a már bejárt állapotokat tartalmazza, hanem az azokat összekötõ mûveleteket is, azaz a reprezentációs gráf egy részgráfját. Kezdetben a globális adatbázis a feladat kiinduló adatait, a kezdõállapotot tartalmazza. A produkciós szabályokat alkalmazva újabb és

újabb állapotok kerülnek az adatbázisba, majd ha a feladatnak van megoldása - bekerülnek a célfeltételt kielégítõ állapotok, a célállapotok is. Ilyenkor azt mondjuk, hogy a globális adatbázis kielégíti a terminálási feltételt. A produkciós szabályok különböznek az állapottéren értelmezett mûveletektõl, hiszen a produkciós szabályok a globális adatbázisra vonatkoznak, azaz tulajdonképpen gráfokon értelmezett transzformációk. Létezhet olyan produkciós szabály is, amely pl töröl egy útszakaszt a globális adatbázisból. Természetesen a produkciós szabályoknak is megvannak a végrehajtási feltételeik. Ha egy idõpontban több produkciós szabály is alkalmazható, akkor ezek közül a vezérlési stratégia alapján lehet választani. A vezérlési stratégia legfontosabb feladata tehát az alkalmazásra kerülõ szabály kiválasztása, de ellenõrzi a szabályok alkalmazhatósági feltételének teljesülését, nyilvántartja a

már alkalmazott szabályokat és figyeli a terminálási feltétel bekövetkezését is. A terminálás után az alkalmazott produkciós szabályok azonosítóinak nyilvántartása alapján megadható a kezdõállapotból a célállapotba vezetõ mûveletsorozat. A legtöbbször erre a mûveletsorozatra vagyunk kíváncsiak. Nézzük meg a produkciós rendszer algoritmusát! Algoritmus: Procedure PRODUKCIÓS RENDSZER Adat : = {kezdõállapot} while Adat nem elégíti ki a terminálási feltételt do R : = egy Adat-ra alkalmazható szabály Adat : = R(Adat) (* R alkalmazása Adat-ra ) enddo end Az algoritmusban jól látható a három elkülönült komponens: Adat a globális adatbázis, az Adat tartalmát újra és újra megváltoztató szabályok (R) és a szabályokat kiválasztó vezérlés. Az algoritmus a feladat kezdeti adatait figyelembe véve addig alkalmazza a produkciós szabályokat, amíg a terminálás feltétele nem teljesül, azaz a kezdõállapotból kiindulva

fokozatosan építette fel a célállapotba vezetõ mûveletsorozatot. Az ilyen irányban mûködõ produkciós rendszert elõre haladó, vagy másképp adatvezérelt produkciós rendszernek nevezzük. Ha a feladat egyetlen és ismert célállapottal rendelkezik, akkor alkalmazhatunk úgynevezett visszafelé haladó vagy célvezérelt produkciós rendszert. Ennek globális adatbázisa kezdetben a célállapotot tartalmazza és a produkciós szabályok inverzeit alkalmazza amíg el nem éri a kezdõállapotot. Azt, hogy mikor melyik irányú produkciós rendszert alkalmazzuk, mindig a konkrét feladat dönti el. Bizonyos esetekben célravezetõ lehet a kétirányú produkciós rendszerek használata Ezek egyidejûleg két irányból, a kezdõ és a célállapot felõl keresik a két állapotot összekötõ mûveletsorozatot, és akkor terminálnak, ha ez a két út összeér. Heurisztika Ha a feladatokat “vak” kereséssel, azaz minden lehetséges út szisztematikus

végigpróbálásával akarjuk megoldani, akkor gyakran hatalmas adattömeghez jutunk (kombinatorikus robbanás), melyeket nem, vagy csak nagy hardver erõforrással (ld. deep blue) tudunk kezelni. A keresési eljárásokat azonban hatékonnyá tehetjük, ha a feladatra jellemzõ speciális ismereteket is figyelembe veszünk. Ezeket a speciális ismereteket nevezzük heurisztikának. A heurisztikának máig nincs általánosan elfogadott pontos definíciója. Általában egy olyan “jó ötletet” értünk alatta, amely a legtöbb esetben csökkenti a próbálkozások számát, így lényegesen növeli a problémamegoldó program hatékonyságát. A heurisztikus eljárások általában “elég jó” megoldást adnak, bár nem garantálnak optimális megoldási utat, sõt, valójában semmiféle megoldást nem garantálnak. A heurisztika feladata, hogy a produkciós szabályok vezérlés által meghatározott sorrendjét pontosítsa. A heurisztika és a költségek kapcsolata

Az eredmény szempontjából a feladatokat a következõ módon csoportosíthatjuk: 1. Meghatározandó egy, a célállapotot elérõ mûveletsorozat 2. Egy viszonylag olcsó mûveletsorozatot keresünk 3. Minimális költségû (optimális) mûveletsorozatot keresünk Az elõállítandó mûveletsorozat költségét nevezzük a megoldás költségének. Megfigyelhetõ, hogy más-más vezérlési stratégiát alkalmazva a produkciós rendszer különbözõ költségû megoldásokat állíthat elõ. De ugyanaz a vezérlési stratégia is más-más költségû megoldáshoz vezethet a beépített heurisztikától függõen. Minél több tudást, minél erõsebb heurisztikát alkalmazunk, annál alacsonyabb költségû megoldáshoz jutunk. A megfelelõ heurisztika megválasztásakor nem egyedüli szempont az elõállítandó megoldás költsége, hanem figyelembe kell venni ezen megoldás megkeresésének költségét, is. A megoldáskeresés hatékonysága két költségtényezõvel

jellemezhetõ: az algoritmus tárigényébõl származó költség az algoritmus futásidejébõl származó költség. Ez a két költség nem teljesen független, általában a heurisztika alkalmazásával mindkettõ egyszerre csökkenthetõ. Vizsgáljuk most a futási idõt! A futási idõ költsége is két komponensbõl tevõdik össze: a vezérlési stratégia költségébõl - ez a kiválaszt függvény bonyolultságával függ össze a produkciós szabályok alkalmazási költségébõl - amely az alkalmazott produkciós szabályok számától függ. Minél erõsebb a produkciós rendszerbe beépített heurisztika, annál jobban informált a rendszer, ezáltal nõ egy szabály kiválasztásának, azaz a vezérlési stratégiának a költsége, csökken viszont az alkalmazandó szabályok száma, azaz a szabályok alkalmazási költsége. Fordítva: kevesebb információ, primitív heurisztika esetén egyszerûbb, gyorsabb egy szabály kiválasztása, de jóval több

próbálkozásra van szükség, azaz növekszik az alkalmazott szabályok száma. A két szélsõ esetben a futási idõt jellemzõ teljes költség nagy, a futási idõ költségének optimumát valahol középen kapjuk, ott, ahol az algoritmus elég erõs heurisztikával dolgozik, de nem túlinformált. A következô ábra a költség változását mutatja az informáltság függvényében: Vezérlési stratégiák A hatékony problémamegoldáshoz nem elég egy jó reprezentáció megtalálása, hanem az adott reprezentációhoz illeszkedõ hatékony keresési stratégiát kell választani. A hatékonyságot a vezérlési stratégia befolyásolja. A produkciós rendszer három komponense (globális adatbázis, produkciós szabályok, vezérlési stratégia) közül ez utóbbi a legmeghatározóbb. Alkalmas választásával hatékonyabbá tehetõ a problémamegoldás. A vezérlési stratégia meghatározása hatással van a globális adatbázis és a produkciós szabályok

kialakítására is. A vezérlési stratégiák két nagy csoportra oszthatóak, a módosítható és a nem módosítható stratégiákra. Az elõbbiek még két újabb csoportra oszthatóak, neminformált és informált, azaz heurisztikus vezérlési stratégiák: Az elsõ csoportosítás arra utal, hogy egy adott állapot esetén kiválasztott szabály véglegesnek tekinthetõ-e vagy sem. A módosítható stratégiák lehetõséget adnak a próbálkozásra Képesek arra, hogy egy korábban alkalmazott szabályról felismerjék, hogy annak alkalmazása helytelen, téves lépés volt. Ilyenkor visszatérnek egy korábbi állapothoz, hogy onnan újabb irányba indulva keressék a célállapotot. A gyakori visszalépések természetesen növelik az eljárás mûveletigényét. A nem módosítható stratégia - amelyben minden lépést végérvényesnek tekintünk - viszont gyakran vezethet tévútra bennünket, ha nem rendelkezünk elég információval a megoldandó feladatról. Ekkor

ugyanis nincs lehetõségünk arra, hogy egy téves lépést visszavonjunk, módosítsunk. A második csoportosítás a heurisztika alkalmazására utal. Nem informált esetben az algoritmus minden választási döntését elõre rögzített stratégia alapján hozza meg, míg a heurisztikus esetben a vezérlés felhasznál az adott problémára vonatkozó speciális ismereteket is. Nem módosítható vezérlési stratégiák A hagyományos feladatmegoldások esetén (pl. adatfeldolgozás) lényegében mindig nem módosítható vezérlést alkalmaznak. A mesterséges intelligencia feladatoknál azonban általában nem rendelkezünk olyan erõs információval az állapottér egy-egy állapotában, hogy biztosak lehessünk a kiválasztott produkciós szabály véglegességében. Emiatt a nem módosítható stratégiát ritkán használják MI feladatok megoldására. Alkalmazhatóságához vagy nagyon sok információt kell beépítenünk a szabály-kiválasztó rutinba, hogy nagy

biztonsággal a megfelelõ alkalmazható operátort válassza, vagy a rendszernek kell olyan speciálisnak lennie, hogy ilyen stratégiát alkalmazhassunk. A nem módosítható vezérlési stratégiák esetén a globális adatbázis a feladatnak csak egyetlen, éppen aktuális állapotát tartalmazza. A produkciós szabályok az állapottér mûveletei, amelyek alkalmazásuk során fokozatosan változtatják az adatbázis tartalmát. Mivel a globális adatbázis nem tartalmazza a korábbi állapotokat, “elfelejti” azokat, ezért egy szabály alkalmazása végérvényes, vissza nem vonható. Csak akkor célszerû nem módosítható vezérlést alkalmazni, ha vagy annyi ismeretet halmoztunk fel a produkciós rendszerben, amely alapján egyértelmûen kiválasztható egy megfelelõ szabály, vagy bármely pillanatban minden alkalmazható szabály megfelelõ. Az egyik legismertebb, az MI keretein kívül is gyakran használt nem módosítható stratégia a gradiens módszer

(hegymászó algoritmus - hill climbing). Ezt a módszert függvények maximumának megkeresésére szokták alkalmazni. Az adatbázison értelmezünk egy valós értékû függvényt. A vezérlés minden lépésben azon szabályok közül választ egyet, amelyekkel a függvényérték legnagyobb növekedését kapjuk, azaz mindig a legmeredekebb érintõ mentén haladunk a keresésben. Ha nincs olyan szabály, amely növelné a függvény értékét, akkor a stratégia olyan szabályt választ, amelyik legalább nem csökkenti a függvény értékét. Ha ilyen sincs, akkor megáll az eljárás Ha több, ugyanakkora függvényértéknövekedést okozó szabály közül kell választani, akkor egy elõre rögzített sorrend szerint választhatunk a szabályok közül. A függvényt úgy kell definiálni, hogy akkor vegye fel a maximumát, amikor a globális adatbázis kielégíti a terminálási feltételt, azaz egy célállapotot tartalmaz. A módszer nem mûködik minden függvény

esetén. Például lokális maximummal rendelkezõ függvény esetén gyakran elõfordulhat, hogy a módszer egy lokális maximumhoz konvergál a globális maximum helyett. Ha pedig olyan a függvényünk, hogy úgynevezett “fennsíkot” tartalmaz, akkor elõfordulhat, hogy az algoritmus ezen a “fennsíkon” bolyong a végtelenségig. Példaként nézzük meg a gradiens módszert a tili-toli játék esetén. Példa A visszalépéses vezérlési stratégia A módosítható stratégiák egyik nagy csoportja a visszalépéses algoritmusok osztálya. Egy olyan technika, amely szisztematikusan végigpróbálja az állapotgráf összes útvonalát, amíg célba nem ér. Sorra próbálja valamilyen rendszer szerint az alkalmazható szabályokat Ha egy adott ponton kiderül, hogy korábban rossz szabályt alkalmazott az eljárás, akkor visszalép egy korábbi állapothoz és megpróbál egy másik szabályt alkalmazni. A visszalépéshez persze szükség van arra, hogy az eljárás

“emlékezzen” rá, hogyan jutott el az adott állapotig, illetve a korábbi pontokon milyen szabályokat próbált már alkalmazni. Az algoritmus hatékonyságát nagymértékben befolyásolja az, hogy milyen sorrendben próbálkozunk az egyes lehetséges szabályok alkalmazásával. Ha a próbálkozási sorrendbe elég sok, a problémával kapcsolatos információt tudunk beépíteni, akkor feltehetõleg nem kell sokszor visszalépnünk, így a rendszer hatékonyabb lesz. A visszalépéses algoritmus akkor ér véget, ha vagy talált egy célcsúcsba vezetõ utat, vagy már minden lehetséges utat végignézett. Innen láthatjuk, hogy a keresés befejezõdhet sikeresen vagy sikertelenül, illetve az is lehet, hogy soha nem ér véget. A visszalépéses produkciós rendszer egyetlen utat tart nyilván. A globális adatbázis tartalmazza ezt az utat, valamint az összes állapotban nyilvántartja adott sorrendbe rendezve a még ki nem próbált mûveletek azonosítóit is. A

visszalépéses produkciós rendszer szabályai: az állapotokon értelmezett mûveletek, valamint egy speciális szabály, a visszalépés mûvelete. Mindegyik az adatbázisbeli utat módosítja. Az elõbbiek hosszabbítják, az utóbbiak rövidítik azt Egy adott pillanatban az alkalmazható szabályok: a globális adatbázisbeli út legmélyebb állapotára végrehajtható, de még nem alkalmazott mûveletek és a visszalépés mûvelete. A vezérlési stratégia: a visszalépés mûveletét csak akkor alkalmazzuk, ha már más alkalmazható szabály nincs. Az alábbiakban megadjuk a visszalépéses eljárás algoritmusát. (Az algoritmust sokszor szokták angol nevén backtracknak nevezni.) Bár formailag eltér a produkciós rendszer általános algoritmusától, rekurzív módon egyszerûbben írhatjuk le a módszert, így most ezt az utat választjuk. (Az érdeklõdõk megnézhetik a nem rekurzív algoritmust is.) Az algoritmust a gráf egy tetszõleges csúcsára definiáljuk,

amely kezdetben a startcsúcs, az algoritmus végrehajtása során pedig a reprezentációs gráf éppen aktuális csúcsa. Algoritmus: Procedure VISSZALÉPÉS(Csúcs) if cél ( Csúcs ) then return (nil) Szabályok : = a Csúcs -ban alkalmazható szabályok listája Talált : = hamis while nem (üres (Szabályok) vagy Talált) do R : = elsõelem (Szabályok) Szabályok : = maradék (Szabályok) Újcsúcs : = R ( Csúcs ) Eredménylista : = VISSZALÉPÉS (Újcsúcs) if Eredménylista ≠ hiba then Talált : = igaz enddo if Talált then return ( fûz (R, Eredménylista)) else return ( hiba ) end A Csúcs és Újcsúcs változók értéke a reprezentációs gráf egy-egy csúcsa. Az R egy alkalmazható szabályt tartalmaz, így Újcsúcs leszármazottja Csúcsnak. A Szabályok lista kezdetben a vizsgált állapotra alkalmazható összes produkciós szabályt tartalmazza. A Szabályok lista létrehozásával dõl el az alkalmazható szabályok sorrendje, vagyis megfelelõ heurisztika

beépítésével itt befolyásolhatjuk a kiválasztott mûveletek sorrendjét. A nil az üres listát jelenti, elsõelem a lista elsõ elemét, maradék pedig a lista maradékát adja. A fûz operátor egy elemet fûz egy lista elé Az Eredménylista az algoritmus végén a startcsúcsból a célba jutás során alkalmazott szabályok listáját tartalmazza. Az eljárást az Eredménylista : = VISSZALÉPÉS ( Start ) utasítással hívjuk meg, ahol Start a kezdõállapotot jelenti. Az algoritmus mindig egy Startból kiinduló utat tart nyilván a reprezentációs gráfban. A legalsó szinten meghívott eljárás akkor tér vissza további rekurzív hívás nélkül a fölötte levõ szintre, ha az általa vizsgált csúcs célállapot, vagy ha erre a csúcsra egyetlen mûvelet sem alkalmazható. Ha az adott csúcsra van alkalmazható mûvelet, akkor ezeket az eljárás sorban megvizsgálja, vagyis végignézi, hogy ez a mûvelet alkothatja-e egy megoldó mûveletsorozat

soronkövetkezõ elemét. Ha az aktuális R mûvelet nem vezet célcsúcs felé, akkor erre a szintre hibajelzéssel tér vissza a vezérlés. Ha a vizsgált csúcs esetén minden mûveletre ez a negatív eredmény igaz, akkor errõl a szintrõl hibajelzéssel eggyel magasabb szintre tér vissza a vezérlés. Ha az eljárás terminál, akkor eredménye az Eredménylistában képzõdik. Ha értéke “hiba”, akkor nincs megoldási út, ha értéke egy mûveletsorozat, akkor az a startcsúcsból vezet egy célállapotba. Ez az algoritmus csak olyan feladatok esetén mûködik elvárásunknak megfelelõen, amelynek reprezentációs gráfja véges, és nem tartalmaz köröket. Ilyenkor az algoritmus biztosan terminál, és ha létezik megoldás, akkor ezek közül egyet megtalál. Ha a reprezentációs gráf végtelen, vagy kört tartalmaz, akkor viszont nem garantált a terminálás. Az elsõ esetben ugyanis könnyen rákerülhet a vezérlés egy célállapotot nem tartalmazó

végtelen útra, a második esetben pedig elõfordulhat, hogy az eljárás egy gráfbeli kör mentén elakad, a kör mentén halad vég nélkül. Ha mélységi korlátot vezetünk be, akkor azonban garantált a terminálás. A mélységi korlát azt jelenti, hogy egy megadott értéknél mélyebben nem keres megoldást, azaz a mélységi korlát elérésekor is visszatér a vezérlés eggyel magasabb szintre. A körök menti fölösleges keresést is ki lehet iktatni, ha az eljárás azt is vizsgálja, hogy az aktuális csúcs szerepel-e már az eddig felderített úton. Természetesen a mélységi korlát önmagában is megakadályozná azt, hogy egy kör mentén végtelen sokáig keressen az algoritmus, a körök kizárásával azonban növelhetõ az eljárás hatékonysága. Mélységi korlát megadásával elérhetõ, hogy mindig termináljon az eljárás, a korlát ügyetlen megválasztásával azonban az is elõfordulhat, hogy - bár létezik célállapot mégis annak

megtalálása elõtt terminál az eljárás. A korlát megadásakor mindig körültekintõen kell eljárnunk, azonban egy-egy konkrét feladat esetén a feladat specifikumainak ismeretében általában jó becsléseket lehet adni a megfelelõ mélységi korlát értékére. A mélységi korláttal módosított algoritmus hasonló az eredetihez, de most szerepel benne a korlát, illetve az ismétlõdés figyelése. Ahhoz, hogy ezeket figyelni tudjuk, szükséges az eddig bejárt út nyilvántartása. Emiatt most az algoritmust nem egy konkrét csúcsra, hanem az eddig bejárt csúcsok egy aktuális listájára fogalmazzuk meg. Algoritmus: Procedure VISSZALÉPÉS(Csúcsok) Csúcs : = elsõelem (Csúcsok) if eleme(Csúcs, maradék (Csúcsok)) then return (hiba) if hossz (Csúcsok) > Korlát then return (hiba) if cél ( Csúcs ) then return (nil) Szabályok : = a Csúcs -ban alkalmazható szabályok listája Talált : = hamis while nem (üres (Szabályok) vagy Talált) do R : =

elsõelem (Szabályok) Szabályok : = maradék (Szabályok) Újcsúcs : = R ( Csúcs ) Újcsúcsok : = fûz (Újcsúcs, Csúcsok) Eredménylista : = VISSZALÉPÉS (Újcsúcsok) if Eredménylista ≠ hiba then Talált : = igaz enddo if Talált then return ( fûz (R, Eredménylista)) else return ( hiba ) end A visszalépéses stratégia elõnye, hogy az általa létrehozott produkciós rendszer könnyen megvalósítható, mûködése kevés tárolóhelyet igényel. Hátránya viszont, hogy egy magas szinten elkövetett sikertelen lépés visszavonására esetleg csak sok fölösleges próbálkozás után kerül sor. Másik hátrány, hogy ha egy csúcsból nem érhetõ el a célcsúcs, de ez a csúcs több úton is megközelíthetõ a startcsúcsból, akkor a stratégia képes újra és újra végigvizsgálni a szóban forgó csúcsból tovább vezetõ zsákutcákat. Ennek oka az, hogy az eljárás egyszerre egy utat tart nyilván, s nem õrzi meg a visszalépéskor sikertelennek

talált csúcsokat. Példa Gráfkeresõ stratégiák A gráfkeresõ stratégiák is a módosítható keresési stratégiák közé tartoznak. Míg a visszalépéses stratégiáknál mindig egy utat próbálunk végigjárni, addig a gráfkeresésnél szimultán próbáljuk végignézni a kezdõállapotból kiinduló utakat, vagyis minden olyan, a startcsúcsból kiinduló utat nyilvántartunk, amelyet már megvizsgáltunk. Ez lehetõvé teszi azt, hogy minden lépésben azon az úton haladjunk tovább, amelyik legigéretesebbnek tûnik a célcsúcs elérése szempontjából. Hogy mit értünk legígéretesebb alatt, azt különbözõ szempontok alapján dönthetjük el. Az egyes gráfkeresõ algoritmusok pontosan ezen szempontok megfogalmazásában különböznek egymástól. A visszalépéses algoritmusban egy állapotban kiválasztottunk egy alkalmazható szabályt, a gráfkeresõ stratégiáknál viszont a nyilvántartott, még meg nem vizsgált állapotok közül választunk ki

egyet, s erre alkalmazzuk az összes alkalmazható szabályt. Ez azt jelenti, hogy a kiválasztott út végén lévõ csúcs minden utódját létrehozzuk. Ezt nevezzük a csúcs kiterjesztésének A gráfkiterjesztés végetér, ha elértünk egy célcsúcsot. Az ilyen stratégiát követõ produkciós rendszereket gráfkeresõ algoritmusoknak nevezzük. Az állapotgráfot természetesen explicit módon is megadhatjuk, például úgy, hogy táblázatba foglaljuk, hogy mely pontokat köt össze él a gráfban. Egy feladat állapottere azonban lehet olyan nagy, hogy az állapotgráfot nem lehet explicit módon megadni. A mesterséges intelligencia területén a legtöbb feladat ilyen Ha nem ismerjük explicit módon egy feladat állapotgráfját, akkor a gráfkeresõ stratégiáknak nemcsak az a feladatuk, hogy bejárják a gráfot, hanem az is, hogy felépítsék a gráfnak azon részét, amit bejárnak. A gráfkeresõk csak addig építik az állapotgráfot, amíg el nem érnek egy

célállapotot. Így a reprezentációs gráf egy részgráfját építjük fel Ezt a részgráfot keresõgráfnak nevezzük. Ez tartalmazza a startcsúcsból kivezetõ és az eljárás által már megismert utakat. Mindegyik út végén találunk egy olyan csúcsot, amelyik utódait az algoritmus még nem építette be a keresõgráfba. Ezeket nyílt csúcsoknak nevezzük. A keresõgráf többi csúcsát pedig zárt csúcsoknak hívjuk Amikor valamelyik utat folytatja az algoritmus, akkor a nyílt csúcsok közül jelöl ki egyet kiterjesztésre. A gráfkeresõ algoritmus is egy produkciós rendszer. A globális adatbázis a G keresõgráf. A produkciós szabályok egy-egy csúcs teljes kiterjesztését végzik A produkciós rendszer vezérlése pedig a soronkövetkezõ csúcs kiválasztásával azonosítható, ekkor kerül kijelölésre az a csúcs, amelyre a kiterjesztés produkciós szabályát kell alkalmazni. A gráfkeresés alapalgoritmusa a következõ: Procedure

GRÁFKERESÉS G : = {Startcsúcs} Nyílt : = {Startcsúcs} Csúcs : = Startcsúcs while nem (cél (Csúcs) vagy üres(Nyílt)) do Nyílt : = Nyílt {Csúcs} G : = G ∪ Γ(Csúcs) Nyílt : = Nyílt ∪ Γ(Csúcs) Csúcs : = eleme (Nyílt) enddo end Az eljárás a startcsúcsból kiindulva építi fel a G gráfot. A nyílt csúcsokat a Nyílt halmazban tároljuk. A csúcskiterjesztést a Γ operátor végzi Csúcs jelöli az éppen aktuális csúcsot és a G ∪ Γ(Csúcs) mûvelet a Csúcs utódait a megfelelõ élekkel együtt hozzáfûzi a keresõgráfhoz. Az eljárás, amennyiben terminál, akkor kétféle képpen terminálhat: vagy célcsúcsot talál, vagy nincsen kiterjeszthetõ csúcs, azaz a Nyílt halmaz üres. Az általános gráfkeresõ algoritmus A gyakorlati alkalmazásokban gyakran egy függvény értékei alapján választjuk ki kiterjesztésre a nyílt csúcsok egyikét. Az erre a célra bevezetett függvényt kiértékelõ függvénynek nevezzük. Megállapodás

szerint az eljárás mindig egy olyan csúcsot választ kiterjesztésre, amelyikre ennek a függvénynek az értéke minimális. (Ha több ilyen csúcs is van, akkor tetszõleges közülük a választás.) Szükség van az utak nyilvántartására is, mert a feladat nem csupán egy célcsúcs elérése, hanem egy odavezetõ út megadása is. Mivel elég meghatározni egyetlen megoldási utat, ezért elegendõ minden csúcs esetén egyetlen, a startcsúcsból hozzá vezetõ utat nyilvántartani. Ha egy gráfban minden csúcshoz egyetlen utat tüntetünk ki, akkor a gráf egy úgynevezett feszítõfájához jutunk. Az egyes utak megjelölésére visszafelé mutató pointereket használunk. A startcsúcsot kivéve minden keresõgráfbeli csúcs pointere - p(Csúcs) egy szülõ csúcsra mutat. Célszerû arra törekedni, hogy ezek a pointerek lehetõleg az eddig talált utak közül a legolcsóbbat jelöljék ki, hiszen a feladatok nagy többségében egy optimális megoldás

meghatározása a cél. Bevezetjük a költségfüggvényt, amely az algoritmus bármely lépésében egy csúcsra megadja a feszítõfában hozzávezetõ út költségét. Az n csúcsba vezetõ út költségét jelöljük g(n)-nel. Ha g*(n) - nel jelöljük a startcsúcsból az n - be vezetõ utak teljes gráfon képzett minimális költségét ( k*(start, n) ), akkor nyilvánvalóan igaz a következõ összefüggés: g*(n) ≤ g(n) Egy gráf feszítõfáját optimális feszítõfának nevezzünk, ha ez minden úthoz optimális utat tartalmaz. Mind a pointer, mind a költségfüggvény kiszámítása az algoritmus mûködése során történik. Ha a gráfkeresés egy n csúcs kiterjesztésével az m csúcsot állítja elõ, akkor kiszámítja a hozzátartozó g(m) értéket és a p(m) pointert n-re állítja. Nyilvánvalóan g(m) = g(n) + c(n,m), ahol c(n,m) az (n,m) él költsége. Ha az m csúcsot nem elõször állítja elõ az eljárás, akkor meg kell vizsgálni, hogy

sikerült-e hozzá most az eddigieknél kisebb költségû utat találnia. Ha igen, akkor az új, csökkentett g(m) értéket kell megõríznie és a p(m) pointert át kell állítani az új szülõcsúcsra, egyébként pedig g(m) és p(m) változatlan marad. Példa Egy csúcs újbóli elõállításánál újabb problémát jelenthet az, ha az újból elõállított csúcs már zárt, azaz az eljárás korábbi kiterjesztései következtében már vannak utódai a keresõgráfban. Tegyük fel, hogy egy m csúcs újbóli elõállításakor az elõbbieknél kisebb költségû utat találtunk, de m zárt, azaz leszármazottai egy kiterjedt részgráfot alkotnak. Ekkor ennek minden csúcsában sor kerülhet a pointer átállítására, vagyis az m-bõl kiinduló teljes részgráf felülvizsgálatára van szükség. A probléma megoldására három módszer kínálkozik, azonban a harmadik lesz a leginkább megvalósítható út. Az egyik megoldás az, hogy az m-bõl elérhetõ összes

csúcsot átvizsgáljuk valamilyen gráfbejárási algoritmus segítségével és elvégezzük a szükséges módosításokat. Ez azonban nehézkesnek tûnõ eljárás. A másik megoldás, hogy olyan ügyesen válasszuk meg a kiértékelõ függvényt, hogy az általa meghatározott gráfkiterjesztési sorrend ne tegye szükségessé a pointerek átállítását. Ez azt jelenti, hogy egy csúcsot nem terjesztünk ki addig, amíg meg nem találjuk a hozzá vezetõ optimális utat. Ilyen függvényt azonban nem mindig sikerül találnunk, csak ha beépítünk az eljárásba a konkrét feladatra vonatkozó speciális ismereteket. Legegyszerûbben megvalósíthatónak a harmadik megoldás tûnik. Ebben az esetben ha az eljárás egy már létezõ zárt m csúcsot állít elõ, akkor ennek ellenére úgy kezeli az eljárás, mintha új csúcs lenne, azaz mintha nem lennének feltárt utódai. Ezt úgy valósítjuk meg, hogy az m csúcsot újból berakjuk a nyílt halmazba. Ebbõl adódóan

a keresés az m csúcsot késõbb újra kiterjesztheti. Ennek az egyszerû módszernek az a hátránya, hogy egy csúcs többször is kiterjesztésre kerülhet, így esetenként nem hatékony. [FGN] bemutatja ennek az algoritmusnak egy javított változatát, amely már megfelelõ hatékonyságú. A következõkben megadjuk a gráfkeresõ algoritmus költségszámítással és pointerátállítással bõvített változatát. Ezt nevezzük általános gráfkeresõ algoritmusnak. Procedure GRÁFKERESÉS G : = {Startcsúcs} Nyílt : = {Startcsúcs} Csúcs : = Startcsúcs; g(Startcsúcs) : = 0; p(Startcsúcs) : = nil while nem (cél (Csúcs) vagy üres(Nyílt)) do Nyílt : = Nyílt {Csúcs} Újcsúcsok : = Γ(Csúcs) while nem üres (Újcsúcsok) do Újcsúcs : = eleme (Újcsúcsok) Újcsúcsok : = Újcsúcsok {Újcsúcs} if nem (Újcsúcs ∈G) vagy g(Újcsúcs) > g(Csúcs) +c(Csúcs,Újcsúcs) then g(Újcsúcs) : = g(Csúcs) + c(Csúcs,Újcsúcs) p(Újcsúcs) : = Csúcs Nyílt :

= Nyílt ∪ {Újcsúcs} endif enddo G : = G ∪ Γ(Csúcs) Csúcs : = minf (Nyílt) enddo end Vegyük észre, hogy az algoritmusba beépítettük az elõzõekben említett kiválasztási függvényt is, a nyílt halmazból azt választjuk következõ kiterjesztendõ csúcsnak, amelyre vonatkozóan ennek a függvénynek minimális az értéke. Speciális esetben a keresõgráf egy fa. Ilyenkor nincs lényeges szerepe a pointereknek és nyilvánvalóan nem is változhatnak az eljárás során, hiszen minden csúcspontnak maximum egy szülõje van. Emiatt is érdemes volt a három említett megoldás közül a harmadikat választani. Az általános gráfkeresõ eljárás alapvetõ tulajdonsága, hogy véges reprezentációs gráf esetén mindig terminál. Ha a gráf körmentes, akkor minden csúcshoz véges sok különbözõ út vezet a startcsúcsból, így egy csúcs legföljebb véges sokszor kerül be a nyílt halmazba és véges sok lépésben eltávolítható onnan. Ha az

eljárás nem talál célcsúcsot, akkor véges számú kiterjesztés után üres nyílt halmazzal terminál. Ha a véges reprezentációs gráf tartalmaz köröket, akkor is igaz, hogy minden csúcshoz véges sok körmentes út vezet. A kört tartalmazó út feltárása pedig nincs semmilyen módosító hatással a nyílt halmazra, ugyanis egy csúcshoz vezetõ kört tartalmazó út költsége mindig nagyobb, mint a megfelelõ körmentes úté. Belátható az is, hogy ha egy véges reprezentációs gráfban létezik megoldás, akkor az általános gráfkeresõ eljárás megtalál egyet. Az állítás bizonyítása megtalálható [FGN] ill. [LS] könyvében Az egyes gráfkeresõ eljárások a kiválasztási függvény megadásában térnek el egymástól. A továbbiakban ezen függvény különbözõ megválasztásával más-más keresõ algoritmust fogunk tárgyalni. A gráfkeresõ algoritmusok két nagy csoportba sorolhatók attól függõen, hogy kiválasztási függvényük

tartalmaz-e az adott feladatra vonatkozó speciális ismereteket, vagyis heurisztikát, vagy sem. Ily módon beszélhetünk informált és neminformált gráfkeresési eljárásokról. Neminformált gráfkeresõ eljárások Ezen eljárások esetén az f kiértékelõ függvénybe nem építettünk be semmilyen, az adott feladatra jellemzõ ismeretet. A kiterjesztési sorrendet mindig valamilyen, az adott feladattól független, elõre rögzített stratégia szerint állapítjuk meg. Ezeket vakon keresõ eljárásoknak is szokták nevezni, utalva evvel arra, hogy a keresés nem vesz tudomást a feladat speciális tulajdonságairól. Három ilyen eljárást ismertetünk. Ezek közül kettõben a sorrend a gráf mélységétõl függ. Ahhoz, hogy errõl precízen tudjunk beszélni, szükségünk van a mélységi függvény fogalmára. Egy m csúcs d(m) mélységét a következõ képpen definiáljuk: d(s) : = 0 , ahol s a startcsúcs d(m) : = d(n) + 1 , ahol n szülõje m - nek. Egy

csúcs mélysége azonos a hozzá vezetõ út hosszával. A d mélységfüggvényt ugyanúgy, ahogy a g költségfüggvényt, az algoritmus számítja. Ha minden él költsége egységnyi, akkor g(n) = d(n) minden n G csúcsra. Szélességi keresés Szélességi keresés esetén a gráf csúcsait mélységük szerint növekvõ sorrendben helyezzük el a nyílt halmazban, s ebben a sorrendben választunk kiterjesztendõ csúcsot. Ez azt eredményezi, hogy a gráfot szintenként teljes egészében végigjárjuk Ezt formálisan úgy oldhatjuk meg, hogy a kiértékelõ függvényt a mélységi függvénnyel azonosnak vesszük: f(n) : = d(n) Vagyis a keresés minden lépésben a legmagasabb szintû csúcsok közül választ ki egyet kiterjesztésre. A szélességi keresés mindig talál megoldást, ha az létezik Ebben az esetben a legrövidebb megoldási utat találja meg. Példa Mélységi keresés Mélységi keresés esetén a csúcspontokat mélység szerint csökkenõ sorrendbe

rendezzük, s ebben a sorrendben terjesztjük ki õket. Így az eljárás mindig a legmélyebben fekvõ csúcsot terjeszti ki. Formálisan tekintve, a kiértékelõ függvényt a következõ módon adhatjuk meg: f(n) : = - d(n) A negatív távolságérték miatt a keresés minden lépésben olyan csúcsot terjeszt ki, amely a keresõgráfban a legmélyebben fekszik. Nagy hasonlóság van a visszalépéses keresés és a mélységi keresés között, a mélységi keresésnél azonban a visszalépésre nincs szükség, hiszen egyszerre több utat tart nyilván. A másik eltérés általános gráfok esetén érzékeltethetõ: mivel a mélységi keresés megõrzi a már bejárt zsákutakat, így nem fordulhat elõ, hogy ugyanarra a zsákutcára még egyszer rátérjen a vezérlés, míg a visszalépéses algoritmusnál ez elõfordulhat. Mivel sok probléma esetén mélységét tekintve végtelen nagy lehet az állapotgráf, ezért itt is meg szoktak adni mélységi korlátot. Az eljárás

a mélységi korlátnál mélyebben fekvõ csúcspontokat nem terjeszti ki. Ha a mélységi korlátot rosszul választjuk meg, akkor elképzelhetõ, hogy az algoritmus nem találja meg a megoldást. Példa Egyenletes keresés Az elõzõ két keresésnél az élköltségeket egységnyinek tekintve a mélységi függvényt felfoghattuk költségfüggvénynek is. Az egyenletes gráfkeresõ algoritmus az eredeti, közelebbrõl nem definiált g(n) költség fogalmát használja. Mindig olyan nyílt csúcsot választ kiterjesztésre, amelyhez a keresõgráfban a legkisebb költségû út vezet. Formálisan: f(n) : = g(n) A keresõfüggvény definíciójából adódóan az egyenletes keresés mindig optimális megoldást talál, feltéve, hogy létezik megoldás. A másik tulajdonsága, hogy minden csúcsot legföljebb egyszer terjeszt ki az algoritmus. A csúcsok ugyanis olyan sorrendben kerülnek kiterjesztésre, hogy egy zárt csúcsot sohasem kell a nyílt halmazba visszahelyezni.

Vegyük észre, hogy a szélességi keresés az egyenletes keresés speciális változata egységnyi élköltség mellett. Az egyenletes keresés általában nem túl hatékony, az optimális megoldást gyakran csak nagyon sok csúcs kiterjesztése árán találja meg. Heurisztikus gráfkeresõ algoritmusok Az információ nélküli keresõ eljárásokban túl sok csúcspontot kell feleslegesen megvizsgálni. Ezért arra törekszünk, hogy minél több heurisztikus információt használjunk fel a keresés csökkentésére. A heurisztika gyakorlatilag az adott feladatra vonatkozó jó ötlet. A jól megválasztott heurisztikák nagymértékben redukálják a keresést, de elképzelhetõ, hogy nem biztosítják a minimális költségû út megtalálását. A heurisztikus információkat arra használjuk fel, hogy a kiterjesztésre váró csúcsok esetén azok “ígéretes” voltát is figyelembe vegyük. Ha sikerülne mindig azt a csúcspontot kiválasztani kiterjesztésre,

amelyik rajta van a megoldási úton, akkor a keresõgráf mérete jelentõsen csökkenne. Az olyan heurisztikát, amely mindig ennek megfelelõen választja ki a kiterjesztendõ csúcsot, perfekt heurisztikának nevezzük. Ha egy konkrét feladat esetén ismernénk a perfekt heurisztikát, akkor tulajdonképpen implicit módon ismernénk a feladat megoldását. De a gyakorlatban használt heurisztikák csak becslik a perfekt heurisztikát, és minél jobban megközelítik, annál hatékonyabb a keresõ algoritmus. Egy konkrét feladat esetén a fõ probléma éppen az, hogy milyen heurisztikákat és hogyan építsünk be az “ígéretes” csúcspontokat kiválasztó rutinba. A keresõ eljárásokban használt heurisztikákat többféle szempont szerint is csoportosíthatjuk. Beszélhetünk egyrészt globális és lokális heurisztikákról A lokális heurisztikák mindig az eljárás megkezdése elõtt, pusztán az egyes csúcspontok tulajdonságai alapján rendelnek valamilyen

értéket a csúcspontokhoz. Például a tilitoli játék esetén ilyen lokális heurisztika lehet a nem megfelelõ helyen lévõ négyzetek számának meghatározása. A globális heurisztikák a keresés addigi lefutása alapján minõsítik a csúcspontokat. Tegyük fel például, hogy egy játéknál megfigyeltük, hogy a tizedik lépésig legalább egyet ütni kell ahhoz, hogy nyerhessünk. Így a játék elõrehaladtával egyre inkább elõtérbe kerülnek az ütõlépések annak ellenére, hogy esetleg lokálisan szemlélve ezek a lépések nem lennének ígéretesek. Feloszthatjuk a heurisztikákat úgy is, hogy azt nézzük, az egyes állapotok mely tulajdonságait próbálják megragadni. Ilyen szempontból beszélhetünk minõségi és mennyiségi heurisztikákról. A mennyiségi heurisztikák az adott probléma állapotainak valamilyen számszerû tulajdonságai alapján rendelnek valamilyen értéket az egyes állapotokhoz. A minõségi heurisztikák egyéb tulajdonságok

alapján határozzák meg az egyes csúcspontok ígéretességét. Például táblás játékoknál nyerõ állás lehet egy konfiguráció, amit nem valamiféle számszerû tulajdonság alapján, hanem a játék ismeretében lehet eldönteni. Például a közismert malom játékot véve, tapasztalatok alapján tudjuk, hogy célszerû az átellenes sarkokba helyezni a bábuinkat. Ezt a heurisztikát is nehéz lenne számszerûen lefordítani az egyes állapotokra. A legkézenfekvõbb mennyiségi heurisztikák is különbözõ elméleteken alapulhatnak. Elképzelhetõ például, hogy kísérletek segítségével meghatározzuk annak valószínûségét, hogy egy adott csúcspont a legjobb úton van-e és ezen valószínûségi értékek alapján választjuk a következõ kiterjesztendõ csúcsot. Az is elképzelhetõ, hogy különbözõ hasonlósági és távolsági metrikákat értelmezünk egy tetszõleges állapot és a célállapotok halmaza között, és ennek megfelelõen haladunk

tovább. Egy keresõ eljárásban egyszerre több heurisztikát is alkalmazhatunk. Mindig az adott szituációtól függõen hol egyik, hol másik heurisztikát részesítjük elõnyben. A szakértõi rendszerekre például kimondottan jellemzõ a sok heurisztika egyszerre való használata. A tanuló rendszerekre nemcsak az igaz, hogy egyszerre több heurisztikával is dolgoznak, hanem az is, hogy az addigi “életük” során tapasztaltakat beépítik a heurisztikájukba, vagy módosítják a korábbi heurisztikákat, vagy újakat vesznek fel a régiek mellé, vagy esetleg a fölöslegessé válókat elhagyják. Költségfüggvényekkel rendelkezõ problémák esetén a heurisztika költség jellegû mennyiségre ad becslést, mégpedig az adott csúcsponton áthaladó utak minimális költségére vonatkozóan. Mivel a gráfkeresõ eljárások esetén költségfüggvénnyel rendelkezõ problémáról van szó, a továbbiakban ezt a fajta heurisztikát tekintjük. Az

elõzõekben tárgyalt neminformált gráfkeresõ algoritmusok a nyílt csúcsok kiterjesztési sorrendjét a startcsúcsból hozzájuk vezetõ út költségei (speciális esetben az út hossza) alapján határozták meg. A kiértékelõ függvényben így a nyílt csúcsoknak csak az “elõélete” tükrözõdik, és nem kap szerepet a valamelyik célcsúcsba vezetõ hátralévõ út költsége. Egy nyílt csúcs “ígéretes” voltát pedig épp avval minõsíthetjük, ha becslést adunk a célcsúcsok halmazától való (minimális) távolságára. Az általunk vizsgált heurisztikus gráfkeresõ eljárások kiértékelõ függvényében mindig ez a fajta költségbecslés jelenik meg. A reprezentációs gráf egy tetszõleges n jelû csúcsára bevezetjük, és h*(n) - nel jelöljük azt a legkisebb költséget, amellyel n-bõl valamely célcsúcsba lehet jutni: h*(n) : = min k(n,t) t∈Τ ahol T a célcsúcsok halmaza. Több olyan t csúcs lehet, és ezekhez rendre több olyan

út vezethet n-bõl, amelyeknek költsége h*(n) - nel azonos. Ha n - bõl nem vezet út T be, akkor a h*(n) érték nincs definiálva. A késõbbiek egyszerûbb megfogalmazása kedvéért h*(n) - et ilyenkor végtelennek szokták tekinteni. A nehézséget az okozza, hogy a keresés egy olyan állapotában, amikor egy n csúcs kiterjesztésre vár, a h*(n) értéket még nem ismerjük, mint ahogy a reprezentációs gráf létre nem hozott részét sem. Ezért h*(n) - et becsülni próbáljuk. Ezt a becslõ függvényt h(n) - nel jelöljük és heurisztikus függvénynek nevezzük. A heurisztikus gráfkeresõ algoritmusok mindegyikének kiértékelõ függvényében szerepel ez a heurisztikus függvény. Elõre tekintõ keresés Az elõretekintõ keresés is az általános gráfkeresõ algoritmus egy speciális változata, bizonyos értelemben ellentéte az egyenletes keresésnek. Míg az egyenletes keresés egy olyan nyílt csúcsot terjeszt ki minden lépésben, amelyhez addig a

legkisebb költségû utat találta, addig az elõretekintõ keresés a csúcsok “elõéletét” figyelmen kívül hagyva egy olyan csúcsot választ, amelybõl várhatóan a legkisebb költséggel lehet célcsúcsba jutni. A kiértékelõ függvény tehát most megegyezik a heurisztikus függvénnyel: f(n) : = h(n) Ügyes heurisztikus függvény választással az elõre tekintõ keresés keresõgráfja jóval kisebb méretû lesz, mint az egyenletes keresés esetén, rosszul megválasztott heurisztika esetén azonban még az is elõfordulhat, hogy az eljárás nem terminál. Általánosságban mondhatjuk azt, hogy az egyenletes keresés “óvatos”, míg az elõretekintõ “kalandor jellegû”, eredményessége nagyban függ a h(n) heurisztikus függvény megválasztásától. Az eljárás sikeres terminálása nem garantált, könnyen lehet, hogy a keresés “elmegy” egy megoldás mellett. Példa Az A algoritmus Az egyenletes keresés óvatosságát és az

elõretekintõ keresés bátorságát, hatékonyságnövelõ lehetõségeit ötvözi az A algoritmus. Legyen most a kiértékelõ függvény: f(n) : = g(n) + h(n) Ez azt jelenti, hogy a keresés mindig olyan csúcsot választ kiterjesztésre, amelybe vezetõ út költségének és a célbaérés várható költségének összege minimális. A heurisztikus függvényre mindössze a h(n) 0 feltételt kötjük ki. Az ilyen kiértékelõ függvénnyel mûködõ algoritmust nevezzük A algoritmusnak. Nézzük meg, milyen költséget becsül az f(n) függvény! Vezessük be az f*(n) : = g(n) + h(n) függvényt. Ennek értéke a startcsúcsból kiinduló, az n jelû csúcson áthaladó és valamelyik célcsúcsban termináló utak költségeinek minimuma, vagyis f*(n) egy, a startcsúcsból kiinduló, az n csúcson áthaladó, célcsúcsban végzõdõ optimális út költsége. Ez azonban nem azonos az optimális megoldási út fogalmával, hiszen arról nem követeljük meg, hogy haladjon

át egy adott csúcson. Az f(n) függvény tagonként becsüli az n jelû csúcshoz tartozó optimális költséget. Azt tudjuk, hogy g(n) g*(n), de h(n) és h*(n) viszonyáról semmit sem tudunk. Belátható (ld. [FGN] ,[LS],[ST]), hogy az A algoritmus mindig talál megoldást, ha az létezik. A többi heurisztikus gráfkeresõ algoritmust az A algoritmus finomításával kapjuk, mégpedig úgy, hogy a h(n) függvényre egyre erõsebb feltételeket kötünk ki. Megjegyezzük, hogy az egyenletes keresés is az A algoritmus speciális esetének tekinthetõ, az azonosan nulla heurisztikus függvénnyel (h ≡ 0 ). Példa Az A* algoritmus Az A* algoritmus kiválasztási függvénye is az f(n) : = g(n) + h(n) függvény, de h(n) re vonatkozóan megköveteljük, hogy h(n) ≤ h*(n) legyen, vagyis a heurisztikus függvény minden csúcsnál alulról becsülje a hátralevõ optimális költséget. Ha az n csúcsból nem érhetõ el egyetlen célállapot sem, akkor h*(n) értékét

végtelennek tekintve, a h(n) érték tetszõleges lehet. Az A* algoritmus a legismertebb és leggyakrabban alkalmazott gráfkeresõ eljárás. Jelentõsége abban van, hogy optimális megoldást talál. Ennek bizonyítását ld [FGN],[LS]. Példa A következetes algoritmus Ha a heurisztikus függvényre vonatkozóan újabb megszorítást teszünk, akkor jutunk a következetes algoritmushoz. Pontosabban: Ha egy A algoritmus heurisztikus függvénye bármelyik él mentén legfeljebb az él költségével csökken, akkor az algoritmust következetesnek nevezzük. A mondott feltételt monoton megszorításnak hívjuk. Formálisan: h(n) - h(m) ≤ c(n,m) teljesül a reprezentációs gráf minden (n,m) élére. Kikötjük még azt is, hogy h(t) = 0 teljesüljön minden célcsúcsra. A monoton megszorítás szemléletesen azt jelenti, hogy a célhoz közeledve nem romlik a hátralévõ költség becslése. A következetes algoritmus nevezetes tulajdonsága, hogy minden csúcsot

legföljebb egyszer terjeszt ki, mivel ha egy csúcsot kiterjesztésre kiválaszt, akkor már n - be optimális utat talált. Az állítás bizonyítását ld [FGN] Szintén belátható ([FGN]), hogy a következetes algoritmus optimális megoldás megtalálásával terminál, feltéve, hogy létezik megoldás. Hogy igazoljuk a fejezet elsõ mondatának igazságát, vagyis azt, hogy a monoton megszorítás további szigorítást jelent a heurisztikus függvényre vonatkozóan, belátjuk a következõ állítást: Állítás: Ha egy h heurisztikus függvény kielégíti a monoton megszorítás feltételét, akkor egyben alsó becslése a h* költségfüggvénynek. Bizonyítás: Ha az n csúcsból nem vezet út a célcsúcsba, akkor az állítás érdektelen, de formailag teljesül, mivel h* értékét ilyenkor végtelennek tekintjük. Ha létezik út n-bõl a célcsúcsok T halmazába, akkor tekintsünk egy optimális (n = n0,n1,.,nk-1, nk = t ) utat Minden benne szereplõ élre írjuk

fel a monoton megszorítás feltételét: h(n) - h(n1) ≤ c(n,n1) h(n1) - h(n2) ≤ c(n1,n2) . h(nk-1) - h(t) ≤ c(nk-1,t) Összeadva az egyenlõtlenségeket, a jobboldalon az optimális út költségét kapjuk, azaz h*(n) -et, a baloldalon pedig, kihasználva, hogy h(t) = 0, h(n) - et. Vagyis h(n) ≤ h*(n). Az állítás azt jelenti, hogy minden következetes algoritmus egyben A* algoritmus is. Fordítva viszont nem igaz a tartalmazás, vagyis megadható olyan A* algoritmus, amely nem következetes. Erre mutat példát [FGN] is A gráfkeresõ algoritmusok kapcsolata Az alábbiakban egy ábrán összefoglaljuk a gráfkeresô algorimusokat és egymással való kapcsolatukat. Szürke folttal emeltük ki a nem informált keresô eljárásokat Problémamegoldás ÉS/VAGY gráfokkal A mesterséges intelligencia sok területén alkalmazzák az egyszerû irányított gráfok általánosításaként kapott ÉS/VAGY gráfokat. A két fõ alkalmazási terület egyike az úgynevezett

felbontható (dekomponálható) rendszerek modellezése, vagy más néven a probléma-redukciós reprezentáció, a másik a kétszemélyes játékok elemzése, de sok egyéb olyan helyen is alkalmazzák ezeket a gráfokat, ahol logikai megfogalmazások segítségével lehet felépíteni egy probléma állapotterét. Az ÉS/VAGY gráfok fogalma A logika két fontos mûvelete az ÉS (konjunkció), illetve a VAGY (diszjunkció). Ezeket, illetve a segítségükkel felépített formulákat szemléltethetjük az ÉS/VAGY gráfokkal, vagy más néven hipergráfokkal. Ebbõl adódóan ezek a gráfok minden olyan területen alkalmazhatóak, ahol a problémák ezen két mûvelet segítségével fogalmazhatóak meg. Hipergráfok esetén egy csúcspontnak lehetnek ÉS utódai és VAGY utódai. Egy ÉS kapcsolat akkor valósulhat meg, ha a kapcsolat összes tagja megvalósul, a VAGY kapcsolat igazzá válásához elég egy tagjának igaz volta. Ezért ábrázoláskor körívvel kötjük össze az

ÉS utódokhoz vezetõ éleket és nem kötjük össze a VAGY utódhoz vezetõket. Ha egy gráfban minden csúcspont utóda VAGY utód, akkor az adott gráf tulajdonképpen egy egyszerû irányított gráf. Az ÉS utódokhoz egy (körívvel összekötött) él köteg vezet. Ezt nevezzük hiperélnek, vagy másképpen k-adrendû élnek. Pontosabban, egy k-adrendû él mindig egy csúcsból egy k elemû csúcshalmazba vezet. (n,M) jelöli azt a hiperélet, amelyik az n csúcsból az M = {m1,.,mk} csúcshalmazba mutat Az n jelû csúcsot szülõnek, az M halmazt utódhalmaznak, elemeit utódoknak nevezzük. Az olyan gráfot, amelyik hiperéleket tartalmaz hipergáfnak, vagy másképpen ÉS/VAGY gráfnak nevezzük. Bevezetjük a hiperút foglamát: Hiperútnak nevezünk egy olyan részgráfot, amelynek minden csúcsából egyetlen hiperél indul ki. Ha a hiperút kezdõcsúcsát n-nel, végpontjainak halmazát K-val jelöljük, akkor nK jelöli az n-bõl K-ba vezetõ hiperutat. Az n

csúcsot õsnek, a K csúcshalmaz elemeit leszármazottaknak nevezzük. { nK} - val az összes n-bõl K-ba vezetõ hiperutak együttesét jelöljük. Ahol a szövegkörnyezetbõl adódóan egyértelmûsíthetõ, ott sokszor a hiperút elnevezés helyett egyszerûen csak az út megnevezést használjuk. Az ÉS/VAGY gráfokban is definiálhatjuk a megoldás, vagy megoldógráf fogalmát. Egy olyan utat nevezünk megoldásnak, amely a startcsúcsból indul ki és a célcsúcsok halmazába vezet. Egy ilyen út az ÉS/VAGY gráfban egy részgráfot határoz meg. Ezt nevezzük megoldásgráfnak. Az alábbi hipergráfban négy hiperút van, melyek egyúttal megoldásgráfok is, feltéve, hogy ebben a gráfban az n4, n5, n6, n7 csúcsok alkotják a célcsúcsokat. A megoldásgráfok: A közönséges gráfokhoz hasonlóan a hipergráfokban is bevezethetjük a költség fogalmát. Jelölje c(n,M) az (n,M) hiperél költségét. Egy út költségét az utat alkotó hiperélek költségeinek

összegeként értelmezzük. Egy hiperélet azonban többször is figyelembe vehetünk a költségszámításban. Az nK úton fekvõ m csúcsból kivezetõ hiperél költségét annyiszor számítjuk bele a hiperút költségébe, ahány közönséges irányított út vezet n-bõl mbe. A költség pontos fogalma a következõ: Jelöljük az nK út költségét k(n,K) - val. Ekkor, ha az n csúcs eleme a K csúcshalmaznak, akkor k(n,K) : = 0, egyébként pedig ahol {n1,.nr} az n csúcs utódhalmaza Ha feltételezzük, hogy az elõzõ ábrán minden k-adrendû él költsége k, akkor az egyes utak költsége rendre 5, 4, 7 és 6. Láthatjuk, hogy a c) megoldásgráfban az n2 csúcsból kivezetõ él költsége kétszer szerepel a költségszámításban, ugyanis kétféle irányból jutottunk el hozzá a hiperúton belül. ÉS/VAGY gráfkeresõ stratégiák Ezek a stratégiák a közönséges gráfoknál alkalmazott stratégiákon alapulnak, de azok nem alkalmazhatóak változtatás

nélkül, hiszen ÉS/ VAGY gráfok esetén nem csupán egy, a startcsúcsból egy terminális csúcsba vezetõ utat keresünk, hanem egy részgráfot, amely a probléma megoldásgráfja. Ahhoz, hogy egy algoritmus alkalmazása során el tudjuk dönteni, hogy elõállítottuk-e már a megoldásgráfot, szükségünk van két új fogalomra, illetve a nekik megfelelõ rutinokra. A keresõ eljárások futtatása során amikor lehetségessé válik, címkékkel látjuk el a gráf bizonyos csúcspontjait. A címkézési szabályok a következõk: Azt mondjuk, hogy egy csúcspont megoldott, ha - megfelel egy primitív (azaz tovább nem bontható) problémának; - van legalább egy VAGY utódja, amely már megoldott címkével rendelkezik; - az összes ÉS utódja már megoldott címkével rendelkezik. Azt mondjuk, hogy egy csúcspont megoldhatatlan, ha - nincs utódja és nem primitív probléma; - az összes VAGY utódja megoldhatatlan; - van legalább egy ÉS utódja, ami

megoldhatatlan. Az algoritmusban használatos MEGOLDOTT, illetve MEGOLDHATATLAN rutinok a fenti definíciók alapján alulról felfelé megcímkézik a gráfokban a lehetséges csúcspontokat. Az ÉS/VAGY KERESÕ eljárásban is van egy “eleme” függvény, amely szintén arra szolgál, hogy kiválasszon egy kiterjesztendõ csúcspontot. Most is (n)-nel jelöljük n utódainak a halmazát, de a kiterjesztés most nemcsak az utódok meghatározását jelenti, hanem azt is, hogy bizonyos esetekben n utódait úgy kapjuk, hogy az n állapotot ÉS kapcsolatú állapotokra bontjuk. Az algoritmusban szerepel egy PRIMITÍV nevû predikátum, ami akkor igaz, ha az argumentumában szereplõ csúcspont egy primitív problémának felel meg. Az algoritmus akkor terminál, ha a gyökér valamilyen címkét kap. Ha a kezdõállapot “megoldott” címkét kap, akkor az algoritmus már elõállított egy megoldásgráfot, melynek csúcspontjai mind “megoldott” címkével rendelkeznek. Ha a

kezdõállapot “megoldhatatlan” címkét kap, akkor viszont fölösleges tovább keresni, mert ez a címke már nem fog megváltozni. Mivel az ÉS/VAGY gráfokhoz is rendelhetõ költség, ezért itt is beszélhetünk optimális megoldásról, illetve annak megkeresésérõl. Most azonban csak a gráfkeresõ alapalgoritmus ÉS/VAGY gráfokra való átalakítását tárgyaljuk. A költségeket is figyelembevévõ algoritmus található például [FGN] könyvében. Algoritmus: Procedure ÉS/VAGY KERESÕ G : = {Startcsúcs} Nyílt : = {Startcsúcs} Csúcs : = Startcsúcs while Startcsúcs címkézetlen do Nyílt : = Nyílt {Csúcs} M : = Γ(Csúcs) Nyílt : = Nyílt ∪ M if M = ∅ then Csúcs-ot címkézzük megoldhatatlannak, és futtassuk le a MEGOLDHATATLAN rutint else while nem (M = ∅ ) do m : = eleme (M) M : = M {m} if PRIMITÍV(m) then m-et címkézzük megoldottnak, és futtassuk le a MEGOLDOTT rutint enddo Vegyük ki a Nyílt halmazból az összes címkézett

csúcspontot, és az olyan csúcspontokat, amelyeknek van címkézett elõdje Csúcs : = eleme (Nyílt) enddo if Startcsúcs címkéje megoldott then az eljárás sikeresen terminál else HIBA. end Probléma-redukciós reprezentáció A hétköznapi életben is és egyéb problémák megoldása során is sokszor próbálunk úgy megoldani egy feladatot, hogy azt egyszerûbb részfeladatokra bontjuk, majd az így kapott részeket további részekre, egészen addig, amíg közvetlenül megoldható problémákhoz nem jutunk, vagy amíg el nem jutunk egy olyan pontig, amelyrõl biztosan tudjuk, hogy megoldhatatlan. Az olyan problémát, melynek valahonnan ismerjük már a megoldását, primitív problémának nevezzük. Egy probléma megoldhatatlan, ha már valahonnan tudjuk, hogy biztosan nincs megoldása, vagy ha az adott problémát nem tudjuk tovább bontani egyszerûbb problémákra és nem ismerjük a megoldását. A probléma részekre bontásának szemléletére épülõ

feladat-reprezentációt problémaredukciós reprezentációnak nevezzük. Több helyen dekomponálható rendszereknek nevezik ezt a fajta problémakezelést. A probléma-redukciós reprezentáció szemléltetésére az ÉS/VAGY gráfokat, vagy más néven hipergráfokat alkalmazzuk. Az ily módon megfogalmazott feladatok egy ÉS/VAGY gráfon való keresési problémaként értelmezhetõek. Egy probléma redukciója a következõ módon ábrázolható: A szemléltetõ gráf csúcsai a problémaleírásoknak felelnek meg. A megoldandó probléma a gráf gyökere. Ha egy problémát részproblémákra vezethetünk vissza, akkor a problémának megfeleltetett csúcsból hiperél vezet a részproblémákat jelképezõ csúcshalmazba. Ha egy problémát többféleképpen is fel lehet bontani részproblémákra, akkor az adott csúcsból több hiperél is indul, mégpedig annyi, ahány féleképpen bontható fel részekre az adott probléma. Mint láthatjuk, egy hiperél, azaz az ÉS

kapcsolatban levõ csúcsok olyan részproblémákat reprezentálnak, amelyek mindegyikét meg kell oldani, míg ha egy csúcsból több hiperél vezet ki, vagyis ezek VAGY kapcsolatban vannak, akkor elég a lehetséges élek közül csak egyet kiválasztani és az annak megfelelõ részproblémákat megoldani. Sokszor célszerû elkerülni a vegyes elágazásokat, azaz arra törekedni, hogy egy csúcspontnak vagy csak ÉS utódai, vagy csak VAGY utódai legyenek. Ezt legegyszerûbben úgy oldhatjuk meg, hogy vegyes elágazás esetén új, közbülsõ csúcspontokat iktatunk be. A következõ ábrán a logikailag A = (B∧C) ∨ (D∧E) ∨ F módon felírt probléma vegyes elágazásokkal ábrázolható. Ha azonban bevezetjük az N : = B∧C, illetve az M : = D∧E csúcsokat, akkor a probléma A = N ∨ M ∨ F módon fogalmazható meg és ezen csúcsok bevezetésével elkerültük a vegyes elágazást. Nézzünk meg két konkrét példát a probléma-redukcióra! Mindkét

példában megpróbáljuk egyszerûbb problémákra bontani az eredetit, és azok megoldásait megkeresve megválaszolni az eredetit. 1. Hanoi torony A feladatreprezentáció tárgyalásánál példaként bemutatott feladat a következõ: Adott három különbözõ méretû korong (A, B és C) és három rúd (1, 2 és 3). Kezdetben mindhárom korong az 1-es rúdon helyezkedik el úgy, hogy felül van a legkisebb korong (A), alul a legnagyobb (C). Helyezzük át a korongokat a 3-as rúdra a 2-es segítségével úgy, hogy egyszerre csak egy korong mozdítható, és nem helyezhetõ egy korong egy nála kisebb korong tetejére. Egy állapot egy háromelemû vektorral reprezentálható, melynek indexei rendre A, B, C, az egyes komponensek értéke pedig az 1, 2, 3 valamelyike. Ez a reprezentáció azt adja meg, hogy az A, B, C korongok rendre melyik rúdon találhatóak meg. Ennek megfelelõen a kezdõállapotot az (1,1,1), a célállapotot a (3,3,3) hármas írja le. Ennek a feladatnak

megoldása tipikus példája a részfeladatokra bontásnak. A feladat a következõ három részproblémára bontható: 1. Tegyük az A és B korongot az 1-es rúdról a 2-esre 2. Tegyük C-t az 1-esrõl a 3-asra 3. Tegyük A-t és B-t 2-rõl 3-ra Mindegyik probléma egyszerûbb az eredetinél, mert kevesebb korongot mozgat. A második részprobléma tovább már nem redukálható, vagyis ez primitív probléma, amely egyszerûen megoldható. Az 1 és 3 részprobléma még tovább redukálható az eredeti felbontáshoz hasonló módon. Az alábbi ábrán láthatjuk a probléma-redukció ÉS/VAGY gráfját. Ennél a példánál minden lépésben ÉS kapcsolatú problémákra bontjuk a feladatot, így a teljes fa egyben a megoldófa is. A csúcspontokban mindig a megoldandó részproblémák szerepelnek. Megjegyzés: A feladat tetszõleges számú korong esetén is hasonló módon reprezentálható. 2. Szimbolikus integrálás A felbontható rendszerek másik klasszikus példája a

szimbolikus integrálás, vagyis egy függvény primitív függvényének meghatározása. Formálisan ez azt jelenti, hogy egy integráljelet tartalmazó szimbólumsorozatból megadott szabályok alapján egy integráljelet nem tartalmazó szimbólumsorozatot kell elõállítani. Egy integrál kiszámításakor olyan szabályokat alkalmazunk, amelyek hatására vagy továbbra is egy integrál kiszámítása a feladatunk, vagy több integrál kiszámítására bomlik a feladat. Ha egy fa segítségével nyomon követjük a lehetséges integrálok menetét, akkor az elsõ esetben VAGY utódot, a második esetben ÉS utódokat kapunk. VAGY utódok származnak például trigonometrikus-, algebrai azonosságok, helyettesítéses integrálás stb. alkalmazása esetén Ugyanakkor például összeg integrálásakor ÉS utódokhoz jutunk, hiszen az egyes tagokat külön-külön kell integrálnunk. Ebben a feladatban az alapintegrálok tekinthetõek primitív problémáknak, mert azok értéke

már elõre elkészített táblázatokból kiolvasható. A következõ ábrán egy konkrét integrál kiszámításának ÉS/VAGY fája látható. Az ábrában az éleken az alkalmazott szabályok vannak feltüntetve. Az eredeti integrálási probléma megoldása a részintegrálok megfelelõen visszahelyettesített összegeként adódik. Probléma-redukciós reprezentáció A hétköznapi életben is és egyéb problémák megoldása során is sokszor próbálunk úgy megoldani egy feladatot, hogy azt egyszerûbb részfeladatokra bontjuk, majd az így kapott részeket további részekre, egészen addig, amíg közvetlenül megoldható problémákhoz nem jutunk, vagy amíg el nem jutunk egy olyan pontig, amelyrõl biztosan tudjuk, hogy megoldhatatlan. Az olyan problémát, melynek valahonnan ismerjük már a megoldását, primitív problémának nevezzük. Egy probléma megoldhatatlan, ha már valahonnan tudjuk, hogy biztosan nincs megoldása, vagy ha az adott problémát nem

tudjuk tovább bontani egyszerûbb problémákra és nem ismerjük a megoldását. A probléma részekre bontásának szemléletére épülõ feladat-reprezentációt problémaredukciós reprezentációnak nevezzük. Több helyen dekomponálható rendszereknek nevezik ezt a fajta problémakezelést. A probléma-redukciós reprezentáció szemléltetésére az ÉS/VAGY gráfokat, vagy más néven hipergráfokat alkalmazzuk. Az ily módon megfogalmazott feladatok egy ÉS/VAGY gráfon való keresési problémaként értelmezhetõek. Egy probléma redukciója a következõ módon ábrázolható: A szemléltetõ gráf csúcsai a problémaleírásoknak felelnek meg. A megoldandó probléma a gráf gyökere. Ha egy problémát részproblémákra vezethetünk vissza, akkor a problémának megfeleltetett csúcsból hiperél vezet a részproblémákat jelképezõ csúcshalmazba. Ha egy problémát többféleképpen is fel lehet bontani részproblémákra, akkor az adott csúcsból több hiperél

is indul, mégpedig annyi, ahány féleképpen bontható fel részekre az adott probléma. Mint láthatjuk, egy hiperél, azaz az ÉS kapcsolatban levõ csúcsok olyan részproblémákat reprezentálnak, amelyek mindegyikét meg kell oldani, míg ha egy csúcsból több hiperél vezet ki, vagyis ezek VAGY kapcsolatban vannak, akkor elég a lehetséges élek közül csak egyet kiválasztani és az annak megfelelõ részproblémákat megoldani. Sokszor célszerû elkerülni a vegyes elágazásokat, azaz arra törekedni, hogy egy csúcspontnak vagy csak ÉS utódai, vagy csak VAGY utódai legyenek. Ezt legegyszerûbben úgy oldhatjuk meg, hogy vegyes elágazás esetén új, közbülsõ csúcspontokat iktatunk be. A következõ ábrán a logikailag A = (B∧C) ∨ (D∧E) ∨ F módon felírt probléma vegyes elágazásokkal ábrázolható. Ha azonban bevezetjük az N : = B∧C, illetve az M : = D∧E csúcsokat, akkor a probléma A = N ∨ M ∨ F módon fogalmazható meg és ezen

csúcsok bevezetésével elkerültük a vegyes elágazást. Nézzünk meg két konkrét példát a probléma-redukcióra! Mindkét példában megpróbáljuk egyszerûbb problémákra bontani az eredetit, és azok megoldásait megkeresve megválaszolni az eredetit. 1. Hanoi torony A feladatreprezentáció tárgyalásánál példaként bemutatott feladat a következõ: Adott három különbözõ méretû korong (A, B és C) és három rúd (1, 2 és 3). Kezdetben mindhárom korong az 1-es rúdon helyezkedik el úgy, hogy felül van a legkisebb korong (A), alul a legnagyobb (C). Helyezzük át a korongokat a 3-as rúdra a 2-es segítségével úgy, hogy egyszerre csak egy korong mozdítható, és nem helyezhetõ egy korong egy nála kisebb korong tetejére. Egy állapot egy háromelemû vektorral reprezentálható, melynek indexei rendre A, B, C, az egyes komponensek értéke pedig az 1, 2, 3 valamelyike. Ez a reprezentáció azt adja meg, hogy az A, B, C korongok rendre melyik rúdon

találhatóak meg. Ennek megfelelõen a kezdõállapotot az (1,1,1), a célállapotot a (3,3,3) hármas írja le. Ennek a feladatnak megoldása tipikus példája a részfeladatokra bontásnak. A feladat a következõ három részproblémára bontható: 1. Tegyük az A és B korongot az 1-es rúdról a 2-esre 2. Tegyük C-t az 1-esrõl a 3-asra 3. Tegyük A-t és B-t 2-rõl 3-ra Mindegyik probléma egyszerûbb az eredetinél, mert kevesebb korongot mozgat. A második részprobléma tovább már nem redukálható, vagyis ez primitív probléma, amely egyszerûen megoldható. Az 1 és 3 részprobléma még tovább redukálható az eredeti felbontáshoz hasonló módon. Az alábbi ábrán láthatjuk a probléma-redukció ÉS/VAGY gráfját. Ennél a példánál minden lépésben ÉS kapcsolatú problémákra bontjuk a feladatot, így a teljes fa egyben a megoldófa is. A csúcspontokban mindig a megoldandó részproblémák szerepelnek. Megjegyzés: A feladat tetszõleges számú

korong esetén is hasonló módon reprezentálható. 2. Szimbolikus integrálás A felbontható rendszerek másik klasszikus példája a szimbolikus integrálás, vagyis egy függvény primitív függvényének meghatározása. Formálisan ez azt jelenti, hogy egy integráljelet tartalmazó szimbólumsorozatból megadott szabályok alapján egy integráljelet nem tartalmazó szimbólumsorozatot kell elõállítani. Egy integrál kiszámításakor olyan szabályokat alkalmazunk, amelyek hatására vagy továbbra is egy integrál kiszámítása a feladatunk, vagy több integrál kiszámítására bomlik a feladat. Ha egy fa segítségével nyomon követjük a lehetséges integrálok menetét, akkor az elsõ esetben VAGY utódot, a második esetben ÉS utódokat kapunk. VAGY utódok származnak például trigonometrikus-, algebrai azonosságok, helyettesítéses integrálás stb. alkalmazása esetén Ugyanakkor például összeg integrálásakor ÉS utódokhoz jutunk, hiszen az egyes

tagokat külön-külön kell integrálnunk. Ebben a feladatban az alapintegrálok tekinthetõek primitív problémáknak, mert azok értéke már elõre elkészített táblázatokból kiolvasható. A következõ ábrán egy konkrét integrál kiszámításának ÉS/VAGY fája látható. Az ábrában az éleken az alkalmazott szabályok vannak feltüntetve. Az eredeti integrálási probléma megoldása a részintegrálok megfelelõen visszahelyettesített összegeként adódik. Kétszemélyes teljes információjú játékok A játékelmélet viszonylag fiatal tudománya a matematikának. Egyre bõvülõ alkalmazási lehetõségei miatt növekszik iránta az érdeklõdés a nem matematikusok körében is. A játékok matematikai elemzésére irányuló kísérletek már a reneszánsz korban megkezdõdtek. A vizsgálat tárgyát a szerencsejátékok képezték, vagyis azok a játékok (pl kockajátékok), amelyekben a játék kimenetele csak a véletlentõl (a szerencsétõl) függ,

a játékosok cselekvésétõl nem. A szerencsejétékok vizsgálata vezetett a véletlen törvényszerûségeinek felismeréséhez, a valószínûségszámítás kialakulásához. A 20. század elején kezdõdött meg a stratégiai játékok elemzése Ezek olyan játékok, amelyekben vagy egyáltalán nincs szerepe a véletlennek (pl. sakk), vagy csak részben van Ezekben a játékokban a játék kimenetelét döntõ mértékben a játékosok tudása, ravaszsága szabja meg. A stratégiai játékok elemzése vezetett a játékelmélet felfedezéséhez Az elmélet megalapozója Neumann János (1903 - 1957), elsõ jelentõs továbbfejlesztõje és alkalmazója Wald Ábrahám (1902 - 1950). A játékelmélet a stratégiai játékokkal foglalkozik. Feladata pedig az egyformán intelligensnek tekintett játékosok optimális cselekvéseinek (stratégiáinak) meghatározása, figyelembe véve a többi játékos ellenlépéseit, a játékszabályok adta korlátokat és esetleg a véletlen

szerepét. A játékosok optimális cselekvési egyensúlyi helyzetet teremtenek a játékban, amelytõl egyik résztvevõnek sem érdemes eltérni. A játékelmélet feladata tehát az egyensúlyi helyzetek keresése. A véletlen szerepe miatt a játékelmélet legtöbb megállapítása statisztikus jellegû, érvényesülésük a játék sokszori lejátszása esetén valósul meg. A stratégiai játékokban a résztvevõk érdekei általában ellentétesek, vagy legalábbis eltérõek, az ilyen játékokra a konfliktusok jellemzõek. Emiatt minden játék egy konfliktushelyzet modelljének tekinthetõ. Ez az alapja a játékelmélet széles körû alkalmazhatóságának, hiszen az élet különbözõ területein sok, játékelméletileg modellezhetõ konfliktushelyzet található. A játékelmélet különösen a hadászatban, közgazdaságtanban, a szociológiában nagy jelentõségû, de behatolt a pedagógiába, sõt az irodalomtudományba is. A gazdaság például - kissé

leegyszerûsítve - olyan játéknak tekinthetõ, amelyben a játékosok az egyes gazdasági egységek és van egy olyan játékos, az állam, amely ha nem nyer eleget, megváltoztatja a játékszabályokat (gazdasági szabályzókat). A játékelméleti kutatások fontosságát jelzi az a tény is, hogy az 1994-es közgazdasági Nobeldíjat a játékelmélet közgazdasági alkalmazásáért kapta e téma három kiemelkedõ kutatója: J.FNash, Harsányi József és RSelten Vannak olyan izgalmas kísérletek is, amelyek a játékelméletet kapcsolatba hozzák az evolúció-kutatás eredményeivel, a génszelekcióval, a kvantumelmélettel, és még sok minden mással is. Evvel foglalkozik Mérõ László nagyon izgalmas és szórakoztatóan olvasmányos könyve. ([M2]) A továbbiakban csak egy speciális játéktípussal, a kétszemélyes játékok elméletével foglalkozunk. Ez a témakör az elsõk között keltette fel a mesterséges intelligencia kutatóinak érdeklõdését. Ez nem

csoda, hiszen a MI olyan szellemi feladatok számítógépes megoldását tûzte ki célul, amelyek az ember részérõl magas fokú intelligenciát, gondolkodó tevékenységet kívánnak. Senki sem vitatja, hogy az olyan játékokra, mint a sakk, vagy a go, ráillik ez a meghatározás. Az MI kutatók célja: számítógépes programokkal túlszárnyalni az ember teljesítményét. Nézzük meg pontosabban, mit is nevezünk teljes információjú kétszemélyes játéknak. Ezt a játékosztályt a következõképpen definiálhatjuk: - Két játékos lép felváltva egymás után, a megadott szabályok szerint. - Mindkét játékos birtokában van a játékkal kapcsolatos összes információnak. Ez azt jelenti, hogy ismerik a játszma során megtett korábbi lépéseket, és minden részletét látják a kialakult állásnak. Lényeg, hogy a szerencsének semmilyen vonatkozásban sincs szerepe egy adott játszma alakulásában. - A játék minden egyes állásában véges számú

szabályos lépés közül lehet választani. - A játék szabályai olyanok, hogy végtelen játszmák nem fordulhatnak elõ. - A játszmák végén az egyik játékos nyer, míg a másik veszít, illetve bizonyos esetekben a döntetlen eredmény is elképzelhetõ. Látható, hogy ez a játékosztály alapos leszûkítése az általánosan említett játékelméleti lehetõségeknek, azonban jól kézbentartható, egyértelmûen megfogalmazhatóak a rájuk vonatkozó törvényszerûségek, ezért alkalmasak arra, hogy a mesterséges intelligenciával foglalkozó kutatók komolyabb figyelmet szenteljenek rá. Sok ismert táblás játék tartozik ide, egyik legismertebb és legkedveltebb a sakk, de idetartozik a go, a malom, a dámajáték, stb. A játékokkal kapcsolatos probléma a nyerés lehetõségének és módjának meghatározása. Vizsgálatainkhoz elõször is alkalmas reprezentációs eszközt kell választani. Erre nagyon jól megfelelnek az irányított gráfok. Ezt

nevezzük játékgráfnak Egy játékgráf az adott játék minden lehetséges játszmáját tartalmazza. Az általános gráfok helyett általában inkább fákat képezünk, mivel az jóval egyszerûbben kezelhetõ szerkezet, és mert a felváltva lépõ játékosoknak a fa páros, illetve páratlan szintjei feleltethetõek meg. Mivel definíció szerint nem fordulhatnak elõ végtelen játszmák, ezért az általunk vizsgált játékok gráfjai, illetve fái végesek, bonyolult játékok esetén azonban a játékfa óriási méretû is lehet. Játékgráf Az összes lehetséges játszmát irányított gráffal ábrázoljuk. A gráf egyes szintjein lévõ csúcspontokban a játék adott fázisának lehetséges állásai szerepelnek, valamint annak jelzése, hogy az adott állásban melyik játékos következik. Az egyes csúcspontokból kivezetõ élek a soronlévõ játékos legális lépéseinek felelnek meg. A gráf gyökere a kiinduló állás Azok a csúcspontok,

amelyekbõl nem vezet ki él (vagyis a gráf levelei) a játszma végállapotát tartalmazzák. Ezt a gráfot nevezzük játékgráfnak A játékgráf tartalmazza az összes lehetséges játszmát. Egy konkrét játszmának egy olyan út felel meg a gráfban, amely a kezdõcsúcsból egy végcsúcsba vezet. Példa Egy játék felfogható produkciós rendszerként is. Pontosabban, a játékgráf alapján olyan produkciós rendszert definiálhatunk, amely mûködése során a játék egy játszmáját állítja elõ. A globális adatbázist a játszma aktuális állása alkotja, kiegészítve avval az információval, hogy melyik játékos következik. A produkciós szabályokat a legális lépések alkotják elõfeltételeikkel együtt. A vezérlés egy nem módosítható stratégia, mivel a mûködés minden lépésében kiválaszt és végrehajt egy alkalmazható szabályt, amelyet már soha sem von vissza. A vezérlés specialitása, hogy felváltva hol az egyik, hol a másik

játékos számára választ ki lépést. Egy játékfa alkalmas egy játék összes játszmáinak ábrázolására, a produkciós rendszer pedig egy játszma elõállítására. A játékkal kapcsolatos alapvetõ kérdés azonban a nyerõ stratégia meghatározása. Azt mondjuk, hogy egy játékos számára létezik nyerõ stratégia, ha mindig van legalább egy olyan lépése, hogy ellenfele tetszõleges lépése esetén számára kedvezõ végállapotba tud kerülni, azaz ellenfele bármilyen játéka esetén is gyõzni tud. A két játékos szempontjából tehát más és más az elérendõ célhalmaz. Példa A nyerõ stratégia meghatározása A kétszemélyes teljes információjú játékok osztályának definíciójában szerepel, hogy a játszmák végén az egyik játékos nyer, a másik veszít, illetve bizonyos esetekben döntetlen is elõfordulhat. A következõkben bebizonyítjuk, hogy mindig létezik az egyik játékos számára nyerõ stratégia, azaz a játék

kimenetele az egyik játékos számára mindig kedvezõvé tehetõ. Ez azt jelenti, hogy az egyik fél számára létezik olyan stratégia, amelyet követve az ellenfél tetszõleges játéka esetén is õ nyer. Állítás: Egy teljes információjú kétszemélyes játék esetén mindig létezik az egyik játékos számára nyerõ stratégia, ha a játék nem végzõdhet döntetlennel. Bizonyítás: Tegyük fel, hogy adott egy játék teljes játékfája. Ekkor a fa leveleirõl (azaz a terminális csúcsokról) egyértelmûen el tudjuk dönteni, hogy melyik játékos számára nyerõek. Írjuk oda mindegyik levélhez annak a játékosnak a betûjelét, aki a megfelelõ végállapotban a gyõztes. Ezek után címkézzük meg alulról fölfelé a közbülsõ csúcspontokat egészen a gyökérig a következõ módon: Ha egy adott csúcspontban A-nak kell lépnie és utódai között létezik A-val címkézett, akkor a kérdéses csúcspontot is A-val címkézzük meg. Ha a szóban

forgó csúcspont utódai között egyetlen A-val jelölt sincs, akkor címkézzük meg B-vel. Ha egy adott csúcspontban a B játékos következik, akkor azt kell vizsgálnunk, hogy létezik-e B-vel címkézett utódja, és ugyanolyan elven végezzük a címkézést mint az elõbb az A esetén. Ezzel a címkézési módszerrel azt határozzuk meg, hogy egy állás melyik játékos számára nyerõ. Mivel a játékfa véges, ezért végül a gyökérelem is kap egy egyértelmûen meghatározott címkét. A gyökérbe annak a játékosnak a címkéje kerül, aki számára létezik nyerõ stratégia. Így az állítást bizonyítottuk, sõt, megadtunk egy nyerõ stratégiát is A gyökérben szereplõ címkéjû játékos számára az a nyerõ stratégia, hogy ezek után mindig olyan csúcspontra lép, amely az õ címkéjét viseli. Így mindig megnyerheti a játékot Példa Döntetlent is megengedõ játékok esetén az elõzõ állítás a következõképpen módosítható:

Állítás: Egy teljes információjú kétszemélyes játék esetén mindig létezik az egyik játékos számára nyerõ stratégia, illetve legalább nem vesztõ stratégia, ha a döntetlen is megengedett. Ez az állítás az elõzõhöz hasonlóan bizonyítható, csak a címkék közé a döntetlent jelzõ is bekerül. A játékfa leírt kiértékelése elsõsorban elméleti jelentõségû, mert a gyakorlatban csak olyan kisméretû fák esetén alkalmazható, ahol belátható idõn belül be tudjuk járni a teljes játékfát. A játékfa megcímkézése meggyorsítható úgy, hogy csak a feltétlenül szükséges csúcsokat értékeljük ki. Ahhoz, hogy a gyökér címkéjét meg tudjuk határozni, nem szükséges kiértékelni az összes csúcsot. Ha ugyanis egy csúcspont ugyanolyan címkével rendelkezik, mint amelyik játékos lép a fölötte levõ szinten, akkor azonnal felfelé “örökíthetjük” ezt a címkét. A fa bizonyos részeinek ily módon való levágása nem

befolyásolja a gyökér megcímkézését, vagyis a nyerõ stratégia meghatározását. Ily módon azonban nem az összes, hanem csak egy lehetséges nyerõ stratégiát olvashatunk le a fáról. A játékfa kiértékelését az is gyorsíthatja, ha megpróbáljuk csökkenteni a csúcsok számát. Bizonyos játékoknál gyakran fordulnak elõ szimmetrikus állások. Ekkor nyilván elegendõ ezek közül csak egyet vizsgálni. Az is elõfordulhat, hogy bizonyos állásokról a játék végigjátszása nélkül is tudhatjuk, hogy melyik fél számára nyerõ állás. Ekkor elég innen kezdeni a címkézést. A sakkprogramok többsége is számos végjátékot ismer A sakkozók igen sok állást kielemeztek már, így az esetek jelentõs részében elõre lehet tudni azt, hogy melyik játékos nyerhet. A nyerõ stratégia létezésére vonatkozó állítás érdekes következménye, hogy például a sakk esetén (vagy a nálunk kevésbé ismert, de a sakknál bonyolultabb go játék

esetén is) létezik valamelyik játékos számára nyerõ, de legalábbis nem vesztõ stratégia. Ennek meghatározása a játékfa óriási mérete miatt gyakorlatilag megvalósíthatatlan. (Becslés) Nem csak a sakk játékfája ilyen hatalmas. Általában a teljes játékfa mérete arányos a játék bonyolultságával. A nagyobb intelligenciát igénylõ játékok fái még a mai nagy teljesítményû számítógépek számára is kezelhetetlenek: teljes elemzésük messze meghaladná a rendelkezésre álló memóriakapacitás és mûveleti sebesség korlátait. Emiatt válik indokolttá a játékfa részleges kiértékelése. A játékfa részleges kiértékelése Mivel egy kicsit is érdekesebb játék játékfája általában terjedelmes méretû, ezért a játékfa teljes mélységû kiértékelésérõl le kell mondanunk. Ennek megfelelõen le kell mondanunk arról, hogy egy biztos nyerõ stratégiát határozzunk meg. Ehelyett csupán soronkövetkezõ játékos számára

egy erõs”, “jónak tûnõ” lépést keresünk. Az ellenfél válasza után újabb jó lépést keresünk a számára, és így tovább. Tehát egyszerre mindig csak a soronlévõ lépést határozzuk meg. A keresésnek valamilyen mélységi korlátot kell szabni, mivel nem akarjuk a fát teljes mélységben generálni. A legegyszerûbb korlátot egy rögzített szintszám jelenti, de korlátozhatjuk a keresési idõ, vagy memóriakorlátok alapján is. Az adott mélységig kiterjesztet keresõfa levelei általában nem egzakt nyerõ vagy vesztõ állások, mivel azokból még nem végállások. Nem tudjuk tehát ezeket az állásokat “nyerõ” vagy “vesztõ” címkével ellátni. Ehelyett egy úgynevezett statikus kiértékelõ függvényt alkalmazunk a keresõfa terminális csúcsaira. Ez a függvény számszerûen jellemzi az illetõ csúcsban lévõ állás “jóságát”, azt minõsíti, hogy a szóban forgó állás mennyire “ígéretes” a fa gyökerében

szereplõ játékos nyerése szempontjából. A “statikus” jelzõ arra utal, hogy a függvény értéke csupán az adott állástól függ. A statikus függvényt az adott játékra vonatkozó ismeretek, tapasztalatok alapján adhatjuk meg. Megválasztásától nagyban függ a kiértékelés “jósága”, vagyis az, hogy valóban kedvezõ elsõ lépéshez jutunk-e a kiértékelés után. A minimax eljárás Az egyik legismertebb részleges kiértékelõ eljárás a minimax algoritmus. Ez egy adott állásban az egyik játékos számára kedvezõnek tûnõ elsõ lépést határozza meg, az állásból kiinduló, elõre rögzített mélységû, teljes szélességben generált játékfa kiértékelésével. Konvenciók alapján nevezzük MAX-nak azt a játékost, aki számára a kedvezõ elsõ lépést keressük, ellenfelét pedig hívjuk MIN-nek. A kiértékelõ függvény pozitív értéket rendel minden olyan álláshoz, amelyben MAX-nak van nyerési esélye, mégpedig minél

nagyobbnak tûnik ez az esély, annál nagyobb értéket. Hasonló módon negatív értéket rendel a MIN számára kedvezõ állásokhoz. Döntetlen színezetû állásokhoz nulla vagy nulla közeli értéket rendel. A MAX számára nyerõ álláshoz szokás - t, a MIN számára nyerõ álláshoz pedig - - t rendelni. Az eljárás a következõ módon mûködik. Tegyük föl, hogy találtunk a vizsgált játékra egy alkalmas statikus kiértékelõ függvényt. Ha az adott mélységig felépítjük a játékfát, akkor annak leveleire alkalmazhatjuk a kiértékelõ függvényt. MAX számára az lenne a kedvezõ, ha eljuthatna egy maximális értékû állásba. Elképzelhetõ azonban, hogy miközben errefelé igyekszik, MIN tud olyanokat lépni, hogy MAX végül kedvezõtlen állásba jut. Ezért figyelembe kell venni MIN lehetséges lépéseit is. Nyilvánvalóan olyan kezdõlépést célszerû választani, amellyel - minden további állásban MIN legerõsebb ellenlépését

feltételezve MAX a legkedvezõbb állásba juthat. Maga az eljárás nagyon hasonlít a címkézési eljáráshoz. Itt is a levelektõl indulva a gráf felsõbb szintjeire “feladott” értékekkel végül a gyökérhez is rendelhetünk egy, az állás “jóságára” jellemzõ értéket, s az érték alapján megadhatjuk a legkedvezõbbnek tûnõ kezdõlépést. Ha egy adott szinten MAX lép, akkor a szinten lévõ csúcsokhoz az utódjaikhoz tartozó függvényértékek maximumát, ha MIN lép, akkor ezen értékek minimumát rendeljük. Ily módon a gyökér is kap egy számértéket és az evvel az értékkel rendelkezõ utódcsúcsba vezetõ lépést kell meglépnie. Formálisan: Egy adott mélységû játékfában alulról felfelé haladva minden n csúcshoz egy v(n) - nel jelölt értéket rendelünk az alábbiak szerint: 1. Ha n terminális csúcs, akkor v(n) : = f(n), ahol f(n) jelöli a statikus kiértékelõ függvény értékét. 2. Ha n nem terminális csúcs és

rákövetkezõit n1,,nk jelöli, akkor v(n) : = max(v(n1),.,v(nk)) ha n páros szinten található (azaz MAX következik), illetve v(n) : = min(v(n1),.,v(nk)) ha n páratlan szinten helyezkedik el. Ezzel az eljárással végül a fa s-sel jelzett gyökérelemnek is értéket ad. A MAX számára legkedvezõbb elsõ lépést egy olyan, s-bõl kiinduló él határozza meg, amely s-nek az egyik olyan rákövetkezõjébe vezet, amelyhez a v(s) érték van rendelve. Ne feledkezzünk meg arról a lényeges tényrõl, hogy a minimax eljárással mindössze MAX következõ lépését és nem a nyerõ stratégiát határozzuk meg. (Megjegyzendõ, hogy teljes játékfák estén azonban a nyerõ stratégia meghatározására is alkalmas.) Példa Az (m,n) átlagoló kiértékelés Általában nem tudunk megadni olyan statikus kiértékelõ függvényt, amely teljesen megbízhatóan minõsítené az állásokat. Ezért a minimax kiértékeléssel kiválasztott lépésrõl a késõbbiek során

könnyen kiderülhet, hogy nem is annyira elõnyös, mint ahogy a lépés megtételekor látszódott. Az (m,n) átlagoló kiértékelés éppen ezeknek a tévedéseknek a mértékét igyekszik csökkenteni, megpróbál “óvatosabban” választani kezdõlépést. Ezt átlagolással teszi A MAX szintjén a rákövetkezõk értékei közül az m legnagyobb átlagát, MIN szintjén pedig az n legkisebb átlagát rendeljük a szülõ csúcshoz. Ha egy csúcspontnak kevesebb rákövetkezõje van, mint n illetve m, akkor az összes utód átlagát tekintjük visszaadott értéknek. (Ennek a kiértékelésnek speciális esete a minimax kiértékelés n = m = 1 esetén.) Ez a kiértékelés egy lépés meghatározásában nem önmagukban tekinti az elérhetõ állásokat, hanem a játékfa szerinti összetartozásukban együttesen veszi figyelembe õket. Egy elõnyös, de izolált csúcs elérése helyett inkább egy olyan részfa felé tör, amely több kedvezõ csúcsot is tartalmaz,

jóllehet ezek egyenként kevésbé elõnyösnek tûnnek, mint az elõbbi csúcs. Az (m,n) átlagoló eljárás egy óvatos játékos (pl. sakkozó) stratégiáját modellezi, aki esetleg lemond egy olyan lépésrõl, amelynek folytatása elvezet egy nagyon elõnyösnek tûnõ álláshoz, ha ennek megítélésében nem biztos, és ráadásul amennyiben téved, akkor ellenfele jut kedvezõbb helyzetbe. Ehelyett inkább olyan kevésbé kockázatos lépést választ, amely több viszonylag jó folytatási lehetõséget kínál. Az alfa-béta levágás A minimax eljárás fölöslegesen sok csúcsot értékel ki a célból, hogy meghatározza a legjobbnak tûnõ kezdõlépést. A most bemutatásra kerülõ eljárás ugyanazt az elsõ lépést határozza meg, de általában jóval kevesebb csúcs kiértékelésével, mint az eredeti formában megfogalmazott minimax eljárás. Az eljárás hatékonysága jelentõsen javítható, ha rájövünk, hogy nincs szükség minden esetben az összes

csúcs kiértékelésére. Ha például egy adott csúcsban MAX lép és a csúcs utódai között van olyan, amelyhez tartozó függvényérték ∞, akkor a további utódokat már fölösleges elõállítani, mert a szülõcsúcsnak visszaadott érték ∞ lesz. De nemcsak akkor lehet a keresés egy részét elhagyni, ha valamely terminális csúcs nyerõ (∞) vagy vesztõ (-∞) állást tartalmaz. Tegyük fel, hogy a MAX kezdõcsúcs egyik rákövetkezõje (A) az õ utódcsúcsai kiértékelése után az α értéket kapta. Ez az érték a MAX kezdõcsúcs számára a visszaadott értékek alsó korlátját jelenti. MAX A-tól különbözõ utódainak kiértékelésével változhat a MAX-nak visszaadott érték, de ez az érték α-nál kisebb nem lehet. Tegyük fel, hogy B is rákövetkezõje MAX - nak. Legyen a B elsõ utódjának kiértékelése során kapott érték β, és rendeljük B-hez ezt az értéket. Mivel B MIN szintjén van, ezért ez számára a visszaadott

értékek felsõ korlátját jelenti. Ha ez a β érték nem nagyobb a MAX-hoz rendelt α értéknél, akkor B további kiértékelése nem adhat újabb eredményt MAX számára, ezért a B csúcs további rákövetkezõit már nem érdemes kiterjeszteni. A keresés csökkentésére az adott lehetõséget, hogy nyilvántartottuk a visszaadott értékekre vonatkozó korlátokat. Fogalmazzuk meg pontosabban az elõzõekben elmondottakat! 1. A keresés során egy csúcshoz hozzá tudjuk rendelni a visszaadott értéket akkor, amikor o o o a csúcs minden rákövetkezõjét kiértékeltük MAX csúcs esetén elõállítottunk egy ∞ értékû utódot MIN csúcs esetén elõállítottunk egy -∞ értékû utódot 2. A keresés során a nem terminális MAX csúcsokhoz alfa értéket, a nem terminális MIN csúcsokhoz béta értékeket rendelünk. o o Egy MAX csúcs alfa értéke a már létrehozott rákövetkezõk értékeinek aktuális maximuma; ez alsó korlát MAX visszaadott

értéke számára. Egy MIN csúcs béta értéke a már létrehozott rákövetkezõk értékeinek aktuális minimuma; ez felsõ korlát MIN visszaadott értéke számára. 3. Egy nem terminális csúcshoz alfa, illetve béta érték rendelhetõ, ha legalább egy rákövetkezõjének már van értéke. o o Egy MAX csúcshoz tartozó alfa érték a keresés során nem csökken Egy MIN csúcshoz tartozó béta érték a keresés során nem növekszik. Ezeknek a szabályoknak megfelelõen a kiértékelést a következõ esetekben lehet abbahagyni: 1. Egy MIN csúcs alatti kiértékelést nem szükséges folytatni, ha a hozzátartozó béta érték kisebb vagy egyenlõ, mint ezen csúcs valamely MAX õséhez tartozó alfa érték. Ekkor ugyanis a MIN csúcs visszaadott értéke nem növelheti a MAX õs számára visszaadott értéket. 2. Egy MAX csúcs alatti kiértékelést abba lehet hagyni, ha a hozzárendelt alfa érték nagyobb vagy egyenlõ, mint ezen csúcs egy MIN õséhez

tartozó béta érték. Ebben az esetben ugyanis a MAX csúcs visszaadott értéke nem csökkentheti a MIN õs visszaadott értékét. A levágás feltételét tömören így fogalmazhatjuk meg: a fában valamely út mentén teljesül az alfa > béta feltétel. Az alfa és béta értékek nyilvántartásával és a levágásokkal módosított minimax eljárást alfabéta eljárásnak nevezzük. Ez is akkor terminál, ha a kezdõcsúcs kapott visszaadott értéket Az alfa-béta eljárással meghatározott elsõ lépés egyenértékû a minimax algoritmus által kiválasztott elsõ lépéssel. Megjegyezzük, hogy amíg a minimax eljárás eredménye független az alkalmazott kiértékelési sorrendtõl, addig az alfa-béta eljárás eredménye (a kiterjesztett csúcsok száma és az elsõ lépés) függ az alkalmazott keresési stratégiától, az elsõ lépés optimális volta azonban mindenképpen garantált. Általában mélységi keresést és azon belül balról jobbra haladó

kiértékelést szoktak alkalmazni. Az alfa-béta eljárás nyilván hatékonyabb, mint a minimax, hiszen ezt alkalmazva bizonyos csúcsokat nem kell megvizsgálnunk. De még ezen eljárás hatékonysága is fokozható, ha megfelelõ heurisztikával elõrendezzük a fát úgy, hogy minél több levágásra kerüljön sor. Példa Tudásreprezentáció Az emberi problémamegoldás alapja az a tudás, amellyel az adott problémakörrõl, szakterületrõl rendelkezünk. Ugyanez a helyzet a mesterséges intelligencia problémamegoldásával kapcsolatban is. De mi is ez a tudás? A tudás egy adott szakterület ismereteit jelenti. Általában több elembõl tevõdik össze Tartalmazza azon heurisztikákat, elméleteket, amelyek a szûk szakterülethez tartoznak, és azon rutin jellegû ismereteket, tapasztalatokat is, melyekkel a szakterület szakértõi rendelkeznek. A “tudás” problémamegoldásban játszott szerepe szerint osztályozható, mégpedig aszerint, hogy ad-e

instrukciókat a problémamegoldáshoz, csak az ismert tények, objektumok leírására szorítkozik, vagy a tudás struktúráját, absztrakt modelljét építi fel, összekapcsolva esetleg problémamegoldó instrukciókkal is. A három fõ tudástípus a következõ: - Procedurális tudás: megadja, hogyan kell a problémát megoldani, hogyan hajtsunk végre egyes lépéseket. Általában szabályok, eljárások, függvények segítségével szokás leírni az ilyen fajta tudást. - Deklaratív tudás: a problémához tartozó azon ismereteket írja le, melyeknél nem áll rendelkezésre semmilyen utasítás arra, hogyan kell õket alkalmazni, milyen összefüggés van közöttük. Általában egyszerû logikai kifejezések, tények tartoznak ide, de a problémához tartozó fogalmak, objektumok leírása is e tudástípushoz tartozik. - Strukturált tudás: a fogalmak, objektumok közti kapcsolatok modelljét adja meg. A kapcsolatok leírása általában grafikus formában

történik, a fogalmak, objektumok pedig adatstruktúrával jellemezhetõek. A tudás szakterületenként általában más-más formában és struktúrában kerül leírásra, azonban kialakult néhány leírási forma, amely a szakterületek többségénél alkalmazható. Ezt nevezik tudásábrázolásnak, vagy tudásreprezentációnak. Sok helyen az ismeretreprezentáció elnevezés is elterjedt. A tudásreprezentáció egy tárgykörrõl szerzett ismeretek ábrázolása olyan szerkezetben, amely a tárgykörben felmerülõ feladatok számítógépes megoldását megkönnyítik, vagyis olyan technika, amely lehetõvé teszi a szaktudás leírását a tudásbázisban. Nyilvánvaló, hogy egy probléma megoldása során alapvetõ szerepe van annak, hogy milyen módon írjuk le, hogyan reprezentáljuk a megoldáshoz szükséges ismereteinket. Többféle ismeretreprezentációs technikát dolgoztak ki, melyek közül a felhasználó kiválaszthatja a problémájához legjobban

illeszkedõ reprezentációs technikát. A leggyakoribb technikák a következõk: - Logika A logika lehetõséget nyújt arra, hogy adott tényekbõl következtetéseket vonjunk le. Fontos tulajdonsága a logikának és a rokon formális rendszereknek, hogy a következtetés garantálja a korrekt kiterjesztést, amelyet más reprezentációs sémák nem biztos, hogy teljesítenek. Annak, hogy a logika alapú rendszerek népszerûek a kutatók körében, egyik oka az, hogy a következtetés, az új tények származtatása a régiekbõl, mechanikussá tehetõ. Ezek a tételbizonyító technikák automatikusan határozzák meg a logikai adatbázis új állításainak érvényességét a meglevõ állításokból. - Szabály alapú rendszerek A szabály alapú reprezentáció a legkorábban kialakult, leggyakrabban alkalmazott tudásreprezentációs módszer. Igen alkalmas a köznapi gondolkodás modellezésére, a szakértõ tapasztalatait megfogalmazó heurisztikák leírására. -

Szemantikus hálók A szemantikus háló grafikusan ábrázolja az objektumokat és jellemzõiket. A szemantikus háló egy irányított gráf, ahol a csomópontok az objektumokat, tulajdonságokat, esetleg a tulajdonságok értékeit tartalmazzák, az összekötõ élek pedig a csomópontok közötti relációkat fejezik ki. - Keretrendszerek, frame-k Az a felismerés, hogy sem a logika, sem a szabályok, de még a szemantikus hálók sem alkalmasak tények csoportba rendezésére, továbbá nem alkalmasak eljárásoknak tényekhez vagy azok valamely csoportjához való rendelésére sem, vezetett a frame fogalmának kialakításához. A frame egy adatstruktúra, amely egy objektum, vagy fogalom jellemzõit tartalmazza. Lényegében egy tulajdonsághalmaz, amely egy adott objektumról, fogalomról az adott pillanatban rendelkezésre álló ismereteket tartalmazza. A legtöbb rendszerben nem határolódnak el ilyen tisztán a tudásreprezentációs módszerek, hanem valamilyen módon

ötvözik ezeket. A frame- és szabály-alapú reprezentálási módok ötvözésével jutunk az úgynevezett hibrid rendszerekhez. Bõvebben ld [Bo], [Sá] Szabály alapú reprezentáció A szabály alapú reprezentáció a legkorábban kialakult, leggyakrabban alkalmazott tudásreprezentációs módszer. Igen alkalmas a köznapi gondolkodás modellezésére, a szakértõ tapasztalatait megfogalmazó heurisztikák leírására. Az alapgondolat elsõ megfogalmazása produkciós szabályok megnevezéssel, a 40-es évekre tehetõ. A produkciós rendszereket az emberi problémamegoldás modellezésére Newel és Simon alkalmazták elõször, az emberi kognitív képességek modellezésére. Produkciós szabályok A produkciós rendszerek három jól elkülöníthetõ komponense (globális adatbázis, produkciós szabályok, vezérlési stratégia) közül most a produkciós szabályokat emeljük ki, majd néhány szót ejtünk a vezérlésrõl is. A produkciós szabályok

feltétel-akció párok, azaz HA <feltétel> AKKOR <következmény> alakú “tudásmorzsák” (“chunk of knowledge”). - a feltétel részben a <feltétel> nem más, mint a szabály alkalmazásának feltételeit megadó állítás, vagy ilyenekbõl ÉS/VAGY (and/or) kapcsolókkal képzett összetett kifejezés, - a következmény részben a <következmény> a szabály alkalmazásának egy vagy több következményét írja le (elvégzendõ “akciók”, mûveletek, tevékenységek, érvényes állítások). Ezek a következõk lehetnek: o o o o a globális adatbázis (a szakértõi rendszerek körében elterjedt szóhasználattal: munkamemória) tartalmát módosító akciók (adatelemek beírása, törlése, módosítása) különbözõ eljáráshívások (ezek biztosítják a belsõ és külsõ környezet közötti információcserét) bizonyos esetekben (szabályozó, vezérlõ rendszerek esetén) a rendszer által vezérelt folyamatba való

beavatkozás (pl. egy kapcsoló bekapcsolását) a felhasználótól való információkérés. Ha a feltételrész teljesül, akkor a következményrészben elõírt tevékenységek rendre végrehajtódnak. A produkciós rendszer vezérlõ komponensének feladata az alkalmazható szabályok kikeresése, majd ezek közül kiválasztani az éppen alkalmazandót. Végül alkalmazza a kiválasztott szabályt, s egy külön komponens rész, a szabály-interpreter elvégzi a következmény részben elõírt akciókat. Szabályalapú következtetési módszerek Következtetésen egy olyan eljárást értünk, amely egy vagy több állításból újabb érvényes állításokat hoz létre. Két következtetési irányt különböztetünk meg: az elõrehaladó, vagy adatvezérelt, illetve a hátrafelé haladó, vagy célvezérelt következtetést. Az adatvezérelt következtetési stratégiával mûködõ szabály alapú rendszer a kezdõállapotból indul ki (a kiinduló adatokat a

munkamemóriába helyezve), majd további új információ meghatározásához a szabályokat vizsgálja. Ha egy szabály feltétel része a munkamemória adatai alapján teljesül, azaz “aktivizálódik” a szabály, a konklúzió által szolgáltatott adat új tényként a munkamemóriába kerül. Az új tény bevonásával azután további szabályok kerülnek alkalmazásra mindaddig, amíg egy adott cél, mint tény ismertté nem válik, vagy addig, amíg a rendszer talál alkalmazható szabályt. A következtetési folyamat közben többször is célt téveszthet, ilyenkor visszalép és új irányban folytatja a cél keresését. A következtetés algoritmusát egy szabályinterpreter valósítja meg, amire többféle algoritmus is létezik. Más irányú a feladat akkor, ha egy ismert célállapotról be kell bizonyítani, hogy valóban célállapot, vagyis hogy elérhetõ valamely kezdõállapotból. A célvezérelt következtetésnél az elérendõ célból indul ki a

rendszer. Ha a cél még nem ismert, olyan szabályt, illetve szabályokat keres a rendszer, melyek következmény részében a cél szerepel, majd megvizsgálja ezen szabályok feltétel részét és ellenõrzi, hogy szerepelnek-e már a munkamemóriában a meghatározáshoz szükséges paraméterek. Ha nem, akkor ezek a paraméterek lesznek az új közbülsõ célok, és olyan szabályokat keres, melyek konklúziójában e közbülsõ célok szerepelnek. A folyamat addig ismétlõdik, amíg egy közbülsõ cél levezethetõ valamely szabályból, vagy kiderül, hogy ez a közbülsõ cél egyetlen szabálynak sem lesz a következménye. Ez utóbbi esetben vagy az állapítható meg, hogy a kívánt cél nem érhetõ el a kezdõállapotból, vagy bizonyos rendszerek ebben az esetben a felhasználótól kérnek újabb információt. A szabályalapú célvezérelt következtetés algoritmusát szintén egy szabályinterpreter valósítja meg. A következõkben megadjuk mindkét

következtetési stratégia algoritmusát. Algoritmusok: Procedure ADATVEZÉRLÉS S : = az összes olyan szabály, amely alkalmazható az adatbázisra while S ≠ ∅ or nem értük el a céladatot do R : = eleme(S) S : = R alkalmazása S-re enddo end A célvezérelt következtetés algoritmusát a stratégiának megfelelõ módon rekurzív eljárással adjuk meg. Az eljárást meghívásakor G az elérendõ cél Procedure CÉLVEZÉRLÉS (G) S : = az összes olyan szabály, amely a következmény részében tartalmazza a G céladatot. if S = ∅ then információkérés a felhasználótól else while G nem ismert or S ≠ ∅ do R : = eleme (S) G: = R feltétel része if G ∉ adatbázis then CÉLVEZÉRLÉS (G) else R alkalmazása enddo end Példa: Sok rendszer kombinálja a kétféle következtetési technikát. Számos olyan probléma létezik, amelynek megoldásánál egyes részlépéseknél adatvezérelt, másoknál célvezérelt következtetést célszerû alkalmazni. Hogy mikor

melyiket érdemes alkalmazni, ahhoz nézzünk néhány javaslatot: - Ha arra vagyunk kíváncsiak, hogy bizonyos adatokból mire lehet következtetni, akkor az adtvezérelt következtetés célszerû. - Ha van hipotézisünk a problémamegoldásra, akkor bizonyítását célvezérelt következtetéssel kérhetjük. - Ha inkább adatok kellenek, mint következtetések, akkor célvezérelt következtetés a célszerû, ha inkább következtetések szükségesek, mint adatok, akkor adatvezérelt következtetés célszerû. A szabályalapú rendszerek értékelése A szabályalapú rendszerek alkalmazásának elõnyei: - Modularitás: minden szabály az ismeretanyag egy egységének (egy “ismeretmorzsának”) megfogalmazása, amely a többi szabálytól függetlenül hozható létre, törölhetõ vagy módosítható (a modulatitásnak azonban hátrányai is vannak). - Univerzális megjelenítés: minden ismeretet szabályok formájában fogalmazunk meg. - Természetesség: a

hétköznapi életben is igen sok helyzetben feltételes szabályokkal fejezzük ki magunkat. - Bizonytalanság-kezelés támogatása: a szabályok könnyen kiegészíthetõk bizonytalanságkezelési lehetõségekkel, egyszerûen a következtetést végzõ eljárásokat ki kell egészíteni a megfelelõ számításokat végzõ kalkulussal. A szabályalapú rendszerek alkalmazásának hátrányai: - Végtelen láncolás: mind elõrehaladó, mind hátrafelé haladó esetben (épp az elõnyként említett modularitás miatt) könnyen írhatunk olyan szabályokat, amelyekkel a feladatmegoldás során “körbejárunk”, végtelen szabályláncot generálva. - Új, a korábbiakkal ellentmondó ismeret beépítése: nincs általános módszer a szabályok esetleges ellentmondásainak ellenõrzésére, így - a modularitás adta lehetõségek miatt - egy új szabály felvétele könnyen ellentmondásossá teheti a szabályhalmazt. Ugyanez a probléma a meglévõ szabályok módosításánál

is elõfordulhat. - Nincs szabványosítva a szabályok “nyelve”, vagyis ez implemetnációnként nagyon eltérhet, ami nehezíti a szabálybázisok másik rendszerbe való “átvitelét”. Szemantikus hálók A szemantikus hálókat eredetileg a 70-es évek végén angol mondatok jelentésének (szemantikájának) leírására fejlesztette ki Quillian. Célja olyan reprezentáció kidolgozása volt, amellyel két szó összehasonlítását, szembeállítását, valamint egy szöveg jelentésének meghatározását “emberhez hasonló módon” lehetne megtenni. Ma már ezt a reprezentációt legtöbbször asszociatív hálók néven emlegetik, mivel jóval több területen alkalmazzák sikerrel különbözõ fogalmak, objektumok, fizikai és/vagy oksági kapcsolatának, asszociációjának leírására. Matematikailag a szemantikus hálók általában címkézett irányított gráfok, ahol a gráf csúcsai fogalmakat vagy objektumokat reprezentálnak, az élek pedig a fogalmak

között fennálló viszonyoknak, kapcsolatoknak felelnek meg. Ily módon hierarchikus kapcsolatokat is tudunk ábrázolni. Néhány gyakori kapcsolat például: instance of : példánya is equivalent to : ekvivalense has properties of : tulajdonságú subclass of : részosztálya is a : ez egy has part of : része set member : eleme type of : típusa A hálóban az élek mentén öröklõdést tudunk megvalósítani. A háló a fogalom és alfogalom osztályba tartozó alfogalmak esetén lehetõvé teszi a fogalom osztály tulajdonságainak öröklését. Az osztályhoz tartozást az “is a” (“ez egy”) reláció jelöli, és a reláció révén az osztály tulajdonságait öröklik egyedei. Természetesen nem biztos, hogy az öröklött tulajdonságok minden objektumnál azonos értékûek lesznek. Ezt az eltérést külön kell jelölni a szemantikus hálóban és ez ad lehetõséget a kivételkezelésre is. Az “emberhez hasonló módon” való feladatmegoldás az élek

mentén történõ következtetéssel valósul meg. Példa: A szemantikus hálók értékelése A szemantikus hálók alkalmazásának elõnyei: - minden fontos kapcsolatot explicit módon és tömören lehet leírni - a keresési idõ nagymértékben lecsökken (a kapcsolatok direkt ábrázolása miatt). A szemantikus hálók alkalmazásának hátrányai: - nincs szabvány a hálókon való manipulálásra (nincs a hálók szemantikája úgy definiálva, mint pl. a logikáé) - gyakran érvénytelen a következtetés (fõleg nagyméretû, nehezen átlátható hálóknál) - fennáll a kombinatorikus robbanás veszélye (pl. egy kapcsolat hamis voltának igazolásához az egész hálót végig kell járni) - uniformitás : címkézett élek szolgálnak mind az attribútumok, mind pedig a relációk ábrázolására. Hogy a leírás “nagybani” struktúráját jobban lehessen “látni” és kezelni, a nagyobb méretû asszociatív hálókat particionálni szokták. Frame A frame

a kognitív pszichológia séma fogalmából alakult ki. A séma egy tudásábrázolási mód, amely egy objektumról, fogalomról minden meglévõ ismeretet egy helyen tárol. A frame ábrázolási módot Minsky vezette be 1975-ben, ugyanis az emberi gondolkozást objektum orientáltnak tartotta, és úgy vélte, hogy egy átélt szituációt, a hozzá tartozó viselkedéssel együtt az agy egy belsõ struktúrában, frame-ben tárol. Ha egy új szituációba kerülünk, agyunk megpróbálja az új szituációt a régivel azonosítani, és ez alapján alakítja viselkedésünket, elvárásainkat. Nem mindig találunk teljes azonosságot a régebbi szituációkkal, ilyenkor a régit módosítani kell, vagy új frame-t kell kialakítani. A mesterséges intelligencia frame, vagy “keret” fogalma tehát ismeretelméleti eredetû, de kialakításához az objektum-orientált programozás elterjedése is hozzájárult. A frame a tárgyköri szakértõ ismereteinek egyetlen fogalmi

egységbe tartozó részét jelenti, leíró jellegû megfogalmazásban. A frame egy fogalom vagy egy objektum strukturált szimbolikus modellje: a fogalom számunkra fontos tulajdonságait egybefoglaló struktúra, amelyet a fogalom neve foglal egységbe, vagyis a frame egy adatstruktúra, amely egy objektum vagy fogalom jellemzõit tartalmazza. A tulajdonságokat (attribútumokat) a frame slotjai (magyarul “rés” vagy “fiók”) nevezik meg. Ezekben különbözõ dolgokat tarthatunk: az attributum értékét, annak alapértelmezését, forrását, az érték változásakor végrehajtandó eljárásokat (az úgynevezett démonokat), különbözõ járulékos információkat, stb. A frame-eket relációkkal lehet összekapcsolni Különös szerepe van a hierarchikus kapcsolatoknak, amelyek mentén bizonyos attribútumok és azok jellemzõi öröklõdhetnek. Ily módon csökkenthetõ a redundancia. Egy frame struktúra látható a következõ ábrán: Vagyis frame-kkel

osztályokat és elemeiket ábrázolhatunk. Formailag nincs köztük különbség. Az elemek öröklik az osztály tulajdonságait, emiatt néhány frame leíró nyelvben az osztályhoz tartozást, és így az öröklõdési kapcsolatot az “is a” relációval jelzik. Ha az osztály még további osztály alosztálya, akkor a másik osztálytól is örökli a tulajdonságokat. Ugyanúgy, ahogy a szemantikus hálóknál, a frame-kkel is kialakítható összetettebb osztály, alosztály kapcsolat. A szemantikus hálónál látható objektum hierarchia a frame-k osztály, alosztály kapcsolatával is megadható. Példa Egy objektum azonban nem csak az osztály és a tulajdonságok értékeivel jellemezhetõ, hanem a tulajdonságok értékeire különbözõ kikötéseket tehetünk, eljárásokat kapcsolhatunk az objektumhoz. A frame alapú reprezentáció értékelése A frame alapú reprezentáció elõnyei : - Eseményvezérelt végrehajtás : a rendszer eljárásai egy-egy

attribútumérték megváltozásakor aktivizálódnak (az ilyen eljárásokat démonoknak nevezik). A démonok végrehajtása esemény-vezérelt. A szabályalapú rendszerekkel ellentétben, ahol a szabályokat a feladat végrehajtásának minden lépésénél “megpörgeti” a rendszer, a démonok csak akkor terhelik a végrehajtást - de akkor azonnal - amikor az adott slot az elõre specifikált értékváltozást elszenvedi. - Az ismeretek szervezése: az asszociatív hálóhoz képest egy frame-struktúra sokkal világosabban van szervezve (a szemantikus hálónál az attribútumokat is és a relációkat is ugyanolyan jellegû címkézett élek ábrázolják). A frame-k slotjainak elérése (pl érték beírásakor) sokkal gyorsabban, direkt módon történik, nem úgy, mint a szemantikus hálóknál. - Ön-vezérlés: a frame-k úgy vannak strukturálva, hogy adott feladatmegoldási szituációban képesek meghatározni saját maguk alkalmazhatóságát. Ha pedig egy frame

éppen nem alkalmazható, sugallhatja más frame-k alkalmazását. - Dinamikus értékek elhelyezése: a végrehajtás közben dinamikusan változó értékeket könnyû beírni a megfelelõ slotokba. - Deklaratív és procedurális ismeretek együttes ábrázolása: a deklaratív szemléletû frame alapú rendszerek szerves alkotóelemei a procedurális szemléletû démonok és szabályok. Ez nagyon tágítja a frame alapú alkalmazások körét, továbbá lehetõvé teszi más reprezentációs sémák frame alapú realizálását. A frame alapú reprezentáció hátrányai : - Prototípusoktól való eltérés: nagyon sok valós jelenség eltér a megszokott sémától. Pl egy kerékpár kétkerekû jármû, de akad közöttük háromkerekû is, ha nem ragaszkodunk a szigorú elnevezésekhez, hanem elfogadjuk a hétköznapi kerékpár fogalmat. Ha nem megfelelõ absztrakciós szintrõl indítottuk a frame-k kibontását, akkor ilyen kivételek miatt nagyon elbonyolódhat a rendszer.

- Új szituációkhoz való alkalmazkodás: probléma van akkor, ha olyan új szituációt vagy objektumot kellene ábrázolnunk, amelyre nincs felkészülve a rendszer (pl. sehova sem tudjuk beilleszteni a frame hierarchiába). Ez erõsen korlátozza a frame alapú reprezentáció alkalmazhatóságát, mert fontos a megvalósítás elõtti alapos elemzés. - Heurisztikus ismeretek ábrázolása: míg a szabályalapú rendszereknél könnyen írhatunk heurisztikákat, addig itt ez problémás. Frame-kkel könnyen le tudunk írni egy tipikus beteget, egy általános betegséget, valamely egyedi betegség specifikus szimptómáit, azt azonban, hogy egy beteg diagnózisánál az egyes szimptómák hogyan hatnak egymásra, inkább a szabályok alkalmazásával lehet elegánsan leírni. Ezért van az, hogy a tisztán frame alapú rendszerek helyett inkább hibrid rendszereket alkalmaznak. Szakértõi rendszerek A szakértõi rendszerek (SZR) a mesterséges intelligencia egyik kutatási

területe, felhasználja mindazokat a mesterséges intelligencia módszereket, amelyek a probléma megoldásához tartoznak. A szakértõi rendszerek a tudásalapú rendszerek közé tartoznak. Könnyen strukturálható, könnyen formalizálható, szabályokkal leírható ismeretanyag esetén alkalmazhatóak. Fõ feladatuk a problémamegoldás, és ezeket az emberi problémamegoldáshoz hasonló módon próbálják megvalósítani. A szakértõi rendszer egy olyan számítógépes program, amely az ember problémamegoldó képességét modellezi. A problémamegoldó képesség jelenleg korlátozott - csak jól körülhatárolt, viszonylag szûk körben képes problémamegoldásra. A problémakör általában egy szûk szakterület és a probléma megoldása az emberi szakértõkhöz hasonlóan szakvélemény, tanács, vagy esetleg egy konkrét értékelés. A problémamegoldás képessége lényegében attól függ, hogy mennyi és milyen magasan kvalifikált ismeretanyag áll

rendelkezésre az adott tárgyterület vonatkozásában. A SZR-ek feladataik megoldásához általában nem rendelkeznek egzakt megoldó algoritmussal - a megoldást a rendelkezésre álló heurisztikákból építik fel a probléma és a tárgykör függvényében. A feladat specifikációjának és részben a megbízó céljainak figyelembevételével a rendelkezésre álló tudásra és képességekre támaszkodva oldja meg a feladatot. Emiatt a SZR-eknek lényegesen szorosabb kapcsolatot kell fenntartania a felhasználóval, mint a hagyományos rendszereknek. A SZR használata konzultáció révén valósul meg - a konzultáció során a rendszer újabb adatokat kérdezhet a felhasználótól, a felhasználó viszont magyarázatokat kérhet a feladat megoldásával kapcsolatban. A felhasználó szemszögébõl a SZR nagy része “fekete doboz”, amellyel csak a felhasználói felület révén kerül kapcsolatba. A szakértõi rendszerek felépítése A SZR olyan program, amely

több különálló részbõl, modulból áll. Az egyes moduloknak más-más a feladatuk, különféle módszerek alapján mûködnek és egy probléma megoldásánál természetesen együttmûködnek. A rendszer felépítését mutatja a következõ ábra: Az egyes modulok feladata a következõ: Ismeretszerzõ modul: A tudás, ismeret bebáplálását teszi lehetõvé, ezt segíti elõ. Lehetõvé teszi a formalizált ismeretek bevitelét, vagy a tudásbázis aktualitását. A SZR fejlesztõi, karbantartói használják (szakértõ, akinek a tudását modellezni kell, és a tudásmérnök, aki ezt a tudást képes átvenni, formalizálni és beépíteni a rendszerbe). Tudásbázis A tudásbázis a problémakör ismeretanyagát tartalmazza, ez a szakértõi rendszer hosszú távú memóriája. Kétféle ismerettípust tárol: - tényeket, amelyek bizonyos szituációkat írnak le, - heurisztikákat, amelyek olyan szabályok, módszerek, melyek a probléma megoldásánál

közvetlenül használhatóak. Az ismeretek különbözõ ábrázolási formában kerülhetnek a tudásbázisba, de egy szakértõi rendszer általában csak egy-két ábrázolási formát enged meg. A leggyakoribb tudásábrázolási formák: logikai kifejezések, szabályok, szemantikus hálók, framek. Következtetõ mechanizmus A SZR a logika következtetõ módszerei segítségével a tudásbázisból automatikusan újabb tényeket vezet le és interaktív módon újabb adatokat kér a felhasználótól. A következtetõ mechanizmus a következtetési sorozat végrehajtását vezérli. Sorra kijelöli a munkamemória és a tudásbázis tényei alapján a következtetéshez felhasználható szabályokat, eljárásokat. Ha pl. egy szabály feltétel része teljesül, a következmény, mint új tény, a munkamemóriába kerül Ha ez a tény nem a keresett megoldást adja, további szabályok feltételrészét kezdi el vizsgálni. Alapvetõen két következtetési stratégiát

különböztethetünk meg: - adatvezérelt (forward-chaining) következtetést, amely a tényekbõl, kezdõ adatokból kiindulva keres egy megoldást; - célvezérelt (backward-chaining) következtetést, amely a bizonyítandó célból indul ki, és keresi hozzá azon tényeket, összefüggéseket, amelyek alapján be tudja bizonyítani a kitûzött célt. Munkamemória Konzultáció során a felhasználótól kapott vagy a következtetések során nyert új tények a munkamemóriába kerülnek. Ez a SZR rövid távú memóriája, adatai a konzultáció befejezése után törlõdnek. A munkamemória egy speciális formája a blackboard (tábla). Ha több SZR, vagy a SZR több modulja párhuzamosan dolgozik, és egymás eredményeit, vagy esetleg részeredményeit fel akarják használni, a tényeket egy közösen használható területre, a blackboardra küldik. (A blackboard használata külön adminisztrációt, felügyeletet igényel.) Magyarázatadó képesség A magyarázó

képesség révén a SZR következtetési folyamatába pillanthatunk be. A felhasználó kérdéseket tehet fel a rendszernek, amely tájékoztatja a felhasználót a megoldás aktuális állapotáról, megmagyarázza pl. a felhasználónak feltett kérdéseket, illetve a feladatmegoldás után megindokolja a rendszer javaslatát, megmutatja, hogy milyen összefüggéseket használt a megoldás során a rendszer. A következõ típusú kérdések tehetõk föl: - “Miért?”(why?), vagyis miért pont ezt az input adatot kéri a rendszer. Válaszul általában az éppen vizsgált szabályt mutatja meg a rendszer, de sok esetben lehetõség van az illetõ szabályhoz vezetõ végrehajtási út visszapörgetésére is. - “Hogyan?” (how?), azaz hogyan jutott a rendszer az adott következtetéshez, hogyan kapta ezt az eredményt. Válaszként visszafelé haladva a következtetési folyamatban sorra megnézhetjük az alkalmazott szabályokat, egyes rendszerek az eredményhez vezetõ

utat tömören összegezve indokolják. A munkamemória, illetve a tudásbázis aktuális állapotáról is lehet tájékozódni a “what is” kérdés segítségével, illetve egyes rendszereknek a “mi lenne ha.” (what if) kérdés is feltehetõ egy-egy változat kipróbálásához. Felhasználói interface A SZR-t különbözõ “státusú” emberek használják: - a kész rendszert alkalmazó felhasználó - a rendszert fejlesztõ tudásmérnök - a szakterület szakértõje, aki bizonyos esetekben fejlesztõként, másokban felhasználóként kerül kapcsolatba a rendszerrel. A felhasználói interface ezeknek az embereknek teszi lehetõvé az input adatok bevitelét, itt kapják meg a megoldást, vagy a kért magyarázatokat. A párbeszéd több formában jelenhet meg a képernyõn: szövegesen, menükbõl való választás révén, vagy ikonok kijelölésével. A párbeszéd az esetek többségében passzív, azaz a SZR kérdéseire kell válaszolnia a felhasználónak. A

SZR-t gyakorlatilag a felhasználói interface-n keresztül ismerjük meg, a többi modul rejtve marad számunkra. Alkalmazási területek Az utóbbi években egyre több területen alkalmazzák a szakértõi rendszereket. A statisztikák szerint 1990 után ugrásszerûen megnõtt a számuk - pl. az Egyesült Államokban az 1985-ös 50 alkalmazáshoz képest 1992-ben 12500 alkalmazást tartottak számon. Számos ipari, orvosi, üzleti élethez kapcsolódó alkalmazás ismert, de jelentõs mennyiségû szakértõi rendszer foglalkozik a mezõgazdaság, ûrkutatás, szállítás témakörével is. A relatíve legtöbb alkalmazás az orvosi és technikai diagnosztika területérõl származik, ami a könnyû megvalósíthatósággal magyarázható. A leggyakoribb problématípusok a diagnosztika, irányítás, konfigurálás, oktatás, tervezés, szimuláció, stb. Errõl ad rövid összefoglalást a [Bo] alapján készült táblázat: Problématípus Feladat Irányítás A rendszer

viselkedésének szabályozása az elõírt specifikációknak megfelelõen. Konfigurálás Objektumok összeállítása adott feltételek szerint Diagnosztika A megfigyelhetõ jellemzõk alapján a mûködési hibákra való következtetés Oktatás A tanuló tanulmányainak, viselkedésének vizsgálata Értelmezés Az adatok alapján egy eset leírására való következtetés Nyomkövetés A megfigyelések és a várakozások összehasonlítása Tervezés Eljárások tervezése Prognózis Következtetés adott szituációk valószínû következményeire Javaslat Javaslat a rendszer hibáinak megoldására Szelekció A lehetõségek listájában a legjobb válasz felismerése Szimuláció A rendszer komponensei közötti kölcsönhatások modellezése További részletesebb információért ld. pl [Bo], [LS], [Sá] Bizonytalanságkezelés Problémamegoldások, döntéshozatalok során gyakran kell bizonytalan - részleges, elégtelen vagy közelítõ

információval dolgoznunk. Különösen igaz ez a mesterséges intelligencia területén felmerülõ problémák esetén. Bizonytalanságról akkor beszélhetünk, ha vagy nem tudunk valamit, vagy nem pontosan tudjuk azt, vagyis amikor tudásunk - hiányos, - nem teljesen megbízható, - ellentmondásos : van olyan információ, amelyet bizonyos források valószínûsítenek, más források kizárnak. A statisztikus, illetve véletlen adatok kezelésének klasszikus módszere a valószínûségszámítás. Ez azonban sokszor nem alkalmas arra, hogy bizonyos területekre vonatkozó tapasztalataink alapján megfogalmazott heurisztikákat, a szokásostól eltérõ kivételeket, hiányos információkat kezeljen. Emiatt a mesterséges intelligencia feladatok megoldásánál, különösen a szakértõi rendszerek területén más bizonytalanságkezelõ módszerek is kialakultak. A bizonytalanság eredete, formalizálása Egy probléma bizonytalansága több forrásból származhat. Ez

mutatja a [Sá] alapján készült következõ táblázat: A bizonytalanság eredete Példa,szituáció a hiányos adat Egy kérdõívnek nincs kitöltve minden pontja b bizonytalan következtetés A megfigyelt tünetekbõl az adott betegség csak valószínûsíthetõ c bizonytalan fogalom, bizonytalan adat Kati szép. (Ki számít szépnek? Jóska annak látja, Feri nem) d bizonytalan adat Egy mérõmûszer nem elég megbízható. e ellentmondó adat, ellentmondó következtetés Az adatokból levonható következtetések egymásnak ellentmondanak. f ellentmondó következtetések Két különbözõ szakértõ ugyanazokból az adatokból egymásnak ellentmondó következtetéseket von le. g hiányos adat, így nincs Van-e intelligens élet a Földön kívül? alkalmazható következtetés h “még nem következett be” típusú adat Felel-e a gyerek holnap az iskolában? i bizonytalan adat, bizonytalan következtetés A probléma pontosabban is megfogalmazható

lenne, de annak megvalósítása költséges. Ezért megelégszünk egy olcsóbb, de kevésbé megbízható megoldással. j az adat biztos, csak nem tudjuk közvetlenül megfigyelni Van-e gyulladás a beteg gyomrában? A bizonytalanságkezelés modelljeit a következõ módszerekre szokták bontani: 1. Numerikus modellek A módszer lényege, hogy minden egyes rendszerelemhez (adathoz, állításhoz) egy, annak megbízhatóságát jellemzõ számot rendelnek. Ezekkel a számokkal egy elméletileg megalapozott kalkulus szerint végeznek különbözõ mûveleteket. Ez a módszer leginkább a bizonytalan adatok, bizonytalan fogalmak, hiányos adatok kezelésére alkalmas, vagyis a táblázat b,c,d,i,j esetében. 2. Szimbolikus (nem numerikus) modellek Vannak esetek, amikor a bizonytalanság mértékét nem lehet számszerûsíteni, hanem pl. egy hiányzó adat helyett csak feltételezéssel élünk, vagy ellentmondó adatokat, ellentmondásos következtetéseket kell kezelnünk. Olyan

modellt kell megalkotni, amely segítségével helytelen eredményre vezetõ következtetés esetén valamely korábbi feltételezés módosításával kiküszöbölhetõ az ellentmondás. Ilyen modell alkalmazását kívánja az a,e,f,g,h eset. 3. Heurisztikus módszerek Formailag hasonlítanak a numerikus módszerekhez, de az itt alkalmazott kalkulusok elméletileg nem megalapozottak, hanem bizonyos tapasztalatok alapján készült “ad hoc” modellek. Leginkább a c,i,j esetben alkalmazzák. A heurisztikus módszerek konkrét szakértõ rendszer alkalmazásokban kidolgozott eljárások. Ilyeneket használ pl. a MYCIN és a PROSPECTOR is A módszerek közötti választás mindig a megoldandó problémától függ - a probléma alapos elemzése után lehet csak kiválasztani a megfelelõ módszert. Az elemzés fontosabb kérdései a következõk: - Hogyan reprezentáljuk a bizonytalan információt? - Hogyan kombináljunk egy vagy több bizonytalan “információdarabkát”?

(Pl. az ÉS, VAGY, NEM logikai összekötõk alkalmazása során hogyan adhatjuk meg az eredmény bizonytalanságát.) - Hogyan következtethetünk (hogyan következtessünk) bizonytalan információkból? Mi lesz a bizonytalan feltételekbõl, bizonytalan szabály alkalmazásával kihozott következmény bizonytalansága? Hogyan dolgozzunk tovább, ha több szabály - mint különbözõ ismeretforrások - ugyanazt a következményt hozza ki, de különbözõ bizonytalansággal? Numerikus modellek A bizonytalanságkezelés numerikus modelljeinek elmélete a legjobban kidolgozott a bizonytalanságkezelõ módszerek közül. A legismertebb módszer a legrégebben kidolgozott és gyakran használt Bayes módszer, valamint az alkalmazások körében egyre jobban tért hódító fuzzy modell. Bayes szabály A Bayes módszer a valószínûségelméletben kidolgozott feltételes valószínûség fogalmára épül. Egy A eseménynek egy B eseményre vonatkozó feltételes valószínûsége

tulajdonképpen azt fejezi ki, hogy ha tudjuk, hogy a B esemény bekövetkezett, akkor ez mennyire változtatja meg az A esemény bekövetkezésében való bizalmunkat. A Bayes tétel az okok valószínûségét vizsgálja az esemény bekövetkezésének függvényében, és ennek kiszámítására ad egy összefüggést. Emiatt ezt a tételt szokták az “okok valószínûségének tételeként” is emlegetni. Az elnevezést az indokolja, hogy a Bayes-tételt leginkább akkor alkalmazzák, amikor egy A esemény bekövetkezésébõl akarnak a Bk (k = 1,2,.) hipotézisek (okok) valószínûségére következtetni, azaz ha azt akarják vizsgálni, hogy az A esemény bekövetkezése mennyire támaszt alá vagy cáfol meg bizonyos következtetéseket. Egy orvosi szakértõi rendszer esetén pl. a Bayes tétel alkalmazásával a tünetbõl, mint feltételbõl tudunk következtetni a betegség, vagyis a hipotézis fennállásának bizonytalansági mértékére. A tétel precíz,

matematikailag megalapozott tárgyalását ld. [R], rövid, tömör ismertetõ jellegû tárgyalását ld. [Sá],[LS] A szabály alkalmazásának elõnyei: - szilárd elméleti alapok (valószínûségszámítás) - jól definiált szemanitka Hátrányai: - Nagyon sok valószínûséget kell megadni. (Pl egy 50 betegséget és 300 tünetet kezelõ diagnosztizáló rendszernél minimum 50*300 + 50 = 15 050 adatot. - Ezen adatok száma nõhet, ha nem egymástól független eseményekrõl van szó.) - Mi alapján adjuk meg az elsõdleges és a feltételes valószínûségek értékét? Statisztikai mintavétellel? A szakértõ megérzései alapján? . - Új hipotézis, új bizonyíték megjelenése esetén nehéz a korábbi számításokat módosítani. - Szakértõi rendszerek esetén a felhasználó “szakértõi szintû” magyarázatot kérhet. A tétellel kapcsolatos eredményekhez azonban nagyon nehezen fûzhetõ jól követhetõ magyarázat. Fuzzy modell A tudás

ábrázolásánál gyakran fordul elõ, hogy olyan tudást kell szabályba foglalni, amelyek bizonytalan, nehezen megfogalmazható tényeket tartalmaznak. Pl: “Ha a költségek magasak ,de a minõség kitûnõ, akkor a termék még eladható.” “Ha valaki elég fiatal, akkor valószínûleg könnyen tanul.”, stb Az elõzõ szabályokban több olyan kifejezés is szerepel, amely a hétköznapi életben megszokott, számítógépes rendszer számára viszont nehezen modellezhetõ. A “költségek magasak”, az “elég fiatal” vagy a “könnyen tanul” mind olyan tények, amelyek egyértelmûen nem számszerûsíthetõek. A második szabály esetén még a következtetés is bizonytalan Az ilyen tények kezelése, illetve az ilyen szabályok alkalmazása a fuzzy halmazok, illetve a fuzzy logika elméletének alkalmazásával lehetséges. Példa: A fuzzy modell alkalmazásának elõnyei: - A fuzzy modell szemlélete közel áll az ember napi valóság szemléletéhez. Itt nem

feltétlenül kell számszerûsíteni a bizonyosság mértékét, használhatjuk helyette a megszokott nyelvi kifejezéseket - amelyek gépben ábrázolt szimbolikus vagy mennyiségi mértékkel szoros kapcsolatban vannak. - Jóval egyszerûbb rendszerleírást tesz lehetõvé, mint a többi numerikus modell. - A fuzzy bizonyosságokkal könnyû számolni. Hátrányai: - A fuzzy tagsági függvény nem annyira szilárd elméleti megalapozottságú, mint például a valószínûségszámítás. Nem mindig nyilvánvaló, hogy hogyan kell megadni az “eleme” függvényt. - A kombinációs függvényeket is sok kritika éri. Például, ha két halmaznak nincs közös eleme, együttes bizonyosságuk a halmazok bizonyosságának minimuma, holott 0-nak kellene lennie. A fuzzy modell alkalmazásainak száma egyre nõ. Elsõ sikeres alkalmazása metróvonat vezérlésénél volt, de sikerrel alkalmazzák számos egyéb területen is. Hogy közeli példát említsek, érdekes

kísérletek folynak a Pollack Mihály Mûszaki Fõiskolán is a fuzzy szabályozások körében. Szimbolikus, nem numerikus modellek Különbözõ emberek más és más dolgokban hisznek, és mindenki a saját “axiómarendszerén belül” vonja le a (saját világában érvényes) következtetéseit. E következtetéseket gyakran kell visszavonnunk. Például: - idõnként megváltoztatjuk az emberekrõl, vagy bizonyos dolgokról alkotott véleményünket - gyakran hiszünk olyan (természetesnek látszó) dolgokban, amelyek ellenkezõjérõl nincs tudomásunk - ezt a nézetünket késõbb esetleg meg kell változtatnunk - a gyermek ennek révén képes új, korábbi világával ellentmondó ismereteket befogadni. Ezekben az esetekben nem tudunk bizonytalansági mértékekkel dolgozni, mint a numerikus modellek esetén, hanem olyan módszereket alkalmazunk, amelyek lehetõvé teszik a tévedés beismerését, vagyis azt, hogy ha helytelen következtetést vontunk le, akkor ezt

késõbb visszavonhassuk, módosíthassuk. Az ilyen következtetési módszert nem monoton következtetésnek nevezzük. Nem monoton következtetési rendszerek A hagyományos következtetõ rendszerek (pl. az elsõrendû predikátumkalkulus ) három fontos jellemzõje: a teljesség ( a rendszer minden érvényes formulája egyben tétel is, azaz található hozzá formális levezetés), konzisztencia (egy rendszer konzisztens - ellentmondásmentes - ha nincs benne olyan tétel, amelynek a negáltja is levezethetõ lenne) és a monotonitás. Ez utóbbi azt jelenti, hogy ha egyszer a rendszer axiómáiból kiindulva bizonyítottunk egy állítást, az végig érvényes marad, továbbá, ha egy új axiómát vagy új tényt adunk, ezek, és az ezekbõl levezethetõ állítások csak növelik az igaz állítások halmazát; újabb tudás hozzáadásával ez a halmaz sohasem fog csökkenni. Ha azonban olyan modellt akarunk létrehozni, amely hiedelmeken, feltételezéseken alapul, akkor ez

a hiedelemhalmaz nem tekinthetõ olyan “változtathatatlannak”, mint a matematikai axiómák halmaza - ismereteink növekedésével megváltozhat ez a hiedelemhalmaz, s elképzelhetõ, hogy egy korábban igaznak vélt állítás hamissá válik, vagyis az igaz állítások halmaza nem monoton növekvõ módon változik. A nem monoton következtetési rendszer a legvalószínûbbnek tûnõ feltételezéseket igaz állításoknak tekintve végez következtetéseket. Ha késõbb kiderül, hogy ez a feltételezés téves volt, akkor megváltoztatja, majd újravizsgálja az ebbõl adódó konklúziókat. A nem monoton következtetési rendszerek leírására sok formális elmélet született, ezek mindegyike a modális logikák elméletére épül. Ezekrõl a rendszerekrõl ad bõvebb áttekintést pl. [Sá] A nem monoton következtetési rendszerek esetén, mivel hiányos ismeretanyagon dolgoznak, nem várjuk el a hagyományos következtetõ rendszerek említett három

jellemzõjét (teljesség, konzisztencia, monotonitás). Ez azonban sok problémát vet föl Például: - Hogyan kell kiterjeszteni egy tudásbázist ahhoz, hogy meglévõ és hiányos ismeretek alapján is lehessen következtetéseket levonni? - Hogyan módosítsuk a tudásbázist új tények befogadásakor, régiek eltávolításakor? - Hogyan használjuk fel a tudásbázisban tárolt ismereteket olyan konfliktushelyzetekben, amikor a tárolt ismeretekkel ellentmondó következményhez jutunk? Összefoglalásul elmondhatjuk, hogy a bizonytalan tudás formális módszereinek alkalmazásával az emberi gondolkozást a klasszikus logikánál jobban megközelítõ, a valóságos világot jobban modellezõ programokat írhatunk. Az alkalmazható módszerek nagyon különbözõek, nem egységesek, nagy szerepe van bennük az intuíciónak, ami óvatosságra kötelez. A mesterséges intelligencia nyelvei Nincs tökéletes programozási nyelv. Egy programnyelvnek jól olvashatónak, jó

számítási képességgel rendelkezõnek, hatékonynak, stb. kellene lennie Ezt mindet nem tudja megvalósítani egy nyelv, de erre talán nincs is szükség. A legtöbb programozási nyelvet célirányosan dolgozták ki, vagyis hatékonyan alkalmazhatóak egy-egy speciális típusú feladatra. Üzleti, adatfeldolgozási célokra legtöbbször valamilyen adatbáziskezelõ nyelvet használnak (pl. COBOL, Dbase) A mûszaki, tudományos feladatok megoldására leginkább pl a FORTRAN, Pascal, C használható. Ahogy füvet is kevesen nyírnak ollóval, ha van fûnyíró, úgy általában MI alkalmazásokra is kevéssé használják pl. a COBOLT Erre a célra elsõsorban a LISP-et, illetve a PROLOG-ot dolgozták ki. Ezeknek a nyelveknek a segítségével az ember egy magasabb, a feladat megfogalmazásához közelebbi fogalmi szinten tudja megoldani a problémáját, és a megvalósítást egy alacsonyabb szintre, a gépi implementáció szintjére bízza. Az MI nyelvekkel szemben

támasztott elvárások 1. A szimbolikus számítások támogatása, szimbólumkezelés 2. Rugalmas vezérlési képesség 3. A próbálkozó programozási módszerek támogatása 4. Megszorítások, illesztések tovaterjedésének kezelése 5. Világos, jól definiált szemantika Részletesebben: 1. A szimbolikus számítások támogatása, szimbólumkezelés Bár többféle módon szervezhetjük a tudást (ld. tudásreprezentáció), mégis a legtöbbjük valamely szimbólum-mintákon való mûveletekkel implementálható. Emiatt van szükség olyan nyelvekre, amelyek inkább a szimbólumok, mint a numerikus adatok kezelését segítik. Az általunk vizsgált világ leírásának egyik hatékony eszköze a predikátumkalkulus. Erre épül a PROLOG. A szimbolikus struktúrák felépítésének egy másik fontos eszköze a lista. A lista elemek egy olyan sorozata, amelyben minden elem vagy egy újabb lista, vagy egy atomi szimbólum. A listák segítségével hatásosan lehet

ábrázolni különbözõ szimbolikus struktúrákat, mint a fa, tetszõleges gráf, logikai predikátumok, de még a hagyományos adatstruktúrák (pl. mátrixok) is megadhatóak az összetett listák segítségével. A listák kezelésére készült a LISP A PROLOG-ban is van listakezelési lehetõség, de a PROLOG elsõsorban a predikátumkalkulusra épül és csak speciális reprezentációs eszközként kezeli a listákat. 2. Rugalmas vezérlés Az intelligens viselkedés egyik alapismérve a rugalmasság. Abban mindenki egyetért, hogy a hagyományos programok mûködése - egy elõre meghatározott utasítássorozat lépésenkénti végrehajtása - nem tekinthetõ igazán intelligens feladatmegoldásnak. Az MI programok felépítésének legelterjedtebb módja a produkciós rendszerek ábrázolása. A produkciós rendszerekben a program egy szabályhalmaz, s ezeket a szabályokat az adatok által meghatározott sorrendben, az adatok illesztésével értékelhetjük ki. Az MI

különbözõ vezérlési stratégiákat használ. Ezek közül legtöbb a produkciós rendszerekhez kapcsolódik, és nagyon sok illesztéssel dolgozik. A PROLOG esetén magába a nyelvbe van beépítve az illesztési és keresési algoritmus. A LISP -ben ugyan nincs benne közvetlenül ez az algoritmus, de a szimbolikus számításokra való képessége könnyen alkalmassá teszi erre. 3. A próbálkozó programozási módszerek támogatása Az MI feladatok jellege miatt nagyon ritkán tudunk azonnal teljes és tökéletes programot adni egy konkrét feladat megoldására. Általában sokszor kell módosítani a programot a fejlesztés során. Ennek különbözõ okai vannak Pl: a/ A legtöbb MI feladat kezdetben rosszul definiált, s csak menet közben lehet javítani és pontosítani a feladatspecifikációt. b/ A problémamegoldás tartományfüggõ, azaz hiába vannak általános módszerek pl. a produkciós rendszerek vagy a keresési stratégiák alkalmazására, a

feladatmegoldás mégis erõsen függ attól, hogy mik alkotják a konkrét produkciós rendszert, hogy milyen tartományon kell keresnünk. c/ Sokszor heurisztikát építünk be a megoldásba, és maguk a heurisztikák is változhatnak, cserélõdhetnek a program fejlesztése során. d/ Az intelligens rendszerek valamiféle tudást használnak a feladatmegoldáshoz, s ez a rendelkezésre álló tudás is bõvülhet, változhat. e/ Az MI reprezentációk formalizmusai és struktúrái újak, nincsenek precízen, egyértelmûen, “recept szerûen” definiálva, emiatt többször kell kísérletezni a megfelelõ reprezentáció megtalálásával. Emiatt kell az MI nyelveknek támogatniuk a programalkotási “kísérletezést”. Ezért elvárjuk tõlük a következõ tulajdonságokat: - Modularitás Célszerû, ha a program kis, könnyen áttekinthetõ részekbõl tevõdik össze. Ily módon egy-egy kis modul könnyen módosítható, tesztelhetõ, stb. A PROLOG kis, áttekinthetõ

szabályokból épül fel, a LISP pedig különálló függvények gyûjteménye. - Fejleszthetõség Mindkét nyelven könnyen, rugalmasan lehet újabb nyelvi konstrukciókat létrehozni. - Magas szintû konstrukciók létrehozása Mindkét nyelvben lehetõség van arra, hogy a felhasználó által definiált függvények illetve predikátumok standardizálódjanak, vagyis a nyelv standard részévé váljanak. Továbbá fontos még, hogy jól fel lehessen használni a korábbi prototípusokat, jól olvasható és jól dokumentálható programokat lehessen készíteni, hogy a programfejlesztés során inkább interpretereket lehessen használni és csak a végsõ állapotban forduljunk a compilerhez. Végül fontos, hogy a fejlesztõ környezetek jó nyomkövetési, hibadetektálási lehetõségekkel is rendelkezzenek. 4. Megszorítások, illesztések tovaterjedésének kezelése Az MI feladatoknál gyakran elõfordul, hogy bizonyos értékek ismeretlenek maradnak a

problémamegoldás során mindaddig, amíg elég információ nem gyûlik össze róluk. Ezt az információt úgy tekinthetjük, mint az adott változó értékére vonatkozó megszorítások, elõírások sorozatát. Ily módon a szóba jöhetõ értékek halmaza egyre szûkül, míg végül eljutunk az összes megszorításnak (feltételnek) eleget tevõ értékig. (Pl orvosi diagnózis) Ezt a változók illesztésével lehet megoldani, vagyis úgy, hogy a változó értéke mindaddig ismeretlen marad, amíg egy megfelelõ értékkel nem tudjuk illeszteni. Ez mindkét nyelvben, a LISP-ben is és a PROLOG-ban is megoldható. 5. Világos, jól definiált szemantika A hagyományos programok sokszor a gép fizikai rendszerét, felépítését tükrözik vissza magasabb, emberközelibb szinten. Az MI nyelvek viszont inkább a matematikai, logikai formalizmust tükrözik, így jóval elegánsabb megoldást nyújtanak bizonyos feladatokra. A PROLOG a logikán alapszik, a LISP a rekurzív

függvények elméletén. Végül [Sá] alapján nézzünk egy összefoglaló táblázatot, amely összehasonlítja a PROLOG és a LISP jellegzetes ismérveit: PROLOG LISP Európában született a 70-es években. Az USA-ban született az 50-es években. A “PROgramming in LOGic” rövidítése. A “LISt Processing” rövidítése. Relációs (nem determinisztikus szemléletû). Funkcionális (determinisztikus) szemléletû. Elméleti alapok: matematikai logika. Elméleti alapok: -kalkulus. Alapelemek: predikátumok (logikai formalizmus, objektumok közötti relációk leírásai). Alapelemek: függvények (kalkulus formalizálása, Skifejezések). Nem algoritmikus, hanem leíró, deklaratív. Procedurális: elõírt sorrendû végrehajtás. Szimbólumfeldolgozás. Szimbólumfeldolgozás. Beépített végrehajtási mechanizmus, célvezérelt, visszalépéses kereséssel. A végrehajtási mechanizmust a programozónak kell megépítenie. Megegyeznek a program és

adatstruktúrák. Megegyeznek a program és adatstruktúrák. A programokat könnyû olvasni. A programokat nehéz olvasni. Európában (és Japánban) gyakorlati rendszerek építésére Az USA-ban sok MI kutatási használják, a japán 5g projekt bázisnyelve volt. Az USA- eredmény született LISP-ben, “az ban kezd népszerûvé válni. Formális leíró nyelvként MI assembly nyelvén”. egyre elterjedtebben alkalmazzák. A LISP programozási nyelv A LISP-et az 1950-es évek végén John McCarthy fejlesztette ki. Eredetileg McCarthy célja az volt, hogy egy olyan - a rekurzív függvények elméletére épülõ - nyelvet hozzon létre, amely inkább a szimbolikus, mint a numerikus számításokat támogatja. Bár ez az egyik legrégibb nyelv, továbbfejlesztett változatait még ma is használják, sõt, egyre több alkalmazása születik. Sõt, ez a programozási modell olyan hatékonynak bizonyult, hogy késõbb több funkcionális programozási nyelv is kialakult a

LISP filozófiájára alapozva. (Pl SCHEME, ML, stb) A LISP az adatokat is, programokat is listaként kezeli és ezekkel a listákkal manipulál. Neve is innen származik: LISt Processing language. (Rossz nyelvek szerint inkább a “Lot of Irritating Silly/Superfluous Parentheses” (egy csomó bosszantóan buta/fölösleges zárójel) kezdõbetûibõl alakult ki ez a név, s ez a megjegyzés, ismerve a LISP szintaktikáját, nem tûnik teljesen alaptalannak.) Kezdetben ez csak kis és egyszerû nyelv volt, melyben listákat lehetett létrehozni és bejárni, új függvényeket definiálni, egyenlõséget kezelni és kifejezéseket kiértékelni. A nyelv rekurziót és egyszerû feltételvizsgálatot tudott. Egy bonyolultabb függvényt ezeknek a primitív függvényeknek a segítségével lehetett definiálni. Az idõk során az ily módon definiált legjobb, leghasznosabb függvények is a nyelv részévé váltak. A nyelv a prefix jelölésmódot használja (pl. 7*9 helyett ( 7 9)

), ami a nyelvvel ismerkedõnek eleinte kényelmetlenséget jelent. Példa: A nyelvet bõvebben tárgyalja pl. [ST], [LS] A PROLOG programozási nyelv A PROLOG a logikai programnyelvek családjának legismertebb eleme. Az 1970-es évek elejére nyúlik vissza az a felismerés, hogy magát a logikát programozási nyelvként lehet használni. Az elsõrendû logika egy résznyelvéhez ugyanis hatékony kalkulus, tételbizonyítási módszer adható. Az elméleti alapok kidolgozása (Robert Kowalski) után Marsaillesben fejlesztették ki a PROLOG (PROgramming in LOGic) programozási nyelvet (Colmerauer, Roussel és társai). A PROLOG másik “fellegvára” Edinbourgh, de több hazai implementáció is készült. A nyelv az elsõrendû logika nyelvének egy olyan megszorítása (az ún. Horn klózok nyelve), amelyben a problématerület feltétel nélküli és feltételes állításokkal (“klózokkal”) írható le, egy megoldásra kitûzött konkrét feladat pedig az ezekben

szereplõ összefüggésekre vonatkozó kérdésként fogalmazható meg. Egy PROLOG program (általában rekurzív) szabályok (klózok) gyûjteménye, amelyben egy állításra több szabály is vonatkozhat. A PROLOG rekurzív szerkezete helyettesíti a hagyományos programok vezérlésátadó utasításait. Kowalski a logikai programozás lényegét a logikai és a vezérlési komponens szétválasztásában látja. Mint 1994 szeptember 13-i budapesti elõadásában is megfogalmazta: “PROLOG program = logika + vezérlés” A nyelv végrehajtási mechanizmusa alapvetõen a mintaillesztésre és a visszalépéses keresésre épül. Két kifejezés akkor illeszthetõ, ha a bennük szereplõ változókhoz találunk olyan helyettesítést, amelyek a két kifejezést közös formára hozzák. A visszalépéses keresés pedig az alternatív módon alkalmazható szabályok bejárására szolgál. A PROLOG a célállítás igazolását a (“ha-akkor”) szabályok felhasználásával

nyert részcélok igazolására vezeti vissza. Egy részcél igaz, ha van vele illeszthetõ tényállítás, vagy ha van rá illeszthetõ, igazolható szabály. Ellenkezõ esetben a részcél hamis, amikor is a rendszer visszalép és új részcél igazolásával próbálkozik. A PROLOG implementációkban realizált következtetési mechanizmus elméleti hátterét a rezolúció elve (Robinson, 1965.) képezi A bizonyítás indirekt: a bebizonyítandó cél akkor igaz, ha negáltját () hozzávéve a klózokhoz ellentmondásra jutunk. A következtetés a rezolúció szabálya alapján mûködik, aminek lényege nagyon leegyszerûsítve a következõ: ha “A B” és “ B C” igazak, akkor “A C” is igaz. A rezolúcióról és a PROLOG elméleti hátterérõl ld. pl [CL],[FGN],[K],[L], [Pá] A nyelv deklaratív problémaleírási módjából eredõen jól olvasható és könnyen módosítható. Hátránya viszont, hogy nem minden probléma fejezhetõ ki jól logikai

formalizmusban. Mivel alapja kétértékû klasszikus predikátumkalkulus, ezért nem alkalmazható a bizonytalanságkezelésre, illetve hiányos adatok kezelésére. (De vannak eredményes próbálkozások a fuzzy logikára épülõ PROLOG szerû nyelv kialakítására.) A nyelv másik hátránya, hogy logikai eszközökkel nem lehet megoldani a következetes vezérlést, a programfutás hatékonyságának emelése érdekében a PROLOG kénytelen nem logikai (procedurális) eljárásokat biztosítva kilépni a “tiszta logika” körébõl (ilyen pl. a visszalépést korlátozó “cut” eljárás). Példa: Gráfelméleti alapfogalmak Általános gráf: Az általános gráfot véges vagy végtelen sok csúcs és a csúcsokat összekapcsoló élek alkotják. Egy csúcsból legföljebb egy él vezet egy másik csúcsba Irányított gráf: Ha egy gráf éleihez irányt rendelünk, akkor irányított gráfhoz jutunk. Ha egy n csúcsból egy m csúcsba irányított él vezet, akkor azt

mondjuk, hogy m közvetlen rákövetkezõje n-nek; n-et szülõnek, m-et utódnak nevezzük. Az n-bõl m-be vezetõ irányított él jelölése: (n,m). Ha a gráfban van egy (n, n1), (n1,n2),.(nk-1,m), vagy rövidebben jelölve (n, n1, n2, , nk-1, m) élsorozat, akkor azt mondjuk, hogy irányított út vezet n-bõl m-be. Ekkor n-et õsnek, m-et leszármazottnak nevezzük. Útnak tekintjük az egyetlen irányított élet is és az egyetlen élet sem tartalmazó üres élsorozatot is. Az n-bõl m-be vezetõ utat n m módon jelölhetjük {n m} -mel az összes, n-bõl m-be vezetõ utat jelöljük. Ha egy út kezdõ és végpontja megegyezik, akkor azt mondjuk, hogy ez az út egy kört alkot. Fa gráf: A fa gráf egy speciális irányított gráf. Van egy kitüntetett csúcsa - a gyökér amelynek nincs szülõje Az összes többi csúcsnak pedig pontosan egy szülõje van Azokat a csúcsokat, amelyeknek egyetlen rákövetkezõje sincs, leveleknek nevezzük. A fa gráf

definíciójából látható, hogy a fa gráf nem tartalmaz kört. Példa: A baloldali ábra egy irányított gráf, melyben pl. c leszármazottja b-nek, b pedig ôse c-nek A gráfban utat alkot például a {b,c,f,e}élsorozat, kör pl. az {e,f}, a {c,d,c}, {b,c,f,e,b} élsorozat A jobboldali ábra egy fa gráf, melynek gyökere az r csúcs, egyik levele pedig a t. Az irányított gráf éleihez költségeket is rendelhetünk. Az (n, m) él költségét c(n,m)-mel jelöljük. Egy út költségét az utat alkotó élek költségeinek összegeként értelmezzük Ha az utat az (n, n1,., nr=m) élsorozat alkotja, akkor költsége: Értelmezzük azt a minimális költséget is, amellyel egyik csúcsból a másikba eljuthatunk. Ez a két csúcs közötti utak költségeinek minimuma. Jelöljük az n, m csúcsok közötti minimális költséget k*(n,m) - mel, azaz: Ha a két csúcs között nem létezik út, akkor a két csúcsra nem értelmezzük ezt a költség fogalmat, vagy gyakran

végtelen nagynak tekintjük az értékét. Logikai alapfogalmak A mesterséges intelligencia témaköreiben számos helyen alkalmazzák a matematikai logikát, emiatt tárgyaljuk most röviden az ide tartozó alapfogalmakat. A régi görög filozófusok számára alapvetõ probléma volt, hogy milyen formájú érveléseket, következtetéseket fogadnak el általánosan helyesnek, s milyeneket nem. A lehetséges érvényes következtetési formulák rendszerezésébõl alakult ki (ld. logikatörténet) a formális logikai rendszerek tudománya. A többes szám használata azért indokolt, mert a kiindulástól és a következtetési módoktól függõen több fajta logikáról is beszélhetünk. Ily módon beszélhetünk klasszikus vagy nem klasszikus, két vagy többértékû logikákról. A logika két alkotóelemre bomlik: a nyelvre, melyen az ismeretek kifejezhetõek és a következtetési rendszerre, (“gondolkodási szabályokra”), melynek segítségével a konkrétan

megadott ismeretekbõl bizonyos “többlet tudást” származtathatunk. A nyelv valós objektumok leírására szolgál, s segítségével ezekrõl az objektumokról fogalmazunk meg formális állításokat, melyek egy-egy interpretáció révén válnak konkréttá. A következtetési rendszer a nyelv által megfogalmazott formulákkal manipulál, s egy formula univerzálisan igaz voltát vizsgálja. A következõkben nézzük meg a klasszikus kétértékû logika felépítését! Klasszikus logika Klasszikus modellen olyan halmazt (úgynevezett alaphalmazt) értünk, amelyen definiálva vannak bizonyos függvények (mûveletek), relációk, és a halmaz elemei között lehetnek kitüntetett elemek (úgynevezett konstansok). (A matematikában a legtöbb modell ilyen) A klasszikus modellek természetesen nem egyformák. A leglényegesebb különbség köztük az, hogy milyen függvényeket, relációkat, konstansokat tartalmaznak. A relációk leírásához úgynevezett

predikátumszimbólumokat használunk. A logikák definiálásakor mindig a következõ módon járunk el: Elõször megadjuk a nyelv szintaktikáját, vagyis megadjuk a nyelv ábécéjét és a nyelvépítõ szabályokat, majd szemantikát rendelünk hozzá. A szemantika megadásakor a nyelv formuláihoz úgynevezett igazságértékeket rendelünk hozzá, vagyis olyan szabályokat fogalmazunk meg, melyek segítségével el tudjuk dönteni egy formula (vagyis egy állítás) igaz vagy hamis voltát. A legismertebb esetekben egy állítás kiértékelése során két igazságértéket - igazat és hamisat kaphatunk. Emiatt ezeket a logikákat kétértékû logikának is nevezik A vizsgált állítások lehetnek teljesen konkrétak, és lehetnek általánosabb érvényûek is. Ez utóbbiak a változók használata miatt válnak általánosabbakká. Az, hogy egy nyelv milyen tág világról tud beszélni, attól függ, hogy mennyire használunk benne változókat. Ha egyáltalán nem,

akkor nulladrendû nyelvhez jutunk Elsõrendû nyelvet kapunk, ha megengedünk elemváltozókat, másodrendût, ha függvények és predikátumok is szerepelhetnek változóként. A nulladrendû logikát szokták kijelentés-kalkulusnak vagy ítéletkalkulusnak is nevezni, az elsõrendû logika másik szokásos elnevezése: predikátum-kalkulus Nulladrendû logika A nulladrendû logika csak konkrét állításokkal foglalkozik. Precízebben: 1.1Definíció: A nulladrendû L0 nyelv szimbólumai: - ítéletváltozók (vagy logikai változók) - ítéletkonstansok (i, h) - logikai összekötõjelek: ∧ (konjunkció), ∨ (diszjunkció), ¬ (negáció), (implikáció) - zárójelek: (, ) Az ítéletkalkulus formuláit ezekbõl a szimbólumokból építhetjük fel a következõ módon: 1.2Definíció: Atomi formulának vagy atomnak nevezünk egy ítéletkonstansot vagy egy ítéletváltozót. 1.3Definíció: Formula, vagy teljes nevén jól formált formula: - egy atom, - ha ϕ és

ψ formulák, akkor (¬ϕ), ( ϕ∧ψ), (ϕ∨ψ), (ϕψ). 1.4Definíció: Egy szimbólumhalmazhoz tartozó nulladrendû nyelv a szimbólumokból készíthetõ összes jól formált formula. Eddig a nulladrendû nyelv szintaktikáját fogalmaztuk meg. A nyelv szemantikájának feladata, hogy a vizsgált nyelv kifejezéseinek értelmet tulajdonítson. Ez két lépésben valósítható meg, elõször interpretáljuk a formulát, majd az interpretált formulát kiértékeljük. Egy formula interpretációja azt jelenti, hogy a formula minden egyes ítéletváltozójához a logikai igaz vagy hamis értéket rendeljük minden lehetséges módon. A formula egy interpretációja egy lehetséges hozzárendelést jelent. Ha szerepelnek a formulában ítéletkonstansok, azokhoz is hozzá kell rendelni a jelentésüket. Az i-hez rögzített módon a logikai igaz, a h-hoz a logikai hamis értéket rendeljük. Az interpretált formula kiértékelését a mûveleti jelek szemantikája alapján

végezzük. Pontosabban: 1.5Definíció: Az L0-on való igazságértékelés egy olyan leképezés, amely L0 minden formulájához hozzárendeli az {i, h} halmaz valamely elemét a következõ igazságtábla szerint: ϕ ψ ¬ϕ ϕ∧ψ ϕ∨ψ ϕψ i i h i i i i h h h i h h i i h i i h h i h h i 1.6Definíció: Egy ϕ formula kielégíthetõ, ha van olyan I interpretációja, amelyben ϕ igaz. I-t a ϕ modelljének nevezzük. Formulák egy Φ halmaza kielégíthetõ, ha van olyan I interpretáció, amelyben minden ϕ∈Φ igaz. I-t a Φ modelljének nevezzük Jelölése: I |= Φ 1.7Definíció: Ha egy Φ formulahalmazt kielégítõ összes interpretáció kielégíti a ψ formulát, akkor azt mondjuk, hogy ψ a Φ logikai következménye. Jelölése: Φ |= ψ Ha ψ -t minden lehetséges interpretáció kielégíti (vagyis logikai következménye az üres formulahalmaznak), akkor azt mondjuk, hogy ψ logikailag igaz, vagy logikailag érvényes. Az ilyen

formulát tautológiának is nevezik. 1.8Definíció: Egy ϕ formula (Φ formulahalmaz) kielégíthetetlen (inkonzisztens), ha nincs olyan interpretáció, amely kielégítené ϕ-t (Φ-t). Példa A logika alapfeladata, hogy eszközt szolgáltasson annak eldöntésére, hogy egy állítás tétel-e vagy sem, vagyis, hogy következménye-e bizonyos axiómáknak és feltételeknek. Egy formula logikai következménye egy formulahalmaznak, ha minden olyan interpretációban, ahol a formulahalmaz minden formulája igaz, a vizsgált formula is az. Ennek eldöntésére különbözõ módszerek vannak, melyek részletesen olvashatóak pl. [FGN], [L], [Pá]-ban Elsõrendû logika Az elsõrendû logika megengedi az úgynevezett elemváltozók használatát, vagyis az állítások egy alaphalmaz elemeire vonatkoznak. Emiatt jóval általánosabb kijelentések fogalmazhatóak meg, mint a nulladrendû logikában. Itt olyan állításokat vizsgálhatunk, mint “minden elemre igaz, hogy .”, vagy

“van olyan elem, amelyre ” Precízebben: 2.1Definíció: Az elsõrendû L1 nyelv szimbólumai: - változók: x1 , x2 , . - konstansok: c1, c2 , . - n változós függvényszimbólumok ( n = 0,1,2,.) - n változós predikátumszimbólumok ( n = 1,2,.) - logikai összekötõjelek: ¬, ∧, ∨, - kvantorok: ∀ (univerzális kvantor), ∃ (egzisztenciális kvantor) - zárójelek: (, ) 2.2Definíció: Termnek nevezünk - egy változót, - egy konstansot, - ha f egy n-változós predikátumszimbólum és t1, . , tn termek, akkor f( t1, ,tn )-t 2.3Definíció: Ha p egy n-változós predikátumszimbólum és t1, . , tn termek, akkor p( t1, , tn ) atomi formula vagy atom. 2.4Definíció: Jól formált formula: - egy atom, - ha ϕ és ψ formulák, akkor (¬ϕ), ( ϕ∧ψ), (ϕ∨ψ), (ϕψ), - ha ϕ formula és x változó, akkor ( ∀xϕ ) és ( ∃xϕ ). 2.5Definíció: Egy szimbólumhalmazhoz tartozó elsõrendû nyelv a szimbólumokból készíthetõ összes jól formált

formula. Lényeges különbség a kijelentés-kalkulushoz képest az interpretáció módja. Az elsõrendû logikában ugyanis egy formula végtelen sok féle képpen interpretálható (szemben a nulladrendû logika véges sok interpretációjával). Az interpretáció ugyanis a következõt jelenti: 2.6Definíció: Egy elsõrendû formula interpretációja egy nem üres D halmaz (univerzum) és a rajta értelmezett következõ hozzárendelés: A formulában szereplõ összes konstanshoz hozzárendelünk egy-egy D-beli elemet. A formula minden n-változós függvényszimbólumához hozzárendelünk egy Dn D leképezést ( Dn = D ×.× D) A formula minden n-változós predikátumszimbólumához hozzárendelünk egy Dn {igaz, hamis} leképezést. Alapvetõ kérdés annak eldöntése, hogy egy formula igaz-e vagy sem, pontosabban, hogy vane olyan interpretáció, amelyben a formula igaz, vagy esetleg igaz-e bármely interpretációban. 2.7Definíció: Egy ϕ formula kielégíthetõ, ha

van olyan I interpretációja, amelyben ϕ igaz. I-t a ϕ modelljének nevezzük. Formulák egy Φ halmaza kielégíthetõ, ha van olyan I interpretáció, amelyben minden ϕ∈Φ igaz. I-t a Φ modelljének nevezzük Jelölése: I |= Φ. 2.8Definíció: Ha egy Φ formulahalmazt kielégítõ összes interpretáció kielégíti a ψ formulát, akkor azt mondjuk, hogy ψ a Φ logikai következménye. Jelölése: Φ |= ψ Ha ψ -t minden lehetséges interpretáció kielégíti (vagyis logikai következménye az üres formulahalmaznak), akkor azt mondjuk, hogy ψ logikailag igaz, vagy logikailag érvényes. 2.9Definíció: Ha a ϕ és ψ formulákra ϕ |= ψ és ψ |= ϕ , akkor a két formula logikailag ekvivalens. 2.10Definíció: Egy ϕ formula (Φ formulahalmaz) kielégíthetetlen (inkonzisztens), ha nincs olyan interpretáció, amely kielégítené ϕ-t (Φ-t). Példa 2.2 Formulák klóz alakja Ahhoz, hogy egy formula logikailag igaz voltát, vagy esetleg kielégíthetetlen

voltát meg tudjuk állapítani, a formulát célszerû speciális alakra hozni, hiszen ily módon tudjuk eldönteni a formulára vonatkozó kérdést. A továbbiakban ezen speciális alakú formulák vizsgálatára szorítkozunk. 2.11Definíció: Literálnak nevezünk egy atomi formulát vagy annak negáltját. Literálok diszjunkciója a klóz 2.12Definíció: A Q1 x1 . Qk xkϕ formulát prenex formulának hívjuk, ha Qi a ∀ vagy a ∃ kvantor és ϕ-ben már nincs kvantor. Ha xi - k különbözõek, és mindegyik szerepel ϕ-ben, akkor prenex normálformáról beszélünk. 2.13Definícó: Az olyan prenex normálformát, amelyben minden Qi univerzális kvantor és ϕ klózok konjunkciója, Skolem standard formának vagy klózformának nevezzük. Mint többek között [CL], [M], [Pá] is bizonyítja, van olyan algoritmus, amely segítségével bármely zárt formula átalakítható Skolem standard formává. Ez az átalakítás azért fontos, mert a következõ tétel alapján egy

formula kielégíthetõsége helyett elég a Skolem standard formájának kielégíthetetlenségét bizonyítani. 2.1Tétel: Legyen ϕ formula és ϕ a Skolem standard formája. A ϕ akkor és csak akkor kielégíthetetlen, ha ϕ kielégíthetetlen. A logikai programozás elméletében kitüntetett szerepet játszik egy speciális klóz, az úgynevezett Horn-klóz. 2.15Definíció: Horn-klóznak nevezzük az olyan klózt, amelyben legfeljebb egy nem negált atom szerepel. Horn-formula az olyan Skolem standard forma, amelyben szereplõ klózok Horn-klózok. Megjegyzés: Az A1 ∨ . ∨ Ak ∨ ¬ B1 ∨ ∨ ¬ Bn klóz átírható A1 ∨ ∨ Ak ← B1∧ ∧ Bn alakba Így speciálisan egy Horn-klóz A ∨ ¬ B1 ∨ . ∨ ¬ Bn ≡ A ← B1 ∧ ∧ Bn alakú Ha egyetlen pozitív literál sem szerepel a klózban, akkor a ¬ B1 ∨ . ∨ ¬ Bn ≡ ← B1∧ ∧ Bn jelölést használjuk. 2.3 Herbrand tétel Egy formula a definíció szerint akkor inkonzisztens, ha egyetlen

interpretációban sem elégíthetõ ki. Ez azt jelenti, hogy az inkonzisztencia eldöntéséhez az összes interpretációt meg kellene vizsgálni, ami gyakorlatilag lehetetlen. Erre a problémára adott megoldást 1930-ban Herbrand, melynek az a lényege, hogy lecsökkenti a modellek osztályát egy speciális alaphalmazra, a Herbrand univerzumon vett modellekre. 2.15Definíció: Egy kifejezést alapkifejezésnek nevezünk, ha nem szerepel benne változó. Ilyen módon használjuk az alapterm, alapatom, alapliterál és alapklóz elnevezéseket. 2.16Definíció: Egy Φ formulahalmaz HΦ Herbrand univerzuma a Φ-ben elõforduló konstansokból és függvényszimbólumokból képzett alaptermek halmaza. (Ha Φ-ben nincs konstans, akkor tetszõlegesen fölveszünk egyet. ) 2.17Definíció: Egy Φ formulahalmaz BΦ Herbrand bázisa a Φ-ben elõforduló predikátumszimbólumokból és a HΦ-ben szereplõ alaptermekbõl képzett alapatomok halmaza. 2.18Definíció: Herbrand

interpretáció a Herbrand univerzumon vett olyan interpretáció, amely a konstansoknak önmagukat felelteti meg, egy n-változós f függvényszimbólumnak pedig olyan leképezést, amely a t1, . , tn ∈ H termekhez az f(t1, , tn) ∈ H termet rendeli Legyen B = {A1,A2, . , An ,} a formulahalmaz Herbrand bázisa Egy I Herbrand interpretációt kényelmes módon egy I = {m1, m2, . , mn ,} halmazzal reprezentálhatunk, ahol mi vagy Ai vagy ¬ Ai (i = 1,2,) Ez azt jelenti, hogy ha mi = Ai, akkor Ai - t igaznak tekintjük, ellenkezõ esetben hamisnak. 2.19Definíció: A formula Herbrand modelljén egy olyan Herbrand interpretációját étjük, amely a formula modellje. Többek között [CL] és [L] bizonyítja a következõ fontos állítást: 2.2Tétel: (Herbrand) Egy klózforma akkor és csak akkor kielégíthetetlen, ha hamis a hozzá tartozó összes Herbrand interpretáción . Ez azt jelenti, hogy az inkonzisztencia eldöntéséhez nem kell megvizsgálni az összes

interpretációt, hanem elég csak a Herbrand univerzumon vett interpretációt vizsgálni. Ez lényeges felfedezés, hiszen ezt használja föl a a logikai programozás alapelve, a rezolúció is. Lásd, pl. [FGN], [L], [Pá] A logika rövid története A matematikai logika története több mint kétezer évre nyúlik vissza. Alapjait Arisztotelész (i.e384-322) rakta le szillogisztikus következtetési elméletével Munkája és - a ma már kevésbé ismert - társainak munkája a modern matematikai logikára is hatást gyakorol. Az ókortól a tizenhetedik századig gyakorlatilag nem történt változás ezen a területen. Újabb irányzatok csak a XVI-XVII. században alakultak ki Bacon (1561-1626), Descartes (1596-1650) és Leibniz (1646-1716) munkája nyomán. Leibniz foglalkozott elsõként a formális logika fogalmaival. Bár Leibniz érdemei elvitathatatlanok, a logika igazi fejlõdése csak a XIX. században indult meg. Boole (1815-1864) "The Mathematical Analysis

of Logic" címû könyve volt az arisztotelészi logika átalakításában az elsõ nagy lépés. Ez a munka az alapja a matematikai logika egyik irányzatának, a "logika matematikájának", a Boole-algebrának. Boole kutatási irányzatához tartozott és az õ mûvét fejlesztette tovább Jevons (1835-1882), Peirce (18391914), Schröder (1841-1902), Löwenheim (1878-1957). A másik irányzat, a "matematika logikája" arra törekszik, hogy lehetõvé tegye a matematika különbözõ ágaiban elõforduló állítások formális leírását. A matematika axiomatizálásával kapcsolatban Frege (1848-1932), Cantor (1845-1914) és Peano (1858-1932) nevét kell megemlíteni. A matematikai logika történetében fontos mérföldkõ Whitehead (1861-1947) és Russel (18721970) "Principia Mathematica" címû három kötetes mûve, amelyben egyesítik ezt a két irányzatot. ( Kis kitérõként megjegyzem, hogy akkor sem volt könnyû a tudósok élete Russel

és Whitehead tíz éves kemény kutatómunkájával fejenként minusz száz - száz fontot keresett, s összesen négy olyan embert ismertek, aki mindhárom kötetet elolvasta, két lengyelt, akiket késõbb kivégeztek a nácik és két amerikait, akik késõbb teljesen beolvadtak az amerikai életformába.) A "Principia Mathematica" megjelenése után további komoly fejlõdést jelentett Hilbert, Post, Ackerman, Gödel munkássága, amely a matematika egyes fejezeteinek ellentmondásmentességére vonatkozott és meghatározó volt a logika axiomatizálásában vagy más szóval élve bizonyításelméleti megalapozásában. A logikai problémák kutatása vezetett többek között a matematikai logika nyelvészeti tárgyalásához. Ebben a tárgyalásmódban - melyet modellelméletnek is neveznek - a logikát mint egy adott szintaxissal és szemantikával rendelkezõ formális nyelvet tekintik. A modellelméleti és bizonyításelméleti megközelítés

ekvivalenciájának bizonyítása egy sor algoritmuselméleti és bizonyításelméleti eredményre vezetett. (Church, Kleene, Lukaseiewicz, Tarski, Kalmár) A matematikai logika fejlõdése olyan önálló tudományterületek kialakulásához vezetett, mint a kiszámításelmélet (Boolos, Jeffrey, Cohen), a rekurzív függvények elmélete (Goodstein, Kleene), automatikus tételbizonyítási elméletek (Chang, Lee, Gallier, Loveland, Prawitz). Ez utóbbi terület fejlõdése a 30-as években kezdõdött Gödel, Skolem, Church, Kleene, Turing, Herbrand, Löwenheim munkássága alapján. Herbrand 1930-as alapvetõ tételére építve 1965-ben Robinson megalkotta a rezolúciós elvet, mely az automatikus tételbizonyítás alapelve lett. A rezolúciós elv az egységesítés segítségével tud formulákból újabb formulára következtetni. Ez egy cáfoló eljárás, amely teljes abban az értelemben, hogy kielégíthetetlen formulahalmaz esetén mindig ellentmondásra vezet.

Késõbb sok változatát vezették be (Chang, Kowalski, Robinson, stb), melyek a keresési tér csökkentésével növelik az eljárás hatékonyságát. A rezolúciós elvre épül a logikai programozás elmélete (Deville, Elcock, Kowalski, Lloyd). Az elméletet a 70-es évek elején Colmerauer ültette át a gyakorlatba megalkotva az elsõ logikai programnyelvet, a PROLOG-ot.(PROgramming in LOGic) A nyelv megalkotásához az elsõrendû logika egy részhalmazát, a Horn-klózokra épülõ Horn-klóz logikát vették alapul. A logikai programozás procedurális interpretációjában minden Horn-klóz egy procedureleírásnak tekinthetõ, és ezen procedure-k halmaza alkotja a programot. A "fõprogram"-nak a célmegadás felel meg, a program az itt feltett kérdésre keresi meg a választ. A procedure-k az illesztés segítségével aktivizálódnak. Egy programnyelv Horn-klózokra való leszûkítése szûkíti az alkalmazhatóság körét is. Ezért a 80-as években

élénk kutatás indult meg a logikai programozás körének kiszélesítésére. Vizsgálódások folytak a negatív premisszák bevezetésére vonatkozóan (Apt, Barbuti, Martelli, Lloyd, Clark, Chan, Reiter, Shepherdson, stb.) a deklaratív és procedurális szemantikák kidolgozására (Gelfond, Lifschitz, Kunen, Przymusinski, van Emden, Abiteboul, Vianu, stb.), a teljes elsõrendû logikára való kiszélesítés lehetõségeire (Lobo, Minker, Topor), magasabb rendû logikákra való kiszélesítésre (Maher, Mancarella, Pedreschi) és a logikai programozás különbözõ alkalmazási területeinek feltérképezésére. Kowalski szerint egy logikai program két összetevõre választható szét, a logikai komponensre, amely megadja az algoritmus logikáját, és a kontroll komponensre, amely megadja, hogy milyen módon oldja meg a logikai komponens a programot. A logikai komponens határozza meg a program jelentését, a kontroll komponens csak a hatékonyságba szól bele. Egy

ideális logikai programnyelv tisztán deklaratív Egy deklaratív programozási környezetben a programozónak csak az algoritmus logikai komponensét kell megadnia, s nem kell törõdnie a kontroll komponenssel. Egyéb logikák 1. Klasszikus többértékû logikák Minél több változótípus használatát engedjük meg, annál nagyobb a logika kifejezõereje, vagyis annál több fajta probléma modellezhetõ, formalizálható a segítségével. Idõnként azonban a legegyszerûbb mondatok is zavarba ejtenek. Mit mondhatunk pl errõl a mondatról: “Ez a mondat hamis.” Ez az úgynevezett “hazug” paradoxonok egyik klasszikus mondata, hiszen ez a mondat nem lehet sem igaz, sem hamis. A matematikában fontos szempont az ellentmondástalanság, így érthetõ, hogy az elõzõ ellentmondás felfedezése komolyan aggasztotta a matematikusokat, és megindultak az ellentmondás kiküszöbölésére irányuló kutatások. Az egyik lehetséges megoldási út az, hogy szakítunk a

kétértékûséggel és megengedjük, hogy a mondat az igaz, hamis értékek helyett egy harmadik értéket kapjon, pl.: ismeretlen, közömbös, bizonytalan, stb. Ekkor feloldódik az ellentmondás Ha megengedjük ennek a harmadik igazságértéknek a használatát is, akkor jutunk a háromértékû logikához. A háromértékû logikában is a konjunkció(∧), diszjunkció(∨), implikáció(), negáció(¬) segítségével juthatunk összetett mondatokhoz, csak a kalkulust kell egy kicsit bonyolultabban definiálnunk. A mûveletek szokásos értelmezése a következõ: Legyen I(A) az A állítás igazságértéke (szokás 0, 0.5, 1-gyel jelölni) Ekkor I(¬ A) = 1-I(A) I(A ∨ B) = max(I(A),I(B)) I(A ∧ B) = min(I(A),I(B)) I(A B) = 1 ha I(A) ≤ I(B) 0 egyébként Néhány ettõl eltérõ definíció is ismeretes, különösen az implikációnak vannak eltérõ definíciói, de mindegyik figyelembe veszi az általánosítás szokásos alaptörvényét, vagyis azt, hogy

megõrizze az eredeti összefüggéseket, azaz az igaz, hamis igazságértékekre ugyanazt az eredményt adják, mint a kétértékû logika. Örömmel tapasztaljuk, hogy a háromértékû logika bevezetésével megszûnt a kínzó ellentmondás. Örömünk azonban koránt sem lehet teljes Könnyû ugyanis olyan másik mondatot megfogalmazni, amely a most rendelkezésre álló három igazságérték egyikét sem veheti föl. (Pl: “Ez a mondat hamis vagy közömbös”) Ennek kiküszöbölésére persze bevezethetnénk egy újabb igazságértéket, de akkor újabb ellentmondásos mondatokat lehet találni. Belátható, hogy minden véges értékû logikában megfogalmazható ellentmondást okozó mondat. Ugyanakkor nem ismerünk ilyen mondatot végtelen értékû logikák esetén A végtelen értékû logikák közös jellemvonása az, hogy a mondatok végtelen sok igazságértéket vehetnek fel. Ezek az értékek pl a [0,1] zárt intervallum számai Az eltérés a kalkulus, vagyis a

mûveletek definiálásában van. Elõször a 20-as évek elején Lukasiewicz vezetett be végtelen értékû logikát, azóta több fajta végtelen értékû logikát sikerült kidolgozni. Ezek közül egyik az egyre ismertebbé váló fuzzy logika A végtelen értékû logikák kialakulását más forrás is táplálta: a kvantummechanika, melyben a véletlen események fontos szerephez jutottak. A kvantummechanika matematikai megalapozása és a véletlen matematikai vizsgálata során kialakult egy új logika, melyet valószínûségi logikának neveznek. A valószínûségi és a fuzzy logika kalkulusának eltérése miatt a két logika között lényeges eltérések mutatkoznak, ugyanakkor ismert tény, hogy létezik közös általánosításuk, ezt standard bizonytalansági logikának nevezzük. Ismeretek reprezentációjánál gyakran van szükség a bizonytalanság kezelésére. Jelenleg a bizonytalanság kezelésére alkalmas összes ismert módszer ennek a standard

bizonytalansági logikának valamilyen praktikus formába öltöztetett speciális esete. 2. Nem klasszikus logikák Történetileg a legegyszerûbb nem-klasszikus nyelveket olyan mondatok formalizálására hozták létre, mint pl.: “Lehetséges, hogy .” “Szükségképpen igaz, hogy .” Késõbb S. Kripke a nevét viselõ modellek segítségével definiálta az ilyen mondatok pontos szemanikáját. Az egyik legismertebb nem klasszikus logika a modális logika. A modális nyelv ábécéjét úgy kapjuk a (nullad-, elsõ- vagy másodrendû) klasszikus nyelv ábécéjébõl, hogy ahhoz két új jelet (“modális kvantort”) csatolunk. Ezek a ◊(“lehetséges”) és a  (“szükséges”) jelek Természetesen a modális logika szintaktikája és szemantikája is precízen épül fel, de most nem foglalkozunk ezek bemutatásával. A modális logika egy - az idõbeliséget jobban kihangsúlyozó - változata az úgynevezett temporális logika. Itt a ◊ és a  kvantorok

helyett az egyetlen “amíg” kvantort definiálják A temporális nyelv valamivel általánosabb, mint a modális. Az említetteken kívül egyéb logikák is definiálhatóak a Kripke modellek segítségével, de ezek bemutatásával sem foglalkozunk. A fuzzy halmaz fogalma A filozófusok jó ideje egyetértenek abban, hogy a túlzott egzaktság sokszor mesterséges és erõltetett. Mint Bernard Russell írja 1923-ban Vagueness címû cikkében (Australian J Phil 1 84-92): ". minden hagyományos logika feltételezi a precíz szimbólumok használatát Emiatt nem alkalmazhatóak erre a földi életre, csak egy képzeletbeli mennyei létre." A mindennapi élet fogalmainak, szituációinak leírására nagyon hatékony eszköz a természetes emberi nyelv. Azt tapasztaljuk, hogy a beszélt nyelv fogalmai sok bizonytalanságot tartalmaznak. Ha például azt mondjuk valakire, hogy okos, vagy hogy fiatal, magas, hogy nem lakik túl messzire innen, akkor nem határozzuk meg

teljes precízséggel, hogy mit is jelent az okosság, magasság, stb. Mit jelent az, hogy valaki fiatal? Ha egy osztályba vagy halmazba szeretnénk sorolni a fiatalokat, hamarosan komoly probléma elé kerülnénk. Ennek a halmaznak a határai elmosódottak. Nem minden emberrõl tudjuk egyértelmûen eldönteni, hogy beletartozik-e ebbe a halmazba vagy sem. Ha a hagyományos értelemben vett halmazfogalommal akarunk dolgozni, akkor a "határon" lévõket önkényesen vagy belevesszük a halmazba vagy sem. Épp ez az oka annak, hogy a precíz matematikai fogalmak nem mindig alkalmazhatóak a gyakorlatban. Kézenfekvõ megoldásnak látszik, hogy precíz igen-nem válasz helyett "elkent" válaszokat adjunk, vagyis minden egyes elemhez hozzárendeljünk egy mérõszámot, amely a halmazba tartozás mértékét jelöli. Minél kisebb ez az érték, annál "kevésbé" tartozik bele az illetõ elem a halmazba. Célszerû a mérõszámok skáláját a [0,1]

intervallumnak választani, vagyis a legesélytelenebb értéket a 0-val, a legesélyesebbet az 1-gyel jelölni. Ha minden egyes elemhez egy [0,1] közötti értéket rendelünk, akkor egy fuzzy (bolyhos) halmazt kapunk. A fuzzy halmaz fogalmát L.A Zadeh 1965-ben publikált dolgozata vezette be, s ez a dolgozat indította el e terület fejlõdését. A fuzzy halmaz gyakorlatilag a klasszikus halmaz karakterisztikus függvényének általánosítása. Precízebben: Definíció: Legyen D egy halmaz. A D feletti fuzzy halmaz egy F : D [0,1] függvény Az F függvényt szokták beletartozási függvénynek is nevezni, az F(d) ∈ [0,1] értéket pedig a d ∈ D elem halmazba tartozási szintjének vagy fokának. Ha F(d) = 0, akkor d nem tartozik F - hez. Ha egy F fuzzy halmaz csak a véges sok d1 ,., dn elemen vesz föl 0-tól különbözõ értéket, akkor az F fuzzy halmazra az { F(d1)/d1, . , F(dn)/dn } halmazjelölést is alkalmazzuk Ha F végtelen sok elemen válik 0-tól

különbözõvé, akkor a {(d,F(d)) | d ∈ D} jelölést használjuk. Ugyancsak szokásos az jelölés is, ahol (d,αd) ∈ D × [0,1]. Példa: A halmazelméleti mûveleteket többféle módon is általánosítják a fuzzy halmazokra. Általában a t-norma és t-conorma felel meg a metszetnek illetve az uniónak, de gyakorlati szempontból rendszerint elég ezek speciális eseteként a minimum és a maximum operátort alkalmazni, vagyis : F∪G(d) = max(F(d),G(d)) F∩G(d) = min(F(d),G(d)) Egy F(.) fuzzy halmaz komplementerének tekintjük az 1- F() fuzzy halmazt Az üres fuzzy halmaznak az azonosan 0 függvényt, az alaphalmaznak az azonosan 1 függvényt feleltetjük meg. Az így bevezetett mûveletekre a legtöbb halmazelméleti azonosság érvényben marad, de például egy fuzzy halmaz és komplementerének metszete nem feltétlenül az üres halmaz, és uniójuk sem adja ki az egész alaphalmazt. A fuzzy halmaz fogalmához vezetõ általánosítás folytatható részben

úgy, hogy a [0,1] egységintervallumot egy algebrai struktúrával (hálóval) helyettesítjük (pl. [No]), részben pedig a következõ módon: megengedjük, hogy a beletartozási függvény értéke maga is fuzzy halmaz legyen. Az ilyen fuzzy halmazt második típusú fuzzy halmaznak (vagy ultrafuzzy halmaznak) nevezzük. A második és magasabb típusú fuzzy halmazok fogalmát precízen definiálja [No], mi azonban most eltekintünk ettôl. Példa: A beszélt nyelvben gyakran használunk olyan kifejezéseket, mint "nagyon magas", "elég messze", stb.A fuzzy halmazok világába átvihetôek ezek a megfogalmazások A "nagyon", "elég", stb. kifejezéseket módosítóknak nevezzük, és [0,1] [0,1] típusú függvényekkel adhatjuk meg. Ilyen módosító például a nagyon(x) = x2 alig(x) = √x stb. Példa: Megjegyzés: A fuzzy adatmodellek megalkotásakor tárolási szempontok és az aritmetikai, összehasonlítási mûveletek egyszerûbb

kiértékelhetõsége miatt a lehetséges fuzzy halmazok körét leszûkítik, és csak a véges sok paraméterrel megadható speciális formájú fuzzy halmazokat használják. Folytonos tartományon csak trapéz alakú fuzzy halmazokat engednek meg, melyek speciális esetként tartalmazzák a háromszög és az S alakú fuzzy halmazokat is. A trapéz alakú fuzzy halmazokat négy számmal, a csúcspontok helyét jelzõ a, b, c, d értékekkel reprezentálják. Ez a halmazosztály elég bõ ahhoz, hogy a gyakorlatban elõforduló, folytonos halmazon adott bizonytalanságot modellezni lehessen. A szóban forgó halmazokat a következõ ábra szemlélteti: A fuzzy logika alapelemei Fuzzy logika terminológia alatt a nem hagyományos logika két ágát is értjük - mindkettõ a klasszikus kétértékû logika általánosítása. Ez a két ág a következõ: a/ Többértékû logika, vagyis az a logika, amelyben az igazságértékek egy adott halmaz rendszerint a [0,1] intervallum -

elemei. b/ Lingvisztikus logika, vagyis az a logika, melynek igazságértékei a természetes beszélt nyelv szavai, pl. igaz, többé kevésbé igaz, inkább hamis, stb Ezeket a kifejezéseket a [0,1] intervallum fuzzy halmazaival modellezhetjük. A fuzzy logika mindkét ágának precíz felépítése megtalálható pl. [No] könyvében A továbbiakban nem tárgyaljuk teljes részletességgel ezt a témakört, hanem megelégszünk egy leszûkített tárgyalásmóddal. A fuzzy logika szintaktikája a következõkbõl áll: A nyelv szimbólumai: változók: x1 , x2 , . konstansok: c1, c2 , . az igazságértékek szimbólumai: ; [0,1] n változós függvényszimbólumok: f1 , f2 , . n változós predikátumszimbólumok: p1 , p2 , . logikai összekötõjelek: ∧ (konjunkció), ∨ (diszjunkció), ¬ (negáció), (implikáció) kvantorok: ∀ (univerzális kvantor), ∃ (egzisztenciális kvantor) zárójelek: (, ) Termnek nevezünk egy változót, egy konstansot, és ha f egy

n-változós függvényszimbólum és t1, . , tn termek, akkor f( t1, ,tn ) - t A nyelv formulái: - az α igazságértékszimbólum - ha p n-változós predikátumszimbólum és t1, . , tn termek, akkor p( t1, ,tn ) - ha ϕ és ψ formulák, akkor (¬ϕ), ( ϕ∧ψ), (ϕ∨ψ), (ϕψ), - ha ϕ formula és x változó, akkor ( ∀xϕ ) és ( ∃xϕ ). A klasszikus elsôrendû logikához hasonlóan itt is bevezethetjük a szabad és kötött változó fogalmát. Ha t term és ϕ egy formula, akkor ϕx(t) azt a formulát jelöli, amelyet úgy kapunk, hogy ϕ-ben az x minden szabad elôfordulását t-vel helyettesítjük. Egy formula zárt, ha minden változó kötött benne. Egy formulát a következõ módon interpretálhatunk: Egy elsõrendû formula interpretációja egy nem üres D halmaz (univerzum) és a rajta értelmezett következõ hozzárendelés: - A formulában szereplõ összes konstanshoz hozzárendelünk egy-egy fuzzy értéket, {α/d}-t, ahol α ∈ [0,1] és d ∈ D. -

A formula minden n-változós f függvényszimbólumához hozzárendelünk egy n változós f fuzzy függvényt. (A fuzzy függvény fogalma többféleképpen értelmezhetõ, de mivel a késõbbiekben nem használjuk, ezért itt nem részletezzük.) - A formula minden n-változós predikátumszimbólumához hozzárendelünk egy P : Dn [0,1] leképezést. Minden egyes ϕ formulához hozzárendelhetjük a formula igazságértékét, v(ϕ) - t: - Ha α igazságértékszimbólum, akkor v(α) = α . - Ha t term, akkor v(t) az interpretációnak megfelelõ érték. - Ha ϕ és ψ formulák, akkor - v(ϕ ∧ ψ) = min( v(ϕ),v(ψ)) - v(ϕ ∨ ψ) = max( v(ϕ),v(ψ)) - v(¬ϕ) = 1- v(ϕ) - v(ϕψ) = I(ϕ,ψ), ahol I(x,y) implikációs operátor - v(∀xϕ ) = inf t∈D v(ϕ x(t)) . Megjegyzések: 1. Az interpretációban szereplõ D tetszõleges halmaz, így speciálisan fuzzy halmaz is lehet 2. Az itt definiált fuzzy logika erõs megszorítása és speciális esete a [No] által

definiált logikának, ahol az igazságértékek egy reziduális háló lehetséges elemei, és az általam említett, a klasszikus logikából ismert összekötõkön és kvantorokon kívül egyéb összekötõket és kvantorokat is értelmeznek. Egy ϕ formula α szinten igaz egy adott interpretációban, ha v(ϕ) =α . A formula -tautológia, ha v(ϕ) = α teljesül minden interpretációban. Ez utóbbi jelölése: |= ϕ [No] bebizonyítja, hogy |= ϕψ ⇔ v(ϕ) ≤ v(ψ) A formula igazságértékét az implikációs operátor segítségével értelmeztük, de az implikációs operátorok fogalma bõvebb kifejtést igényel. Az implikációs operátorok megválasztásával és tulajdonságaival kapcsolatban sok vizsgálódás folyik. A különbözõ implikációs operátorokat a normák és conormák segítségével értelmezik. Ezek a metszet és az unió mûveletének a fuzzy halmazokra való kiterjesztése, pontosabban: t-norma (trianguláris norma) egy T : [0,1]2 [0,1]

kommutatív, asszociatív, mindkét változójában monoton növekvõ függvény, melyre T(1,x) = x ∀x ∈ [0,1]. t-conorma egy S : [0,1]2 [0,1] kommutatív, asszociatív, mindkét változójában monoton növekvõ függvény, melyre S(0,x) = x ∀x ∈ [0,1]. Három fõ implikációs osztályt különböztetünk meg: 1. S - implikációk Ez a fajta implikáció a klasszikus implikáció = tulajdonságán alapszik, és I(x,y) = S(n(x),y) alakú, ahol S a többértékû diszjunkció kifejezésére szolgáló t-conorma, és n erõs negáció, vagyis n szigorúan csökkenõ, folytonos [0,1] [0,1] függvény, melyre n(0) = 1 és n(1) = 0. 2. R-implikációk Ez a klasszikus implikáció azon az elképzelésen alapul, miszerint az implikáció parciális rendezést indukál, vagyis I(x,y) = 1⇔ x ≤ y . Ez a fajta implikáció a reziduális hálók tulajdonságain alapszik - innen is származik elnevezése. Az R-implikációk általános alakja: I(x,y) = sup{ z ∈ [0,1] | T(x,z)

≤ y }, ahol T trianguláris norma. 3.QL implikációk Ez a kvantumlogikában használatos implikációs forma: I(x,y) = S ( n(x), T(x,y) ) , ahol S egy t-conorma, n egy erõs negáció, és T az S n-duálisa, azaz: T (x,y) = n( S( n(x), n(y) ) A következõ táblázatban összefoglaljuk a leggyakoribb implikációs operátorokat: jelölés név formula implikáció-típus I1 1 ha x ≤ y R ( T = min(x,y)) Gödel y egyébként I2 Lukasiewicz 1 ha x ≤ y S (S = min(1,x+y)) 1- x + y egyébként R (T = max(0,a+b-1)) I3 Goguen 1 ha x ≤ y R (T = xy) y/x egyébként I4 Kleene-Dienes max(1-x, y) S (S = max(x,y)) QL (S = min(1,x+y)) I5 Reichenbach 1 - x + xy S (S = x+y-xy) I6 Zadeh max(1-x,min(x,y)) QL (S = max(x,y)) I7 Gaines-Rescher 1 ha x ≤ y csak formálisan R 0 egyébként Más tárgyalásmód szerint az implikációs operátoroktól megkövetelik, hogy eleget tegyenek egy axiómarendszer feltételeinek. A legelfogadottabb feltételek a következõk: 1.

Ha x ≤ x akkor I(x,y) ≥ I(x,y) (elsõ változójában monoton csökkenõ) 2. Ha y ≥³ y akkor I(x,y) ≥ I(x,y) (második változójában monoton növekvõ) 3. I(0,y) = 1 (a hamis bármit implikál) 4. I(1,y) = y (a tautológia semmit sem indokol) 5. I(x,y) ≥ y (ψ(ϕψ) numerikus megfelelõje) 6. I(x,x) = 1 (az identitás elve) 7. I(x,I(y,z)) = I(y,I(x,z)) (felcserélhetõségi elv) 8. I(x,y) = 1 x ≤ y (az implikáció egy rendezést definiál) 9. I(x,y) = I(n(y),n(x)) valamely erõs negációra (kontrapozíció elve) 10. I folytonos A következõ táblázat megmutatja, hogy az elõzõekben értelmezett implikációs operátorok mely tulajdonságoknak tesznek eleget. jelölés tulajdonságok I1 1-8 I2 1-10 I3 1-8, 10 I4 1-5, 7, 9-10 I5 1-5, 7, 9-10 I6 2, 3, 4, 10 I7 1-3, 6-9 A táblázatokból is látható, hogy a Lukasiewicz implikáció az egyetlen olyan, amely mind a tíz feltételnek eleget tesz, és ez az egyetlen olyan, amely egyszerre R és S

impliáció is. Általában az S implikáció megsérti az identitási feltételt (6.) és nem definiál rendezést (8), az R implikáció viszont gyakran nem tesz eleget a kontrapozíciós elvnek (9.) A visszalépéses algoritmus nem rekurzív változata Vezessük be a következô jelöléseket: Jelölje Út az aktuálisan kipróbált útvonalat, vagyis azon csúcsok listáját, melyek az éppen vizsgált útvonalon helyezkednek el. Ha célállapotot talál az algoritmus, akkor Út a megoldási útvonal állapotainak rendezett listáját tartalmazza. Jelölje Csúcsok a kiértékelésre váró csúcsok listáját, vagyis azon csúcsokat, amelyek leszármazottait még nem vizsgáltuk. Rossz jelölje azon csúcsok listáját, melyek leszármazottaiból nem vezet út a célhoz. Végül jelölje Csúcs az aktuálisan vizsgált állapotot. Ekkor a visszalépéses algoritmus: Algoritmus Procedure visszalépés Út : = [Start]; Csúcsok : = [Start]; Rossz : = []; Csúcs : = Start while

nem üres (Csúcsok) do if cél (Csúcs) then return (Út) if van leszármazottja (Csúcs) (kivéve azokat, amelyek Rossz-ban, Csúcsok-ban vagy Út-ban vannak) then helyezze Csúcs leszármazottait (kivéve azokat, amelyek Rossz-ban, Csúcsokban vagy Út-ban vannak) Csúcsokba Csúcs : = elsô eleme (Csúcsok) fûz (Csúcs, Út) else while nem üres (Út) and Csúcs az Út elsô eleme do fûz(Csúcs, Rossz) töröljük Út elsô elemét töröljük Csúcsok elsô elemét Csúcs : = elsô eleme (Csúcsok) enddo fûz (Csúcs,Út) endif return (fail) end Példaként tekintsük a következô gráfot: Alkalmazzuk az algoritmust erre a gráfra a G célcsúcs esetén. Ekkor a következô lépésekben kapjuk meg a megoldást: Iteráció Csúcs Csúcsok sorszáma Út Rossz 0 A [A] [A] [] 1 B [BA] [BCDA] [] 2 E [EBA] [EFBCDA] [] 3 H [HEBA] [HIEFBCDA] 4 I [IEBA] [IEFBCDA] [H] 5 F [FBA] [FBCDA] [EIH] 6 J [JFBA] [JFBCDA] [EIH] 7 C [CA] [CDA] [BFJEIH]

8 G [GCA] [GCDA] [BFJEIH] [] Példák feladatreprezentációra 1. Tili-toli játék (8-as puzzle) Egy, a szakirodalomban gyakran bemutatott példa, a 8-as puzzle játék. A játék lényege a következõ: Adott egy 3 x 3 -as táblán nyolc, 1-tõl 8-ig számozott négyzet alakú lapocska, és egy üres hely. Bármelyik lapocska elmozdítható úgy, hogy a szomszédos üres helyre toljuk A feladat az, hogy adott kezdõállapotból kiindulva adott célállapotnak megfelelõ elrendezést alakítsunk ki a számozott lapocskákból. (A játékot sokszor 4 x 4 -es táblán játsszák, a könnyebb áttekinthetõség kedvéért azonban csak az egyszerûsített változattal foglalkozunk.) A játék egy állapota a nyolc lapocska egy konkrét elhelyezkedése. Az állapottér az összes lehetséges elhelyezkedést tartalmazza, ezek száma a lapocskák összes lehetséges permutációjának száma, azaz 9!=362880. A játék egy mûvelete, amikor az egyik lapocskát az üres helyre toljuk.

Egyszerûbb azonban az üres hely elmozgatásával definiálni a mûveleteket. Az üres hely egy elmozdításával egy állapotból egy másik állapotba kerülünk. A mûveleteket a következõ módon fogalmazhatjuk meg: 1. Az üres hely mozgatása fölfelé 2. Az üres hely mozgatása jobbra 3. Az üres hely mozgatása lefelé 4. Az üres hely mozgatása balra Egy állapotra nem mindig alkalmazható mind a négy mûvelet, ugyanis figyelnünk kell arra, hogy az üres hely ne kerüljön a táblán kívülre. A kezdõállapot egy tetszõleges elrendezés. A célfeltétel most közvetlenül a célállapot megadásával írható le. Meg kell jegyeznünk, hogy egy adott kezdõállapotból csak az állapotok fele érhetõ el, illetve, ha rögzítünk egy célállapotot, akkor ez csak a lehetséges állapotok felébõl érhetõ el. Számítógépes programban az állapotokat egy 3 x 3 -as egész típusú mátrix segítségével ábrázolhatjuk. Az üres helyet a 0, a többit a megfelelõ

számjegyek reprezentálják Egy mûvelet végrehajtása a 0 és a megfelelõ szomszédos számjegy felcserélésével oldható meg. Mind a négy mûvelet végrehajtása egységnyi költségûnek tekinthetõ. A játék egy reprezentációs fájának részlete, ahol a fa gyökere a startállapot: 2. Tic-tac-toe játék (amõba) Egy 3 x 3 - as táblán két játékos felváltva ír egy helyre X -et vagy O -t. A kezdõ állapot az üres tábla, a célállapot pedig az, ha három X szerepel egymás mellett egy sorban, oszlopban vagy valamelyik átlóban. Mivel egy konkrét játszmában nem fordulhat elõ az X és O összes lehetséges kombinációja, így a feladat állapottere az X, O összes lehetséges kombinációjának részhalmaza. Az állapottéren értelmezett mûvelet X vagy O elhelyezése felváltva valamelyik üres helyre. Számítógépes programban az állapotokat egy 3 x 3 -as, {X, O, üres} elemekbõl álló mátrix segítségével ábrázolhatjuk. Egy mûvelet

végrehajtása az üres és X vagy O felcserélésével oldható meg. Mivel egy lépés nem vonható vissza, ezért a reprezentációs gráf nem tartalmaz köröket. A szimmetrikus állások elhagyásával jelentôsen csökkenthetô az állapottér mérete. Az ily módon csökkentett reprezentációs gráf három elsô szintje látható a következô ábrán: 3. A 4-királynõ probléma A feladat szokásos megfogalmazása nyolc királynõre vonatkozik (8-királynõ probléma) és a következõképpen hangzik: Helyezzünk el egy sakktáblán nyolc királynõt úgy, hogy egyik se üsse a másikat. A könnyebb áttekinthetõség kedvéért ennek egy egyszerûsített változatát vizsgáljuk meg, ez pedig a következõ: Helyezzünk el egy 4 x 4 - es sakktáblán (a szokásos sakk-szabályok alapján) négy királynõt úgy, hogy egyik se üsse a másikat. Az állapotteret most sakkállások alkotják. Az állapotteret elsõ megközelítésben azok az állások alkotják, ahogy a

sakktáblán 0, 1, 2, 3 vagy 4 királynõt helyezünk el az összes lehetséges módon. Fölösleges azonban ekkora méretû állapottérrel foglalkoznunk, hiszen jóval kisebb méretû, és így jóval könnyebben kezelhetõ állapottérhez jutunk, ha csak olyan állásokat tekintünk az állapottér elemének, amelyek nem tartalmaznak egymással kölcsönösen ütésben álló királynõket. Ez a következõképpen érhetõ el: Legyen a 4 x 4 -es sakktábla mezõinek háromféle státusza: 1. Királynõ áll rajta 2. Egy korábban elhelyezett királynõ “üti”, azaz ide nem helyezhetõ el újabb királynõ 3. Szabad, elhelyezhetõ rá királynõ Ezekkel a státuszokkal rendelkezõ mezõkbõl kialakított állás nem tartalmaz kölcsönösen ütésben álló királynõket. Ha a királynõk száma 4, akkor egy ilyen állás célállapotot valósít meg. Egy mûvelet egy királynõ adott sor, adott oszlopába való elhelyezése. Számítógépes programban az állapotok egy 4 x

4 -es, mátrix segítségével ábrázolhatóak. A mátrix elemei a “királynõ”, “szabad”, “ütés” státusz, a fenti meghatározás szerint. A királynõ elhelyezésével a mátrixelemek státusza megváltozik. Az adott sor, adott oszlopába úgy helyezhetjük el a királynõt, hogy az egész sor, egész oszlop és a teljes fõ és mellékátló elemeinek státusza “ütés”-re változik, a megfelelõ elem pedig “királynõ”-re. Egy mûvelet csak akkor van értelmezve, ha még szabad mezõre akar királynõt elhelyezni. Ezen kívül megköveteljük, hogy egy sorba csak akkor helyezzünk el királynõt, ha az elõzõ sorba már tettünk. Az értelmezési tartomány ilyen megszorításával lényegesen csökkentettük a kezdõállapotból (üres sakktábla) elérhetõ állapotok számát, úgy hogy nem veszítettünk egyetlen célállapotot sem. Ez a reprezentáció sok, a feladat sajátosságait kihasználó információt tartalmaz, ezért lehetett ennyire

leszûkíteni az állapottér-reprezentációt. A következô ábra a feladat reprezentációs gráfját szemlélteti, x jelzi a tábla megfelelô mezôjére helyezett királynôt. 4. Hanoi torony A közismert feladat a következõ: Adott három különbözõ méretû korong (A, B és C) és három rúd (1, 2 és 3). Kezdetben mindhárom korong az 1-es rúdon helyezkedik el úgy, hogy felül van a legkisebb korong (A), alul a legnagyobb (C). Helyezzük át a korongokat a 3-as rúdra a 2-es segítségével úgy, hogy egyszerre csak egy korong mozdítható, és nem helyezhetõ egy korong egy nála kisebb korong tetejére. Minden állapot egyértelmûen megadható, ha megmondjuk azt, hogy melyik korong melyik rúdon helyezkedik el. Egy állapot egy háromelemû vektorral reprezentálható, melynek indexei rendre A, B, C, az egyes komponensek értéke pedig az 1, 2, 3 valamelyike. Ez a reprezentáció azt adja meg, hogy az A, B, C korongok rendre melyik rúdon találhatóak meg. Ennek

megfelelõen a kezdõállapotot az (1,1,1), a célállapotot a (3,3,3) hármas írja le. Az állapottéren értelmezett mûvelet a következõ: Az Mij mûvelet végrehajtása azt jelenti, hogy az i-edik rúdról a j-edik rúdra helyezzük át a legfölsõ korongot (1 i,j 3). Ennek az a feltétele, hogy a j-edik rúdon az áthelyezendõ korongnál kisebb korong nincs. A mûveletekhez költséget is rendelhetünk. Legyen ez a költség 1, 2 vagy 3, attól függõen, hogy a legkisebb (A), középsõ (B) vagy a legnagyobb (C) korongot mozgatjuk. A költségeket egységnyinek is tekinthetjük, ekkor az összköltség a mozgatások számát adja meg. A feladat reprezentációs gráfja: 5. Az utazó ügynök Egy ügynöknek meg kell látogatnia valahány várost, majd hazatérnie úgy, hogy minden várost csak egyszer érinthet az út során és - ismerve a városok közötti út költségét - az össz út költsége a lehetõ legkevesebb legyen. Figyeljük meg, hogy ez a célleírás az

egész bejárt útvonaltól függ, és nem az egyes állapotoktól. Konkrétan tegyük föl, hogy az ügynöknek A városból indulva el kell jutnia B, C, D, E-be, majd haza. A cél a legolcsóbb út A következô ábra a probléma egy lehtséges megadását mutatja. A gráf csúcsai reprezentálják a városokat, és a köztük lévô élekre pedig az utazási költség van ráírva : A feladat reprezentációs gráfjáról leolvasható több lehetséges útvonal is: Ilyen útvonal például az ABCDEA, melynek költsége 375 egység, de egyéb útvonalak is leolvashatóak, pl. ABCEDA (425 egység), ABDCEA (475 egység), stb Játékelmélettel kapcsolatos példák Példa játékgráfokra A kicsit is komolyabb játékok gráfja általában hatalmas méretû, de még a viszonylag egyszerû tic-tac-toe játék gráfja is jókora. Ezért most egy nagyon egyszerû játékot és annak játékgráfját illetve játékfáját mutatjuk be. Ez a játék a Grundy féle játék. A játék

kezdetén adott egy olyan pénzoszlop, amely legalább három pénzérmét tartalmaz. Az elsô játékosnak ezt a pénzoszlopot úgy kell kettéválasztania, hogy a lépése után kialakuló két oszlop különbözô számú érmét tartalmazzon. A második játékos a kialakult két oszlop közül választ egyet, amelyet az elôbb leírtak szerint bont ketté. Ezek után a játékosok felváltva választanak ketté egy-egy oszlopot két különbözô számosságú részre mindaddig, amíg ez lehetséges. Ez azt jelenti, hogy ha az összes pénzoszlop már csak egy vagy két érmét tartalmaz, akkor véget ér a játék. Az a játékos nyer, aki utoljára tudott lépni. A játék teljes játékgráfja (a számok az egyes pénzoszlopokban levô érmék mennyiségét, a betûk a soron következô játékos betüjelét mutatják) : A játék egy lehetséges játszmája: A játék teljes játékfája: Példa a két játékos szempontjából különbözô felépítésû ÉS/VAGY

fára Egy játékkal kapcsolatos alapvetô kérdés mindig a nyerô stratégia meghatározása. Ez azonban a két játékos számára más és más. Emiatt célszerû valamelyik játékos szempontjából felírni a játék fáját. Ez azt jelenti, hogy az illetô játékos a soronkövetkezô lépését tetszôlegesen teheti meg, vagyis ezek a lépések vagy kapcsolatban vannak, ellenfelének azonban minden lépésére fel kell készülnie, vagyis ezek a lépések és kapcsolatban vannak. Így ha valamelyik játékos szemszögébôl írjuk fel a játékfát, akkor egy ÉS/VAGY gráfot kapunk. Ha például az A játékos szempontját vesszük figyelembe, akkor abban az esetben, ha ô következik, bármelyik legális lépést megteheti, de B összes lépésére fel kell készülnie. Ez látható az elôzôekben ismertett Grundy féle játékhoz kapcsolódó alábbi ábrán. A baloldali ábra A szempontjából, a jobboldali B szempontjából épül fel. Az ÉS/VAGY fa alkalmas

reprezentációs eszköz az egyik játékos nyerô stratégiájának vizsgálatához. A szóban forgó játékos számára akkor létezik nyerô stratégia, ha a játék teljes ÉS/VAGY gráfjában létezik olyan részfa, amelynek terminális csúcsai mind az ô számára nyerô állások, és a kérdéses részfa tartalmazza a fa gyökerét, valamint ha egy csúcspontban az ellenfél következik, akkor szerepel benne az összes kimenô él, ha az adott játékos lép, akkor pedig legalább egy él. Az ábráról látható, hogy B szempontjából van ilyen megoldásfa (a jobboldali ábrán vastag vonallal jelölt részgráf), de A szempontjából nem létezik ilyen. (B szempontjából több megoldásfa is van.) Példa egy cimkézésre Tekintsük a következô fiktív játékfát! A levelekre a gyôztes játékos betûjele került. Az elôzô fa csúcsait a címkézési eljárással megcímkézve a következôt kapjuk (bekarikáztuk az eljárás során kapott cimkéket) : Az

ábráról leolvasható, hogy ezen játék esetén A számára van nyerô stratégia. Példa a minimax eljárásra A következô ábra a minimax eljárára mutat egy példát. Egy fiktív játék részgráfját figyelembe véve a leveleken szereplô számértékek az adott álláshoz rendelt kiértékelô függvény értékét, a többi csúcson a bekarikázott számok az eljárás során kapott értékeket mutatják. Vastag vonal jelöli az elljárás alapján legjobbnak tûnô kezdôlépést. Ha a vizsgált fa a játék teljes játékgráfja, akkor a levelekhez rendelt számértékek a nyerô (1), vesztô (-1) vagy döntetlen (0) állapotot mutatják. Ebben az esetben a minimax eljárás a nyerô stratégia meghatározására is alkalmas. A következô ábrán vastagon jelölt útvonalak az ily módon meghatározott nyerô stratégiát mutatják. Végül nézzük meg egy konkrét játék esetén is a minimax algoritmus mûködését! Legyen ez a játék a tic-tac-toe, azaz a

3x3-as amôba! Tegyük fel, hogy a minimax eljárás során egy állásból kiindulva mindig két mélységû játékfát generálunk.A fa leveleire a következô statikus kiértékelô függvényt alkalmazzuk: - Ha n nem nyerô állás egyik fél számára sem, akkor f(n) : = (a MAX számára nyitott sorok, oszlopok és átlók száma) - (a MIN számára nyitott sorok, oszlopok és átlók száma). (Egy játékos számára az a nyitott sor/oszlop/átló, amelyben még ki tud alakítani egy, a jeleibôl álló hármast.) - Ha n nyerô állás MAX számára, akkor f(n) : = ∞ - Ha n nyerô állás MIN számára, akkor f(n) : = - ∞ A következô ábrán MAX szempontjából határozzuk meg a legjobbnak tûnô kezdôlépést a fa gyökerében levô állásban. Példa az alfa-béta levágásra Az alábbi ábrán egy fiktíiv játékfa esetén példát láthatunk az alfa-béta levágásra. Szaggatott vonal jelzi az alfa-levágást, illetve a béta levágásokat. Példák

különbözõ vezérlési stratégiákra Példa a hegymászó algoritmusra Tekintsük a 8-as játéknál azt a W függvényt, amely minden állapothoz hozzárendeli a nem saját (célállapot szerinti) helyén álló lapocskák számát. Formálisan: ahol n jelöli a pillanatnyi állapotot, n(i,j) az i-edik sor j-edik oszlopában lévô lapocska sorszámát (vagy az üres helyet), t(i,j) pedig a célállapotban ezen a helyen lévô lapocska sorszámát. h egy logikai függvény, melynek értéke 1, ha változója igaz, és 0, ha argumentuma hamis. Ahhoz, hogy ezt a függvényt alkalmazni tudjuk, minden értékét meg kell szoroznunk -1-gyel, ekkor ugyanis maximumát (0-t) a célállapotban veszi föl. Más függvényt alkalmazva esetleg hamarabb juthatunk megoldáshoz. Ha például annak a függvénynek a -1 - szeresével dolgozunk, melyet úgy kapunk, hogy minden állapotban összeadjuk, hogy az egyes lapocskák hány mozgatásra (mekkora távolságra) vannak a célbeli

helyüktôl, akkor optimális megoldást kapunk. (Ezt a függvényt késôbbi hivatkozások kedvéért P(n)-nel jelöljük.) Elôfordulhat azonban az is, hogy egy rosszul választott függvény esetén egyáltalán nem jutunk megoldáshoz. Az elôbbiekben definiált függvények sem “jók” abban az értelemben, hogy minden esetben megoldáshoz vezetnének. Példa visszalépésre 1. Négy királynô Példaképpen nézzük meg a négy királynô probléma megoldását a visszalépéses algoritmus segítségével! Soronként próbáljuk elhelyezni a bábukat. Az azonos szinten alkalmazható szabályok között elôre rögzítünk egy fix sorrendet. Esetünkben azt a szabályt részesítse elônyben a stratégia, amely egy adott soron belül a legkisebb sorszámú szabad oszlopba helyez el királynôt. A globális adatbázis tartalmának változása követhetô végig az alábbi ábrán. X-szel jelöltük a királynôk elhelyezését, üresen hagytuk az ütésben álló és a

szabad mezôket. Egy állás áthúzása azt jelenti, hogy az adott szinten már nincs kipróbálatlan alkalmazható szabály. Ilyenkor kerül sor a visszalépésre Csökkenthetô a visszalépések száma, ha az azonos szinten alkalmazható produkciós szabályok közötti sorrendet valamilyen heurisztika alapján állítjuk fel. Ha például minden mezôhöz hozzárendeljük a rajta áthaladó hosszabbik átlónak a hosszát és egy-egy sorban a szabad mezôk közül mindig azt választjuk, amelyre ez az érték kisebb (illetve több egyforma esetén itt is betartjuk a balról jobbra sorrendet), akkor evvel a heurisztikával visszalépés nélkül talál rá az algoritmus a megoldásra. (Nyolc királynô esetén is) 2. Tili-toli játék A játék reprezenációs gráfja köröket tartalmaz, ezért célszerû mélységi korlátot bevezetni. Az említett körök közül speciális helyzetben vannak a 2 hosszúságú körök, (vagyis az üres hely húzása valahova és vissza), ezek

ugyanis könnyen kizárhatók. Az algoritmusnak elég csak azt figyelnie, hogy egy állapotra ne az abba vezetô mûvelet inverzét alkalmazza, vagyis ne a kettôvel magasabban lévô csúcsot hozza létre újra. Az alábbi ábrán a feladat megoldása látható adott kezdôállapot mellett. Az alkalmazható szabályok sorrendjét a következô módon rögzítettük: az üres hely fel, le, balra és jobbra. A mélységi korlátot 5-nek választottuk. Példa nyílt csúcs pointerének átállítására Az ábrán látható esetben az m csúcs pointerét és költségfüggvényének értékét át kell állítani, mert egy késôbbi kiterjesztés során jobb m-be vezetô utat találtunk. Példa gráfkersô algoritmusok használatára A következôkben a tili-toli játék megoldását mutatjuk be különbözô keresési algoritmusok esetén. Az ábrákon mindig feltüntettük a kiterjesztések sorrendjét is 1. Szélességi keresés Az alábbi ábrán nyomon követhetjük a

szélességi gráfkeresô eljárást, a csúcsok mellé írt számok a kiterjesztések sorszámát mutatja. Megjegyzés: Egységnyi élköltségeket feltételezve az elôzô keresés felfogható egyenletes keresésnek is. 2. Mélységi keresés mélységi korláttal A mélységi korlátot válasszuk 5-nek. Ekkor a keresés: 3. Elôretekintô keresés Válasszuk heurisztikus függvénynek a hegymászó algoritmusnál ismertetett W(n) függvényt, azaz rendeljük az n csúcshoz az adott állapotban nem a célállapotnak megfelelô helyen lévô lapocskák számát. Ilyen heurisztika mellett a keresés a következô: Az ábrán minden csúcspont mellé melléírtuk a megfelelô f(n) értéket. Vegyük észre, hogy ebben az esetben a hegymászó algoritmus ugyanilyen sorrendben terjeszti ki a csúcsokat. 4. A és A* algoritmus A W heurisztika teljesíti az A* algoritmus h(n)-re vonatkozó kikötését, vagyis alulról becsli a várható minimális költséget. Valóban, hiszen

ahhoz, hogy egy n állapotból célba érhessük, legalább W(n) mozgatásra van szükség. Ezért ilyen heurisztika mellett az A algoritmus egyúttal A* algoritmus is. Az ábrán szaggatott vonallal jelöltük a 3 kiterjesztés után adódó nyílt csúcsok halmazát. A továbblépéshez ezek közül kell kiválasztani azt, amelyhez tartozó f(n) érték a legkisebb. Más heurisztikát alkalmazva esetleg hamarabb jutunk megoldáshoz. Ha például a hegymászó algoritmusnál említett másik heurisztikát, P(n)-et (melyet úgy kapunk, hogy minden állapotban összeadjuk, hogy az egyes lapocskák hány mozgatásra (mekkora távolságra) vannak a célbeli helyüktôl), akkor a következô megoldást kapjuk: Végül hasonlítsuk össze a szélességi keresés és a W(n) heurisztikával rendelkezô A* algoritmus által felépített keresôgráfot. Az ábrán szürkével jelölt részgráfot építi fel az A* algoritmus, a teljes gráfot pedig a szélességi keresés. Példa

szemantikus hálóra A közlekedési eszközök egy csoportjáról mutat be egy szemantikus hálót a következõ ábra: A “közlekedési eszköz” csomóponthoz a “repülõ” és a “gépjármû” csomópont kapcsolódik az “ez egy” reláció segítségével. A csomópontok objektumokat jelölnek, és a reláció az osztályhoz tartozást fejezi ki. Hasonlóan a “személyautó”, a “busz” és a “teherautó” csomópontok is objektumokat jelölnek, amelyek a gépjármû osztályhoz tartoznak. A többi reláció már tulajdonságokat jelöl és a csomópontok a tulajdonságok értékeit tartalmazzák. (A tulajdonság további objektum is lehet.) A hálón megfigyelhetõ az öröklõdés: a gépjármû egy közlekedési eszköz, így örökli azt a tulajdonságot, hogy embereket szállít. Hasonlóan a személyautó és a busz is örökli ugyanezt a tulajdonságot, mivel a gépjármû osztályhoz tartoznak, a gépjármû pedig a közlekedési eszközök

osztályába. Sõt, e két objektumnál még további öröklõdést is megfigyelhetünk: a gépjármû osztálytól öröklik azt, hogy van motorjuk, és azt, hogy úttesten közlekednek. Természetesen nem biztos, hogy az öröklött tulajdonságok minden objektumnál azonos értékûek lesznek. Ha az autó objektum teherautó alosztályát nézzük, akkor ott a szállít tulajdonság értéke már nem az öröklött “emberek”, hanem tetszõleges “tárgyak” lesznek. Példa szabály alapú következtetésre Egy produkciós rendszer ismeretbázisa legyen a következõ: A∧BE C∧DG EH B∧GI E∧HX G∧EX I∧KX A kiinduló adatbázis legyen: {B, C, D, E} A szabályokat adatvezérelt következtetési stratégiával a leírás sorrendjében alkalmazva ez az adatbázis rendre a következõ értékekkel bõvül: G, H, I, X. (Megjegyzés: Ha a fenti szabályokat egyszerre, párhuzamosan alkalmazzuk, akkor is ugyanezt az eredményt kapjuk, de a “bõvülés” sorrendje

megváltozik. A párhuzamos vagy a szekvenciális alkalmazás ugyanarra az eredményre vezet, ha a szabályok egyike sem tartalmaz negációt. Negációt tartalmazó esetben azonban a helyzet sokkal bonyolultabb, és ekkor a szekvenciális, illetve párhuzamos kiértékelés más-más eredményt szolgáltathat.) Célvezérelt következtetési stratégia esetén legyen az elérendõ cél az X érték! Ekkor a CÉLVEZÉRLÉS algoritmusát és annak jelölésmódját alkalmazva a következõt kapjuk: 1. S = { E ∧ H X; G ∧ E X ; I ∧ K X} 2. Tegyük föl, hogy a szabálykiválasztás a leírás sorrendjében történik, így: R=E∧HX 3. G = {E, H} 4. S = { E H} 5. E benne van a kiinduló adatbázisban, vagyis a kiválasztott két szabály egymás utáni alkalmazásával ebbõl az adatbázisból levezethetõ az X érték. Példa fuzzy modellre Megadjuk egy egyszerû kis példa egy lehetséges formalizálását: Példa: “Piri nagyon kövér” “Piri közelítõleg

középkorú” “A kövér és középkorú embereknek célszerû abbahagyniuk a dohányzást.” Kérdés: “Pirinek célszerû abbahagyni a dohányzást?” Egy lehetséges formalizálás: kövér(Piri) / 0.8 középkorú(Piri) / 0.75 ∀x ( kövér(x) ∧ középkorú(x) ne dohányozzon(x) ) ne dohányozzon(Piri) / x A modellben természetesen meg kell adni x kiszámítási módját, vagyis azt, hogy a fuzzy logika melyik konjunkció definícióját és melyik implikációs operátorát alkalmazzuk. Egyik lehetséges megoldás, ha a konjunkciót minimumképzéssel és az implikációt a Gödel féle implikációs operátorral definiáljuk, ekkor x = 0.75 Természetesen lehet olyan modellt is készíteni, ahol a szabályokhoz is rendelünk bizonytalansági értékeket.(ld [AK2]) Példa egy LISP függvényre Az alábbi kis LISP függvénnyel a nyelv szerkezetét szeretném illusztrálni. A faktoriálist kiszámoló függvény feltételvizsgálatot

és rekurzív hívást tartalmaz: (defun factorial (arg)) (cond ((= arg 1) 1) ( t (* arg (factorial (- arg 1)))))) A “defun” függvény segítségével lehet definiálni újabb függvényeket. A “cond” függvény egy feltételsorozat kiértékelését végzi. Formája: (cond ( <teszt 1> <kiértékelés alanya 1> ) (<teszt 2> <kiértékelés alanya 2> ) . (<teszt n> <kiértékelés alanya 2> ) A kiértékelést a feltételek sorrendjében hajtja végre. Hamis igazságértékû feltétel esetén továbblép, és megvizsgálja a következõt. Ha ez igaz, végrehajtja a kiértékelés alanyát A program utolsó sorában szereplõ “t” feltétel az azonosan igaz (true) állítást jelenti. Példa egy PROLOG programrészletre Tekintsük a következõ klózhalmazt (figyelembe vettük egyes PROLOG implementációk azon elõírását, miszerint konstansot kis, változót nagy kezdõbetûvel jelöl): apja(lajos,peter). apja(lajos,pal).

apja(peter,tamas). apja(tamas,jozsi). apja(tamas,jani). apja(pal,laszlo). apja(pal,gabor). apja(gabor,imre). ose(X,Y):-apja(X,Y). ose(X,Y):-apja(X,Z),ose(Z,Y). Az “apja” predikátumra egyszerû tények vonatkoznak (szabályfej nélküli szabályok), az õse predikátumra pedig egy rekurzív, illetve egy nem rekurzív szabály együttese. A programrészlethez különbözõ kérdéseket (célokat) fogalmazhatunk meg. Pl: 1. ? apja(pal,gabor) 2. ? apja(pal,lajos) 3. ? ose(X,jozsi), stb Az elsõ és a második kérdésre hamar megtalálja a választ, a kérdésben szereplõ állítást megpróbálja az “apja” predikátumra vonatkozó tényekkel illeszteni. Elsõ esetben a kapott válasz “igen”, a másodikban “nem”. A harmadik kérdésre bonyolultabban találja meg a választ, hiszen az “ose” predikátumra vonatkozó szabályokat kell illeszteni. Az illesztést a leírás sorrendjében végzi, vagyis elõször az elsõ “ose” szabályt vizsgálja, amely igazzá

tételéhez az apja(X,jozsi) predikátumot kell illesztenie. Ez sikerül is, ha az X változóhoz “tamas”-t illesztjük Vannak implementációk, amelyek megelégszenek az elsõ megtalált megoldással - ebben az esetben külön be kell építeni egy mechanizmust, ha az összes megoldásra kíváncsiak vagyunk. Vannak azonban olyan implementációk is, amelyek az összes lehetséges megoldást megpróbálják felderíteni. Ebben az esetben figyelembe veszi a második szabályt is és azt is megpróbálja illeszteni. Ezt addig folytatja, amíg az összes lehetséges utat ki nem próbálta Ily módon a harmadik kérdésre adott válasz: ose(tamas,jozsi), ose(peter,jozsi), ose(lajos,jozsi). Példák logikai formulákra Példa nulladrendû logikai formulára Legyen egy nulladrendû formula pl. a következõ: (a ∧ ¬b) c ahol a,b,c úgynevezett ítélet változók. Lehetséges interpretációk például: 1. Jelentsék az ítélet változók a következõket: a : 1.5 < 2; b : 1

≤ 1.5 < 2; c : 1.5 < 1 ekkor az állítás igaz. 2. Legyen a, b, c a következõ három állítás: a : a síkidomnak három oldala van b : a síkidomnak egyenlõek a szögei c : a síkidom egyenlõ oldalú háromszög ekkor az állítás hamis. Példa elsõrendû logikai formulára Legyen egy elsõrendû formula pl. a következõ: ∀x [p(f(x,x),b) p(x,b)] ahol f függvényszimbólum, p predikátumszimbólum, x elemváltozó, b konstans (elemkonstans). Lehetséges interpretációk például: 1. Legyen D : = N (a természetes számok halmaza); ekkor a formula: ∀x ( xx = 1 x = 1) ez az állítás igaz. b : = 1; reláció f(x,y) : = xy; p : = az egyenlõség 2. Változtassuk meg az elõzõ interpretáció értelmezési tartományát, vagyis legyen D az egészek halmaza (Z), vagy a valós számok R halmaza. Ekkor már nem igaz az állítás 3. Legyen D a síkvektorok halmaza; b : = [1,0] vektor; f(x,y) : = x+y; reláció (⊥) p : = a merõlegesség ekkor a

formula:: ∀x ( 2x ⊥ [1,0] x ⊥ [1,0]), ami szintén igaz állítás. A fönti három interpretáció azt mutatja, hogy ez a formula kielégíthetõ (hiszen van olyan interpretáció, amelyben igaz), de nem érvényes (hiszen nem minden interpretáció elégíti ki). Példák fuzzy halmazokra 1.Példa: a/ A 10-hez közeli egészek jellemezhetôek pl. a { 0.1/7, 05/8, 08/9, 1/10, 08/11, 05/12, 01/13} halmazzal. b/ A 10-hez közeli valós számok pedig például az {(x,F(x)) | xR}, F(x) = [1+(x-10)4] -1 halmazzal. Grafikonon ábrázolva: c/ A 10-hez közeli valós számok a alakú fuzzy halmazzal is jellemezhetôek. Megjegyzés: Ez utóbbi alakú halmaz a könnyû kezelhetôség miatt elônyt élvezhet, ha a 10-hez közeli számokat valamely adatbázisban szeretnénk felhasználni. 2. Példa: Legyen D = { János, Péter, Zsófi }. Ekkor az "okosság"-ot jellemzô elsô típusú fuzzy halmaz lehet pl.az okos = { 0.9/János, 03/Péter, 06/Zsófi }, míg ugyanezt a

fogalmat második típusú fuzzy halmazzal például a következô módon adhatnánk meg: okos = { nagyon/János, alig/Péter, közepesen/Zsófi }, ahol az alig, közepesen, illetve nagyon maguk is fuzzy halmazok, melyeket pl. a következô módon értelmezhetünk: alig = { 0.8/01, 1/02, 08/03, 06/04 } közepesen = { 0.7/04, 08/05, 1/06, 08/07, 07/08 } nagyon = { 0.5/07, 07/08, 09/09, 1/1 } 3. Példa: Értelmezzük a "magas" tulajdonságot a magas = (180, 190, 190, ∞) trapéz alakú fuzzy halmazzal. Ekkor a nagyon (magas) és a 189 = nagyon(magas) állítás kiértékelését az alábbi ábra mutatja :