Informatika | Mesterséges intelligencia » Mesterséges intelligencia 2. laborgyakorlat

Mesterséges intelligencia 2. laborgyakorlat Keresési módszerek A legtöbb feladatot meg lehet határozni keresési feladatként: egy ún. állapottérben, –amely tartalmazza az összes lehetséges állapotot– fogjuk keresni a megoldást. A keresést úgy fogjuk tekinteni mint egy keresési fa építését. Az algoritmus minden egyes lépésben valamilyen stratégia szerint kiválaszt egy levelet, amelyet kifejt, és az így kapott csúcsokat gyerekként beteszi a kifejtett csúcs alá. A fában a gyökér a kiinduló állapot, a levelek azok a csúcsok amelyek kibontásra várnak. A keresés addig tart, amíg vagy meg nem kaptuk a keresett csúcsot, vagy nincs több kibontható levél. A kibontásra váró leveleket rendszerint egy sorban tároljuk. Az a mód, ahogyan ide újabb csúcsokat teszünk be, illetve távolítunk el képezi a keresési stratégia lényegét. Minden keresési módszernél a következő tulajdonságokat kell figyelembe venni: 1. teljesség - a

stratégia megtalálja-e a megoldást? 2. időigény 3. tárigény 4. optimalitás - ha több megoldás van, akkor a legjobbat adja-e vissza? Nem informált (vak - blind) keresési módszerek Ebben az esetben semmiféle információnk nincs az aktuális állapotból a célállapotba vezető út lépésszámáról, vagy útköltségéről. Az ilyen keresési algoritmusok csak arra képesek, hogy meg tudják különböztetni a célállapotokat a nem célállapotoktól. Szélességi keresés 1 NODE * breadth first search(NODE root) 2 { 3 QUEUE * queue = QUEUE new(); 4 QUEUE push back(queue, root); 5 while(!QUEUE is empty(queue)) 6 { 7 NODE * act = QUEUE pop front(queue); 8 if (is solution(act)) 9 { 10 QUEUE free(queue); 11 return act; 12 } 13 while(NODE has more child(act)) 14 QUEUE push back(queue, NODE next child(act)); 15 } 16 QUEUE free(queue); 17 return NULL; 18 } Tulajdonságok: teljes, exponenciális memóriaigény, exponenciális időigény. Egyenletes költségű

keresés Az egyenletes költségű keresés (EKK) a szélességi keresés módosított változata. Az EKK nem a legelső elemet veszi ki a kibontásra váró csúcsok sorából, hanem azt, amely minimizál egy g (·) útköltség függvényt. Az útköltség függvény a gyökérből az illető csúcsig való eljutás költségét jelenti. Ha ez a költség a csúcs mélységével egyenlő, akkor visszakapjuk a szélességi keresést. 1 NODE * uniform cost search(NODE root) 2 { 3 QUEUE * queue = QUEUE new(); 4 QUEUE push back(queue, root); 5 while(!QUEUE is empty(queue)) 6 { 7 NODE * act = QUEUE pop min(queue, g); 8 if (is solution(act)) 9 { 10 QUEUE free(queue); 11 return act; 12 } 13 while(NODE has more child(act)) 14 QUEUE push back(queue, NODE next child(act)); 15 } 16 QUEUE free(queue); 17 return NULL; 18 } Tulajdonságok: bizonyos feltételek mellett (g (chi l d i (X )) ≥ g (X ) ∀i ) optimális, exponenciális tárigény, exponenciális időigény. Mélységi

keresés 1 NODE * depth first search(NODE root) 2 { 3 QUEUE * queue = QUEUE new(); 4 QUEUE push front(queue, root); 5 while(!QUEUE is empty(queue)) 6 { 7 NODE * act = QUEUE pop front(queue); 8 if (is solution(act)) 9 { 10 QUEUE free(queue); 11 return act; 12 } 13 while(NODE has more child(act)) 14 QUEUE push front(queue, NODE next child(act)); 15 } 16 QUEUE free(queue); 17 return NULL; 18 } Tulajdonságok: lineáris memóriaigény, exponenciális időigény. Mélységkorlátozott keresés 1 NODE * depth limited search(NODE root, int max depth) 2 { 3 QUEUE * queue = QUEUE new(); 4 QUEUE push front(queue, root); 5 int depth = 1; 6 while(!QUEUE is empty(queue)) 7 { 8 NODE * act = QUEUE pop front(queue); 9 if (is solution(act)) 10 { 11 QUEUE free(queue); 12 return act; 13 } 14 if (NODE is last child(act)) depth--; 15 if (depth < max depth) 16 { 17 while(NODE has more child(act)) 18 QUEUE push front(queue, NODE next child(act)); 19 depth++; 20 } 21 } 22 QUEUE free(queue); 23

return NULL; 24 } Tulajdonságok: nem teljes, nem optimális, lineáris memóriaigény, exponenciális időigény. Iteratívan mélyülő keresés 1 NODE * iterative deepening search(NODE root) 2 { 3 int i; 4 NODE * res; 5 for (i = 0; i < INFINITY; i++) 6 if (res = depth limited search(root, i)) return res; 7 } Tulajdonságok: nem optimális, bizonyos feltételek mellett teljes, lineáris memóriaigény, exponenciális időigény. Informált keresési módszerek Ebben az esetben problémaspecifikus információkat is figyelembe veszünk. Mohó módszer Legyen h(n) egy olyan függvény, amely megbecsüli egy n állapotnak a célállapotba vezető út költségét. A kifejtésre váró csomópontok közül azt választjuk ki mindig, amelyre a h minimális. Megkötés: h(n) = 0, ha n egy célállapot. Mohó keresés 1 NODE * greedy search(NODE root) 2 { 3 QUEUE * queue = QUEUE new(); 4 QUEUE push back(queue, root); 5 while(!QUEUE is empty(queue)) 6 { 7 NODE * act = QUEUE

pop min(queue, h); 8 if (is solution(act)) 9 { 10 QUEUE free(queue); 11 return act; 12 } 13 while(NODE has more child(act)) 14 QUEUE push back(queue, NODE next child(act)); 15 } 16 QUEUE free(queue); 17 return NULL; 18 } A* algoritmus Az A* algoritmus ötvözi az egyenletes költségű keresés és a mohó módszer előnyeit. Az egyenletes költségű keresés teljes, és optimális, a mohó módszer pedig a becsült távolságot minimizálja. Legyen • g (n) az a függvény, amely a start állapotból az n állapotig tartó út valódi költségét adja meg • h(n) egy olyan heurisztikus függvény, amely megbecsüli az n állapotnak a célállapotba vezető út költségét. • f (n) = g (n) + h(n) Az A* algoritmus egy legjobbat először típusú keresés, ahol a csomópontok közül azt választjuk ki mindig, amelyre f minimális. Az A* a legjobb megoldást találja meg, feltéve, hogy h nem ad pesszimista becslést. Ezt elfogadható heurisztikának hívják. A

heurisztikus függvénnyel kontrollálhatjuk az A* viselkedését: • ha h(n) = 0, akkor csak g (n) játszik szerepet, tehát visszakapjuk az egyenletes költségű keresést • ha h(n) mindig kisebb vagy egyenlő mint n-ből a célba vezető optimális út valódi költsége (h elfogadható heurisztika), akkor A* garantáltan megtalálja a legrövidebb utat • ha h(n) pontosan egyenő az n-ből a célba vezető optimális út költségével, akkor A* csak a legrövidebb úton levő csomópontokat fogja kibontani, ezért rendkívül gyors lesz • ha h(n) nagyobb mint a mint n-ből a célba vezető optimális út valódi költsége, akkor az A* nem biztos, hogy a legrövidebb utat találja meg • ha h(n) À g (n), akkor csak a heurisztikus függvény fog szerepet játszani a keresésben, és A* visszaalakul mohó kereséssé. Heurisztikák rácsszerkezetű állapotterekre: • Manhattan távolság: h(n) := λ(abs(n.x − cél x) + abs(ny − cél y)) p • Euklideszi

távolság: h(n) := λ (n.x − cél x)2 + (ny − cél y)2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Initialize OPEN list Initialize CLOSED list Create goal node; call it node goal Create start node; call it node start Add node start to the OPEN list while the OPEN list is not empty { Get node n off the OPEN list with the lowest f(n) Add n to the CLOSED list if n is the same as node goal then return Solution(n) Generate each successor node n’ of n for each successor node n’ of n { Set the parent of n’ to n Set h(n’) to be the heuristically estimate distance to node goal Set g(n’) to be g(n) plus the cost to get to n’ from n Set f(n’) to be g(n’) plus h(n’) if n’ is on the OPEN list and the existing one is as good or better then discard n’ and continue if n’ is on the CLOSED list and the existing one is as good or better then discard n’ and continue Remove occurrences of n’ from OPEN and CLOSED Add n’ to the

OPEN list } } return failure Feladatok 1. Az A* algoritmust használva oldja meg a 8-as (n-es) kirakójátékot. GUI nem szükséges Beküldési határidő: március 17, 23:59. 2. EC +1 pont Módosítsa a rabló-pandúr játékot úgy, hogy • a pályán véletlenszerű akadályokat helyez el, és • a rendőrök stratégiájának részét képezi az A* algoritmus. Könyvészet 1. Russel&Norvig – Mesterséges intelligencia modern megközelítésben 2. http://theorystanfordedu/~amitp/GameProgramming/AStarComparisonhtml#S3 3. http://wwwbriangrinsteadcom/files/astar/