Döntéstámogató rendszerek
dr. Szűts István
Történeti áttekintés
60-as évek – TPS (Transaction Processing Systems) – tranzakciófeldolgozó rendszerek 70-es évek – MIS (Management Information Systems) – vezetői információrendszerek, VIR 70-es évek – OAS (Office Automatization Systems) – irodaautomatizálási rendszerekek 80-as évek – DSS (Decision Support Systems) – döntéstámogató rendszerek, DTR 80-as évek – ES (Expert Systems) – szakértő rendszerek , SzR 90-es évek EIS (Executive Information Systems) – felsővezetői információs rendszerek, FVIR
Összefoglaló elnevezésük: VTR Vezetéstámogató Rendszerek és MSS Management Support Systems 2
A döntéstámogató rendszerek használatának előnyei hatékonyabb döntéshozatal (minőség); költségcsökkentés; a döntéshozók közötti jobb kommunikáció; a vezetők (döntéshozók) gyorsabb betanulása. GIGO (Garbage in, Garbage out = szemét be, szemét ki)
A DTR felhasználói által vétett leggyakoribb hibák a következők: túlhangsúlyozzák a DTR-ek szerepét; az adatok pontosságának és fontosságának feltételezése; az objektivitásba vetett hamis illúzió. 3
A döntési folyamat részei feladat meghatározás és adatgyűjtés tervezés döntés megvalósítás (Herbert Simon: döntés = tervezés, szervezés, ellenőrzés)
A tudományos kutatás alapvető lépései a következők: megfigyelés, a probléma meghatározása, egy hipotézis megfogalmazása, kísérletezés, ellenőrzés, „jóslás”.
4
Struktúrált döntési problémák megoldása • információs összegyűjtése • a lehetséges kimenetek egy teljes halmazának megkeresése • az elemekhez egy eredmény (kívánatosság) hozzárendelése • a legkívánatosabb kimenetel kiválasztása
Nem jól strukturált problémák megoldásának lépései • identifikálás fázisa • fejlesztés fázisa • választás fázisa 5
A racionális döntéshozatalnak a következő kritériumai vannak: Konzisztencia Ha döntéshozatalkor kettő vagy több (megengedett) technikát használnak, a lehetséges eredményeknek, következményeknek ugyanazoknak kell lenni.
Folytonosság
Ha valaki a módszertan alkalmazásával két, nagyon hasonló döntést hoz, akkor a döntések eredményeinek úgyszintén nagyon hasonlóknak kell lenni.
Univerzalitás
A módszertannak általánosan alkalmazhatónak kell lenni üzleti és nem üzleti döntések egy széles körére és nem csak specifikusan a döntések egy osztályára 6
Egyértelműség
Csak egyértelmű és explicit információk alapján kapunk eredményt.
Nincs visszatartott információ
Ha bizonyos információkat visszatartottak és csak később használhatók fel, akkor a döntési javaslat menetközben lényegesen módosulhat.
Túl szigorú kritériumok
Gyakorlati problémák ezeket nem teljesítik.
7
Feladat meghatározás és adatgyűjtés • folyamatos figyelés, monitorozás • probléma észlelés • probléma azonosítás • probléma osztályozás (strukturált, nem strukturált) • részproblémákra bontás
8
Tervezési fázis modellezés: • elméleti alapok • struktúra • komponensek • kritériumrendszer • alternatíva generálás • előrejelzés • mérés • értékelés 9
Modell típusok
normatív leíró kielégítő
Normatív modellek: céljai
lehetnek: legeredményesebb, fix ráfordítás mellett legalacsonyabb költség megadott hatékonyság mellett legjobb hatékonyság (cél/ráfordítás)
10
A normatív modellek feltételrendszere Az emberek gazdasági alanyok, kiknek célja az elérhető célokból származó hasznosság maximalizálása. A döntéshozó mindig racionális. Egy adott döntési szituációban mind a lehetséges alternatívák, mind a hozzájuk rendelhető akciók és következmények ismertek, de legalább az előfordulási valószínűségeik adottak. A döntéshozónak világos preferencia-sorrendje van, ami lehetővé teszi számára a kívánatos kimenetelek rangsorolását. 11
A leíró modellek
Az összes alternatíva egy részhalmazát tekintjük át. A legjobb nem feltétlenül azonos az optimálissal, elégséges lehet egy elfogadható is. A kielégítő döntés
időhiány, erőforráshiány, költségek, optimalizáció nehézségei, az emberi döntések csak korlátozottan racionálisok 12
Alternatívák generálása DSS: manuális ES: automatikus
biztos kimenetel bizonytalan kimenetel determinisztikus, sztohasztikus kockázatos kimenetel
Az alábbi kimenetelek elemzése: legrosszabb eset legjobb eset a legvalószínűbb eset
13
Döntés (választás)
14
Választási technikák:
analitikus technikák – optimalizálás (struktúrált problémák): algoritmusok (lépésről-lépésre) a kívánt célállapot közvetlen elérése kiinduló állapotból keresési úton keresztül a célállapotba
15
Keresési technikák:
véletlen keresés heurisztikus keresés
Keresés iránya:
a célorientált – alapadat végállapot adatorientált – végállapot előfeltételek keresése kombinált
16
Az érzékenység vizsgálata lehet:
automatikus – a modell szolgáltatja,
próba – szerencse módszerrel,
„akkor, ha” – adott bemenethez milyen kimenet tartozik célkeresés – alternatív célokhoz a megfelelő bemenetek meghatározása és vizsgálata, kritikus sikertényező elemzése – a vállalat céljainak elérésében legfontosabb tényezők elemzése a modellen keresztül 17
Értékelés Bonyolult, több (esetenként ellentmondó) célok megoldása. Problémák: célhierarchia felállítása a résztvevők célrendszereinek különbségei a döntést hozó céljainak változása (időben és a körülmények függvényében) szervezeti célok különbözősége a célok objektív változása a célok és az alternatívák kapcsolatainak feltárása
Érzékenység vizsgálat. 18
EMBEREK
ÚJSÁGOK
RIPORTOK
TV
EGYÉB BENYOMÁSOK
ES, NLP A PROBLÉMA DEFINIÁLÁSA
ES
EIS ÉS ES
MENNYISÉGI ANALÍZIS (TERVEZÉS)
MINŐSÉGI ANALÍZIS (TERVEZÉS)
DÖNTÉS
DSS QM
GDSS
(VÁLASZTÁS)
IGEN
DSS ÉS
IMPLEMENTÁCIÓ
ES
19
DSS
STRATÉGIAI TERVEZÉS
MIS
VEZETŐI KONTROLL
ÜZEMELTETÉSI FELÜGYELET
TRANZAKCIÓS ELJÁRÁSOK
EDP
20
Megvalósítás A fenti folyamatok támogatása: adatgyűjtés: - MIS, EDP, EIS, ES, DSS tervezés:- DSS, ES választás: - DSS, ES megvalósítás:- DSS, ES
21
INFORMÁCIÓGYŰJTÉS Perceptív
Információkiértékelés
Intuitív
Szisztematikus
Receptív
22
AZ EMBERI PROBLÉMAMEGOLDÁS ÁLL:
HEURISZTIKUS ÉS TRANSZFORMÁCIÓS ELEMEKBŐL
A HEURISZTIKUS PROBLÉMAMEGOLDÁS BELSŐ SZERKEZETE NEM ISMERT
PRODUKCIÓS RENDSZEREK: EGY ZÁRT VILÁG ELEMEINEK TRANSZFORMÁCIÓS SZABÁLYRENDSZEREKÉNT HATÁROZHATÓK MEG. 23
Egyszerű logikai transzformáció az a következtetés pl., hogy az A személy B anyja és B a C személy anyja, akkor A csak C nagyanyja lehet Produkciós rendszer komponensei:
Munkaterület Produkciós szabályok rendszere Kontroll stratégia 24
Egyéni döntéshozatal Meghatározók
intuíció preferencia szubjektív értékelés tapasztalat
A kognitív folyamat
perceptív (rendszerszemléletű) receptív (analitikus) szisztematikus intuitív
25
Szervezeti döntéshozatal Csoportos döntések
a személyek közötti kommunikációs biztosítása egyetértés kialakításának technikái a csoportdöntés eredményének kifejezése
26
Tételezzük fel, hogy egy háromtagú család autót akar vásárolni, és a kiválasztott típus három színben kapható. Mindenki felírja egy darab papírra, hogy számára melyik szín a legvonzóbb, és melyik a legkevésbé az. Tegyük fel, hogy ennek eredményeként a következőket kapjuk: Apa Anya Kislány
sötétkék > citromsárga > meggypiros meggypiros > sötétkék >citromsárga citromsárga > meggypiros > sötétkék
Próbáljuk az egyedi sorrendekből a családi preferenciát meghatározni. Állapítsuk meg először is, hogy vajon a meggypiros vagy a sötétkék szín a kedveltebb a családban. Kettő az egyhez arányban a piros színt választják, hiszen csak az apa listáján előzi meg a kék szín a pirosat, azaz meggypiros > sötétkék
27
Hasonlóan megállapítható, hogy a citromsárga szín kedveltebb a családban, mint a meggypiros, hiszen mind az apa, mind a kislány jobban szeretné, ha ilyen színű lenne a családi autó, s csak az anya választana fordítva. Vagyis citromsárga > meggypiros E két következtetés együttes alkalmazásával (vagyis tranzitív módon) a család végül is a citromsárga színt fogja választani, s a sötétkék szín bizonyul a legkevésbé kedveltnek, vagyis a családi preferencia egybeesik a kislány egyéni sorrendjével, azaz citromsárga > meggypiros > sötétkék Tételezzük fel, hogy az anya elégedetlen a színválasztással, s egy másik következtetési módot javasol. Nevezetesen azt, hogy először hasonlítsák össze a kék és a sárga szín kedveltségét, majd pedig a pirosat és a kéket. 28
Az első esetben csak a kislány választaná inkább a sárga színt, tehát a családi szavazat sötétkék > citromsárga S csak az apa részesítené előnyben a kék színt a pirossal szembe, a többségi családi vélemény tehát meggypiros > sötétkék E két reláció együtt a következő sorrendet adja meggypiros > sötétkék > citromsárga
29
Végül belátható, hogy ha előbb a sárga és a piros színt, majd a kéket és a sárgát hasonlítjuk össze és többségi szavazással állapítjuk meg a preferenciákat, akkor az alábbi eredményre jutunk
sötétkék > citromsárga > meggypiros.
A fentiekben leírt eredmény Condorcet-paradoxon néven ismert, s úgy interpretálható, hogy a többségi szavazással csoportreferencia nem mindig állapítható meg, mivel az egyéni preferenciák összegezése nem szükségképpen ad egyértelmű csoportos véleményt.
30
Az Arrow – féle követelmények:
bármilyen csoport tag preferenciák esetén, elő kell állítani a csoportos preferencia sorrendet ha minden tag A-t preferálja B-vel szemben, akkor ennek a csoport preferenciában is tükröződni kell a csoport preferenciája két lehetőség között kizárólag a csoport tagjainak két lehetőség közötti preferenciájától függhet nincs a csoportban a saját akaratát mások rovására érvényesíteni tudó személy
Arrow szerint nem létezik olyan eljárás, amely a fenti négy feltételt egyidejűleg teljesítené. 31
DSS (Döntéstámogató rendszer), GDSS (Csoportos döntéstámogató rendszer)
32
DSS jellemezői
egyszerű szerkezet nagy volumenű adatkezelés könnyen ellenőrizhető módosítható fontos kérdésekben teljes körű egyszerűen használható
33
DSS TPS összehasonlítása Paraméter
DSS
TPS
Használat
Aktív
Passzív
Felhasználó
Vezetők
Beosztottak
Cél
Hatásosság
Hatékonyság
Időtáv
Jelen és jövő
Múlt
Fő szempont
Rugalmasság
Konzisztencia 34
További követelmények a DSS-el szemben:
bővíthető képes ad hoc értékelésekre és modellezésekre jövőorientált alkalmazható váratlan szituációkban is
Felépítése (Bonczek szerint):
kommunikációs rendszer tudás rendszer probléma megoldó rendszer
Hasonló felfogás a szakértő rendszerek felépítéséhez. 35
Definíció: A DSS-ek azok a döntéshozatal folyamán használható számítógépes rendszerek, amelyek a strukturált és kevéssé strukturált feladatok megoldásához is segítséget nyújtanak a beépített döntési szabályok és modellek felhasználásával, s ezeket a felhasználó is módosíthatja vagy bővítheti. A DSS tehát komplex döntési szituációk megoldásában segít, növelve a döntések hatásosságát.
36
DSS tulajdonságok
dinamikus együttműködés a számítógép és az ember között a különböző vezetői szintek támogatása Egyéni és csoportos döntési folyamatok támogatása elkülönülő és láncolt döntések kezelése a döntési folyamat végigkísérése különböző döntési stílusok és technikák támogatása rugalmasság és adaptivitás barátságos felhasználói felület hatásosság teljes körű felhasználói kontroll fejleszthetőség – belső és külső végfelhasználói fejleszthetőség 37
38
Külső és belső
Egyéb Számítógépes
adatok
rendszerek
Adatmenedzsment
Modellmenedzsment
Dialógusmenedzsment
Menedzserek (felhasználók)
39
A DSS részei
adatkezelő alrendszer modellkezelő alrendszer kommunikációs alrendszer
40
Adatkezelő alrendszer
DSS-adatbázis Adatbázis kezelő rendszer Adatszótár Lekérdezés
41
Adatbázis-kezelő rendszer funkciói:
DSS adatbázis
rekord-alapú hierarchikus hálós relációs objektumorientált
a DSS –adatbázis elérése, adatok kinyerése gyors adatfelújítások különböző forrásokból származó adatok együttes kezelése lekérdezések, jelentések (riportok) generálása az adatok biztonságának garantálása személyes és szervezeti adatok alternatíváinak kezelése az adathasználat nyilvántartása 42
Adatszótár Belső és külső adatok egységes kezelésére szolgáló adatbázis, amellyel a tárolt és felhasznált adatok forrása, állapota, kapcsolatai leírhatók és felhasználhatók.
Lekérdezés Speciális lekérdező nyelvek, adatbázis specifikus
43
Modellkezelő alrendszer Formailag hasonló részekre bontható, mint az adatbázis-kezelő alrendszer:
modellbázis modellbázis-kezelő alrendszer modellszótár modell végrehajtása 44
Modellbázis A modelleket a felhasználási szint és funkció szerint csoportosíthatjuk: stratégiai taktikai működtetési valamint modellblokk, illetve szubrutin típusúakra. 45
Modellbázis-kezelő alrendszer Feladata:
összeépíteni a modelleket blokkokból, szubrutinokból bővíteni a blokkok készletét részmodelleket összekapcsolni
46
Modellszótár Hasonló az adatszótárhoz o
o o
katalogizálja a modelleket tájékoztató információk modellekről esetleg segítség nyújtás a választáshoz
Modellvégrehajtás (aktuális futtatás) 47
Kommunikációs alrendszer A felhasználó
előfizetői mód rendszeres jelentés, nem interaktív
hivatalnoki mód változó tartalmú jelentés offline módon
terminál mód interaktív kérdés-felelet
közvetítéses mód kijelölt munkatársakon keresztül, kellő számítástechnikai ismeret hiányában felhasználó barát rendszerek esetében a közvetítők kiküszöbölődnek 48
A közvetítőket három csoportba lehet sorolni, lehetnek: DSS-asszisztensek DSS-specialista, szakmai és számítástechnikai felkészültséggel
specialisták üzleti szakterület szakértői
szakértők egy-egy modellezési módszer szakértői
49
DSS-hardver és – szoftver Steven Alter nyomán a döntéstámogató rendszerek 7 szintjét különböztetjük meg: javasló rendszerek (suggestion systems) optimalizáló rendszerek reprezentációs modellek könyvelési modellek elemző információs rendszerek (analysis information systems) adatelemző rendszerek adatkezelő rendszerek (file drawer systems) 50
Adatkezelő rendszerek
Egyszerű lekérdezések, szabálytalan időközökben
Adatelemző rendszerek
Periodikusan, vagy szabálytalan időközökben végzett adatmanipulációs tevékenység
Elemző információs rendszerek
Szabálytalan időközökben vagy felkérésre végzett adatelemzés kisebb modellekkel
Könyvelési modellek
Rendszeres időközökben végzett, standard modelleken alapuló elemzési, előrejelzési számítások 51
Reprezentációs modellek
Periodikus vagy ad hoc elemzések bizonyos részleges hatású lépések várható eredményeiről
Optimalizáló rendszerek
Periodikus vagy ad hoc elemzések bizonyos lépések várható eredményeiről optimalizáló modellekkel
Javaslattevő rendszerek
A napi munkafolyamatok irányítását segítő egyszerű döntési modellek alapján ad javaslatokat
52
Csoportos döntéstámogató rendszerek Három fő típusa: független döntéshozás független részdöntések sorozata csoportmunkát követelő döntéshozás
53
Definíció: A csoportos döntéstámogató rendszer (GDSS=Group Decision Support System) olyan számítógép alapú információs rendszer, amely képes nem strukturált problémák megoldásához segítséget nyújtani döntéshozók együtt dolgozó csoportjának. Egy GDSS-t hardver, szoftver, az alkalmazott módszerek és emberi résztvevők jellemeznek.
54
A csoportot érintő feladatok a következők: A csoporttagok szavazatainak, véleményének, modelleredményeinek numerikus és grafikus összegezése. (Nem feltétlenül összeadása – fontos lehet a megoszlás is.) A döntési alternatívák közös értékelése, az ötletek anonim gyűjtése és szelektálása, csoportvezető választása és más konszenzust igénylő akciók lebonyolítása. Az információk összes formájának továbbítása a csoporttagok között, illetve információcsere a GDSS adatbázisával 55
A GDSS tipológiája Döntési termek Döntési hálózat Távkonferencia Távoli döntéshozatal A GDSS viszonya a DSS-hez: a csoporttagok közötti kommunikáció lehetősége a szavazási, pontozási, értékelési technikákat, a konszenzus kialakításának eszközei több technikai-technológiai kiegészítő 56
DDS-ek készítése A DDS fejlesztési folyamata
57
A DSS fejlesztési lépései a következők:
tervezés – problémaanalízis, a DSS céljai, szükségletelemzés kutatás – a szükségletek kielégítésének lehetőségei: igények, erőforrások analízis – koncepcionális tervezés, normatív definíciók a rendszerre vonatkozóan kialakítás – részletes specifikáció, minden részrendszerre konstrukció – a DSS összeállítása, igen eszközfüggő implementáció – tesztelés, kiértékelés, demonstráció, betanítás, bevezetés karbantartás és dokumentálás – a rendszer élettartamára figyelemmel adaptáció – az újabb igények felmerülésének hatására
58
A DSS technológiai szintjei önálló DSS-ek DSS keretrendszerek DSS generátorok DSS eszközök A DSS fejlesztés megközelítései gyors fejlesztés lépcsőzetes-fejlesztés teljes DSS-fejlesztés 59
A DSS szoftverekkel szembeni követelmények interaktivitás és végfelhasználói használat könnyű hozzáférés a tárgyhoz tartozó szükséges információkhoz a felhasználók közötti kölcsönhatás a felhasználói igények változásaihoz történő gyors alkalmazkodás portabilitás megbízhatóság nagy teljesítmény 60
Szoftvereszközök DSS alkalmazásokra
általános programnyelvek táblázatkezelő programok DSS-keretek és – generátorok
61
DSS-alkalmazások OPTRANS OBJECT (francia DSS-fejlesztő környezet)
62
A generátor szerkezete A generátor legfontosabb részrendszerei (erőforrásai): adatbázis-kezelő rendszer a jelentéskészítő a modellező nyelv a file-kezelő rendszer (alkalmazási file) a statisztikai algoritmusok eszköztára és a felhasználói interfész 63
A főmenü Az interfész A felhasználó szövegszerkesztővel leírja az alkalmazás logikáját. A modellező nyelv A modell elkészítéséhez modellező nyelv szükséges. Riportgenerálás alkalmazásból való adatok és táblázatok grafikák egyszerűen illeszthetők a szövegbe riportok aktualizálása automatikus egy alkalmazási példa: benchmarkteszt különböző szoftvertermékek összehasonlító elemzésére 64
A döntés strukturálása A leggyakrabban a DSS-eket a következő döntéstípusokban alkalmazzák: forrásallokáció személyi döntések projektmenedzsment tenderezés beruházások
65
Tudásalapú rendszerek elméleti alapjai
66
Problémareprezentáció az MI területén Problémareprezentációk: állapottér-reprezentáció problémaredukciós reprezentáció AND/OR gráfok játékokat reprezentáló fák
67
Állapottér reprezentáció Elemei: állapotok, amelyek azok az adatstruktúrák, (adathalmazok),amelyek megadják a probléma minden egyes megoldási lépéshez tartozó feltételeket operátorok, amelyek az egyik állapotból a másikba transzformálják a problémát halmaz állapottér operátor - változókat is tartalmazhat (OSG) O:alkalmazott operátorok halmaza S: kezdeti állapot halmaza G: célállapot halmaza gyakran jellemezhető irányított gráffal csomópont-állapot élek-operátorok megoldás: út kezdő és a célpont között (költség hozzárendelés) 68
Problémaredukciós reprezentáció A problémákat részproblémákra bontja. Pl.: Hanoi-tornyok Problémareprezentáció, problémaredukció: egy kezdeti problémaleírás azon operátorok halmaza, amelyek a problémát részproblémákká transzformálják az egyes primitív problémák leírása
69
AND/OR GRÁFOK Egy AND/OR gráf a következő szabályok egymás utáni alkalmazásával jön létre:
Minden csomópont vagy egy megoldandó problémát, vagy egy megoldandó problémahalmazt reprezentál. A gráf tartalmaz egy kezdő csomópontot, amely az eredeti problémának van megfeleltetve. A primitív problémát reprezentáló csomópontot utolsó csomópontnak hívjuk, mivel innen nincs további elágazás a fában. A P probléma megoldásában használatos operátor minden lehetséges alkalmazása a P-t részproblémák halmazára bontja, ennek megfelelően él köti össze a P-t és a részproblémákat reprezentáló csomópontokat 70
AND/OR gráfok Játékokat reprezentáló fák Számítógépes játékok nagy része: sakk, gót, amőba
Két játékos játszik Szabályok írják le az elvégezhető lépéseket Ismert az ellenfél pozíciójáról az összes információ
„Játék”- fák: Kezdő vagy gyökér csomópont a kezdeti állapot
Minden út a játék egy lehetséges játszmáját adja 71
A „Játék” – fák két egymás ellen játszó játékos lépéseit mutatják be
Állapottérfák Az élei egy egyedülálló problémamegoldó lépéseit mutatják be
Az AND/OR fa A játékos szempontjait OR csomópontok reprezentálják, az ellenfél lehetséges lépéseit AND csomópontok reprezentálják.
72
Keresési eljárások Hegymászó (Hill-climbing) keresés függvények maximumának keresése függvényérték legnagyobb növekedése Visszalépés keresés (Backtracking) egyszerre csak egy utat tart nyilván zsákutcába jutott, visszalép alapváltozat nem garantálja a cél elérését végtelen méretű vagy kört ábrázoló gráfban: mélységi korlát, körök figyelése
Gráf keresés (Graph search) 73
Breadth-first (szélességben először) keresés
gyökér csomópont összes lehetséges kiterjesztésével kezdődik sok memóriát igényel
A breadth-first keresés a következő algoritmussal adható meg: Helyezzük a gyökér csomópontot egy OPEN (KEZDŐ) nevű listába, a nem kiterjesztett csomópontok listájába. Ha az OPEN csomópont egyben a cél csomópont is, a megoldást megtaláltuk. Ha az OPEN üres, nincs megoldás 74
1
3
2
4
5
6 75
Vegyük elő az első csomópontot, n-t az OPEN-ből, és rakjuk át a kiterjesztett csomópontok CLOSED listájába. Terjesszük ki az n csomópontot (állítsuk elő utódait). Ha nincsenek utódai, lépjünk vissza a 2. ponthoz. Helyezzük n összes utódait az OPEN lista végére. Ha az n csomópont utódai között van a cél csomópont, a megoldást megtaláltuk, ellenkező esetben a 2. lépés következik.
76
A depth-first (mélységben először) keresés A csomópont mélysége:
a gyökér csomópont mélysége 0 minden más csomópont mélysége 1-gyek több, mint az elődjének mélysége.
77
A csomópontok generálásának sorrendje (például): Tegyük a gyökér csomópontot egy OPEN (KEZDŐ) nevű, kiterjesztetlen csomópontokat tartalmazó listába. Ha ez a cél csomópont, akkor a megoldást megtaláltuk. Ha az OPEN üres, nincs megoldás. Helyezzük át az OPEN lista első elemét, n-t a CLOSED (ZÁRT) nevű, kiterjesztett csomópontokat tartalmazó listára. Ha az n csomópont mélysége a maximális mélységgel megegyezik, lépjünk a 2. pontra. Terjesszük ki n-t (azaz hozzuk létre az utódait). Ha nincsenek utódai, a 2. pont következik. Az n csomópont összes utódát rakjuk az OPEN lista elejére. Ha az n csomópont utódai között van a cél csomópont, készen vagyunk. Ellenkező esetben a 2. pont jön.
78
79
Branch-and bound (elágazás és korlátozás) keresés
hasonlít a hegymászó kereséshez a legkisebb költségű út
Best-first search (előretekintő keresés) Nem azt a csúcsot választja ki, amelyhez a legkisebb költséget rendelte, hanem azt, amelyikből várhatóan a legkisebb költséggel lehet célba jutni.
80
Tudásreprezentáció (ismeretreprezentáció) A tárgykörről szerzett ismeretek ábrázolása számítógépes megoldásra alkalmas szerkezetben
összegyűjtés rendszerezés finomítás
Ismeretreprezentációs technikák: keresés állapottérben logika procedurális reprezentáció szemantikus hálók produkciós rendszerek keretrendszerek
81
Logika Logikai formalizmusok segítségével adott tényekből következtetések levonása Mechanikussá tehető, gépesíthető
Az ítéletkalkulus
axiómák felállítása következtetési szabályok halmaza, következtetési struktúra
82
A leggyakrabban használt műveletek:
„és” műveletek „vagy” műveletek „nem” műveletek implikáció („ha, akkor” művelet) ekvivalencia (akkor és csak akkor művelet)
83
Következtetés:
a feltételek vagy premisszák halmaza (ezekből következtetünk) a következmény vagy konklúzió a premisszákra alkalmazott következtetési szabály
A predikátumkalkulus az objektumok közötti relációk definiálása az ítéletkalkulusban megfogalmazott logikai műveletek Korábban tárgyalt relációk és gráfok
84
Kvantorok
Többféle állítás kifejezéséhez szükséges változók Lásd korábban tárgyalt relációk és gráfok. : minden : létezik
85
Logikai kvantifikátorok
86
„Minden ember halandó” „Van ember, aki halandó” Közös
Ítélet alanya Ítélet állítmánya
Eltérő
Állítás terjedelme Általánosítás foka
Az első ítélet: általános A második ítélet: létezik, van legalább egy ember 87
Egy ítélet „kvantifikálása” Az állítás terjedelmének meghatározását jelenti, melyhez a formális logikában a kvantifikátornak vagy kvantornak nevezett operátorok használatosak
88
: általános kvantifikátor, jelentése MINDEN, vagy BÁRMELY Ha S egy emberekből álló sokaságot jelent, ahol F a férfiak és N a nők osztálya, akkor
(x S )x F x N Minden x-re, mely eleme S-nek fennáll, hogy x vagy az F, vagy az N osztályhoz tartozik, de a kettőhöz együtt nem tartozhat.
89
: egzisztenciális kvantifikátor,
jelentése LÉTEZIK, VAN
Ha T a természetes számok halmaza, akkor
t T t 2 a következőképpen értelmezhető: „van olyan természetes szám, amely nagyobb kettőnél”
90
A kvantifikátorok egymással kombinálva is alkalmazhatók Ha X a valós számok halmaza, akkor x X y X x y jelentése: „Minden x valós számhoz található egy olyan y, hogy x kisebb mint y” y X x X x y A kombinált alkalmazásnál az operátorok sorrendje nem közömbös. Az jelentése: „Létezik olyan y a valós számok körében, hogy bármi legyen is x, x kisebb mint y.” 91
A kvantifikált ítélet tagadása Legyen egy emberekből álló sokaság S, és legyen H a halandó emberek osztálya. x S x H „nem igaz, hogy minden ember halandó” Ez azonban egyenértékű azzal az állítással, hogy „létezik olyan ember, aki nem halandó”
x S x H
Ahol H a halandók osztályának komplementuma, felírhatjuk az alábbi ekvivalenciát:
[x S x H ] x S x H
92
Hasonló megfontolások alapján a következő sémával foglalhatjuk össze a tagadások különböző típusait és ezek kölcsönös megfeleltetését.
„nem igaz, hogy minden ember nem halandó” ítélet, amely nyilván egyenértékű a „létezik (van legalább egy) halandó ember” állítással
x S x H x S x H
93
EKVIVALENS ÍTÉLET-PÁROK
94
Elsőrendű logika Valamilyen objektum lesz az argumentumhoz rendelt érték. Például a nagybácsi(X), egyváltozós függvény esetében, ha X=Éva, nagybácsi(Éva)=Péter, tehát az X-hez rendelt érték a Péter. Két változó, X és Y akkor és csak akkor egyenlő, ha bármely predikátumba, illetve függvénybe helyettesítve őket, azonossághoz jutunk. A predikátumkalkulust az előzőekkel kiegészítve kapjuk az elsőrendű logikát (az elsőrendű arra utal, hogy kvantorok argumentumai között csak individuumok szerepelhetnek, predikátumok, függvények nem).
95
Alkalmazási területek:
kérdés-felelet rendszerek problémamegoldó rendszerek robotika új elvű programozási nyelve
Procedurális reprezentáció Olyan kisebb eljárások, programok, amelyek „tudják” hogyan kell meghatározott szituációkat kezelni. Deklaratív reprezentáció – statikus, adott állapotról tájékoztat 96
Szemantikus hálók Részei:
csomópontokból (amelyeket ponttal, körrel vagy boxokkal jelölhetünk az ábrázolásokban) élekből (vagy kapcsolatokból, amelyeket nyilakkal szemléltetünk)
Csomópontok: objektumok, fogalmak, szituációk
Élek: közöttük fennálló relációk Kísérlet a humán memória pszichológiai modelljének megalkotására.
97
Produkciós rendszerek
Newell és Simon fejlesztették ki (1972) Az emberi kognitív képességek modellezése
az adatbázis olyan szabályokból épül fel, amelyek feltétel-akció párok, produkciós szabályok
98
Keretrendszerek, frame-alapú reprezentációk A frame olyan adatstruktúra, amely deklaratív és procedurális információkat tartalmaz előre meghatározott belső relációkban. Generic DOG Frame (A kutyára vonatkozó frame)
Self: an ANIMAL (állat) a PET (kedvenc háziállat) Breed (tenyészet): Owner (tulajdonos): a PERSON (egy személy) Name (név): a PROPER NAME (tulajdonnév) 99
Egy adott egyedre vonatkozó Frame
Self: a DOG Breed: mutt Owner: Jimmy Name: Fido
A kategóriák minden kutyára azonosak. Az egyes ismertető jegyek konkrét tartalma az egyedekre jellemző
100
Az MI alaptechnikái
101
A mesterséges intelligencia főbb részterületei:
látásmodellezés problémamegoldás tanulás szakértő rendszerek neurális hálózatok data mining
102
Tudásalapú rendszerek, szakértő rendszerek A tudásalapú rendszerek (Knowledge-based Systems, KBS) olyan MI-programok, amelyek a problématerületet leíró ismereteket a rendszer többi részétől elkülönítve, az ún. tudásbázisban tárolják. A szakértő rendszerek (ES:Expert Systems) lényegében olyan tudásalapú rendszerek, amelyek egy szűk tárgyterületen belül, szakértői ismeretek felhasználásával, gyakorlati szinten alkalmazhatóak feladatmegoldásra
103
A szakértő rendszerek jellemzői:
az emberi szakértőhöz hasonló javaslatokat ad kérdéseit megmagyarázza, indokolja szimbólum-manipulációkat használ korrekt válaszadás mellett vagy helyett képes elfogadható válasz, eredmény, javaslat adására
Három komponense van:
a felhasználói interfész a következő gép és a tudásbázis 104
A szakértői rendszerek megvalósításának technikái Neurális hálózatok Hatótényezők: hatékonyabb tanulási algoritmusok használata a számítógépek számítási kapacitásának nagymértékű növekedése párhuzamos programozás előtérbe kerülése Neurális hálózatok fő jellemzői: nagyszámú neuronszerű processzorból állnak párhuzamos architektúrával rendelkeznek az elemek közötti kapcsolatok súlyozottak tanulásra képesek képesek az osztályozásra
105
Előnyös az alkalmazásuk: ahol a problématerület gazdag történeti adatokban a megoldást meghatározó függvény ismeretlen vagy előállítása bonyolult az alkalmazást egymásra ható paraméterek írják le az adathalmaz bizonyos számú hibát tartalmaz
106
Alkalmazási területek:
karakter felismerés képfelismerés zajszűrés előrejelzés optimalizálás
Neurális hálózatok alkalmazása nem előnyös:
ahol a feladat matematikai pontosságot vagy precíz eljárást igényel ahol az adatok bizonyos időközönként cserélődnek (pl. leltárkészítés) 107
Neurális hálózatok felépítése Biológiai hálózatok:
1010 számú lassú, primitív processzorból állnak nagy fokú párhuzamosság nagymértékű adatáramlás rugalmas kapcsolódó képesség
108
Neuron részei:
axon: az információ továbbítója neuronban dendrit: idegvégződés szinapszis: más neuronhoz való kapcsolódás pontja
Mesterséges neuronokból felépített hálózat:
csomópont: képezi a jelek súlyozott összegét, küszöbfüggvény rétegek: rendezett csomópontok neurális hálózat
109
Fuzzy modellek Genetikus algoritmusok t-időponthoz tartozó P(t) populáció kiválasztás t+1 időponthoz tartozó P(t+1) időponthoz tartozó populáció genetikus operátorok mutációs transzformáció program konvergálása
110
A HANOI TORNYAI PROBLÉMA
1
2
3
1
A
3
A
B C
2
B C
111
A HANOI TORNYAI PROBLÉMA ÁLLAPOTGRÁFJA (Nilsson 1971) (3,3,3)
(2,3,3)
(1,3,3) (1,2,3)
(2,1,3)
(2,2,3)
(1,1,3)
(3,1,3)
(3,2,3)
(1,1,2)
(2,2,1)
(3,1,2)
(1,2,1)
(2,1,2)
(3,2,2)
(2,3,2)
(3,2,1)
(1,3,1)
(3,1,1)
(2,2,2)
(1,1,1) (1,2,2)
(1,3,2)
(3,3,2)
(3,3,1)
(2,3,1)
(2,1,1)
112
A hegymászó módszerrel bejárt megoldási út (3,3,3)
(1,3,3)
(1,2,3) (2,2,3)
(2,2,1)
(1,2,1)
(1,3,1)
(2,3,1)
(2,1,1)
(1,1,1)
113
A Hanoi tornyai probléma megoldás visszalépéses kereséssel
(3,3,3)
(1,3,3)
(1,2,3) (2,2,3)
(2,2,1)
(1,2,1)
(3,2,1)
(1,3,1) (3,1,1)
(3,3,2)
(3,3,1)
(2,3,1)
(2,1,1)
(1,1,1)
114
A Hanoi tornyai probléma megoldása gráfkereséssel (3,3,3) 1. (1,3,3) 2.
(2,3,3)
(1,2,3) 3. (2,2,3) 4.
(3,2,3)
(2,2,1) 5.
(3,2,1) 8.
6. (1,2,1)
(3,1,1) 9.
7. (1,3,1)
(3,3,1)
(2,3,1)
(2,1,1)
(1,1,1)
115
