1

Intelligens Rendszerek Elmélete 4

2012. ősz

Óbudai Egyetem, NIK

Dr. Kutor László

IRE 4/32/1

Problémamegoldás kereséssel http://nik.uni-obuda.hu/mobil

2012. ősz


Dr. Kutor László

IRE 4/32/2

”Egyszerű” lények intelligenciája? http://www.youtube.com/watch?v=tLO2n3YMcXw&NR=1

2012. ősz


Dr. Kutor László

IRE 4/32/3

A problémák csoportosítása a megoldási idő szerint P (Polynomial) „viszonylag egyszerűen megoldható problémák.” P típusú egy probléma ha létezik olyan problémamegoldó algoritmus, melynek időszükséglete legfeljebb N polinomjával függ össze. NP (Non-deterministic Polynomial) „Nehéz problémák.” Azok a problémák, melyek bármely feltételezett megoldása polinomiális idő alatt eldönthető, hogy helyes –e. NP-teljes (NP complete): A legnehezebben megoldható, (nagy változószám esetén megoldhatatlan) problémák. A megoldásához szükséges idő eN (vagy n!) szerint változik.

2012. ősz


Dr. Kutor László

IRE 4/32/4

A problématér matematikai ábrázolása  Minden feladat (probléma) direkt vagy implicit módon    

meghatároz egy gráfot, (egyszerűbb estben egy fát) melynek: Kezdőcsúcs: a kiinduló adathalmaz Élek: az alkalmazható műveletek Gráfpontok: „levelek”, „gyerek csomópontok” Általános csúcsok: az adathalmaz egy-egy változatát tartalmazzák, amelyeket a megfelelő élek menti műveletek alkalmazásával kapunk. S

S

Fa struktúra C

Gráf struktúra

B

A D

E

B

A C

D

E

F G

G

2012. ősz

F

cél

cél


Dr. Kutor László

IRE 4/32/5

A keresési tér nagyságának becslése 1. Sakk :

Fekete Gregorics-Nagy: Bevezetés a mesterséges intelligenciába

1

 Egy átlagos játszma lépésváltásainak száma 45 ( a fa mélysége 90)

 Egy állásban a legális lépések átlagos száma 35  A lehetséges levelek száma: 3590  Ha egy erős játékos minden állásban 1.76 lépést tart jónak, akkor 1.7690 tehát 1.25 * 10 22 kiértékelendő csúcs adódik

 4.6 milliárd év ~ 1018 másodperc   Ha egy másodperc alatt 10 000 állást értékelünk, akkor 4,6 milliárd évre lenne szükség

2012. ősz


Dr. Kutor László

IRE 4/32/6

A keresési tér nagyságának becslése 2. B

Az utazó ügynök problémája: S 1. Minden városba el kell utazni, 2. Minden városba csak egyszer kell elutazni,

A

D

C

Felkeresendő városok száma (n) A lehetséges útirányok száma:n!/2n 10 181 440 20 6.08 * 1016 30 4.42 * 1030

Kombinatorikus robbanás !!! 2012. ősz


Dr. Kutor László

IRE 4/32/7

Produkciós (kereső) rendszer A produkciós rendszer a klasszikus mesterséges intelligencia egyik alapvető fogalma, egy sajátos probléma megoldási szemléletet tükröző feladat megoldási rendszer. Külön kezeli: A feladat adatait Az adatokon értelmezett műveleteket A műveleteket algoritmussá szervező vezérlési stratégiákat. (pl. keresés) 2012. ősz


Dr. Kutor László

IRE 4/32/8

A produkciós rendszer általános algoritmusa Kezdeti állapot kiválasztása While állapot ≠ célállapot do Begin Az állapotra alkalmazható operátor kiválasztása állapot:=operátor(állapot) End. 2012. ősz


Dr. Kutor László

IRE 4/32/9

A kereséssel kapcsolatos alapfogalmak  Globális optimum  Lokális optimum → „Niche”  Keresés matematikai értelemben = a gráf adott csomópontjából az operátorok segítségével egy másik csomópontba vitele, (kiterjesztése) → „gyermek” csomópontokba  Keresési típusok: Nem informált Próba-hiba keresés Keresés a költség figyelmen kívül hagyásával Keresés a költség figyelembe vételével Heurisztikus keresések  Listák a vizsgált csomópontok tárolására: „open” lista a megnyitott csomópontok nyilvántartására „closed” lista a megvizsgált csomópontok számontartására 2012. ősz


Dr. Kutor László

IRE 4/32/10

Mélységi keresés („depth first”) LIFO adatkezelés: (Last In First Out) „open” lista, az állapotok (csomópontok) tárolására

S B

A C

D

E

G

F

cél

„Mindig a zsák tetejére pakolunk, és onnan is veszünk el”

Open lista:

(S)(A,B)(C,D,B)(D,B)(B)(E,F)(G,cél,F)(cél,F) 2012. ősz


Dr. Kutor László

IRE 4/32/11

Mélységi keresés algoritmusa Open lista: (S)(A,B)(C,D,B)(D,B)(B)(E,F)(G,cél,F)(cél,F) Fabejárás: 1. tedd a start csomópontot az open listára 2. hurok: IF open=üres lista then kilépés; {! sikertelen , ha az összes csomópontot megvizsgáltuk} 3. n:=első(open); {az open lista első elemének beolvasása} 4. IF cél(n) then {sikeres} kilépés 5. vedd le (n, open); {n levétele az open listáról} 6. terjeszd ki n-t és helyezd az összes "gyermek" csomópontot az open lista elejére 7. Go TO hurok 2012. ősz Óbudai Egyetem, NIK Dr. Kutor László IRE 4/32/12

Példa mélységi keresésre gráfban S B

A X

open lista:

C E

(S)(AS,BS)(XA,CA,BS)(EX,CA,BS) D

cél

(CA,BS)(EC,célC, BS)(célC,BS) closed lista S,AS,XA,EX,CA,

2012. ősz


Dr. Kutor László

IRE 4/32/13

Mélységi keresés gráfban 1. tedd a start csomópontot az open listára

2. hurok: 3. 4. 5. 6.

 2012. ősz

IF open=üres THEN kilépés; sikertelen keresés n:=első(open) IF cél(n) THEN sikeres kilépés vedd le (n, open), add hozzá (n, closed) n kiterjesztésével generáld az összes "gyermek" csomópontot. Az open és a closed lista által nem tartalmazott gyermek csomópont az open lista elejére kerül és az n-re irányuló mutatót kap. GO TO hurok Óbudai Egyetem, NIK

Dr. Kutor László

IRE 4/32/14

Szélességi (horizontális) keresés („breadth-first ”) S

FIFO adatkezelés

A C

(First In First Out)

B

D

E

G

F

„Mindig a cső elejére pakolunk, és a végéről veszünk el”

cél

Open lista:

(S)(A,B)(B,C,D)(C,D,E,F)(D,E,F)(E,F)(F,G,cél)(G,cél)(cél) 2012. ősz


Dr. Kutor László

IRE 4/32/15

A szélességi keresés algoritmusa fa bejárásnál Open lista (S)(A,B)(B,C,D)(C,D,E,F)(D,E,F)(E,F)(F,G,cél)(G,cél)(cél)

1. tedd a start csomópontot az open listára 2. hurok: IF open=üres THEN kilépés; sikertelen keresés 3. n:=első(open) 4. IF cél(n) THEN sikeres kilépés 5. vedd le (n, open)terjeszd ki n-t és helyezd el az összes "gyermek" csomópontot az open lista végére 6. Go to hurok 2012. ősz


Dr. Kutor László

IRE 4/32/16

A szélességi keresés algoritmusa gráf bejárásnál 1. tedd a start csomópontot az open listára 2. hurok: IF open=üres THEN kilépés; sikertelen keresés 3. n:=első(open) 4. IF cél(n) THEN sikeres kilépés 5. vedd le (n, open), add hozzá (n, closed) n kiterjesztésével generáld az összes "gyermek" csomópontot. Az open és a closed lista által nem tartalmazott gyermek csomópont az open lista végére kerül és az n-re irányuló mutatót kap. 6. Go to hurok 2012. ősz


Dr. Kutor László

IRE 4/32/17

Példa szélességi keresésre gráfban S B

A c1

C E

2012. ősz

open lista:

(S)(AS,BS)(BS,c1A,CA)(c1A,CA,DB) D

c2

closed lista AS,BS


Dr. Kutor László

IRE 4/32/18

Optimális (egyenletes) keresés S 4

1 B

A 1 C

2

2

D

E 4

H

3 F

3 c1

2 I

1

„A kiindulási pontból mindig a minimális költségű csomópontot vizsgáljuk”

c2

Open lista: S(0)

BS(1)AS(4) EB(3)AS(4),FB(4) AS(4)FB(4)c1E(6)HE(7) FB(4)CA(5)c1E(6)DA(6)HE(7) c2F(5)CA(5)c1E(6)DA(6)IF(6)HE(7)

2012. ősz


Dr. Kutor László

IRE 4/32/19

A optimális keresés algoritmusa Fabejárás:

1. tedd a start csomópontot az OPEN listára 2. hurok: IF open=üres THEN kilépés; sikertelen! 3. n:=első(open) 4. IF cél(n) THEN sikeres kilépés 5. vedd le (n, open) 6. ha lehet, n kiterjesztése, minden n-nél a költség kiszámolása. A gyermek csomópontok felírása az open listára majd növekvő "költség" szerint sorrendbe rendezése 7. GO TO hurok Gráf keresésnél: 5. vedd le (n, open), add hozzá (n, closed) 6. az open és closed lista által nem tartalmazott gyermek csomópontok az open listára kerülnek, az n-re irányuló mutatót kapnak, majd növekvő "költség" szerint sorrendbe rendezzük. 2012. ősz Óbudai Egyetem, NIK Dr. Kutor László IRE 4/32/20

Példa optimális megoldás keresésre gráfon Előzetes open lista

S

2 5

3 C 2 E

2012. ősz

DB(6) c1A(7) EC(6) c2C(5)

B

A

c1 2

3

1 1 1 c2

S(0) AS(2) BS(3) BS(3) c1A(7) CA(5) c1A(7) CA(5) CB(4) DB(6)

(rendezett) open lista

3 D

S(0) AS(2) BS(3) BS(3) CA(5) c1A(7) CB(4) DB(6) c1A(7) c2C(5) DB(6) EC(6) c1A(7)


Dr. Kutor László

closed listA S(0) S(0) AS(2) S(0) AS(2) BS(3) S(0) AS(2) BS(3) CB(4)

IRE 4/32/21

Gyakorló feladat optimális megoldás keresésre gráfon

S

25 2

5 C 16 E

2012. ősz

B

A

c1 10

4

9 23

2 D 24

c2


Dr. Kutor László

IRE 4/32/22

Heurisztikus keresés Heurisztika:

Heuriskein (görög)= felfedező, Archimedes„Heuréka” = megtaláltam a feladatoknak a tapasztalatokra és megalapozott ötletekre épülő próbálkozásokkal történő megoldási módszere. Az utazó ügynök probléma egy lehetséges heurisztikus megoldása: „Minden lépésnél a helyi legjobb alternatíva kiválasztása.” 1. Önkényesen kiválasztani a kezdő várost. 2. Megvizsgálni az összes nem meglátogatott várost és a legközelebbit felkeresni. 3. Ismételni a 2. lépést, amíg az összes várost meg nem látogattuk. A megoldás időszükséglete: 2012. ősz

n2 ami << n!/2N


Dr. Kutor László

IRE 4/32/23

Legjobbat először („best first”) algoritmus 1. tedd a start csomópontot az open listára 2. hurok: IF open=üres then sikertelen kilépés 3. n:=első(open) 4. IF cél(n) THEN sikeres kilépés 5. vedd le (n, open), add hozzá (n, closed) 6. terjeszd ki n-et és generáld az összes gyermek csomópontot. Csak az open és closed listákban nem szereplőket tedd az open listára és kapcsolj hozzájuk n-re irányuló mutatót. Rendezd az open lista csomópontjait növekvő h(n) szerinti sorrendbe 7. GO TO hurok. Sokat idézett optimunkereső algoritmus: Edsger Dijkstra „legrövidebb útkereső algoritmusa” 2012. ősz


Dr. Kutor László

IRE 4/32/24

Nehezen kereshető „ felszínek” 1

2012. ősz


Dr. Kutor László

IRE 4/32/25


2012. ősz


Dr. Kutor László

IRE 4/32/26

„Hegymászó” algoritmus numerikus analízis -> ~ = gradiens módszer "A cél elérését az ahhoz megjósolhatóan legközelebb álló csomópontok (állapotok) kiválasztásával kísérli meg." h(n) = a csúcs és az n közötti távolság. Cél

Start 2012. ősz

Cél

Start Óbudai Egyetem, NIK

Dr. Kutor László

IRE 4/32/27

Helymászó algoritmus 1. n:=start csomópont 2. hurok: IF cél (n) THEN sikeres kilépés 3. terjeszd ki n-et, számold ki h(ni)-t minden gyermek csomópontra és a legkisebb "költségű" (csúcstól való távolságot) vedd a következő n-nek. 4. IF h(n)

Dr. Kutor László

IRE 4/32/28

Nehezen kereshető „ felszínek” 3.

2012. ősz


Dr. Kutor László

IRE 4/32/29

Nehezen kereshető „ felszínek” 4.

2012. ősz


Dr. Kutor László

IRE 4/32/30


2012. ősz


Dr. Kutor László

IRE 4/32/31

Kérdések - Miért van szükség kereső algoritmusokra a mesterséges intelligencia létrehozásához? - Tudnak-e heurisztikát alkalmazni a számítógépek? - Miért nehéz probléma eldönteni, hogy az egyes feladatok melyik probléma osztályba tartoznak?

2012. ősz


Dr. Kutor László

IRE 4/32/32

1

Recommend Documents