Predrag Janiˇci´c
Mladen Nikoli´c
Veˇ
staˇ
cka inteligencija
c
Juni 2010
2
Autori:
dr Predrag Janiˇci´c
, vanredni profesor Matematiˇckog fakulteta u Beogradu
email:
[email protected]
url:
www.matf.bg.ac.rs/~janicic
Mladen Nikoli´c
, asistent na Matematiˇckom fakultetu u Beogradu
email:
[email protected]
url:
www.matf.bg.ac.rs/~nikolic
VEˇSTA ˇ
CKA INTELIGENCIJA
Sva prava zadrˇzana. Nijedan deo ovog materijala ne moˇze biti reprodukovan niti smeˇsten
u sistem za pretraˇzivanje ili transmitovanje u bilo kom obliku, elektronski, mehaniˇcki,
fotokopiranjem, smanjenjem ili na drugi naˇcin, bez prethodne pismene dozvole autora.
4
SADR ˇ
ZAJ
4.6
Operator seˇcenja
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.7
Negacija kao neuspeh
. . . . . . . . . . . . . . . . . . . . . . . . .
83
4.8
Liste
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
4.9
Ugradjeni predikati
. . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.10 Implementacija KNF algoritma
. . . . . . . . . . . . . . . . . . .
92
4.11 Implementacija DPLL algoritma
. . . . . . . . . . . . . . . . . .
94
4.12 Pretraga grafa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
4.13 Primer reˇsavanje jednostavnog problema
. . . . . . . . . . . . .
97
II
Pretraga
101
5
Reˇsavanje problema kao pretraga
103
5.1
Kvalitet algoritama pretrage
. . . . . . . . . . . . . . . . . . . . .
105
5.2
Neinformisana i informisana pretraga
. . . . . . . . . . . . . . .
106
6
Pohlepna pretraga
109
6.1
Penjanje uzbrdo u sluˇcaju diferencijabilne funkcije cilja
. . . . .
110
7
Odre ¯
divanje puteva u grafu
113
7.1
Obilazak grafa u dubinu i ˇsirinu
. . . . . . . . . . . . . . . . . .
113
7.2
Dejkstrin algoritam
. . . . . . . . . . . . . . . . . . . . . . . . . .
114
7.3
A*
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
115
7.3.1
Primer upotrebe algoritma A*
. . . . . . . . . . . . . . . .
117
7.3.2
Specijalni sluˇcajevi
. . . . . . . . . . . . . . . . . . . . . .
119
7.3.3
Primer upotrebe algoritma A* na uniformnoj mreˇzi
. . .
120
7.3.4
Svojstva algoritma A*
. . . . . . . . . . . . . . . . . . . .
124
7.3.5
Implementaciona pitanja
. . . . . . . . . . . . . . . . . .
124
8
Programiranje logiˇckih igara
127
8.1
Razvoj automatskog igranja logiˇckih igara i osnovni koncepti
.
127
8.2
Legalni potezi i stablo igre
. . . . . . . . . . . . . . . . . . . . . .
129
8.3
Otvaranje i biblioteka partija
. . . . . . . . . . . . . . . . . . . . .
131
8.4
Srediˇsnjica
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
132
8.4.1
Statiˇcka ocena pozicije i funkcija evaluacije
. . . . . . . .
132
8.4.2
Pretraˇzivanje stabla igre
. . . . . . . . . . . . . . . . . . .
133
8.4.3
Algoritam minimaks
. . . . . . . . . . . . . . . . . . . . .
133
8.4.4
Algoritam alfa-beta
. . . . . . . . . . . . . . . . . . . . . .
134
8.4.5
Heuristika
killer
. . . . . . . . . . . . . . . . . . . . . . . .
137
8.4.6
Iterativni alfa-beta/killer algoritam
. . . . . . . . . . . .
138
8.4.7
Stabilno pretraˇzivanje
. . . . . . . . . . . . . . . . . . . .
139
8.4.8
Prekidi i vremenska ograniˇcenja
. . . . . . . . . . . . . .
139
8.4.9
Sloˇzenost algoritama za pretraˇzivanje stabla igre
. . . . .
140
8.5
Zavrˇsnica
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
141
8.5.1
Skupovi pozicija kao klase ekvivalencija
. . . . . . . . . .
142
8.5.2
Tekstovi saveta
. . . . . . . . . . . . . . . . . . . . . . . .
142
8.6
Implementaciona pitanja
. . . . . . . . . . . . . . . . . . . . . . .
143
SADR ˇ
ZAJ
5
9
Genetski algoritmi
147
9.1
Motivacija za genetske algoritme
. . . . . . . . . . . . . . . . . .
147
9.2
Osnovni genetski algoritam
. . . . . . . . . . . . . . . . . . . . .
148
9.3
Reprezentacija jedinki
. . . . . . . . . . . . . . . . . . . . . . . .
149
9.3.1
Binarna reprezentacija
. . . . . . . . . . . . . . . . . . . .
149
9.4
Funkcija prilago ¯
denosti
. . . . . . . . . . . . . . . . . . . . . . .
150
9.5
Inicijalizacija i zaustavljanje
. . . . . . . . . . . . . . . . . . . . .
151
9.6
Selekcija
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
151
9.6.1
Ruletska selekcija
. . . . . . . . . . . . . . . . . . . . . . .
152
9.6.2
Turnirska selekcija
. . . . . . . . . . . . . . . . . . . . . .
153
9.7
Reprodukcija i genetski operatori
. . . . . . . . . . . . . . . . . .
153
9.7.1
Ukrˇstanje
. . . . . . . . . . . . . . . . . . . . . . . . . . .
153
9.7.2
Mutacija
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
154
9.8
Zaustavljanje
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
154
9.9
Parametri algoritma
. . . . . . . . . . . . . . . . . . . . . . . . . .
155
9.10 Svojstva genetskih algoritama
. . . . . . . . . . . . . . . . . . . .
155
9.11 Primer primene genetskih algoritama — evolucija agenta
. . . .
156
9.11.1 Implementaciona pitanja
. . . . . . . . . . . . . . . . . .
157
III
Maˇsinsko uˇcenje
159
10 Uvod
161
10.1 Generalizacija i apstrakcija
. . . . . . . . . . . . . . . . . . . . . .
162
10.2 Primer problema uˇcenja
. . . . . . . . . . . . . . . . . . . . . . .
163
10.3 Nadgledano i nenadgledano uˇcenje
. . . . . . . . . . . . . . . . .
166
10.4 Ciljna funkcija i modeli podataka
. . . . . . . . . . . . . . . . . .
166
10.5 Podaci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
167
10.5.1 Reprezentacija podataka
. . . . . . . . . . . . . . . . . . .
167
10.5.2 Podaci za trening i podaci za testiranje
. . . . . . . . . .
168
10.6 Dizajn sistema koji uˇci
. . . . . . . . . . . . . . . . . . . . . . . .
168
11 Klasifikacija
171
11.1 Metode klasifikacije zasnovane na instancama
. . . . . . . . . .
171
11.1.1 Metoda
n
-najbliˇzih suseda
. . . . . . . . . . . . . . . . . .
172
11.1.2 N-grami
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
173
11.2 Uˇcenje stabala odluˇcivanja
. . . . . . . . . . . . . . . . . . . . . .
177
11.3 Mere kvaliteta i tehnike evaluacije klasifikacije
. . . . . . . . . .
183
11.4 Preterano prilago ¯
davanje modela podacima za trening
. . . . .
186
12 Regresija
189
12.1 Linearna regresija
. . . . . . . . . . . . . . . . . . . . . . . . . . .
189
12.2 Pretpostavke linearne regresije
. . . . . . . . . . . . . . . . . . .
192
12.3 Ispitivanje kvaliteta linearne regresije
. . . . . . . . . . . . . . .
192
12.4 Preterano prilago ¯
davanje modela podacima za trening
. . . . .
196
13 Klasterovanje
199
Predgovor
Ovo su beleˇske koji prate predavanja i veˇzbe iz predmeta
Veˇstaˇca inteligen-
cija
koje smo drˇzali akademskih godina 2007/08, 2008/09, 2009/10. Funkcija
beleˇski je da olakˇsaju pra´cenje predavanja i da sluˇze kao podsetnik tokom
pripremanja ispita. Oni ne mogu da zamene poha ¯
danje nastave i koriˇs´cenje
druge literature.
Predrag Janiˇci´c i Mladen Nikoli´c
Beograd, juni 2010.
7
