363

Mesterséges Intelligencia Csató Lehel

Mesterséges Intelligencia Csató Lehel Matematika-Informatika Tanszék Babe¸s–Bolyai Tudományegyetem, Kolozsvár

2010/2011

1/363

˝ Az Eloadások Témái Mesterséges Intelligencia

˝ mi a mesterséges intelligencia ... Bevezeto:

3

„Tudás”–reprezentáció

Csató Lehel

Gráfkeresési stratégiák

Hogyan írjunk jól angolul?

Szemantikus hálók / Keretrendszerek

Gráfok ábrázolása

Játékok modellezése Bizonytalanság kezelése

Irányított gráfok Irányított utak Optimális út

Fuzzy rendszerek

Irányított fa ÉS/VAGY gráfok

Grafikus modellek

ÉS/VAGY gráfok átalakítása

Tanuló rendszerek

Problémák reprezentációja

Szimulált kifutés, ˝ Genetikus algoritmusok

Gráfkereso˝ algoritmusok

A perceptron modell

Visszalépés

Gráfkeresési feladatok

˝ Neurális hálók, önszervezodés Gépi tanulás 46/363

Admin ...

http://www.cs.ubbcluj.ro/~csatol/mestint

Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása

... trívia

Vizsga Szóbeli (60%) + Gyakorlat (40%) Laborgyakorlatok:

Irányított gráfok Irányított utak Optimális út

1

Gráfok ábrázolása - dedukciós algoritmus

18%

2

Játékelmélet

10%

3

Matlab - tanulási algoritmus

12%

4

Opcionális feladatok - max. 3/személy

Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

Problémák reprezentációja Gráfkereso˝ algoritmusok Visszalépés


Bemutatók (5–20 pont) Alkalmazások bemutatása, melyek adaptív, gépi tanulásos vagy mestint módszereket alkalmaznak. 47/363

sok%

Hogyan írjunk jól angolul? Mesterséges Intelligencia

˝ szoftvere. A WhiteSmoke “szövegérto”


˝ „Elofordul, hogy jól beszélünk angolul, ám fontos leveleinkbe ˝ becsúsznak hibák és a címzett az eredeti szándéktól különbözonek olvashatja mondandónkat. Egy izraeli szoftver a helyesíráson és a nyelvtanon túlmutató megoldást kínál.”

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

˝ oje ˝ csak e két Míg például a Word helyesírási és nyelvtani ellenorz területen hatékony, addig jelen szoftver lényegesen többet tud: a


szöveget mesterséges intelligencia segítségével fürkészi át, majd azt pontosabbá, egyértelmubbé ˝ és folyékonyabbá tevo˝ javaslatokkal áll


˝ (azaz ?kozmetikáz?) elo.

Visszalépés


agent.ai 48/363

I

Hogyan írjunk jól angolul? Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása



49/363

II

Gráfkereso˝ stratégiák Mesterséges Intelligencia

3

˝ Egy korai M.I. terület - külön tudományággá fejlodött

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása

Nagyon sok feladatot lehet gráfokkal reprezentálni: a gráfreprezentáció az algoritmusok keresési tere.

Irányított gráfok

1

irányított gráfok

2

ÉS/VAGY gráfok

Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


Példák:


Hanoi tornyok

Visszalépés

Irányított gráf?


50/363

reverzibilis lépések – irányítatlan gráf

Irányított GRÁFOK Mesterséges Intelligencia

3

Jelölés:

1

N – csúcsok (nodes)

Csató Lehel

A – élek A ⊂ N × N (adjacency)


szülo˝ – 1 a 2-nek

Gráfok ábrázolása Irányított gráfok

6 4

3

utód – . . .

Irányított utak

7

Optimális út

c(n, m) – költség


2

5

Tulajdonságok:



σ-tulajdonság:

∃σ ∀n |{m|(n, m) ∈ A}| ≤ σ

δ-tulajdonság:

∃δ > 0 ∀(n, m) ∈ A c(n, m) ≥ δ hyper

51/363

Gráfok ábrázolása Mesterséges Intelligencia

3

δ-gráfok = a δ és σ tulajdonsággal rendelkezo˝ gráfok.

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


× 1 2 3 4 5 6 7

1 . . . . 1 1 1

2 1 . . . . . .

3 . 1 . 1 . . 1

4 . . 1 . . . .

5 . . . . . 1 .

6 . . . . . . .

7 . . . 1 1 . .

1 2

6 4

3 7 5

Gráfkereso˝ algoritmusok Visszalépés


Konvenció: amennyiben nem specifikáljuk, az élek bejárásának a költsége 1. 52/363

Irányított utak Mesterséges Intelligencia


˝ az m-be Irányított út – út: az n-bol Ha ∃ n1 , . . . , nk úgy hogy {(n, n1 ), . . . , (nk , m)} ∈ A. Út: α = (n = n0 , n1 , . . . , nk = m)

1

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

2

Út költsége

6 4


Problémák reprezentációja Gráfkereso˝ algoritmusok

α

c (n, m) =

k X j=1

3

c(nj−1 , nj )

7 5

Visszalépés


Példa: α = (6, 5, 7, 3, 4, 3, 4, 7, 5, 1, 2) költsége 10. 53/363

Irányított utak Mesterséges Intelligencia


˝ az m-be Irányított út – út: az n-bol Ha ∃ n1 , . . . , nk úgy hogy {(n, n1 ), . . . , (nk , m)} ∈ A. Út: α = (n = n0 , n1 , . . . , nk = m)

1

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

2

Út költsége

6 4



α

c (n, m) =

k X j=1

3

c(nj−1 , nj )

7 5

Visszalépés


Példa: α = (6, 5, 7, 3, 4, 3, 4, 7, 5, 1, 2) költsége 10. 53/363

Optimális út Mesterséges Intelligencia

3

˝ az m-be Optimális költség: az n-bol c∗ (n, m) =

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok

min

cα (n, m)

α∈{n→m}

˝ az m-be Optimális út: az n-bol

Irányított utak Optimális út

α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés

Létezik mindig – optimális – út?


Amennyiben igen, egyedi? 54/363

nem. Ekkor az út hossza ∞ nem - δ-gráf


3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés






3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés






3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés





Irányított Fa Mesterséges Intelligencia

3

Irányított fa: gráf, melyben egy kitüntetett csúcsból - a ˝ – minden más csúcsba csak egy út vezet. gyökérbol

Csató Lehel Hogyan írjunk jól angolul?

A gyökérbe nem vezet él.

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

˝ nem vezet ki él. Levél – csúcs, melybol



Tulajdonságok: Bejárása egyszeru; ˝

Visszalépés


Nem minden feladat ábrázolható faként. 55/363

ÉS/VAGY gráfok Mesterséges Intelligencia


ÉS/VAGY gráfok Olyan irányított hipergráfok, melyekben egy hiperél egy csúcsból egy csúcshalmazba vezet. R(N, A)

ahol

A ⊆ {(n, M) ∈ N × 2N |0 6= |M| ≤ ∞}




Hiperélek: (1, {2, 3}) (1, {4}) (2, {5, 6}) (3, {7}) (4, {6, 7}) (7, {6})

1

2

3

4

Élköltség: c(n, M) Kérdés: σ és δ tulajdonságok G 56/363

5

6

7

Hiperutak ÉS/VAGY gráfokban Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul?

Irányított hiperút (n, M) között Részgráf, melyben mindegyik csúcsból legfeljebb egy hiperél indul ki. ˝ nem indul hiperél. M-bol

Gráfok ábrázolása Irányított gráfok Irányított utak

Hiperutak 1 → {5, 6}:

1

Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

(1, {2, 3}), (2, {5, 6})


2

3

4

(1, {2, 3}), (3, {6}),


(1, {4}), (4, {5})


57/363

5

6

7

ÉS/VAGY gráfok átalakítása Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

ÉS/VAGY gráfok kezelése nehézkes. Átalakíthatóak irányított gráfokká. Új csúcsok bevezetése: utódcsúcs = átalakítandó hiperél utódainak halmaza. ˝ A fenti muveletet ˝ kiterjesszük a kezdocsúcstól a célig. 1



Feladat: az 1 → {5, 6} egy hiperútjának megfelelo˝ gráfátalakítás.


2

5 58/363

3

4

6

7

8-as kirakós játék Mesterséges Intelligencia

2 8 3 1 4 7 6 5

3 Csató Lehel Hogyan írjunk jól angolul?

I

1 2 3 8 4 7 6 5

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

˝ Kódolás: 9 hely – 9! = 362880 lehetoség.



Üres hely mozgatása – meghatároz egy állapotgráfot.



59/363

8-as kirakós játék

II 2 8 3 1 4 7 6 5

Mesterséges Intelligencia

3 Csató Lehel 2 8 3 1 6 4 7 5


2 8 3 1 4 7 6 5

2 3 1 8 4 7 6 5

2 8 3 1 4 7 6 5

2 3 1 8 4 7 6 5

2 3 1 8 4 7 6 5

2 8 1 4 3 7 6 5

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa

2 8 3 1 4 5 7 6

ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


1 2 3 7 8 4 6 5


60/363

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

2 3 4 1 8 5 7 6

4 királyno˝ Mesterséges Intelligencia

3 Csató Lehel

˝ 4 × 4-es táblán 4 királynot elhelyezni.


Állapottér: sakk–állások ˝ 1 − 4 királynovel.


Muvelet: ˝ egy királyno˝ egy ˝ helyezése. mezore


˝ Kezdoállapot: üres sakktábla.


˝ Célállapot: 4 királynot tartalmazó sakktábla.

Visszalépés


61/363

Gráfkereso˝ algoritmusok Mesterséges Intelligencia

3

Nem-módosítható keresések: Egy lépést – szabályt – nem lehet visszavonni.

Csató Lehel 1 Hogyan írjunk jól angolul?

Hegymászó algoritmus (hill-climbing) kritérium-függvény, mely „vezérli” az algoritmust. nem-determinisztikus gond a lokális minimum jelenléte

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

2


Kommutatív rendszerek (commutative systems) a D-re alkalmazható szabályok alkalmazhatóak a D leszármazottjaira is. ˝ eloállított ˝ a D-bol adatbázis független a muveletek ˝ ˝ – felcserélheto. ˝ sorrendjétol ha a D kielégíti a terminálási feltételt, akkor annak minden leszármazottja is.



Nincs bonyolult stratégia. Heurisztika =⇒ hatékonyság. 62/363

I

Visszalépés Mesterséges Intelligencia

Egy utat tart nyilván a reprezentációs gráfból.

3 Csató Lehel

Induló érték: start-csúcs.

Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak

Vezérlési stratégia – visszalépés alkalmazása ha:




63/363

1

nincs több él – zsákutca;

2

nincs több „jó út” – vágás;

3

minden továbbvezeto˝ útról visszaléptünk – torkolat;

4

egy már bejárt csúcshoz jutunk – kör;

5

túl hosszú a bejárt út – mélységi korlát.

I


3

Visszalépés ha


1


2


3


4


5


Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


Tétel A visszalépéses algoritmus az (1) és (2) feltételekkel terminál véges és körmentes gráfokon.

Visszalépés


64/363

II


3

Visszalépés ha


1


2


3


4


5





Tétel A visszalépéses algoritmus az (1)–(5) feltételekkel mindig terminál. Ha létezik a mélységi korlátnál nem hosszabb megoldás, megtalálja azt.

64/363

II

Buvös ˝ négyzetek I Mesterséges Intelligencia

3

Feladat: ábrázoljuk a buvös ˝ négyzetek keresését gráf-kiterjesztési feladatként: építsük fel a feladat állapotterét; defniáljunk egy gráfot a helyes megoldásokat eredményezo˝ kitöltések folyamataként;


definiáljunk egy gráfkiterjesztési procedúrát;

Irányított gráfok Irányított utak

keressük meg az összes lehetséges megoldást gráfkereso˝ (?backtracking?) módszerrel.



1. laborfeladat

Buvös ˝ négyzet: az az N × N-es négyzet, melyben az elemek száma megegyezik sorok és oszlopok szerint.



Ssor

N2 N N2 + 1 1 X 1 N2 N2 + 1 = n= · = N N 2 2 n=1

65/363

Buvös ˝ négyzetek II Mesterséges Intelligencia

1. laborfeladat

Követelmények:

3

Dokumentáció, mely tartalmazza a

Csató Lehel 1 Hogyan írjunk jól angolul?

2 3

Gráfok ábrázolása

paraméterterét a feladatnak, a gráfkiterjesztés lépéseit, a gráfbejárás sorrendjét.

Irányított gráfok Irányított utak

Program, mely az N szám ismeretében kiírja (pl. egy TXT állományba) az összes megoldást valamint kiírja ˝ a megoldások számát. a képernyore



.

Visszalépés

A bemutatás személyesen történik – valamely futtatási környezetben – úgy, hogy a programban módosítani lehessen paramétereket.


(8 pont) 66/363

Kötelezo˝ feladat

Buvös ˝ négyzetek II Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása



Example: 93 108 123 107 122 137 121 136 151 135 150 165 149 164 10 163 9 24 8 23 38 22 37 52 36 51 53 50 65 67 64 66 81 78 80 95 79 94 109 67/363

138 152 166 11 25 39 40 54 68 82 96 110 124

153 167 12 26 27 41 55 69 83 97 111 125 139

168 13 14 28 42 56 70 84 98 112 126 140 154

Példa 1 15 29 43 57 71 85 99 113 127 141 155 169

16 30 44 58 72 86 100 114 128 142 156 157 2

31 45 59 73 87 101 115 129 143 144 158 3 17

46 60 74 88 102 116 130 131 145 159 4 18 32

61 75 89 103 117 118 132 146 160 5 19 33 47

76 90 104 105 119 133 147 161 6 20 34 48 62

91 92 106 120 134 148 162 7 21 35 49 63 77

Sudoku Mesterséges Intelligencia

3 Csató Lehel

2. laborfeladat

A sudoku-ban számokat helyezünk el egy n2 × n2 méretu˝ négyzetrácsban. Az {1, . . . , n2 } számokat úgy helyezzük el n2 -szer úgy, hogy egy oszlopban, egy sorban és minden kisebb négyzetben egy szám egyszer szerepeljen (lásd ábra). Az n = 2-re mi a paraméter–tér?


1p.

Jelenítsük meg „szépen” a megoldásokat az n = 2 és n = 3 esetekre. 1p.


Az n = 2 esetre generáljuk az összes megoldást.

Optimális út Irányított fa ÉS/VAGY gráfok

1p.



Találjuk meg egy részlegesen kitöltött feladat kitöltött változatát.

3p.

× Generáljunk egy sudoku rejtvényt: egy részlegesen kitöltött feladat, melynek csak egy megoldása van.

4p.


(10 pont) 68/363

Kötelezo˝ feladat

363

Recommend Documents