Eloadó: Dr. Várterész Magdolna

Eloadó: Dr. Várterész Magdolna Tartalomjegyzék: 1. Bevezetés 1.1. A jegyzet megtekintéséhez ajánlott környezet 1.2. Információ a mesterséges intelligencia kurzusról 1.3. Röviden a mesterséges intelligenciáról 2. Problémareprezentációs technikák, megoldáskereső módszerek 2.1. Állapottér-reprezentáció 2.1.1. Állapottér 2.1.2. Szemléltetése 2.2. Állapottér-reprezentált problémák megoldását kereső módszerek 2.2.1. Nem módosítható megoldáskeresők 2.2.1.1. Próba-hiba módszer 2.2.1.2. Hegymászó módszer 2.2.2. Módosítható megoldáskeresők 2.2.2.1. Backtrack (visszalépéses) 2.2.2.1.1. "alap" backtrack 2.2.2.1.2. Kör kiküszöbölése 2.2.2.1.3. Úthossz-korlát 2.2.2.1.4. Optimális megoldás keresése 2.2.2.2. Keresőgráffal megoldást keresők 2.2.2.2.1. Szélességi és mélységi kereső 2.2.2.2.2. Optimális kereső 2.2.2.2.3. Best-first kereső 2.2.2.2.4. A-algoritmusok 2.2.2.2.4.1. "alap" A-algoritmus 2.2.2.2.4.2. A*-algoritmus 2.2.2.2.4.3. Monoton A-algoritmus 2.2.2.2.4. B-algoritmus 2.3. Probléma-redukciós reprezentáció 2.3.1. Probléma-redukció 2.3.2. Szemléltetése 2.4. Probléma-redukcióval leírt feladatok megoldását kereső módszerek 2.4.1. Backtrack (visszalépéses) 2.4.2. Keresőgráffal megoldást keresők 2.4.2.1. AO algoritmus 3. Kétszemélyes, teljes információjú játékok 3.1. A játékok osztályozása 3.2. A játékok reprezentációja és a reprezentáció szemléltetése 3.3. A stratégia 3.4. Adott állásban a következő lépés kiválasztásának módszerei 3.4.1. Mini-max módszer 3.4.2. Nega-max módszer 3.4.3. Alfa-béta vágás

1.3. Röviden a mesterséges intelligenciáról A mesterséges intelligencia kutatások célja olyan feladatok számítógépes megoldása, amelyeket nem tudunk képlettel megoldani. Ezen feladatok megoldásában az ember az intelligenciáját használja. 1956 - konferencia. Itt fogalmazzák meg a célokat, itt nevezik el mesterséges intelligenciának (AI - artificial intelligence). Néhány, a mesterséges intelligenciában használt alapvető technikák és eszközök: ·

mesterséges intelligencia nyelvek (LISP, Prolog (3. félév))

·

probléma reprezentáció (ezen félév anyaga)

·

ismeret reprezentáció (logikai ismeret reprezentáció (2. félév))

·

megoldáskereső technikák (ezen félév)

·

következtetési technikák

Fogalmak: heurisztika: a heurisztika egy olyan trükk, módszer, ami a nagyméretű reprezentációs gráfot oly módon csökkenti, hogy reményünk van a megoldás megtalálására.

2. Problémareprezentációs technikák, megoldáskereso módszerek A problémát ahhoz, hogy kezelni tudjuk, valamilyen módon meg kell adni, le kell írni. Milyen problémákkal fogunk foglalkozni? Olyanokkal, amelyek megoldásához nincs ismert megoldó-algoritmus, képlet. Tapasztalat, tudás segítségével oldjuk meg a problémát. Ezen problémák számítógépes megoldásához keresünk algoritmusokat. Elso feladatunk a probléma leírása, reprezentálása. Háromféle reprezentációs eszköz: 1. Állapottér-reprezentáció 2. Probléma-redukció 3. Logikai alapú (elsorendu nyelvvel) 2.1. Állapottér-reprezentáció 2.1.1. Állapottér Legyen adott egy p probléma. A probléma állapottér-reprezentációjának elkészítéséhez meg kell vizsgálni, hogy melyek p világában azok a tulajdonságok, jellemzok, amelyek fontosak számunkra. Tegyük fel, hogy n ³1 ilyen jellemzot találtunk. Minden egyes jellemzo p világát különbözo értékekkel jellemzi (pl.: életkor: 20; szín: fekete; stb.). Ha a világ n különbözo jellemzojét rendre a h1,...,hn értékek jellemzik, akkor azt mondjuk, hogy a (h1,...,hn) érték n-essel azonosított állapotban van p világa. Jelölje az i. jellemzo által felveheto értékek halmazát Hi (i = 1,...,n). Ekkor p világának állapotai elemei a H1´...´Hn halmaznak. Az állapotok halmazát állapottérnek nevezzük, és A-val jelöljük. AÍH1´...´Hn

Lehet, hogy a világunkban a jellemzokhöz tartozó bizonyos értékek egyszerre nem léphetnek fel, tehát az állapottér az értékhalmazok Descartes-szorzatának csupán valamely részhalmaza.

Kényszerfeltétel: az a feltétel, ami az állapotteret kijelöli az értékhalmazok Descartesszorzatából jelölése: kf(a) ,mely igaz, ha a állapot, egyébként hamis A = { a | aÎH1´...´Hn és kf(a) } Problémafelvetés: 1. Az állapottér mely állapotában vagyunk kezdetben: kezdoállapot. Ez is egy érték nes, s kitüntetett szerepe van. kÎA 2. cél, hova akarunk eljutni. cÎC Í A célállapotok halmaza a feladat általában: a kezdoállapotból jussunk el a megfelelo célállapotba Megadása kétféleképpen történhet: 1. explicit módon, felsorolással. Egy- vagy többféle állapot is lehet. Több állapot esetén ez nehézkes lehet. Ilyenkor: 2. implicit módon, célfeltételek megadásával: C = { a | aÎA, cf(a) }

3. Ahhoz, hogy eljussunk a célállapotba: meg kell változtatni az állapotot. oÎO

o: A ® A állapottérbol állapottérbe képezo függvény. Az állapot megváltoztatásáért felelos. o: operátor O: operátorok halmaza

Természetesen nem minden operátor alkalmazható minden esetben. Meg kell adni a pontos értelmezési tartományt: operátor-alkalmazási elofeltételek. (minden egyes operátorhoz hozzátartoznak) dom(o) = { a | aÎA, efo(a) }

, ahol efo(a) azon elofeltétel, mely megmondja, hogy az adott állapoton értelmezheto-e a kérdéses operátor efo(a) esetén o(a) = a' ÎA

Definíció: A p problémát leírtuk állapottér-reprezentációval, ha megadtuk a p = négyest, ahol · · · ·

A: a probléma állapottere, ezt meg kell adni k: kitüntetett kezdoállapot O: a probléma operátorainak halmaza, minden egyes operátornál elofeltételek C: a probléma célállapotainak halmaza

p =

ilyenkor megadtuk a p probléma állapottér-reprezentációját Több reprezentáció is megadható ugyanarra a feladatra.

Mit jelent ennek az implementálása? 1. egyrészt meg kell adni az értékhalmazokba tartozó értékek típusát kényszerfeltételek: az értékhalmazból mely értékek valódi állapotok Boolean függvények: a formális paraméterben vár egy érték n-est, s egy logikai értéket ad vissza (igaz v. hamis) 2. kezdoállapot. Állapot típusú konstans 3. célállapotok. Megadása történhat: a. célfeltételekkel: boolean, kap egy állapotot, s visszaad egy logikai értéket b. konstansokkal 4. operátorok: függvények, eljárások. Kap egy állapotot, s egy új állapotot állít elo. Minden egyes operátorhoz tartozik egy elofeltétel is (boolean típusú függvény). Kezdoállapotból mikor, melyik operátor alkalmazásával tudunk eljutni a célállapotba? Az aÎA -ból az a'ÎA közvetlenül elérheto, ha van olyan oÎO: efo(a) és o(a) = a' Az aÎA -ból az a'ÎA elérheto, ha van olyan a1,...,anÎA (állapotsorozat), hogy a=a1, a'=an és aibol ai+1 közvetlenül elérheto. (a a kezdoállapot, a' a célállapot, i=1,...,n-1). Ilyenkor van egy operátorsorozat, ami ezt az elérést lehetové teszi: o1,o2,...,on-1 Egy állapottér-reprezentált probléma megoldható, ha a kezdoállapotból elérheto valamelyik célállapot.

Mi a megoldása? Az az operátorsorozat, amely ezt az elérést lehetové tette. (De lehet több megoldása is függetlenül attól, hogy hány célállapot van). A feladat lehet egy vagy több megoldás eloállítása. Célunk: minosítés alapján jó megoldás keresése, azaz a megoldások között különbséget teszünk, pl.: költség. Költség: az operátorok alkalmazása költségbe kerülhet. (egy operátor használata egy állapotra ® ennek van költsége) ez lehet mindig azonos, vagy függhet attól, hogy melyik állapotra alkalmazzuk r(o,a) d > 0 (pozitív alsó korlátja van, aminél a költség nem lehet kisebb) r(o,a) -ban o az operátor, a pedig, hogy milyen állapotban alkalmazható Ha r(o,a) 1, akkor ez az alkalmazott operátorok számát fogja jelölni Az operátoroknál meg kell adni az operátorok költségét (függvénnyel, eljárással megadható). Mi a megoldás költsége? Az operátorsorozat operátorainak költségösszege:

A különbözo megoldásokat így össze lehet hasonlítani! Optimális költség: (olcsó), legolcsóbb megoldás keresése. Feladat: megoldást kell eloállítani. Nem tudom megmondani, hogy mikor melyik operátort alkalmazzuk. A megoldást keresni kell. Példák § § § §

8-as játék Hanoi tornyai Építokocka játék Utazó ügynök probléma

2.1.2. Szemléltetése Legyen a p probléma az állapottér-reprezentációval megadva. Szemléltessük egy gráffal ezt a probléma-leírást a következoképpen: az állapottér állapotait csúcsokkal szemléltetjük, különbözo állapotokat különbözo csúcsokkal. A kitüntetett állapotokat, mint a kezdo- és célállapotokat a csúcsok között is kitüntetjük, a kezdoállapotot szemlélteto csúcsot startcsúcsnak, a célállapotokat szemlélteto csúcsokat terminális csúcsoknak nevezzük.

Minden aÎA -t szemlélteto n csúcsból irányított élt húzunk az a'ÎA -t szemlélteto n' csúcsba, ha a-ból közvetlenül elérheto a'. Így egy gráfot kapunk, ahol N a csúcsok halmaza s a start csúcs T a terminális csúcsok halmaza E az élek halmaza Ezt a gráfot a p probléma állapottér-reprezentációjához tartozó állapottérgráfjának vagy reprezentációs gráfjának nevezzük. Fogalmak: irányított utak:

Pontosan akkor vezet az állapottérgráfban az n csúcsból az n' csúcsba irányított út, ha az n által szemléltetett állapotból az n' által szemléltetett állapot elérheto. van a start csúcsból valamelyik terminálisba vezeto irányított út

megoldható: megoldás: költség:

pontosan ez ( ) az irányított út szemlélteti a megoldást r(o,a) Az irányított élekhez rendelhetok költségek, hiszen azok az operátorok alkalmazását szemléltetik

irányított út költsége: Egy probléma megoldásának keresése:

a benne szereplo élek költségösszege r(n,n') d > 0 a probléma-reprezentációs gráfban fogunk utat keresni a start csúcsból a terminálisba

Egy gráfban annál könnyebb keresni, minél egyszerubb annak a felépítése, ill. minél kisebb. Ez többféleképpen is elérheto: 1. csúcsok számának csökkentése (állapotok számának csökkentése) egy (1) csúcsból kiinduló élek számának 2. csökkentése (operátorok ügyes, alkalmas megválasztása) 3. fává egyenesítés

ü ç ý állapottér-reprezentációval van ç kapcsolatban þ

A reprezentációs gráfban lehet hurok:

illetve kör:

ezeket kell kiegyenesíteni!

Hurok kiegyenesítése:

®

Ugyanazt az állapotot két különbözo csúccsal reprezentáljuk! Gond: no a fa terjedelme! Kör kiegyenesítése:

®

Gond: a kör kiegyenesítése végtelen szerkezettel jár együtt. Mérlegelni kell, hogy a fává egyenesítés megéri-e.

Példák (néhány probléma gráfreprezentációja): 1.) 8-as játék: Minden él mellett van egy párhuzamos visszairányuló él. Ilyenkor használhatunk egy irányítás nélküli élet is.

Megoldás!!! Ez egy olyan probléma, ahol a fává egyenesítéssel érdemes élni.

2.) Utazó ügynök probléma

Ez egy fa-gráf, s minden egyes útjának végén (a levél) terminális csúcs. Az utak közül az optimálisat kellene kiválasztani.

2.2. Állapottér-reprezentált problémák megoldását kereső módszerek Komponensek: -adatbázis Az állapottérgráf tárban tárolt része. Megoldáskeresésnél nem lesz az egész gráf a tárban, csupán valamilyen, a keresés szempontjából fontos része. -műveletek Segítségükkel módosítjuk az adatbázist. Ilyen műveletek például: a) állapottér-reprezentációs operátorokból származtatott műveletek b) technikai műveletek (pl. visszalépés) -vezérlő A vezérlő irányítja a keresést. Megmondja, hogy a megoldáskeresés során az adatbázis mely részén mikor, melyik művelet hajtódjon végre. Operátorból származtatott művelet választása előtt vizsgálja az operátoralkalmazási előfeltételeket. Figyeli a terminálási feltételek segítségével, hogy befejeződhet-e a keresés (sikeresen, avagy sikertelenül). Ha a terminálási feltételek nem teljesülnek, akkor tovább kell keresni. Ha ezek nem teljesülnek: még nem találtuk meg a megoldást. Ő fogja figyelni is. Osztályozásuk: I. nem-módosítható megoldáskeresők: egy állapotváltozást vissza lehet-e vonni, vagy sem. Ha utólag nem tudjuk magunkat módosítani: nem-módosítható megoldáskeresés (ez a hagyományos programozásra jellemző). Mesterséges intelligenciában inkább módosítható megoldáskeresőket alkalmaznak. II. módosítható megoldáskeresők: a vezérlő által kiválasztott művelet hatása visszavonható a) visszalépéses (backtracking) b) keresőgráffal III. irányítatlan (szisztematikus): a vezérlő mi alapján választ: - véletlenszerűen - valamilyen általános szisztéma alapján (pl. gráfban fentről le, stb.) Heurisztikus keresésnél a generálás IV. heurisztikus: irányításánál helyet hagyunk a tárgyköri ismereteknek is, azokat is felhasználjuk. Jelentősége: megpróbáljuk a keresést a reprezentációs gráfban ott folytatni, ahol a megoldást reméljük (valamilyen becslés alapján) ® csökken a reprezentációs gráf tárban tárolt részének mérete

Keresés iránya: 1. előrehaladó(adatvezérelt): 2. visszafelé haladó (célvezérelt): 3. kevert:

kezdőállapotból célállapotba visszafelé haladva rekonstruálunk mindkét irányból elindul, s valahol találkozik

Linkek: § §

nem-módosítható megoldáskeresők módosítható megoldáskeresők 1. visszalépéses (backtracking) 2. keresőgráffal

2.2.1. Nem módosítható megoldáskeresők Ezen megoldáskeresőknek kisebb a jelentőségük, ritkábban is használják őket. Előnyük viszont az, hogy egyszerűbbek. Csak olyan feladat megoldásánál alkalmazzuk, ahol nem a megoldás a lényeg (azaz a kezdőállapotból a célállapotba vezető operátorsorozat), hanem csupán az, hogy eldöntsük: a feladatnak egyáltalán létezik-e megoldása, vagy egy célfeltételnek eleget tevő állapot előállítása. Komponensek: adatbázis: aktuális állapot műveletek: állapottér-reprezentációs operátorok Az adatbázisra egy művelet alkalmazható: ha az aktuális állapotban teljesülnek a műveletet meghatározó operátor alkalmazási előfeltételei. A művelet hatása az adatbázisra: az aktuális állapotban alkalmazzuk a műveletet meghatározó operátort, és az előállt új állapot lesz az új aktuális állapot. vezérlő: 1. aktuális állapot ¬ kezdőállapot (inicializáljuk az adatbázist. Az aktuális állapot legyen először a kezdőállapot) Célállapotot kell előállítani, nem egy operátorsorozatot (hiszen ez már plusz információ lenne). 2. tesztelés. Az aktuális állapot egyenlő célállapot-e? Ha igen: sikeresen befejezhetjük a keresést, előállítottunk egy célállapotot Ha nem: erre az aktuális állapotra van-e alkalmazható művelet? a) ha van: a vezérlő választ egyet, és alkalmazza. Vissza a 2. pontra (tesztelés). b) ha nincs: be kell fejezni a munkát, sikertelen a keresés. Lehet, hogy nincs megoldás, vagy a megoldáskereső rossz irányba ment; de erről nem tudunk többet mondani! A szükséges eljárások: procedure alk (var all: alltip; o: op); procedure valaszt (all: alltip; var o: op; var v: boolean); procedure sikertelen;

procedure sikeres (a: alltip);

művelet alkalmazása az adatbázison művelet választása felhasználó tájékoztatása a keresés sikertelen befejezéséről megoldás visszaadása

Ezek alapján a vezérlő: begin aktall := k; van := true; while van and (not celfelt(aktall)) do begin valaszt(aktall, operator, van); if van then alk(aktall,operator); end; if van then sikeres(aktall) else sikertelen; end. Ugyanazon feladat esetén a választás módjában lehet lényeges eltérés: a) irányítatlanul, szisztematikusan ("próba-hiba" módszer) Pld.: sorrend, s ezeket végignézzük, hogy melyiket tudjuk alkalmazni. A feladattal kapcsolatos tudásunk nincs benne megfogalmazva. Véletlenszerűen választunk: ez a próba-hiba módszer. Ezt könnyű implementálni, kicsi az adatbázis, viszont általános esetben nem garantál semmit. Milyen feladatosztály esetén van reményünk a megoldásra? Csak olyan esetben, ha minden csúcsból elérhető valamelyik cél. Kört nem tartalmazhat, ui. nincs rá garancia (végtelenszer ismételheti). Hurok még lehet benne. b) heurisztikusan ("hegymászó" módszer) Akkor beszélünk heurisztikus megoldáskeresésről, ha megpróbáljuk felhasználni a tudásunkat, tapasztalatunkat. A heurisztika valamilyen mennyiségi, minőségi heurisztika lesz. A heurisztikától függ majd, hogy a megoldást megtaláljuk-e vagy sem. Jó heurisztika esetén lesz majd reményünk a megoldás megtalálására. h(n)

a csúcs hány élnyire van a legközelebbi terminálishoz (azaz hány operátor alkalmazására van szükség). Ha ezt tudnánk, akkor ez egy felhasználható tudás lenne. Ezt próbáljuk meg becsülni.

h(aktall)

h(o1(aktall)) h(o2(aktall)) ... h(on(aktall))

alkalmazzuk az összes lehetséges operátort, s utána megnézzük, hogy közelebb kerültünk-e valamilyen célhoz (vagy legalábbis nem távolabb). Azt fogjuk alkalmazni, amelyik a legközelebbi célhoz visz közelebb.

Ez az ún. hegymászó-módszer. "A csúcshoz közelítünk." Távolodni nem szabad a céltól.

2.2.2. Módosítható megoldáskeresők Információ kellene tárolni az információkeresés múltjáról. Ha felismerjük, hogy rossz irányba haladunk, akkor visszalépünk. Módosítható megoldáskeresők osztályozozása:

1. visszalépéses (backtrack) 2. keresőgráffal

2.2.2.1. Visszalépéses (backtrack) Adatbázis: a keresőgráf egy része kerül ide. start-ból induló, aktuális csúcsba vezető aktuális út. Ez az az út amiből véljük, hogy elérjük valamelyik terminális csúcsot. A múltból mi van nyilvántartva: a start-ból milyen módon jutottunk el az aktuális csúcsba. Műveletek:

operátorok + visszalépés operátorok: állapottérreprezentációs műveletek visszalépés: technikai művelet

Operátor: alkalmazzuk az utolsó csúcson, ezzel új állapot keletkezik. Ezt felfűzzük az aktuális útra (annak hossza 1 élnyivel megnő). Ez lesz az új aktuális csúcs.

Az operátor alkalmazása tehát növeli az utat! Visszalépés: töröljük az aktuális csúcsot, és az aktuális csúcs a megelőző csúcs lesz. Vagyis az út rövidebb lesz.

Vezérlő: eldönti, hogy az adatbázis melyik részén mikor, melyik műveletet kell végrehajtani (az aktuális csúcsra fog alkalmazni egy műveletet). Mit figyeljen? ·

operátor vagy visszalépés? Ezt kell eldöntenie. Ha operátor: melyiket alkalmazza?

·

terminálási feltételek teljesülése. Előállt-e a megoldás? Figyeli az akt. csúcsot. Ha az teljesíti a célfeltétel(eke)t, akkor kész vagyunk. Az adatbzis tehát egy megoldás.

Ha nemterminális a csúcs, akkor ezen az úton remény van-e még a megoldás megtalálására vagy sem? Vagy: érdemes-e még folytatni egyáltalán a keresést? Hogy fog a vezérlő megoldást keresni? a) "alap" backtrack 1. inicializálás. Az út egy csúcsból áll: (start csúcs) Van adatbázis, aktuális út, aktuális csúcs 2. tesztelés. Az aktuális csúcs terminális-e? igen: kész vagyunk nem: tovább tudunk-e lépni? Van-e alkalmazható operátor? igen, van: választunk, alkalmazzuk. Új aktuális csúcs, ismét tesztelés (2. pont) nincs: másik művelet: visszalépés. (vagyis ha az akt. csúcsban nincs alkalmazható operátor)

Ha az aktuális csúcsban nincs alkalmazható operátor, akkor meg kell próbálni a megoldást valamilyen másik irányban keresni. A reprezentációs gráfban valamilyen másik irányba kellene lépni. Az adatbázisnak viszont ezt tudnia kell, minden csúcsban nyilván kell tertani, hogy abból a csúcsból mely alkalmazható operátorokat alkalmaztuk, vagy nem alkalmaztuk (ez egy plusz információ). A visszalépés során előállt új aktuális csúcsban egy még nem alkalmazott alkalmazható operátort kell alkalmazni. Van ilyen? igen: alkalmazzuk, folytatjuk a keresést nem: visszalépés a szülőre, s a reprezentációs gráfban egy másik irányba kell próbálkozni. Vagyis: aktuális csúcsban már minden alkalmazható operátort kipróbáltunk, sikertelenül visszalépés. Terminálási feltételek: 1. az aktuális csúcs célcsúcs-e? 2. start csúcsban teljesül a visszalépési feltételünk (vagyis már nincs olyan operátor, amit ne alkalmaztunk volna már sikertelenül) Ekkor nincs megoldás! Ha a reprezentációs gráfunk olyan véges gráf, hogy nem tartalmaz köröket, a visszalépéses megoldáskereső - ha van megoldás - garantáltan előállít egy lehetséges megoldást. Ha nincs megoldás, akkor azt fel lehet ismerni. Eltérés hol lehet? Az operátorok választásában. Ez történhet: § §

szisztematikusan heurisztikusan

Heurisztika: tudásunk alapján megbecsülhetjük, hogy a cél milyen távol van. Ezért választhatunk olyat, ami közelebb visz (hasonló a hegymászó módszerhez). Mik a problémák? Olyan reprezentációs gráfok esetén garantálja a megoldást, amelyben nincsenek körök. Ekkor ui. nincs garantálva a megoldás, végtelen ciklus alakulhat ki. (Végtelen sokszor ugyanazt választjuk ki). Ötlet: ne engedjük, hogy egy körön végtelen sokszor végigmenjen, vagy ne is engedjük bezárni ezt a kört: b) kör kiküszöbölése lesz egy újabb visszalépési feltétel:

az aktuális csúcs szerepelt-e már az aktuális úton Ha igen: rögtön visszalépés (így nem zárjuk be a kört). Azaz körök nélkül próbáljuk meg megtalálni a megoldást. (Ha van megoldás, akkor van körmentes megoldás is).

c) úthossz-korlát Egy másik megoldás az, hogy úthossz-korlátot vezetünk be: l (megoldás) Fává egyenesítünk, végtelen fagráfot állítunk elő. Nem engedjük, hogy az aktuális út hossza meghaladja az úthosszkorlátot. aktuális út hossza úthossz-korlát

(ha ez teljesül

visszalépés)

Viszont ha túl rövidre választjuk az úthossz-korlátot (túl alacsonyan vágjuk el a gráfot) akkor nem találunk megoldást. Ha a start csúcsban áll elő a visszalépési feltétel, akkor: 1. nincs megoldás 2. túl rövidre választottuk az úthossz-korlátot Arról, hogy melyik, nem ad információt! Ez utóbbi (úthossz-korlátos) tartalmazhat kört a megoldásban. Ha körmenteset akarunk, akkor onnan nekünk kell kivágni a kört. Nem feltétlenül véges fa-gráf esetén, ha garantáltan van az úthossz-korlátnál rövidebb megoldás, akkor azt megtalálja. d) optimális megoldás keresése A backtrack alkalmas-e optimális megoldás keresésére? Azaz van költség, s a legkisebb költségű megoldást szeretnénk előállítani. Ez lesz az ág és korlát algoritmus. van egy induló költségkorlát

k (megoldás)

(felső becslés)

Ennél a költségkorlátnál nem költségesebb megoldást keresünk. Csak addig megyünk a reprezentációs gráfban a keresés során, míg a költségkorlátot el nem érjük. Ha találunk egy megoldást, akkor ez lesz az új költségkorlát! (Ez ugye induló költségkorlát) Folytatjuk a megoldáskeresést. Ezt a megoldást elraktározzuk, s úgy tekintjük, mintha nem lett volna megoldás. Ha van újabb megoldás, akkor annak költsége már csak lehet, mint ez. Ismét csere, eltárolás, stb. Így a reprezentációs gráf elég nagy részét nem kell bejárni, egyre kisebb utakat járunk be. Addig folytatjuk, míg a start csúcsból el tudunk valamerre indulni. Mit garantál ez? · ·

előállítja az optimális megoldást ha nem talált megoldást, akkor vagy a költségkorlát volt kicsi (az induló), vagy a feladatnak nincs megoldása.

CSAK körmentes gráfok esetén működik!

Módosítható megoldáskeresők osztályozozása: 1. visszalépéses (backtrack) 2. keresőgráffal 2.2.2.2. Keresőgráffal megoldást keresők Adatbázis: keresőgráf, egy fa. A reprezentációs gráfnak a bejárt részét feszítő fa. Egy csúcspont lehet zárt (az út közbenső csúcsa, rajtuk már továbbhaladtunk), vagy lehet nyílt (az utak végén álló levelek, itt folytathatjuk majd a keresést). Minden csúcsnak pontosan egy szülője lesz nyilvántartva a keresőgráfban (mivel fa). Az éleket visszamutatók segítségével realizáljuk. Így tudunk majd rekonstruálni. (A visszalépéses megoldáskereső csak egy utat tartott számon. Itt több út is számon van tartva, rajtunk múlik, hogy hol folytatjuk). Művelet: kiterjesztés. Levélelemből kivitelezi a továbblépést, Így tudunk majd élnyire továbbmenni. Az összes lehetséges irányba továbbmegyünk majd. (Egy új, nem kiterjesztett csúcsra alkalmazzuk az összes alkalmazható operátort). Vezérlő: melyik nyílt csúcs legyen a következő lépésben kiterjesztve. A kiválasztott nyílt csúcsot tesztelni tudja (célcsúcs, nem célcsúcs), s van egy út visszafelé is. A nyílt csúcsok közül kell választania a megoldáskeresőnek. Nincs megoldás: egyetlenegy nyílt csúcs sincs, amelyen a keresést folytathatnánk. Szisztematikus keresőgráffal keresők Szisztematikus keresőgráffal keresők: § § §

szélességi kereső mélységi kereső optimális kereső

2.2.2.2.1. Szélességi és mélységi kereső A reprezentációs gráf csúcsait oly módon választjuk, hogy az 1. szinten, 2. szinten, stb. lévő csúcsokat vesszük. mélységi szám:

g(s)=0

a start csúcsé 0. 0 szintre van a start-tól

g(m)=g(n)+1

a szülő mélységi száma + 1, ahol (n,m)

E (vagyis él)

Egy csúcs előállításakor mindig kiszámítjuk a mélységi számát. Kiterjesztésre melyik csúcsot választjuk ki? §

szélességi: mindig a legkisebb mélységi számú nyílt csúcs kerül kiterjesztésre

§

mélységi: mindig a legnagyobb mélységi számú nyílt csúcs kerül kiterjesztésre

szélességi+mélységi: egy adott csúcshoz vezető melyik út van éppen nyilvántartva? Mindegy, ezért a legelső számontartott utat fogjuk nyilvántartani.

1. adatbázis inicializálása: rögzítsük a mélységi

ö 0

ý S0(0) nyílt (nyílttá tesszük)

számot: visszamutató:

0

ø

(azt is tudni kell, hogy az induló keresőgráf egyetlen csúcsa nyílt-e vagy zárt) 2. Van-e nyílt csúcs? nincs: van:

be kell fejezni, nem tudjuk folytatni ki kell választani a nyílt csúcsok közül egyet (az alapján, hogy mélységi v. szélességi a keresés) A kiterjesztésre kiválasztott csúcsot teszteljük. Célcsúcs? nem: kiterjesztjük, őt zárttá, gyermekeit nyílttá tesszük. Gyermekek visszamutatnak a szülőre, mélységi szám beírása. Vissza a 2. pontra. sikeres vég, mutatók alapján van egy út igen: vissza

Szélességi, mélységi keresésnél nem cél az optimális megoldás kiválasztása: ha több út van az adott csúcsba, akkor tetszőlegesen tartjuk nyilván az egyiket (legegyszerűbb, ha maradunk az elsőnél). Mikor tesztelünk, a tesztelést előrehozhatjuk, mert nem cél az optimális megoldás. Szélességi: tetszőleges reprezentációs gráfban ha van megoldás, akkor a legkevesebb operátor alkalmazásával előállítható valamelyik terminális. Mindig a legkisebb mélységi számú csúcsot teszteljük, terjesztjük ki, ezért a legkisebb hosszúságú megoldást állítjuk elő. Ha nincs a problémának megoldása, akkor azt a nyílt csúcsok elfogyásával felismeri. Mélységi: tetszőleges, véges reprezentációs gráfban ha van megoldás, akkor a mélységi kereső megoldás a terminál. Ha nincs megoldás: felismeri. (Mint látható, nem kell megkövetelni a körmentességet - ellentétben a backtrack-kel). Implementálás: Szélességi esetben a nyílt csúcsokat egy sorban tartjuk nyilván, amelyből pont mélységi szám szerint növekvőleg fognak kijönni. Mélységi esetben: veremben való kezelés. Ezt onnan lehet könnyen megjegyezni, hogy "a sor széles, a verem pedig mély" :-) Ha a reprezentációs gráf fagráf: kiterjesztéskor nem kell figyelni, hogy a gyermekek szerepeltek-e már vagy sem, mert nem szerepelhettek! (ui. fagráf esetén egy elemnek csak 1 szülője lehet, így egy elemet csak 1 irnyból, a szülő felől érhetjük el, s nem kell attól félnünk, hogy már korábban egy másik irányból kiterjesztették).

2.2.2.2.2. Optimális kereső (a szélességi keresés is egyfajta opimális megoldást adott. Költség: út hossza). r(n,m) d > 0

,ahol (n,m) E

Minden csúcsnál számon tartjuk az odavezető út költségét. g(s)=0 g(m)=g(n)+r(n,m)

,ahol (n,m) E

g*(n)

g(n): szülő költsége, g(n) 0 r(n,m): a szülő és gyermek közti él költsége jelöljük így a start-ból n-be jutás optimális költségét

g(n) g*(n)

,n N

A nyílt csúcsok közül azt fogjuk kiterjesztésre kiválasztani, amelyik eddig a legolcsóbb volt (ott reméljük majd a legolcsóbb megoldást). A legkisebb költségű nyílt csúcsot választjuk ki kiterjesztésre. Ha az új út kisebb költségűnek bizonyul mint a régi, akkor... n

m m szerepelt már akeresőgráfban: Ha az új út költsége < régi, akkor átállítjuk a mutatót ill. a költséget (zölddel jelölve)

m lehetett nyílt: m lehetett zárt:

ekkor átállítjuk a mutatót ill. a költséget (lásd fentebb) már vannak részgráfjai! Az m-ből induló részgráf összes csúcsába is kisebb költséggel juthatnánk el. Gond!

DE! Bebizonyítható, hogy ha m zárt, akkor nem található hozzá vezető kisebb költségű út! Mivel m zárt (most ezt feltételezzük), akkor az m-et hamarabb kellett kiterjeszteni, mint n-et, azaz g(m) g(n) g(m) g(n) g(m) < g(n) + r(n,m) Így tehát az előbbi probléma nem fog minket érinteni. Mit garantál az optimális kereső? Tetszőleges reprezentációs gráfban ha van megoldás, akkor az optimális megoldással terminál. Ha nincs megoldás: jelzi. Tesztelés: mikor teszteljük a csúcsokat, hogy terminális-e? Ez időnként előrehozható, például kiterjesztéskor, amikor előállítunk egy csúcsot akkor rögtön tesztelhetjük. Ez viszont csak csak szélességi és mélységi keresésnél működik ilyeténképpen, optimálisnál nem (ott csak kiválasztás után).

Heurisztikus keresőgráf Heurisztika: a szisztematikus keresőgráffal keresők a gráf jóval nagyobb részét használják (egy egész fát, míg a korábbiak jóval kisebbet). A heurisztika trükk, egyszerűsítés, mely a nagyméretű reprezentációs gráfban a keresést tudja korlátozni. Csak a gráf azon részét kelljen előállítani, amelyben a megoldást reméljük a tudásunk alapján (míg a szélességi bizonyos mélységig az egészet feltárja). Példa: szélességi keresés esetén: 1 csúcsnak van d gyermeke, s l hosszú a legrövidebb megoldás. Hány csúcsú keresőgráfot állítana ez elő?

Vagyis a megoldás mérete a megoldás hosszának exponenciális mérete. Heurisztikával: a nyílt csúcsok közül ha mindig azt terjesztenénk ki, ahol a megoldást reméljük: 1 + d + d + ... + d = 1 + l × d Ez az ún. perfekt heurisztika. Persze perfekt heurisztikánk NINCS (hiszen ha ismernénk a megoldást, akkor nem kellene keresni)! De ez lenne az ideális. A lényeg: csökkentsük a keresőgráf méretét! 2.2.2.2.3. Best-first kereső (A legjobb irányban haladó keresés). h(n) n

becslő függvényérték, ahol n-ből meg tudjuk becsülni a célbajutás optimális költségét

h(n) 0 h(t) = 0

, ha t T (vagyis ha terminális csúcsban vagyunk)

h(n) =

, ha egy csúcsból (n-ből) nem érhető el egyetlen terminális sem, akkor valamilyen nagyon nagy számmal jelöljük

A keresőgráfban minden n csúcshoz előállítjuk h(n)-t. Kiterjesztésre kiválasztás: legkisebb heurisztikájú nyílt csúcs (CSAK ezt tárolja: abból a csúcsból kb. milyen hosszú lesz a hátralévő út. A múltról NEM tárol semmit. Míg az optimális kereső: ami ADDIG a legolcsóbb volt, a múltat figyelte. Ez: a jövőt nézi, milyen hosszú lesz még.) Általában az elsőként nyilvántartott utat szoktuk nyilvántartani. Vagyis: ha kiterjesztés során előállítunk egy csúcsot, s szerepelt a keresőgráfban: nem foglalkozunk vele; nem szerepelt: nyílt csúcs lesz, visszamutatóval.

1. Adatbázis inicializálása: start csúcs, heurisztika megállapítása, nyílttá tesszük 2. Van-e nyílt csúcs? nincs: nincs megoldás van: kiválasztjuk a legkisebb heurisztikájút, s teszteljük. Célcsúcs? igen: rendben, visszamutatók alapján megvan a megoldás nem: kiterjesztjük. A keresőgráfban még nem szereplő gyermekeit felvesszük a nyílt csúcsok közé, szülőre visszamutatnak, becslés esetükben. A szülőt zárttá tesszük. Nincs minősített megoldáskeresés. A terminálási feltételek előrehozhatók; például kiterjesztéskor gyermekek tesztelése. Mit garantál? tetszőleges véges gráf esetén ha a reprezentációs gráf tartalmaz megoldást, akkor véges sok lépésen belül megoldást állít elő. Ha nincs megoldás: jelzi. Probléma: ha a heurisztika nem elég jó, akkor a keresés biztonságát, a garanciát elveszíthetjük.

2.2.2.2.4. A-algoritmusok a) "alap" A-algoritmus optimális keresés esetén: g(s) = 0 g(m) = g(n) + k(n,m) ,ahol (n,m) E, ill. k(n,m) d > 0 best-first:

h(m) 0 h(t) = 0

, ha t

h(m) =

, ha m-ből nem érhető el egyetlen

T

terminális sem Ötlet: ötvözzük a kettőt! f(m) = g(m) + h(m)

ez lesz a kiértékelő függvény, azaz a start-ból m-en keresztül valamilyen terminálisba való jutás becsült költsége

Nyilvántartja az m-ig vezető út költségét, ill. az m-ből a t-be vezető út becsült költségét. g*(m)

a start-ból m-be jutás optimális költsége

h*(m)

g(m) g*(m) m-ből milyen költséggel juthatunk legolcsóbban célba? célbajutás optimális költsége

f*(m)

,vagyis a becslés közelíti ezt az opt. értéket h(m) h*(m) start-ból m-en keresztül a célbajutás optimális költsége f*(m) = g*(m) + h*(m) ,elméleti érték, kiszámítani nem tudjuk

f*(s)

, f*(m) -et szeretnénk közelíteni f(m) f*(m) optimális megoldás költsége start-on keresztül a legolcsóbb célbajutás költsége f*(s) = h*(s) (hiszen g(s) = g*(s) = 0)

Működése: ezt az értéket fogjuk származtatni f(n) = g(n) + h(n) g(n) = f(n) - h(n) f(m) = g(m) + h(m) = g(n) + k(n,m) + h(m) = = f(n) - h(n) + k(n,m) + h(m) Kiterjesztésre mindig a legkisebb f(m) -űt kell kiválasztani! Hátra és előre is tekintünk! Összességében a legolcsóbbat terjesztjük ki. Kiterjesztésre kiválasztani: a legkisebb kiértékelőfüggvény-értékű nyílt csúcsot

1. m még nem szerepelt a keresőgráfban m-et felfűzzük a keresőgráfban nyílt csúcsként (n-re visszamutató pointer) f(m) = f(n) - h(n) + k(n,m) + h(m) 2. m szerepelt már a keresőgráfban a) b)

m-et feltártuk már, de még nem léptünk tovább (azaz nyílt csúcsként szerepel) Ha találunk hozzá egy kisebb költségű utat, akkor tároljuk azt le. Visszamutató nyíl n-re.

Zárt csúcsok problémája:

Zárt csúcsok problémája: m-ből egyszer már továbbmentünk. Amennyivel csökkent f(m) értéke, annyival kell csökkenteni az egész részgráf csúcsainak a költségét. Fel kell újítani!

1. járjuk be a rész-keresőgráfot, s frissítsünk. Gond: visszamutatókat használtunk, nem előremutatókat. (Reprezentációs változtatás). 2. bízzuk a dolgot az A-algoritmusra. Az m zárt csúcsból csináljunk nyílt csúcsot, s ekkor ez olyan, mintha a részgráfot még NEM jártuk volna be. Az újrabejáráskor lesz korrekció! megelőzés. Az optimális kereső olyan volt, hogy 3. mikorra egy csúcs zárt lett, akkor már nem található hozzá vezető kisebb költségű út. Vagyis az opt. keresőnél nincs ilyen gond.

Az optimális keresés egy speciális A-algoritmus, ahol h(n) = 0, vagyis nem számítunk heurisztikát. Kérdés: heurisztikával rendelkező A-algoritmus esetében működik-e? A válasz: igen, a heurisztikának kell olyannak lennie. A vezérlő működése: 1. az adatbázis inicializálása: 2. van-e nyílt csúcs? nincs: van:

start csúcs, nyílttá tesszük kiértékelő-függvény megállapítása sikertelen a keresés kiválasztjuk a legkisebb kiértékelőfüggvényű nyílt csúcsot. Teszteljük: célcsúcs? igen: jó, vége kiterjesztjük. Ha egy gyermeke még nem nem: szerepelt a keresőgráfban: felvesszük, pointer vissza, kiértékelő-függvény kiszámítása a szülő segítségével. Ha szerepelt már: megnézzük, hogy a hozzá vezető új út, vagy a már nyilvántartott (régi) út költsége-e kisebb? Ha az új út költsége (amit az új szülő alapján számítunk) kisebb: akkor van teendő, különben nincs. Ha az új út költsége kisebb: ha ez nyílt, akkor a visszamutatót átállítjuk az új szülőre, s regisztráljuk az új kiértékelő-függvényt. Ha zárt, akkor visszaminősítjük nyílt csúccsá, átírjuk a visszamutatót és a kiértékelőfüggvényt. Az épp kiterjesztett csúcsból zárt csúcs lesz.

Elvárások: tetszőleges reprezentációs gráf esetén ha van megoldás: megoldása a terminál véges sok lépésben. Felismeri véges esetben, ha nincs megoldás. Az optimális kereső is ilyesmi tulajdonságokkal bír, az egy speciális A-algoritmus, a szélességi pedig egy speciális optimális keresés. 1. lemma: az A-algoritmus működése során bármely nyílt csúcs véges sok lépés megtétele után kiterjesztésre kerül, hacsak közben az algoritmus terminális csúcs megtalálásával nem terminál. 2. lemma: az A-alg. terminálása előtt mindig van az optimális útnak eleme a nyílt csúcsok között. Állítás: az A-algoritmus megoldással rendelkező reprezentációs gráf esetén véges sok lépésben terminálissal terminál.

Bizonyítás (1. lemma): legyen

r a keresőgráf egy csúcsa f(r) kiértékelő-függvény (az r csúcsig vezető út költsége + heurisztika)

f(r) = g(r) + h(r) g(r) g*(r) A nyilvántartott, r-ig vezető út vagy az optimális, vagy sem, azaz mint az odavezető opt. út. d*(r) g*(r)

r-ig vezető optimélis út éleinek a száma optimális út költsége g*(r) d*(r) × d

összesen d*(r) él van

f(r) d*(r) × d

"r esetén

Vegyünk egy tetszőleges nyílt csúcsot: m f(m)

f(m) d*(m) × d

Határozzunk meg ebben a keresőgráfban egy olyan mélységet, amely az ismert adatokból meghatározható! m-be vezető legrövidebb mélység alatti mélység

m csúcs felette van a d szintnek legyen r a d-szintnél mélyebben lévő csúcs: d*(r) > d f(r) d*(r) × d

ö

d*(r) > d

ý ø

d*(r) × d > d × d

tehát f(r) > f(m)

d szint felett véges sok csúcsunk van. Véges sok f(m) -nél nyílt csúcsunk van. Nem csak kikerülhetnek nyílt csúcsok, de be is kerülhetnek, DE csak véges sokszor. (Az algoritmus működése során egy csúcs többször is bekerülhet a nyílt csúcsok közé; többször is ki lehet azt választani kiterjesztésre, de csak véges sokszor biztos, hogy minden csúcs véges sok lépés után kikerül a nyílt csúcsok közül.

Bizonyítás (2. lemma): A bizonyítás indukcióval történik. Első kiterjesztésre kiválasztás előtt van az optimális útnak eleme (a start csúcs). Vegyünk az optimális utak közül egyet: s = n1 n2 ... t = nk

start csúcs

utolsó csúcs, terminális

Indukciós feltétel: a k. kiterjesztés előtt tegyük fel, hogy ennek az optimális megoldásnak az i. csúcsa eleme a nyílt csúcsok halmazának (ni Nyílt). A (k+1). kiterjesztés előtt mi a helyzet? A k. lépésben kiterjesztéskor pont az ni -t terjesztettük ki. Előállítottuk az összes gyermekét, köztük ni+1 -et. Ha nem szerepelt: felvesszük nyílt csúcsként. Ha szerepelt (zárt csúcsként): akkor más úton már eljutottunk hozzá. Utódjai közül pár benne van a keresőgráfban pár nyílt csúcsként szerepel. Ha nem az ni -t választjuk kiterjesztésre: ő ott marad nyíltként. A kettő következménye: Az A-algoritmus nem garantálja, hogy az optimális megoldással terminál. Ha van megoldás, akkkor megoldással terminál. Bizonyítása: konstruktív módon:

Heurisztika:

S: 5 A: 3 B: 4 T: 0

Nyílt: S0(0+5) AS(2+3) TA(6+0)

Zárt:

BS(3+4) BS(3+4)

S0(0+5) AS(2+3)

teszt: célcsúcs, kész Holott: a másik út olcsóbb!!! Bebizonyítottuk, hogy az A-algoritmus nem garantálja az optimális megoldást!

b) A*-algoritmus Kérdés: A-algoritmussal előállítható-e az optimális megoldás? (az előbb a heurisztika rontotta el) Ha a heurisztikára adunk egy megkötést, akkor "megjavul". ALULRÓL kell becsülni. Minden csúcsban h(n) h*(n) Ekkor garancia lehet az optimális megoldás megtalálására. Ha a heurisztikánk alsó becslésű: A*-algoritmus. A csúcsokbeli heurisztikánk alulról becsüli a hátralévő optimális út költségét. Állítás: az A*-algoritmus optimális megoldás megtalálását garantálja Bizonyítás:

optimális megoldás: 0 heurisztika triviális Így a szélességire is beláttuk az állításunkat.

3. lemma: az A*-algoritmus által kiterjesztésre kiválasztott bármely csúcs kiértékelőfüggvénye nem nagyobb (kisebb egyenlő), mint az optimális út tényleges költsége: f(n) f*(s) Bizonyítás (3. lemma): 1. ha nincs megoldás (opt. költség = ), akkor f(n) = f*(n) = ,triviális eset 2. ha van megoldás, akkor van optimális megoldás is s = n0 ö n1 ÷ n2 ý problémmánk egy aktuális megoldása (opt. megoldása) ... ÷ t = nk ø Ennek az útnak lesz mindig eleme. Vegyük a legelső olyan elemet, ami a nyílt csúcsok között van: ni. Összes előtte levő: zárt. g(ni) = g*(ni) n - legyen ez az a csúcs, amelyet kiválasztottunk kiterjesztésre f(n)

f(összes_többi_nyílt_csúcs) ,azaz f(n) f(ni) (például)

f(n)

f(ni) =

g(ni) + h(ni) ¯ g*(ni)

Vagyis: f(n)

g*(ni) + h*(ni) = f*(ni) = f*(s)

¯ [h(ni) h*(ni)] (az alsó becslés miatt)

f*(s). Ezt akartuk belátni.

Az A*-algoritmus az optimális megoldással terminál, ha van megoldás.

c) Monoton A-algoritmus Az A-algoritmusnál a gond: zárt csúcsok. Ugyanazt a csúcsot esetleg többször is ki kell terjeszteni (zárt csúcsok problémája). Optimális kereső: speciális A-algoritmus, ahol a heurisztika 0. De van-e nem azonos nulla heurisztikával rendelkező algoritmus, mely ilyen tulajdonsággal bír? (vagyis ahol nem merül fel a zárt csúcsok problémája) Monoton heurisztika: h(n) h(m) + k(n,m) Azaz: szülő heurisztikája

"(n,m) E esetben gyermek heurisztikája + szülőből gyermekbe jutás költsége.

Az ilyen tulajdonságú A-algoritmus: monoton A-algoritmus.

Monoton heurisztikával rendelkezőA-alg. A*-alg. is egyben.

Tétel: Ha h monoton heurisztika, akkor h(n)

h*(n)

Bizonyítás: a) ha n-ből nem érhető el egyetlen terminális csúcs sem h(n) = h*(n) = b) ha n-ből elérhető valamelyik terminális csúcs n0,n1,n2,...,nl = t h(n0) h(n1) + k(n0,n1) h(n1) h(n2) + k(n1,n2) ... h(nl-1) h(nl) + k(nl-1,nl)

¯ h (n) *

h(n0) - h(nl) h*(n) h(n) h*(n) A tételt ezzel bebizonyítottuk!

(a hátralévő optimális út költsége) (a többi páronként 0) (mivel nl terminális csúcs, így heurisztikája 0)

Monoton heurisztika esetén bebizonyítható, hogy tetszőleges kiterjesztésre kiválasztott nyílt csúcs olyan, hogy az adott csúcsban a kiértékelő függvényben olyan értékkel számolunk, ami már optimális. Tétel: a monoton heurisztikájú A-algoritmus által kiterjesztésre kiválasztott minden nyílt csúcsra igaz, hogy g(n) = g*(n) Vagyis optimális megoldást állít elő, ill. a zárt csúcsok problémája itt nincs jelen! (hasonlóan mint az optimális keresőknél) Bizonyítás: s = n0,n1,...,nl = n

optimális út

n Nyílt és kiterjesztésre n-et választjuk Indukciós feltevés: t.f.h. még nem találtuk meg a hozzávezető opt. utat: g(n) > g*(n) ni

az optimális utunk első nyílt csúcsok közötti eleme

f(ni) = g(ni) + h(ni) = g*(ni) + h(ni) g*(ni) + h(ni+1) + k(ni,ni+1) = g*(ni+1) + h(ni+1) g*(ni+1) + h(ni+2) + k(ni+1,ni+2) = g*(ni+2) + h(ni+2) ... g*(nl) + h(nl) Hol is tartunk? f(ni) g*(n) + h(n) < g(n) + h(n) = f(n)

ELLENTMONDÁS!

Tehát a zárt csúcsok problémája a monoton A-algoritmusnál nem lép fel! (Ha egy csúcs zárt csúcs lett, akkor azzal már nem kell foglalkozni). a - súly a=0 a=1

best-first optimális kereső

A keresés során változtathatjuk is ezeket a súlyokat, s áttérhetünk az egyikről a másikra. Ilyen pl. a B-algoritmus! //kövi oldalon olvashatóó

Legyen P és Q két A*-algoritmus. Hasonlítsuk össze a kettőt a heurisztika alapján. P jobban informált mint Q, ha hQ(n) < hP(n) h*(n) Egy jobban informált nem használ nagyobb gráfot mint a kevésbé informált. Tétel: Legyen P és Q két A*-algoritmus. Ha P jobban informált, mint Q Q minden olyan csúcsot kiterjeszt, amit P is. Bizonyítás: T.f.h. P kiterjeszt egy n Nyílt csúcsot. Ekkor (lemma 3 segítségével): fP(n) n' s

f*(s)

n : fP(n') f*(s)

mivel P jobban informált, mint Q

hQ(n') < hP(n')

fQ(n') = g(n') + hQ(n') < g(n') + hP(n') = fP(n') f*(s)

2.2.2.2.5. B-algoritmus Indulunk az A-algoritmussal, de regisztráljuk az addigi legnagyobb kiértékelő függvényű csúcsot. Addigi Ln := f(s) Ha a kiértékelőfüggvény az addigi Ln-nál kisebb, akkor opt. keresővel folytatjuk, egyébként meg A*-gal. Ha h(n) h*(n) ,akkor ugyanazt állítja elő, mint az A*-algoritmus, csak a kiterjesztések száma lecsökken.

2.3. Probléma-redukciós reprezentáció 2.3.1. Probléma-redukció Nagyon gyakori a feladat egyszerűsítése, részproblémákra bontása.

P:

a megoldandó probléma. Ezt valahogy le kell írni. Ez akár az állapottérrel is leírható, de most nem az a fontos. Ehhez a problémához hasonló problémákat keresünk. probléma-halmaz (ebbe gyűjtjük össze őket)

p P

ennek a mi problémánk is eleme lesz

p:

e E

P

egy ismert probléma is legyen benne! Ez az egyszerű probléma. e:

1. meg tudjuk oldani, ismerjük a megoldását 2. meg tudjuk mondani, hogy nem megoldható

Az induló problémát addig kellene gyúrni, alakítani, míg csupa egyszerű probléma nem állna elő. redukciós operátor

r R

dom(r)

P

(egy problémaosztálybeli problémát tud egyszerűsíteni) van előfeltétele is!

r: P

2P

r(p) = {p1,...,pn}

P részhalmazainak a halmazába képez tehát részproblémákra bont, egyszerű részekre bont (n 1)

ezzel a négyessel tudjuk megadni a probléma probléma-redukciós reprezentációját

Def.: P1 = {p1,...,pi-1,pi,pi+1,...,pn} P2 = {p1,...,pi-1,q1,q2,...,qm,pi+1,...,pn} P1-ből egy lépésben (közvetlenül) redukálható P2, ha van: r R: pi dom(r) és r(pi) = {q1,...,qm} Def: A P' problémahalmazból a P'' redukálható, ha van: ·

P' = P0,P1,...,Pk = P'' problémahalmaz-sorozat és

·

Pi

Pi+1 (i = 0,1,...,k-1)

P1

P2

Mikor megoldható? Ha a kezdőproblémából (mint 1 elemű problémahalmazból) csupa megoldható egyszerű problémát tartalmazó halmazt redukálhatunk. Megoldás: az azt megvalósító ri redukciós operátorsorozat. Megint egy keresési feladattal állunk szemben: egy operátorsorozatot keresünk. Itt is lehet költség, redukciós operátor alkalmazási költsége. Megoldás költsége: a megoldásban szereplő operátorsorozat alkalmazási költségeinek összege. 2.3.2. Szemléltetése Problémánk probléma-redukciós reprezentációját a négyessel tudjuk megadni. q P

n N

egy problémát egy csúccsal jelölünk

p P

s N

start-csúcs

e E

P

t T

N

terminális csúcsok

r R r(q) = {q1,...,qk}

k 1

r'(q) = {z1,z2,...,zl} 1 csúcsból annyi élköteg indul, ahány redukciós operátort alkalmazunk, s egy élköteg annyi élből áll, ahány részprobléma állt elő. ÉS, AND élköteg VAGY, OR élköteg

hiperút:

minden részproblémát egy élkötegben kell megoldani vagy az egyik redukció segítségével bontom részproblémákra, vagy a másikkal és/vagy problémaredukciós (reprezentációs) gráf, ahol: G: gráf s: start csúcs T: terminális csúcs(ok) olyan összefüggő része az és/vagy gráfnak, melyben minden csúcsból legfeljebb 1 ÉS-élköteg indul ki. (Ha 1 ÉS-élköteget 1-nek veszünk, akkor az út fogalmához jutunk).

A hiperút a start csúcsból indul, s a levelek: csupa megoldható terminális levelek. A megoldást egy olyan hiperút szemlélteti, mely a start csúcsból indul, s levelei csupa megoldható terminális csúcsok. A megoldáskeresés során egy általánosabb gráfban egy részgráfot keresünk.

k(n, {n1,...,nk})

redukciós operátor alkalmazási költsége ,ahol K - csúcshalmaz

æ 0, ha n g(n,K) = í

K

è

æ c(n) , ha n k(n,{}) = í è

E megoldható

,ha n nem megoldható

Tiszta ÉS-VAGY gráf: olyan gráf, amelyben minden csúcsból csak ÉS vagy csak VAGY élkötegek indulnak ki. Például adott a következő ÉS-VAGY gráf:

Elérhető, hogy csak ÉS vagy csak VAGY élkötegeket tartalmazzon:

Fiktív csúcsokat kell beiktatni. Annyi kell, ahény VAGY élköteg indul ki. Mellette feltüntetve: melyik redukciós operátorral kaptuk. Megoldáskereső módszerek: I. II.

nem-módosítható megoldáskeresők (nem foglalkozunk velük) módosítható keresők a. visszalépéses (backtrack) b. keresőgráffal

2.4. Probléma-redukcióval leírt feladatok megoldását kereső módszerek Osztályozásuk: I. II.

nem-módosítható megoldáskeresők (nem foglalkozunk velük) módosítható keresők a. visszalépéses (backtrack) b. keresőgráffal

2.4.1. Backtrack (visszalépéses) állapottér-reprezentáció esetén:

ÉS-VAGY gráf esetén:

Levelei:

Csúcsok:

adatbázis: start csúcsból induló valamilyen út a reprezentációs gráfban. Aktuális út. Aktuális állapot: az út végi csúcs. Ennek a vizsgálata döntötte el, hogy hogyan tovább. adatbázis: egy hiperút, a start csúcsból indul. Ebből szeretnénk megoldást készíteni. Aktuális hiperút. az eredeti problémának valamilyen szintű részproblémái. Ha a levelek mind egyszerű megoldható problémák: megoldás: probléma, részprobléma, amit éppen reprezentál

Miket tartunk nyilván a csúcsokban? 1. mutató gyermekére, az 1. gyermekére köv. mutató a testvérre szülőre mutató mutató (a visszalépéshez) 2. a még nem alkalmazott (de alkalmazható) redukciós operátorokra valamilyen információ 3. címke (az adott probléma megoldását tartalmazza-e a hiperút vagy sem?) Amikor egy csúcsot előállítunk megnézzük, hogy az egyszerű problémák között szerepelt-e már? Háromféle címkét fogunk alkalmazni: 1. M (megoldható egyszerű probléma) 2. N (nem megoldható egyszerű probléma) 3. F (a többi problémának ez a címkéje, azt jelzi, hogy még folyik a munka) Műveletek:

1. redukciós operátorok 2. visszalépés

1. redukciós operátorok:

csak F címkéjű levelekre alkalmazható! előállítjuk a részproblémákat, s felfűzzük az akt. hiperútra az adott csúcshoz, mint szülőhöz (szülőnél egy mutató fog az 1. gyermekre mutatni). Szülőnél operátor törlése (mert azt már alkalmaztuk). Gyermekek: megjelenik az adott probléma szülőre visszamutató mutató mindegyiknél köv. mutató a testvérre felcímkézzük F címke esetén: összes alk. red. op. felvétele

2. visszalépés:

csak N címkéjű levelekre alkalmazható! Ha a gyermekek közt megjelent egy N címkéjű csúcs, akkor visszalépés: valamilyen más redukcióval kell a hiperutat megoldani. Redukciós operátor hatásának visszavonása:

Kitöröljük a szülő gyermekeit: az N címkéjű csúcsban van egy visszamutató a szülőre (1.), ahonnan elérhető az 1. gyermek (2.). Innen van egy mutató a következő testvérre, ezáltal a szülő gyermekeit be tudjuk járni, s ki tudjuk őket törölni. A visszalépés műveletét kell még akkor is alkalmaznunk, amikor az adott csúcsban elfogytak az alkalmazható operátorok. F címkéjű a csúcs, őt kellene redukálni, de már az összes operátor elfogyott: ekkor is visszalépés.

A vezérlő: 1. inicializálás:

ha a címka F, akkor keresésről van szó

2. keresés (pszeudó-kód): van = választFlevél(n); //(*) 1 2 while (van) 3 { op = választRedOp(n);//(*) 4 5 if (op != 0) 6 { 7 GY = alk(n, op); 8 hiperútbővítés(GY, n, op); 9 if (Ncímkéjű(n, m)) visszalép(m); 10 } 11 else visszalép(n); 12 13 van = választFlevél(n); 14 } magyarázat: 1 egy F címkéjű levéllel tér vissza, ha van ilyen 2 addig dolgozunk, míg van F címkéjű csúcs 3 4 a kiválasztott csúcs esetében választunk egy operátort 5 ha van alkalmazható operátor, akkor (7-8-9), különben meg visszalépés 6 7 előállítjuk a csúcs gyermekeit (GY) 8 a gyermekeket felfűzzük: maga a probléma, szülő mutat az 1. gyermekre, gyermekek köv. mutatója a testvérre mutat, gyermekek visszamutatnak a szülőre, felcímkézzük a gyermekeket 9 a szülőtől bejárjuk a gyermekeket, s N címkéjűt keresünk ha találunk (m-ben adja vissza), akkor visszalépés 10 11 ha az 5-ös pontban nem találtunk alkalmazható operátort, akkor visszalépés 12 13 keressük a következő F címkéjű csúcsot. 14 Ha a start csúcsból lépünk vissza: sikertelen a megoldáskeresés. Beszélhetünk szisztematikus ill. heurisztikus keresésről. Ezen megoldáskeresők a (*)-gal jelölt két választásban térhetnek el lényeges módon (valasztFlevel, valasztRedOp). Heurisztikus esetben hogyan válasszunk? HA van becslés a megoldás költségére, akkor válasszuk a LEGNEHEZEBBET! A valasztFlevel() válassza a legnehezebb problémát!

2.4.2. Keresőgráffal megoldást keresők Állapottér-reprezentációs esetben akkor volt meg a megoldás, amikor a tesztelésre kiválasztott csúcs eleget tett a célfeltételnek. Problémaredukciós esetben a terminálás figyelésére bevezetjük a címkemódszert. Háromféle címkét fogunk alkalmazni: 1. M (megoldható egyszerű probléma) 2. N (nem megoldható egyszerű probléma) 3. F (a többi problémának ez a címkéje, azt jelzi, hogy még folyik a munka) Két eljárás:

- címkéző

- címkemódosító

(az előbb a visszalépéses módszernél tulajdonképpen egy ilyet használtunk. Amikor az adatbázisba bekerül egy új csúcs, akkor azt címkézzük). (a címkék módosíthatóak. Ha a címkéző egy F-től különböző címkét ad egy csúcsnak, akkor ennek a szülőre nézve következményei lesznek).

ha ő VAGY-gyermek, ekkor még nem tudunk mit mondani! akkor a szülő is M lesz

még nem tudunk mit mondani!

ha ő ÉS-gyermek és N címkéjű, akkor a szülő is N lesz

Ha a csúcsnál egy F-től különböző címke jelenik meg, akkor indul a címkemódosító eljárás a csúcs szülőjére nézve. Ha a start csúcsban M címke jelenik meg: van megoldás, előállt a megoldás Ha a start csúcsban N címke jelenik meg: nem oldható meg Egyedül a start csúcs címkéjét kell tehát figyelni! Ha F: folytatjuk a keresést. Ha M, N: sikeres, sikertelen terminálás. Az adatbázis ebben az esetben egy keresőgráf. Hiperutak, melyek a start csúcsból indulnak. Ezek valamelyikéből remélünk megoldást. ÉS-VAGY fagráfok. A hiperutak közül választunk egyet, másrészt ha kiválasztottuk: ezen a hiperúton a még meg nem oldott problémák közül IS választani kell. Itt is beszélhetünk szisztematikus ill. heurisztikus keresésről. Heurisztikus esetben: melyik hiperúton reméljük a megoldást, ill. azon belül a legnehezebb megoldást választjuk ki. Ha kiválasztottuk: kiterjesztjük. Az összes redukciós operátort alkalmazzuk rá. A leveleket címkézzük, s ha kell módosítjuk a szülőt is. Megoldás: a start csúcs címkéje M-re vált.

Az N címkéjű csúcsokból induló hiperútrészleteket töröljük. Az A-algoritmus valamilyen módosítását fogjuk alkalmazni. Ez lesz az: AO-algoritmus Adatbázis: s-ből induló hiperutak (keresés során már felderített hiperutak) csúcsinformáció:

maga a probléma 1. gyermekre mutató mutató következő ÉS testvér (új) következő VAGY testvér (új) szülőre mutató mutató kiértékelő-függvény (új) címke információ a redukciós operátorokról

Művelet: kiterjesztés művelete (pszeudó-kóddal): while (vanMégRedOp(n, op)) { GY = alk(n, op); hiperútbővítés(GY, n, op); } címkemódosító(); kiértékelőfüggvényMódosító(); NcímkéjűHiperutakEltávolítása(); Vezérlő: (pszeudó-kóddal): 1. inicializálás:

2. van = választHiperút(h); while (van && (címke(h)!=M)) { választFlevél(h, n); kiterjeszt(h, n); van = választHiperút(h); }

Kiértékelőfüggvény: æ 0, ha M címkéjű ç

, ha N címkéjű

f(n) = í ç h(n), ha F címkéjű és n levél è , ha F címkéjű és n nem levél

3. Kétszemélyes, teljes információjú játékok 3.1. A játékok osztályozása A játékokat két nagy csoportba tudjuk sorolni: 1. szerencsejátékok (itt minden a véletlen műve, pl.: rulett) 2. stratégiai játékok (a játékos befolyásolhatja a játék kimenetét, pl.: sakk, malom, amőba, üzleti "játékok", harci "játékok") Neumann János maga is foglalkozott ezzel. Harsányi János 1994-ben közgazdasági Nobel-díjat kapott; a játékelmélet az ő nevéhez fűződik. Stratégiai játékok osztályozása: résztvevők száma: 2,3,...,n személyes játékok (néha a véletlent is személynek veszik) véges játékok: olyan stratégiai játékok, amelyben minden állásban véges sok szabályos lépés közül lehet választani, s véges sok lépés után véget ér zérusösszegű: ha nyeremények + veszteségek = 0 (beszélhetünk nem zérusösszegű stratégiai játékokról is) véletlen szerepe: 1. sztochasztikus (pl. bridge) 2. determinisztikus (pl. sakk) teljes információjú: tudom, hogy a másik mit lépett. A játékosok a játékkal kapcsolatos összes információt ismerik, s felváltva lépnek. Leírás:

játékszabályok megadása Milyen játékállások fordulhatnak elő, az egyes állásokban milyen szabályos lépések vannak, mik ezeknek az előfeltétele. Célfeltétel: mikor kell befejezni, milyen állásban, s ekkor kit kell győztesnek kikiáltani.

A kétszemélyes játékot is le kell írni. Ehhez a következő leírást alkalmazzuk: 3.2. A játékok reprezentációja és a reprezentáció szemléltetése H legyen a játék állásainak a halmaza, {A, B} a két játékos. All = { (h, x) | h H, x {A, B} }

- ez az állapottér, ahol x azt jelzi, hogy ki következik

Kezdőállapot: k = (i, I)

,ahol i

H kezdőállás, I

{A, B} kezdő játékos

Végállapot: V = { (h, x) | h H végállások, x nyertes v. vesztes }

megállapodás kérdése, hogy x nyertes vagy vesztes

Lépés: l: H

H

előfeltétell(h)

az egyes lépésekhez előfeltételek is tartoznak

Operátorok: O = { o: (h, x) ® (h', x') | l: h ® h', előfeltétell(h) teljesül, h,h' Î H és x' = x ellenfele } A játék állásait egy reprezentációs gráffal tudjuk szemléltetni. A reprezentációs gráf egy játékgráf:

Véges játék esetén véges a gráf is. Minden út benne véges. Körök: a játékszabályok ezt általában nem engedik, vagy adnak rá valami korlátozást (a köröket fává egyenesítéssel is fel lehet oldani). A start csúcsból egy levélbe vezető út: egy lehetséges játszma. 3.3. A stratégia Egy játékos számára hogyan lehetne egy teret adni, ami befolyásolná a játék kimenetét? Stratégia. Ez mindig egy (1) játékoshoz tartozik. Minden, a játék során előforduló állapotban amikor ő következik a stratégia megmondja, hogy mit lépjen. A stratégia tehát egy döntés. Jó a stratégia, ha minden állapotra van terv, bármit is lép az ellenfél. Lehetséges hiperutak: a játékos különböző stratégiái. Ahány különböző hiperút, annyi különböző lehetséges stratégia a játékos számára. Gyűjtsük össze a játék során előfordulható összes állapotot:

Tegyük fel, hogy például A szeretne nyerni. Ekkor a start állapotnak szerepelnie kell a stratégiában. Menjünk tovább a zölddel jelölt részen. B viszont (az ellenfél) bármit léphet, ezért az ÖSSZES olyan állapotnak is szerepelnie kell a stratégiában amelyet B léphet, hiszen az ellenfél minden válaszlépésére reagálni kell tudni! Ahol A következik lépni: választunk a szabályos lépések közül. VAGY lépések vannak, lehet választani. B lépései ÉS élek. Ha B lép, akkor a stratégiába fel kell venni mindazon állapotokat, ahova B léphet. Át kell alakítani a játékfát az ADOTT játékos alapján ÉS-VAGY gráffá. Ebben kell hiperutakat keresni! Az adott játékosnál VAGY élek lesznek, az ellenfélnél pedig ÉS élek.

Hogyan választunk: úgy, hogy a játék kimenetele lehetőleg nyeréssel végződjön, ne veszítsünk. Nyerő stratégia: a stratégiával játszva a másik játékos lépéseitől függetlenül garantáltan nyerünk! Ha a levélelemek mind nyerőállások, akkor a stratégia nyerő. Feladat: a stratégiák közül válasszunk nyerő stratégiát. 3.4. Adott állásban a következő lépés kiválasztásának módszerei Minden kétszemélyes, teljes információjú játék esetén az egyik (és csakis az egyik) játékos számára garantáltan van nyerő stratégia. Ha van, akkor több is lehet. Kérdés: melyik játékos számára lesz? Az állítás csupán azt garantálja, hogy az egyiknek van nyerő stratégiája. Bizonyítása konstruktív módon történik, s ehhez az egész játékfát elő kell állítani: A leveleket megcímkézzük azalapján, hogy ott ki nyert. Ezután visszafelé haladunk (itt középső szint), s megnézzük, hogy ki lép (itt B). Mivel B tud úgy lépni innen, hogy ő nyerjen, ezért B-t írunk be (szürkével jelölve). Mint látható, ez egy B nyerő játék. A start csúcs címkéje határozza meg, hogy kinek van nyerő stratégiája. Ez megkonstruálja a nyerő játékost, s a nyerő stratégiát is. Címkemódszer. A címke jelöli, hogy az adott állásból kinek van nyerő stratégiája. Az előbbi címkemódszerrel akkor van gond, ha túl nagy a játékfa (nem tudjuk előállítani), s így explicit módon nem tudjuk meghatározni hogy ki nyer. Ekkor használjuk a következő módszerek egyikét: 3.4.1. Mini-max módszer Nem építjük fel az adott állásban a teljes játékfát (pl. nem tudjuk, mert olyan nagy lenne). Amit tehetünk: néhány lépésre előre kombinálunk. Az adott állásból kiinduló játékfának csak egy részét állítjuk elő. A kialakuló állások (levélelemek) nem végállások, de mégis valahogy minősíteni kellene őket, hogy tudjunk választani. Valamilyen heurisztikára lesz szükség, amely megmondja, hogy az adott játékos számára az adott állás mennyire jó, mennyire ígéretes. Minél jobb az állás, annál nagyobb értéket rendelünk hozzá. Döntetlen: 0 körüli érték. Ha az ellenfél számára jobb: negatív érték.

Az azonos szinten lévő levélelemeket kiértékeljük (heurisztika). Az ősöknél ezt vesszük figyelembe, ill. azt, hogy ki következik lépni.

Ha A következik:

a legnagyobb értékű gyermeket fogjuk választani (nekünk az a legjobb) a legkisebb értékűt választjuk (ez B-nek a legjobb, ezért úgy számítunk, hogy ő azt fogja lépni, ami neki a legjobb)

Ha B következik:

Ez a módszer az alapja minden kétszemélyes játékkal kapcsolatos tanácsadásnak! 3.4.2. Nega-max módszer Egy állás kiértékelőfüggvénye az egyik játékos szempontjából értékeli ki az állásokat. Amennyire jó nekünk egy állás, annyira rossz az ellenfélnek (és fordítva). B számára egy állás heurisztikája pontosan az ellentetje az A heurisztikájának. -hA(n) = hB(n) Nem kell szintről-szintre megvizsgálni, hogy ki következik! Levélszinten az ellenfél szerinti kiértékelőfüggvényeket adjuk meg. Ez a játékos pontosan a szülő szint ellenfele. A szülő szinten a lenti értékek az ellentettjére változnak, s ezek közül a maximumot vesszük. A módszer előnye: nem kell egyik szinten minimumot, másikon maximumot venni. Eredménye amúgy azonos az előző módszerével. Mindig a maximumot kell venni. 3.4.3. Alfa-béta vágás Generálás közben fog kiderülni, hogy mekkora részlet kell. Amint van a szülőnek gyermeke, a szülő pontos értékének alsó vagy felső becslését meg tudjuk adni. Max. szülő

alsó becslését tudjuk megadni a végleges értéknek

Min. szülő

felső becslését tudjuk megadni a végleges értéknek

a csúcs értéke legalább 3 lesz

a csúcs értéke legfeljebb 3 lesz

Lehet, hogy még nem állítottuk elő az összes gyermeket, de már tudunk valamit mondani a szülőről. A zölddel jelölt résznél vágunk, mivel azt a részt már nem kell előállítani, hiszen már biztos, hogy nem fog "beleszólni" a felette lévő részbe. -vágás, mert az

alatt vágtuk el

A zölddel jelölt résznél vágunk, mivel az az alatti rész végleges, pontos értékének a kiszámítása már biztos hogy nem fogja módosítani az eredményt. -vágás, mert a

alatt vágtuk el

Ez a módszer is ugyanazt a javaslatot eredményezi, mint a mini-max módszer. Előnye: csökken a játékfa mérete, mert bizonyos részeket nem kell előállítani. - ha ez teljesül, akkor lehet vágni