20071217A

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

1. Milyen környezettipusokat ismer? Milyen különösképpen egy (nem)hozzáférhető környezet? (5p)

• Hozzáférhető vagy nem hozzáférhető
• Determinisztikus vagy nem determinisztikus
• Epizódszerű vagy nem epizódszerű
• Statikus vagy dinamikus
• Diszkrét vagy folytonos

Ha az ágens érzékelő berendezése hozzáférést nyújt a környezet teljes állapotához, akkor az egy hozzáférhető környezet.

2. Hogyan működik az iteratív A* keresés? (5p)

Minden egyes iteráció egy mélységi keresés.

A mélységkorlát helyett egy f-költség korlát.Minden egyes iteráció kifejti az összes -az adott f-költség határvonalon belül fekvő-csomópontot, átnézve a határvonalon, hogy megtalálja, hol fekszik a következőhatárvonal.

3. Magyarázza meg, hogy az indukció milyen, az ágens számára hasznos módszer általános modellje? (5p)

Az indukció az általánosítás modellje. Sok tényt egyetlen ténnyel helyettesítünk. A probléma mérete és bonyolultsága így csökken, az expontenciális jelleg kevésbé zavaró. DE formálisan nem igaz! Ez a tanulás általános modellje.

Kicsit bővebben, hogy miért nem igaz formálisan.

Tegyük fel, hogy a következő tényeket állnak rendelkezésünkre:

- ha felhős az ég és nem süt a nap, akkor esik - ha felhős az ég és Marika néninél esernyő van, akkor esik

Ebből a következő általánosítás vonható le:

- ha felhős az ég, akkor esik

DE! Ez formálisan nem igaz, hiszen ha hozzáadunk egy új állítást, ami erre nem illesztkedik, akkor már nem lesz igaz az előbbi állítás. Például:

- ha felhős az ég és fúj a szél, akkor nem esik

Így mégsem igaz a következtetésünk.

4. Mi a szituációkalkulus? Irjon fel, informális szóbeli magyarázattal kisérve egy olyan szituációkalkulusbeli állítást, amely az apparátusra jellemző minden elemet tartalmaz! (5p)

A változások leírásának egy bizonyos módja az elsőrendű logikában. A világ a szituációk sorozatából áll mindegyike egy pillanatfelvétel a világállapotáról.

Ha nagyon szűken értelmezzük a "szituációkalkulus apparátusa" részt, akkor itt a Eredményez függvény,keret és hatás axiómák kellenek. (Keret és hatás axiómákat összevonva kapjuk az utód-állapot axiómát.)

Esetleg még ide lehet venni ilyeneket is, hogy: - minden relációnál vagy tulajdonságnál, amely időben változhat a hozzátartozó predikátumhoz egy extra szituáció argumentumhozzáadása - ok-okozati szabályok - diagnosztikai szabályok

Lehetséges "informális szóbeli magyarázattal kisért állítás": A legegyszerűbb az utód-állapot axiómával trükközni.

[math] \forall a, x, s Kinyitva(x,Eredmenyez(a,s)) \Leftrightarrow [(a = Kinyitas \wedge Ajto(x) \wedge Szoba Ajtaja(x,s) \wedge Szoba(s)) \vee (Kinyitva(x,s) \wedge a \neq Becsukas)][/math]

Ha az "a" művelet a Kinyitás és x egy ajtó és x az s szoba ajtaja és s egy szoba, akkor az ajtó "Kinyitva" lesz. Ehhez persze az is kell, hogy ha már nyitva van, akkor ne legyen "a" művelet "Becsukás".

Általánosságban:

[math] Igazutána \Leftrightarrow [bármely cselekvés,amely igazzá tette \wedge már igaz volt és nem volt olyan cselekvés,ami hamissá tette volna][/math]

5. Ábrázoljuk valószínűségi hálóval azt, hogy ha a család hazuról elmegy, kiengedik a kertbe a kutyát és felkapcsolják a kerti villágitást. De a kutya megfázott, így gyakran ki kell engedni, akkor is, ha otthon van valaki. Néha szórakozásból a kertet is kivilágítják, stb. A változók nevét első betűkre leröviditve, a feltételes függetlenségeket kihasználva, irja fel a P(H V K U) elemi valószínűséget a hálóban tárolt feltételes valószínűségek szorzatával (minden változó bináris)! Mennyivel kevesebb valószínűség elegendő a háló megadásához a teljes együttes eloszláshoz képest? (10p)

Ezen a helyen volt linkelve a mi_abra.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

P(H V K U)=P(H V K U C) + P(H V K U %$\neg$%C) = 
P(U | H K V C)*P(H K V C) + P(U | H K V %$\neg$%C)*P(H K V %$\neg$%C)=
P(U | K)*P(K | V C H)*P(V C H)+P(U | K)*P(K | V %$\neg$%C H)*P(V %$\neg$%C H)=
P(U | K)*P(K | C H)*P(V | C)*P(H)*P(C)+P(U | K)*P(K | %$\neg$%C H)*P(V | %$\neg$%C)*P(H)*P(%$\neg$%C)=
P(U | K)*P(K | C H)*P(V | C)*P(H)*P(C)+P(U | K)*P(K | %$\neg$%C H)*P(V | %$\neg$%C)*P(H)*(1-P(C))

Összesen 2 (prior) és 2+4+2 valószínűséget kell tárolni. Ez 10, ha minden igaz. Teljes együttes eloszláshoz kellene: (2^N)-1= (2^4)-1= 15

Az eredeti megoldásban is N=5 így (2^N)-1=2^5 -1 = 31 -- Dave - 2010.01.04.

6. Egy egykarú robot kockákat képes egymásra rakosgatni. Csak olyan kockát képes megfogni és egy másik kockára, vagy az asztalra tenni, amire más kocka nincs rátéve. Megfelelően absztrahálva készítse el a robot cselekvéseinek STRIPS reprezentációját és írjon le hozzá egy alkalmas kezdeti és célállapotot is! (10p)

Ugyanez a példa volt 2007. január 2.-án is.

Egy lehetséges megoldást írok le.

Literálok jelentése:

Üreskéz: a robot kezében nincs semmi Szabad(x): x az adott oszlop legtetején lévő kocka (nincsen rajta egyetlen kocka sem) Megfogva(x): igaz, hogyha x a robot kezében van Rajta(x,y): x rajta van y-on

Operátorok Megfogja x-et:

Op(Cselekvés: Megfog(x), Előfeltétel: Szabad(x)[math]\wedge[/math]Üreskéz Következmény: [math]\neg[/math]Üreskéz[math]\wedge[/math]Megfogva(x)[math]\wedge\forall y \neg[/math]Rajta (x,y))

Rárakja x-re y-t Op(Cselekvés: Rárak(x,y), Előfeltétel: Szabad(x)[math]\wedge[/math]Megfogva(y) Következmény: [math]\neg[/math]Szabad(x)[math]\wedge[/math]Üreskéz[math]\wedge\neg[/math]Megfogva(y)[math]\wedge[/math]Rajta(y,x))

Az alap Strips nyelvben egyedül a [math]\forall[/math] életképessége kétséges, elvileg ilyet nem lehet megadni, aki tud jobbat, javítsa.

Mondjuk egy kezdőállapot:

Szabad(A)
Szabad(B)
Rajta(B,C)
Szabadkéz

Ami azt mondja, hogy van 3 kockánk, kettő egymáson, a harmadik meg mellettük. A robot keze szabad.

Célállapot:

Szabad(C)
Rajta(A,C)
Rajta(B,A)
Szabadkéz

Azaz egymásra kell őket pakolni, sorrendváltoztatva.

7. Magyarázza meg mi egy döntési fa és hogyan történik egy ilyen döntési fának a tanulása (vázlatosan)! (10p)

döntési famódszerek: a logikai kifejezések egy szűkített –a tanulás céljára tervezett -halmazát használják döntési fa bemenete: egy tulajdonsághalmaz segítségével leírt objektum vagy szituáció döntési fa kimenete: egy igen/nem "döntés"

A fa mindegyik belsőcsomópontja valamelyik tulajdonság tesztje, a csomópontból kiinduló mindegyik él a teszt lehetséges értékeivel címkézett, a fa mindegyik levél csomópontja az a logikai érték, amelyet akkor kell kiadni, ha ezt a levelet elértük.

Döntési fa tanulása:

• 1. összeírjuk a döntési fa attribútumainak halmazát
• 2. fogunk egy tanító halmazt
• 3. kiválasztjuk a legfontosabb attribútumot - ami a legnagyobb eltérést okozza a példák besorolásánál (a maradék attribútumok közül)
• 4. az attribútum értékei szerint haladunk tovább és a kiválasztott attribútum által szétválasztott halmazokra elvégezzük a 3. lépést mindaddig, amíg a konstans hamis vagy igaz értékig el nem érünk

8. A legjobb először keresés vezeti át Micimackót Kanga házától (K) Füles kunyhójához (F). Mennyire rosszabb megoldást kapunk így a legjobb megoldáshoz képest? (10p)

Ezen a helyen volt linkelve a mi_abra2.jpg nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

h értékek:

**	(hely ) ---> F	(hely) ---> É
F	--	100
K	135	120
É	100	--
H	80	40
M	125	140
N	100	100
B	40	90
Ü	50	65
G	55	35
7	80	115
P	115	170
J	90	155
S	40	115

A legjobbat-először keresés egy algoritmuscsalád, eltérő kiértékelő függvényekkel. Így ez a feladat kicsit furán lett megfogalmazva, hiszen ez egy algoritmuscsalád, nem egy algoritmus. A kiindulás a "csak g-t vizsgáló" algoritmus, de ide tartozik a Mohó algoritmus és az A* keresés is.

Ez persze nem biztos, így aki bármilyen információval rendelkezik ezzel kapcsolatban, az jelezze.

Mindenesetre ha csak g-t vesszük figyelembe - ami egy mélységi kereséssel hasonlatos lesz - akkor az út:

K -> N -> 7 -> S (vagy M, de ettől most tekintsünk el) -> B -> Ü -> H -> E -> G -> F (nem akarunk hurkot képezni Ü választásával)

Útköltség: 270

Ha Mohó keresés, ami csak h-t használja:

K -> H -> U -> B -> F (vagy S)

Útköltség: 145 (de utolsónak S-t választva lehet akár 165 is)

A*, azaz optimális út:

K -> N -> 7 -> S -> F

Útköltség: 125

Az, hogy mennyivel rosszabb megoldás, útkülönbség.

-- Hidden - 2008.01.03.

Itt találtak alapján: Best first search simply chooses the unvisited node with the best heuristic value to visit next.

Szóval a lépések: 1. V={K} L={H(80),N(100),M(125)}
2. V={K,H} L={Ü(50),É(100),N(100),M(125)}
3. V={K,H,Ü} L={B(40),G(55),É(100),N(100),M(125)}
4. V={K,H,Ü,B} L={F(0),S(40),G(55),É(100),N(100),M(125)}
5. V={K,H,Ü,B,F}, ami 170, de ilyen heurisztikával ez nem is csoda.

A fentiek elég erősen torzítanak, Zsombor kolléga nem csinálta meg azt az A*-ot, mivel a legjobb út a K-N-Ü-B-F, ami 120.

-- _HippiE_ - 2010.01.18.