Khoa Công Ngh Thông Tin
ệ
Trư ng Đ i h c C n Th ạ ọ
ờ
ầ
ơ
Ệ
Ạ
TRÍ TU NHÂN T O Artificial Intelligence: Structure and Strategies for Complex Problem Solving. (3rd edition - 1997) George F. Luger, William A. Stubblefield
Giáo viên: Tr n Ngân Bình ầ
TTNT. p.1
ớ
N i Dung ộ . Gi i thi uTTNT ệ Phép tính v tị ừ C u trúc và chi n l
Ch Ch Ch
ng 1 ng 2. ng 3. c dùng cho tìm ki m ế ượ ấ ươ ươ ươ ế
ạ
trên không gian tr ng thái (TK-KGTT) ế
ặ
ề ả ứ ề
đ ng (Automatic reasoning) ậ ự ộ
ng 4. Tìm ki m heuristic ng 5. Đi u khi n và cài đ t TK-KGTT ể ng 6: i quy t v n đ tri fth c chuyên sâu Gi ế ấ ng 7: Suy lu n v i thông tin không chính xác ớ ậ ho c không đ y đ . ầ ủ Suy lu n t ng 8. H c máy ng 9.
Ch ươ Ch ươ Ch ươ Ch ươ ặ Ch ươ Ch ươ
TTNT. p.2
ọ
ạ
ế s ự
t .
Trí Tu Nhân T o là gì? Là m t nhánh c a khoa h c máy tính liên quan đ n ọ ộ ự ộ
i:
ệ ủ đ ng hóa hành vi thông minh Trí tu là gì? ệ ư
Các câu h i ch a có câu tr l ả ờ – Li u trí tu có ph i là m t kh năng duy nh t hay ch là m t ộ ả
ệ
ệ
ộ
t và đ c l p
ấ ệ
ỉ ộ ậ
ả ộ ậ
ạ
tên g i cho m t t p h p các hành vi phân bi ợ ọ nhau? ế ế ề
ọ
– Th nào là kh năng sáng t o? ả – Th nào là tr c giác? ự – Đi u gì di n ra trong quá trình h c? ễ – Có th k t lu n ngay v tính trí tu t
ể ế
ậ
ể
ệ ừ ệ ệ ủ
vi c quan sát m t hành ộ ộ ơ ế
ề ả
vi hay không hay c n ph i có bi u hi n c a m t c ch nào ầ đó n m bên trong ?
ằ
C.1 – Gi
i thi u
TTNT. p.3
ớ
ệ
ỏ
ị
Đ nh Nghĩa AI Rich, E. and K. Knight . 1991. Artificial Intelligence.
•
•
George Luger: “An AI approach problem-solving is one which: • uses domain-specific knowledge to find a good-enough solution • to a hard problem in a reasonable amount of time.”
C.1 – Gi
i thi u
TTNT. p.4
ớ
ệ
New York: McGraw-Hill. “Artificial intelligence (AI) is the study of how to make computers do things which at the moment, people do better.”
Turing Test
Interrogator
u đi m c a Turing Test ủ Ư ể – Khái ni m khách quan v trí tu ệ ề – Tránh đi nh ng th o lu n v quá trình bên trong và ậ
ệ
ữ ề ả
ý th cứ
C.1 – Gi
i thi u
TTNT. p.5
ớ
ệ
– Lo i tr đ nh ki n thiên v c a ng ế ạ ừ ị ị ủ ườ i th m v n ấ ẩ
Các ý ki n ph n đ i Turing Test ả ố ế Thiên v các nhi m v gi i quy t v n đ b ng ụ ả
ế ấ
ề ằ
ệ
ị ký hi uệ
Trói bu c s thông minh máy tính theo ki u con
ộ ự
ể
i có:
ườ
ườ ộ
ng – B nh gi – Có khuynh h
i, trong khi con ng i h n ớ ớ ạ ướ
ắ
Tuy nhiên, tr c nghi m Turing đã cung c p m t ộ ấ c s cho nhi u s đ đánh giá dùng th c s ự ự ơ ở cho các ch
ệ ề ơ ồ ng trình TTNT hi n đ i.
ươ
ệ
ạ
C.1 – Gi
i thi u
TTNT. p.6
ớ
ệ
ng nh m l n ẫ ầ
Các ng D ng c a TTNT
Ứ
ụ
ủ
đ ng
ự ộ
ố ị ệ
i máy
nhiên ườ
ạ
ả
i thu t di truy n ề
ậ
1. Trò ch i và các bài toán đ ơ 2. Suy lu n và ch ng minh đ nh lý t ậ ứ 3. Các h chuyên gia (các h tri th c) ứ ệ 4. X lý ngôn ng t ử ữ ự 5. L p k ho ch và ng ế ậ 6. Máy h cọ 7. M ng Neuron và gi ạ 8. …
C.1 – Gi
i thi u
TTNT. p.7
ớ
ệ
Trí Tu Nhân T o - Đ c Đi m
ệ
ể
ặ
ạ
S d ng máy tính vào
ậ
ậ ạ ẫ
ấ suy lu n trên các ký hi u, ệ … nh n d ng qua m u, h c, và các suy lu n khác ọ ợ ớ ề
Quan tâm đ n các k thu t gi
T p trung vào các v n đ “khó” i mang tính thu t toán ế
i gi ử ụ ậ ậ các l không thích h p v i . ờ ả
ế ấ ả ỹ
Cho l
ậ i quy t v n đ s ậ ề ử d ng ụ các thông tin không chính xác, không đ y đ , ầ ủ m hơ ồ… i gi i ‘đ t i gi t’ i chính ủ ố ch không ph i là l ứ ả ả ờ ờ
ả i uố ư .
C.1 – Gi
i thi u
TTNT. p.8
ớ
ệ
xác hay t S d ng heuristics – “bí quy t” ế ử ụ S d ng ử ụ tri th c chuyên môn ứ …
Nh ng v n đ ch a đ
c gi
ề ư ượ
ữ
ấ
ả
i quy t ế
sinh ra đ
ượ
Ch c heuristic ư ự Ch a có kh năng x lý song song c a con ử
ng trình ch a t ả
ủ
ng
ề
ễ
ộ ấ ư
i m t v n đ theo i. ườ Ch a có kh năng x lý thông tin trong môi ử
i.
tr
ư
i.
ng.
Ch a có kh năng di n gi ả ả ng pháp khác nhau nh con ng ươ ả ụ ả ả
ng liên t c nh con ng ườ Ch a có kh năng h c nh con ng ườ ư Ch a có kh năng t ớ
ọ thích nghi v i môi tr ự
ườ
ươ ư iườ ư nhi u ph ề ư ườ ư ư
C.1 – Gi
i thi u
TTNT. p.9
ớ
ệ
TTNT = Bi u Di n + tìm ki m ễ
ể
ế
TTNT. p.10
TTNT »
bi u di n và tìm ki m
ế
ể
ễ
H th ng ký hi u v t lý
ệ ậ
ệ ố
H th ng ký hi u
ệ ố
ệ = t p h p các ậ
ợ m uẫ và các
t tiêu ả ấ ệ
Các hành vi thông minh đ t đ
c b ng vi c
ạ ượ ằ
ệ
quá trình, trong đó các quá trình s n xu t, tri và thay đ i các m u. ổ ẫ
ễ ạ
s d ng: ử ụ 1. Các m u ký hi u ẩ tr ng c a lĩnh v c ủ
ọ
ể ẫ
i gi ả
TTNT »
bi u di n và tìm ki m
TTNT. p.11
ể
ế
ễ
i có kh năng c a bài toán.. i gi 3. ệ đ bi u di n các khía c nh quan ể ể ự bài toán. 2. Các phép toán trên nh ng m u này đ sinh ra các ữ ủ i trong s các kh năng này. ả l ờ Tìm ki mế m t l ả ộ ờ ả ố
Gi
thuy t v h th ng ký hi u v t
ả
ế ề ệ ố
ệ ậ
có các ph
ươ
ộ ệ ố
ậ
lý ệ ộ
ng ổ
“M t h th ng ký hi u v t lý ủ
ệ ầ
ti n c n và đ cho m t hành vi thông minh t ng quát” (Nowell và Simon) Allen Newell and Herbert A. Simon, Computer Science as Empirical Inquiry: Symbols and Search, Communications of the ACM (March 1976)
TTNT »
bi u di n và tìm ki m
TTNT. p.12
ế
ể
ễ
ư
ễ
TTNT nh là s bi u di n và tìm ự ể ki mế
ự ể
ả : S bi u di n ph i ễ • Cung c p m t c c u t ộ ơ ấ ự ấ ữ ệ
nhiên đ th hi n tri ộ ầ ủ => Tính bi u ể
ể ể ệ th c/thông tin/ d li u m t cách đ y đ ứ đ tạ
ệ ự ả ệ
=> Tính hi u qu ề ả
• H tr vi c th c thi m t cách hi u qu vi c tìm ộ ỗ ợ ệ ki mđáp án cho m t v n đ ệ ộ ấ ế ế : Li u vi c tìm ki m ệ – Có k t thúc không? – Có ch c ch n s tìm đ – Có ch c ch n s tìm đ
i không? i t i gi i gi i u không? ả ả ố ư
ệ ế ắ ắ
TTNT »
bi u di n và tìm ki m
TTNT. p.13
ế
ễ
ể
c l ượ ờ c l ượ ờ ắ ẽ ắ ẽ
ễ
ư
ờ
:
i ự ộ đ th không gian tr ng thái
ế ạ
TTNT nh là bi u di n & tìm ể ki mế Gi i quy t v n đ nh là s tìm ki m l ề ư ế ấ ả i trong m t gi ồ ị ả – Nút ~ tr ng thái (node ~ state) ạ – Liên k t (link) ế
Ví d : ụ
ơ
– Trò ch i tic-tac-toe – Ch n đoán tr c tr c máy móc trong ô tô ặ
ụ
ẩ
TTNT »
bi u di n và tìm ki m
TTNT. p.14
ễ
ế
ể
KGTT c a Trò Ch i Tic-Tac-Toe
ủ
ơ
TTNT »
bi u di n và tìm ki m
TTNT. p.15
ễ
ể
ế
Ch n đoán tr c tr c máy móc trong ô tô ặ
ụ
ẩ
TTNT »
bi u di n và tìm ki m
TTNT. p.16
ế
ể
ễ
Ch
– Phép tính v tị ừ
ng 2 ươ Logic hình th cứ
ứ ễ
ễ
– Logic hình th c = Bi u di n + suy lu n ậ ễ – Dùng nh là m t c ch bi u di n tri th c ứ ộ ơ ế ễ – Dùng nh là tìm ki m không gian tr ng thái trong ế ạ
– Dùng đ hình th c hóa các lu t heuristic ậ
ệ
TTNT. p.17
C2 – Phép tính v tị ừ
ư ư các đ th And/Or ồ ị ứ ể Có hai ngôn ngữ: – Phép tính m nh đ ề – Phép tính v tị ừ
Phép tính m nh đ (1)
ệ
ề
i. ị
ặ ể
ạ => => =>
Đúng Sai Sai
ứ
ệ ệ ệ
ề
ệ ệ
ệ ệ
(cid:217) (h i), ộ (cid:218) (tuy n), ể
(cid:216)
(ph đ nh), ủ ị
ng đ
ng)
(cid:222)
M nh đ : ề là các câu kh ng đ nh v th gi ề ế ớ ẳ M nh đ có th đúng (true) ho c sai (false). ề M nh đ đ n gi n ả : ề ơ Đ ng là m t kim lo i ộ ồ G là m t kim lo i ạ ộ ỗ Hôm nay là th Hai Ký hi u trong phép tính m nh đ : ề – Ký hi u m nh đ : P, Q, R, S,... ệ – Ký hi u chân lý: true, false – Các phép toán logic: (kéo theo) , = (t ươ
ươ
TTNT. p.18
C2 – Phép tính v tị ừ
ệ
ề
ệ
ệ
Phép tính m nh đ (2) ề Đ nh nghĩa câu trong phép tính m nh đ : ề ệ ỗ ộ ủ ủ ị
ộ ng đ
ng c a hai câu là m t câu.
ươ
ủ
ộ
ộ
ị – M i ký hi u m nh đ , ký hi u chân lý là m t câu. ệ – Ph đ nh c a m t câu là m t câu. ộ – H i, tuy n, kéo theo, t ể
ươ ể
c dùng đ nhóm các ký hi u vào các ệ ượ
ể
c g i là m t ệ ượ ọ
c t o ộ câu (hay ể ượ ạ
R) = (cid:216) P (cid:218) (cid:216) Q (cid:218) R
(cid:217) Q) (cid:222)
Ký hi u ( ), [ ] đ ệ bi u th c con. ứ M t ộ bi u th c m nh đ ề đ ứ ể ẩ - WFF) (cid:219) công th c d ng chu n ứ ạ nh ng ký hi u h p l thành t ợ ệ ệ ừ ữ lu t trên. ậ Ví d : ( (P ụ
TTNT. p.19
C2 – Phép tính v tị ừ
thông qua m t dãy các nó có th đ ộ
Ng Nghĩa c a Phép Tính MĐ
ữ
ủ
S thông d ch
(Intepretation):
ị ự – Là s ự gán giá tr chân lý
ị (T / F) cho các câu m nh ệ
đ .ề
ng đ
c
ượ
ườ
xác đ nh b ng
:
ị
ị ằ
– Là m t s kh ng đ nh chân lý c a các câu m nh đ ề ộ ự ẳ ủ ệ ị
P(cid:217) Q P(cid:218) Q P(cid:222) Q P=Q T F F F
Q T F T F
T F F T
T F T T
T T T F
TTNT. p.20
P T T F F C2 – Phép tính v tị ừ
i kh h u nào đó. trong m t th gi ế ớ ộ ả ữ S thông d ch c a m t câu kép th ộ ủ ự b ng chân lý ả (cid:216) P F F T T
S T
ự ươ
ng Đ ng c a Phép Tính ủ
ươ
MĐ
(cid:216) ((cid:216) P) = P (P(cid:218) Q) = ((cid:216) P (cid:222) Q) Lu t t ng ph n: (P ậ ươ ả Lu t De Morgan: ậ
(cid:222) (cid:216) P)
Q) = ((cid:216) Q (cid:222) (cid:216) (P (cid:218) Q) = ((cid:216) P (cid:217) (cid:216) Q), và (cid:216) (P (cid:217) Q) = ((cid:216) P (cid:218) (cid:216) Q)
Lu t giao hoán: (P ậ Lu t k t h p: ậ ế ợ
(cid:217) Q) = (Q (cid:217) P), và (P(cid:218) Q) = (Q(cid:218) P)
Lu t phân ph i: P
((P (cid:217) Q) (cid:217) R) = (P (cid:217) (Q (cid:217) R)), ((P (cid:218) Q) (cid:218) R) = (P (cid:218) (Q (cid:218) R))
(cid:218) (Q (cid:217) R) = (P (cid:218) Q) (cid:217) (P (cid:218) R), ậ ố
TTNT. p.21
C2 – Phép tính v tị ừ
P (cid:217) (Q (cid:218) R) = (P (cid:217) Q) (cid:218) (P (cid:217) R)
ị ừ ữ
ậ
ợ
ữ ố VD: X3,
Phép TínhV T (1) ệ ị ừ là t p h p g m các ch cái, ch s , ký ồ c b t đ u b ng ch cái. ượ ắ ầ ằ
ữ
ệ
Ký hi u v t hi u “_”, và đ tom_and_jerry Ký hi u v t ệ
i.
ế ớ
ộ
ệ
ằ
ng / thu c
ng / thu c tính trong th gi VD: helen, yellow, rain ộ
ố ượ
ị ừ có th là: ể
– ký hi u chân lý ệ : true, false – H ngằ : dùng đ ch m t đ i t ể ỉ ộ ố ượ • Ký hi u b t đ u b ng ch th ng: ữ ườ ắ ầ – Bi nế : dùng đ ch m t l p t ng quát các đ i t ể ỉ ộ ớ ổ
tính.
• Ký hi u b t đ u b ng ch hoa:
ệ
ắ ầ
ữ
ể ỉ ộ
ng:
VD: X, People, Students ng. ố ượ VD: father, plus
ữ ườ
ệ
ằ – Hàm: dùng đ ch m t hàm trên các đ i t • Ký hi u b t đ u b ng ch th ằ ắ ầ • M i ký hi u hàm có m t ngôi n, ch s l ệ
ộ
ỗ
ng các đ i s c a hàm. ố ố ủ
ệ ữ
ặ
ỉ ố ượ ố
– V tị ừ: dùng đ đ nh nghĩa m t m i quan h gi a không ho c ộ
nhi u đ i t
ề
ng.
VD: likes, equals, part_of
ể ị ng. b t đ u b ng ch th ằ ị ừ ắ ầ
ữ ườ
TTNT. p.22
ố ượ • Ký hi u v t ệ C2 – Phép tính v tị ừ
Bi u th c hàm
ị ừ ệ
ộ
ở
Phép TínhV T (2) ứ
ể
ộ ằ
ứ
ế
ể
ộ
M cụ (term): là m t h ng, m t bi n hay m t bi u th c
hàm
ộ ằ
ầ
ở ấ
ầ ế
Câu s c pơ ấ : là m t h ng v t ỗ ở ấ
ơ ấ
ị
v i n ngôi theo sau b i n ị ừ ớ thành ph n (m i thành ph n là m t m c) đ t trong d u (), ặ ộ ụ cách nhau b i d u ‘,’ và k t thúc v i d u ‘.’ ớ ấ – Tr chân lý true, false là các câu s c p. – Câu s c p còn đ ơ ấ
ể
ề
c g i là: bi u th c s c p (atomic ứ ơ ấ ượ ọ (atom) hay m nh đ (proposition) expression), nguyên t ệ ử likes(hellen, mary). VD: friends(helen, marry). likes( X, ice-cream).
likes(helen, sister(mary)).
Ký hi u v t
trong các câu này là friends, likes.
ệ ị ừ
TTNT. p.23
C2 – Phép tính v tị ừ
: là m t ký hi u hàm theo sau b i n đ i s . ố ố VD: father(david) price(bananas) like(tom, football) ộ
Phép TínhV T (3)
ị ừ
c t o ra b ng cách k t h p các câu s c p s ơ ấ ử ế ợ
ằ
ượ ạ
, (cid:217) , (cid:218) , (cid:222)
, =
Câu: đ d ng:ụ : (cid:216) – Các phép k t n i logic – Các l ng t • L ng t
ớ
: dùng đ ch m t câu là đúng v i X likes(X, ice- ng giá
ể ỉ ộ VD: "
ế ượ
:
ng t
• L
ớ
ể ỉ ộ ng giá.
VD: $ Y
ế ố ử ế : bi n ượ ử ổ ế " ph bi n ượ m i giá tr c a bi n l ị ủ ọ cream). ượ ộ ố
ủ
dùng đ ch m t câu là đúng v i ế ượ
ử ồ ạ $ t n t i m t s giá tr nào đó c a bi n l ị friends(Y,tom).
likes(bart, chocolat).
VD: likes(helen, chocolat) (cid:217) (cid:216) X foo(X,two,plus(two,three)) (cid:217) equal(plus(three,two),five)
$
(equal(plus(three,two),five)= true). TTNT. p.24
(foo(two, two,plus(two,three))) (cid:222) C2 – Phép tính v tị ừ
Ng Nghĩa c a Phép Tính V T
ị ừ
ữ
ủ
S thông d ch
ủ c a m t t p h p các câu phép tính v ị ợ
ề
ị ộ ự ộ ậ ự
ề ủ ấ và hàm. ị ừ
ệ
ế
ằ
ỗ
ượ
c xác đ nh qua s ự
ự : ừ là m t s gán các th c th trong mi n c a v n đ đang t ể đ c p cho m i ký hi u h ng, bi n, v t ề ậ
ị ơ ấ
Giá tr chân lý c a m t câu s c p ơ ấ đ ủ ả ố ớ ố ế
ị ộ
thông d ch. Đ i v i các câu không ph i là câu s c p, s ị ử d ng b ng chân lý cho cho các phép n i k t, và: ả ụ – Giá tr c a câu ị ủ
t c ấ ả
các phép gán có th đ
c cho X.
"
i m t phép gán
– Giá tr c a câu ị ủ
ế ồ ạ
ộ
cho X làm cho
$
X là true n u là T cho t
ế
ể ượ
X là true n u t n t
ị
TTNT. p.25
C2 – Phép tính v tị ừ
Phép Tính V T B c Nh t ấ
ị ừ ậ
ng giá tham
chi u đ n các đ i t
ng trong mi n c a v n đ đang đ c p
b c nh t
ế
Phép tính v t ế nh ng KHÔNG đ
ế ượ ề và hàm.
c tham chi u đ n các v t
ượ
ư
ị ừ
ế
ế
ề ậ
ị ừ ậ ố ượ ấ cho phép các bi n l ề ủ ấ
(Likes) Likes(helen, ice-cream)
VD không h p l
VD h p l
" : ợ ệ
– N u ngày mai tr i không m a, tom s đi bi n.
ế
: ợ ệ
ể ẽ go(tom, sea)
ấ ả
ầ
"
tall(X) )
– Có ng
" "
ư ờ (cid:216) weather(rain, tomorrow) (cid:222) – T t c các c u th bóng r đ u cao. ổ ề ủ X ( basketball_player(X) (cid:222) i thích coca-cola ườ X person(X) (cid:217) likes(X, coca-cola)
– Không ai thích thuế
" $
$ X likes(X, taxes)
TTNT. p.26
C2 – Phép tính v tị ừ
" (cid:216)
ị ừ
ụ ề
Cho tr
mother(eve, cain) father(adam,cain)
parent(X,Y)
Ví d v phép tính v t c:ướ mother(eve,abel) father(adam, abel) " X " Y father(X,Y) (cid:218) mother(X,Y) (cid:222) " X " Y $ Z parent(Z,X) (cid:217) parent(Z,Y) (cid:222)
sibling(X,Y)
parent(eve, cain) parent(adam,cain) sibling(cain, abel)
Có th suy lu n: ậ ể parent(eve,abel) parent(adam,abel) sibling(abel, cain) sibling(abel,abel)sibling(cain,cain) !không có nghĩa
TTNT. p.27
C2 – Phép tính v tị ừ
ậ
Q
Các lu t suy di n ễ (MP): P (cid:222)
Lu t Modus Ponens
ậ
P
Q
Lu t Modus Tolens
Q
ậ
Lu t tri n khai ph bi n
ể
ậ
(MT): P (cid:222) (cid:216) Q (cid:216) P ổ ế (Universal
Instantiation):
ủ ề ị
TTNT. p.28
C2 – Phép tính v tị ừ
" X P(X) a thu c mi n xác đ nh c a X ộ P(a)
i,
Ví Dụ ế
ườ
“T t c m i ng ấ ả ọ do đó Socrates s ch t”
i đ u ch t và Socrates là ng ườ ề ẽ ế
=>
mortal(X)
" X man(X) (cid:222) man(socrates)
(1) (2)
T (1),(2) b ng lu t UI, ta có:
ừ
ậ ằ man(socrates) (cid:222)
(3)
T (3) và (2) b ng lu t MP, ta có:
ừ
mortal(socrates) ậ
ằ mortal(bill)
TTNT. p.29
C2 – Phép tính v tị ừ
(4)
ợ
ụ
ẫ ậ
ư
ố ể ả
Đ i sánh m u và phép h p nh t ấ Đ áp d ng các lu t nh MP, m t h suy di n ph i có ả m tộ hay
ộ ệ ể ứ
ể
ả
ộ
ị đ i sánh ố
ấ là m t gi
i thu t dùng đ xác đ nh nh ng ữ ậ t đ làm cho hai bi u th c v ứ ị ế ể
ị ể
ầ
phép th (substitution) c n thi đ i sánh nhau. t ừ ố M t bi n có th thay th b i m t ể ộ
ế ở
ế
ộ m cụ b t kỳ:
ấ
ế
ộ
Thay th b i ế ở
ễ kh năng xác đ nh khi nào thì hai bi u th c là (match). còn g i là ọ Phép h p nh t ợ ế
Bi n đã k t bu c ế (bound)
ư ế
H ngằ
Bi n ch a k t bu c (unbound)
ế ộ
Bi nế Bi n khác ế
TTNT. p.30
C2 – Phép tính v tị ừ
ể ể ứ ế
Bi u th c hàm có ứ th ch a các bi n khác
ẫ
ch khi chúng gi ng h t nhau
ỉ
ố
ệ
ớ
“Gi 1. H ng / h ng ằ VD: ằ
i thu t” Đ i Sánh M u ố ậ ả ằ đ i sánh : ố tom không đ i sánh v i jerry ố đ i sánh ố : ộ
2. H ng a / bi n X ế
ộ ớ ằ
ế
ở
ộ
ế 2. Bi n X/ bi n
ế
ế a. Bi n ch a k t bu c: bi n tr thành k t bu c v i h ng ế ư ế => Khi đó ta có phép th ế {a/X} a. Bi n đã k t bu c : xem (1) ế ế Y đ i sánh ố : a. Hai bi n ch a k t bu c: luôn luôn đ i sánh
ư ế
ế
ộ
ố
ế
ộ
ế
ộ
ộ ộ
ỉ
, s ặ ị ừ ố
ế ế 2. Bi u th c / bi u th c ứ
ể
ể
ố ố ộ
ố
=> Khi đó ta có phép th {X/Y} a. M t bi n k t bu c và m t bi n ch a k t bu c: xem (2) ư ế ộ ế b. Hai bi n k t bu c: xem (1) ế ứ đ i sánh: ố ch khi các tên hàm ho c v t ừ ố ụ ố
ớ
- đ i sánh v i goo(foo(Y)) v i phép th {foo(Y) / X}
ngôi gi ng nhau thì áp d ng đ i sánh t ng đ i s m t. VD: goo(X) - không đ i sánh v i foo(X) hay goo(X,Y) ớ
ế
ớ
ố
TTNT. p.31
C2 – Phép tính v tị ừ
Ph m vi c a m t bi n ủ
ộ
ế
ạ
ộ
ạ ộ
ủ ế
ộ ế ế
ả
Ph m vi c a m t bi n là m t câu. ế ộ M t khi bi n đã b k t bu c, các phép h p nh t ấ ợ ị ế s k t theo sau và các suy lu n k ti p ph i gi ữ ự ế ậ bu c này
ộ VD:
c:
ế
ượ
man(X) => mortal(X) N u ta th X b i socrates thì ta đ ở ế man(socrates) => mortal(socrates)
TTNT. p.32
C2 – Phép tính v tị ừ
ụ
ứ ố
ể
ố ị
Ví d : Bi u th c đ i sánh Hãy xác đ nh xem foo(X,a,goo(Y)) có đ i sánh v i các ớ t phép th ế
foo(Z,a,goo(moo(Z))) foo(W,a,goo(jack))
ế ế
bi u th c sau hay không? N u có thì cho bi ứ ể ng ng: t ươ ứ – foo(X,b,foo(Y)) – foo(fred, a, goo(Z)) – foo(X,Y) – moo(X,a,goo(Y)) – – Cho bi t k t qu có đ ượ c khi h p nh t p(a, X) v i : ấ ợ ớ
TTNT. p.33
C2 – Phép tính v tị ừ
ả ế ế – p(Y,Z) => q(Y,Z) – q(W,b) => r(W,b)
Th t c h p nh t “Unify”
ủ ụ ợ
ấ
Ghi chú:
p(a,b) ~ (p a b)
p(f(a), g(X, Y) ~ (p (f a) (g x Y) )
TTNT. p.34
C2 – Phép tính v tị ừ
ấ
ế
ủ
ế
ậ ị
ụ
Tích các phép th h p nh t ế ợ (Composition) N u S và S’ là hai t p h p phép th , thì tích c a ợ c xác đ nh b ng cách áp d ng S’ cho ằ c a S và b sung k t qu này
ượ ầ ử ủ
ế
ả
ổ
S và S’ đ nh ng ph n t ữ vào S. VD: {X/Y, W/X}, {V/X}, {a/V, f(b)/W}
TTNT. p.35
C2 – Phép tính v tị ừ
=> {a/Y, f(b)/Z}
ợ ử ổ
t ng quát nh t H p t ấ (Most General Unifier)
i thu t h p nh t là h p t
ậ ợ
ầ ủ
ợ ử ấ t: đó là h p t ợ ử ố ứ
ể
ấ
Yêu c u c a gi ả (unifier) càng t ng quát càng t ổ t ng quát nh t tìm th y cho hai bi u th c. ấ ổ VD: Khi h p nh t p(X) và p(Y): ấ
ợ
(cid:222)
t ng quát nh t ấ ợ ử ổ
TTNT. p.36
C2 – Phép tính v tị ừ
(cid:222) không nên ch nọ {fred/X, fred/Y} vì fred không ph i ả là h p t nên ch nọ {Z/Y, Z/Y}
v n tài chính
Ứ
ụ
ng D ng: H t ệ ư ấ (1)
ệ ư ấ ắ
H t Các cá nhân không đ ti n ti t ki m nên tăng ti n ti t v n tài chính ho t đ ng theo các nguyên t c sau: ế ế ề
ệ ki m, b t k thu nh p là bao nhiêu. ệ
ấ ể Các cá nhân có đ ti n ti ạ ộ ủ ề ậ ủ ề ế ậ
xem xét vi c đ u t
ệ ầ ư ớ t ki m và đ thu nh p nên ủ ệ vào ch ng khoán. ứ ấ ư
Các cá nhân v i thu nh p th p nh ng đ ti n ti ủ ề ậ ki m có th chia ph n thu nh p thêm vào ti ế ầ ch ng khoán.
ể ậ t ế t ki m và ệ
ệ ứ
t ki m đ là 5000$/ ng ườ
TTNT. p.37
C2 – Phép tính v tị ừ
V i:ớ ti ụ ế Thu nh p đ 15000$ + (4000$ / ng i ph thu c ộ i ph thu c) ủ ệ ậ ủ ườ ụ ộ
v n tài chính
Ứ
ụ
ng D ng: H t ệ ư ấ (2)
nh sau:
ự
ệ ố
ị ừ ư
ớ
Xâu d ng h th ng logic v i các câu v t 1.
investment(saving)
2.
investment(stocks)
3.
savings_account(inadequate) (cid:222) savings_account(adequate) (cid:217) income(adequate) (cid:222) savings_account(adequate) (cid:217) income(inadequate) (cid:222)
investment(combination)
4 .
" X amount_saved(X) (cid:217)
$ Y(dependents(Y) (cid:217) greater(X,minsavings(Y)))
savings_account(adequate)
5 .
$ Y(dependents(Y) (cid:217)
savings_account(inadequate)
6 .
$ Y(dependents(Y) (cid:217)
income(adequate)
7 .
$ Y(dependents(Y) (cid:217)
income(inadequate)
8 .
income(inadequate)
" X amount_saved(X) (cid:217) (cid:216) greater(X,minsavings(Y))) (cid:222) " X earning(X, steady) (cid:217) greater(X,minincome(Y))) (cid:222) " X earning(X, steady) (cid:217) (cid:216) greater(X,minincome(Y))) (cid:222) " X earning(X, unsteady) (cid:222) With: minavings(X) = 5000 * X
minincome(X)=15000+(4000*X)
TTNT. p.38
C2 – Phép tính v tị ừ
(cid:222)
v n tài
Ứ
ụ
ệ ư ấ
ng D ng: H t chính(3)
v i tình tr ng nh sau: ạ
ư
ộ
M t nhà đ u t ầ ư ớ amount_saved(22000) 9. 10. earnings(25000,steady) 11. dependents(3)
Dùng phép h p nh t và lu t Modus Ponens, suy
investment (?) ấ ợ
ậ
ra:
(cid:222)
12. income(inadequate) 13. savings_account(adequate) investment (combination)
TTNT. p.39
C2 – Phép tính v tị ừ
(cid:222)
ng 2
Bài T p Ch ậ
ươ
TTNT. p.40
Ch
- C u trúc và chi n
ế
ấ
ươ l
c cho TK - KGTT
ng 3 ượ
ễ ộ ấ ộ ồ ị ề ư
ể ạ
ể ử ụ ộ ứ ạ ủ
rb1
Khi bi u di n m t v n đ nh là m t đ th không gian tr ng thái, chúng ta có th s d ng lý thuy t đ ế ồ th đ phân tích c u trúc và đ ph c t p c a các v n ấ ấ ị ể đ cũng nh các th t c tìm ki m. ề
b2
b4
ủ ụ ư ế
Riverbank 1
b3
b1
i2
4
2
3
i1
1
Island 2
Island 1
b6
b7
b5
6
5
7
rb2
Riverbank 2
H th ng c u thành ph Konigsberg và bi u di n đ th t
ng ng
ồ ị ươ ứ
ệ ố
ể
ễ
ầ
ố
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.41
ế
ạ
ng 3
ộ
ươ
N i dung ch ạ
ị
Đ nh nghĩa Không Gian Tr ng Thái Các chi n l
c tìm ki m trên không gian tr ng
ế ượ
ế
ạ
ng t ng t
d li u m c tiêu
ừ ữ ệ (data – driven) ừ ụ
(goal – driven). Tìm ki m trên không gian tr ng thái:
thái: – TK h ướ – TK h ướ ế
ạ – TK r ng ộ (breath – first search) – TK sâu (depth – first search) – TK sâu b ng cách đào sâu nhi u l n
ằ
ề ầ (depth – first
ể ễ
S d ng không gian tr ng thái đ bi u di n suy ạ :
ễ ị ừ Đ th Và/Ho c
ồ ị
ặ (And/Or
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.42
search with iterative deepening) ử ụ lu n v i phép tính v t ớ ậ Graph) ế
ạ
Ạ
ộ ạ
c a đ th . ủ ồ ị ữ ậ
ĐN: KHÔNG GIAN TR NG THÁI M t ộ KGTT (state space) là 1 b [N, A, S, GD] trong đó: N (node) là các nút hay các tr ng thái A (arc) là t p các S (solution) là m t t p ch a các
tr ng thái đích c a bài cung (hay các liên k tế ) gi a các nút. ạ ủ ứ
N (cid:217) S „
c mô t ượ ả
ng đ
c các tr ng thái g p trong quá
toán.(S (cid:204) ạ ộ
ể
ặ
ặ
ạ
theo m t trong hai đ c tính: – Đ c tính có th đo l ượ
c hình thành trong quá trình tìm
ế ủ ườ
ượ
ộ ậ ˘ ) Các tr ng thái trong GD (Goal Description) đ ặ ườ trình tìm ki m. VD: Tic-tac-toe, 8-puzzle,… ng đi đ
i ủ ờ ả (solution path) là m t con ộ
ng đi qua đ th này t ừ ộ m t nút thu c S đ n m t ộ ế ộ i gi ồ ị
– Đ c tính c a đ ặ ki m. VD: TSP ế Đ ng đi c a l ườ đ ườ nút thu c GD. ộ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.43
ế
ạ
ầ
ộ
M t ph n KGTT tri n khai ể trong Tic-tac-toe
Đ th có h
ướ
ồ ị
ặ ạ
ng i (directed không l p l acyclic graph - DAG)
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.44
ế
ạ
ố
Trò đ 8 ô hay 15 ô ạ ạ
Tr ng thái ban đ u Tr ng thái đích ầ
11
14
4
7
4
1
2
3
10
5
6
5
12
13
14
Trò đố 15 ô
1
2
13
15
6
11
15
9
3
12
8
7
10
9
8
2
8
1
2
3
5
7
3
8
4
Trò đố 8 ô
2
1
6
7
6
5
C n bi u di n KGTT cho bài toán này nh th ư ế
ễ
ể
ầ nào?
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.45
ế
ạ
ủ
KGTT c a 8-puzzle sinh ra b ng ằ phép “di chuy n ô tr ng”
ố
ể
ả
ả
Có kh năng x y ra vòng l p không? ặ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.46
ế
ạ
M t ví d c a bài toán TSP
ụ ủ
ộ
C n bi u di n KGTT cho bài toán này nh th ư ế
ể
ễ
ầ nào?
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.47
ế
ạ
KGTT c a bài toán TSP
ủ
ỗ
ượ ằ
ng t
ủ nút ế
c M i cung đ đánh d u b ng ấ t ng giá c a con ổ đ ườ ừ b t đ u đ n nút ắ ầ i. hi n t ệ ạ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.48
ế
ạ
Các Chi n L
c cho TK-KGTT
ế
ượ
d li u (Data-driven Search)
TK h
TK h
m c tiêu (Goal-driven Search)
ng t ừ ữ ệ ướ – Suy di n ti n (forward chaining) ế ễ ng t ừ ụ ướ – Suy di n lùi (backward chaining) ễ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.49
ế
ạ
D Li u
ừ ữ ệ
Vi c tìm ki m đi t
ế
TK H ng t ướ ừ ệ d li u đ n m c tiêu ế ữ ệ
đ u.
ặ
ừ ầ
Thích h p khi: ợ ấ ả ề
ụ
– T t c ho c m t ph n d li u đ ầ ữ ệ ượ ộ – Có nhi u m c tiêu, nh ng ch có m t s ít các phép toán có ỉ
ụ
thuy t ngay lúc đ u.
c cho t ộ ố ư th áp d ng cho m t tr ng thái bài toán. ộ ạ – R t khó đ a ra m t m c tiêu ho c gi ụ ộ
ể ấ
ư
ế
ả
ặ
ầ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.50
ế
ạ
ụ
TK H ng T M c Tiêu
ừ ụ
ướ Vi c tìm ki m đi t ệ ừ ế m c tiêu tr v ở ề ụ d li u. ữ ệ
Thích h p khi:
thuy t
ụ
ặ
– Có th đ a ra m c tiêu ho c gi ả – Có nhi u phép toán có th áp d ng trên 1 tr ng thái c a bài ụ
ế ngay lúc đ u.ầ ủ
toán => s bùng n s l
ể ổ ố ượ
ự ữ ệ ủ
c, nh ng h ệ ư
th ng ph i đ t đ
– Các d li u c a bài toán không đ ả ạ ượ
ố
ạ ng các tr ng thái. ạ c cho tr ướ ượ c trong quá trình tìm ki m. ế
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.51
ế
ạ
ợ ể ư ề
Các ph
ươ
ng pháp tìm ki m trên đ ồ
ế
th KGTT:
ị
back –
gi
i thu t quay lui (
ậ
ể ừ ả
ộ (breath-first search) (depth-first search)
ằ
ề ầ (depth-
Phát tri n t tracking): Tìm ki m r ng ế Tìm ki m sâu ế TK sâu b ng cách đào sâu nhi u l n first search with iterative deepening)
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.52
ế
ạ
Tìm Ki m R ng ế
ộ
1.
2.
2.
3.
4.
5.
6.
Open = [A]; closed = [] Open = [B,C,D]; closed = [A] Open = [C,D,E,F]; closed = [B,A] Open = [D,E,F,G,H]; closed = [C,B,A] Open = [E,F,G,H,I,J]; closed = [D,C,B,A] Open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A] Open = [G,H,I,J,K,L,M]; (vì L đã có trong open); closed = [F,E,D,C,B,A] …
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.53
ế
ạ
Tìm ki m Sâu ế
1.
2.
3.
4.
5.
6.
7.
8.
Open = [A]; closed = [] Open = [B,C,D]; closed = [A] Open = [E,F,C,D];closed = [B,A] Open = [K,L,F,C,D]; closed = [E,B,A] Open = [S,L,F,C,D]; closed = [K,E,B,A] Open = [L,F,C,D]; closed = [S,K,E,B,A] Open = [T,F,C,D]; closed = [L,S,K,E,B,A] Open = [F,C,D];
closed = [T,L,S,K,E,B,A]
9. …
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.54
ế
ạ
Tìm Ki m Sâu hay R ng? (1)
ộ ng đi ng n nh t ắ
ấ đ n ế
Có c n thi ầ
ộ đ
ườ
ế t tìm m t ế m c tiêu hay không?
ụ
ạ
S ự phân nhánh c a không gian tr ng thái ủ Tài nguyên v ề không gian và th i gian s n cóẵ Kho ng cách trung bình ng d n đ n ế ẫ
ờ c a đ ủ ườ
ả
ạ
ụ
t c các l
i gi
i
i
tr ng thái m c tiêu. ầ ư
ờ
ả hay ch là l
ỉ
ờ
ấ ả c đ u tiên.
gi
Yêu c u đ a ra t i tìm đ ượ ầ
ả
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.55
ế
ạ
ằ
ế
ề
Đ sâu gi
ớ ạ ạ
i thu t TK sâu i gi ả ạ ế ậ ộ ớ
TK Sâu b ng cách đào sâu nhi u l n:
ề ầ TK sâu v i ớ i GT TK
ị
Tìm ki m sâu b ng cách đào sâu nhi u l nầ (depth-first iterative deepening) i h n (depth bound): ộ s quay lui khi tr ng thái đang xét đ t đ n đ sâu gi ẽ h n đã đ nh. ạ ằ i h n là 1, n u th t b i, nó s l p l ớ ạ
ế
ấ ạ ế ụ
ẽ ặ ạ ế i tăng đ sâu lên 1. ớ ộ c m c tiêu, m i l n l p l ụ ộ
ộ ứ ạ
ề ờ
ậ
v i TK R ng và TK Sâu. ớ
ộ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.56
ế
ạ
đ sâu gi ộ sâu v i đ sâu là 2,… GT ti p t c cho đ n khi tìm đ ỗ ầ ặ ạ ượ GT này có đ ph c t p v th i gian cùng b c
Trò ch i ô đ 8-puzzle
ố
ơ
h t i
5 d n u o b h t p e d d n a n o i t c e t e d p o o l
w m e t s y s n o i t c u d o r p a y b d e h c r a e s e l z z u p - 8 e h T
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.57
ế
ạ
Đ th Và/Ho c ặ S d ng KGTT đ bi u di n suy lu n v i phép ậ
ồ ị ể ễ
ễ
ớ
.
ng pháp
qui bài toán v các bài toán con
ử ụ tính v tị ừ ươ
ề
Là ph M t t p h p các m nh đ / câu v t
ợ
ề
ệ
ị ừ ạ
ộ
t c các bài
ấ ả
t o thành m t ộ ậ đ th Và/Ho c (And/Or graph) hay siêu đ th ồ ị ặ ồ ị (hypergraph). Trong đ th Và/Ho c: ặ ồ ị – Các nút AND bi u th s phân chia bài toán, t ị ự ứ
i quy t bài toán khác
ể toán con ph i đ ả ượ – Các nút OR bi u th các chi n l ể
ế
ứ
Có th áp d ng TK theo ki u h
ủ d li u hay t
c ch ng minh là đúng. c gi ế ượ ả ị nhau, ch c n ch ng minh m t chi n l ế ượ ộ ng t ể ướ
c đúng là đ ừ ữ ệ
ỉ ầ ụ
ừ ể
ế ủ ễ ậ
ế
i thu t c n ghi nh n di n ti n c a quá trình. TTNT. p.58 m c tiêu. ụ Trong gi ậ ầ ả C 3 – Tìm ki m không gian tr ng thái ạ
Ví d Đ th Và/Ho c ặ
ụ ồ ị
s m t tình hu ng v i các m nh đ sau: ớ
ệ
ề
ố
c
Gi ả ử ộ b a a(cid:217) b(cid:222) da(cid:217) c(cid:222) e b(cid:217) d(cid:222) a(cid:217) e(cid:222) h
f f(cid:222) g
i các câu h i sau: ỏ
C 3 – Tìm ki m không gian tr ng thái
TTNT. p.59
ế
ạ
Hãy tr l ả ờ 1. h có đúng không? 2. h có cón đúng nêu b sai?
Ví d : H T V n Tài Chính
ụ ệ ư ấ
ầ ồ ể
i ể
TTNT. p.60
Đ Th And/Or ị bi u di n ph n ễ KGTT đã duy t ệ qua đ đi đ n l ế ờ gi iả
: VÍ D Đ TH AND/OR
Ụ Ồ Ị
c mô t
b ng
ộ
ượ
ả ằ
Cho m t bài toán đ các câu v t
:
ị ừ
ẽ ồ ị
ễ
ầ
ể ỏ
đâu?” (Áp d ng suy
i câu h i: ụ
ở
Hãy v đ th AND/OR bi u di n ph n KGTK đ tr l ể ả ờ “Fred đang di n lùi)
ễ
TTNT. p.61
ng 3
Bài T p Ch ậ
ươ
TTNT. p.62
Ch
ng 4
ươ
c ch ng d a
ừ
ự
ướ
Các h gi
ệ ả
– Tìm ki m heuristic ế Heuristics: là các ph ng đoán, trên kinh nghi m, tr c giác. ệ s d ng heuristic trong ử ụ
ư chi phí ể ấ ạ
ơ ờ i phát bi u bài ự ề ớ
ỏ ự i quy t AI ế hai tình hu ng c b n ơ ả : ố – Bài toán đ c đ nh nghĩa chính xác nh ng ượ ị ả b ng TK vét c n là không th ch p i i gi tìm l ằ ờ nh nậ . VD: S bùng n KGTT trong trò ch i c vua. ổ ề ự ơ ồ trong l ể ấ ư
– V n đ v i nhi u s m h ữ ệ ờ ứ ẵ
TTNT. p.63
toán hay d li u cũng nh tri th c s n có. VD: Ch n đoán trong y h c. ọ
ẩ C 4 – Tìm ki m Heuristic ế
Gi
i Thu t Heuristic
ả
ậ
c xem g m 2
i thu t heuristic có th đ
ể ượ
ồ
ậ
ả
M t gi ộ ph n:ầ – Phép đo heuristic: th hi n qua
ể ệ
hàm đánh giá ể
ể ủ
ộ ạ i thu t tìm ki m heuristic: ế ậ
TTNT. p.64
C 4 – Tìm ki m Heuristic ế
heuristic (evaluation function), dùng đ đánh giá các đ c đi m c a m t tr ng thái trong KGTT. ặ – Gi ả • Gi ả • TK t i thu t leo núi (hill-climbing) t nh t (best-first search) ố ậ ấ
KGTT c a tic-tac-toe đ ủ ố
TTNT. p.65
C 4 – Tìm ki m Heuristic ế
c thu nh nh tính đ i ỏ ờ . ượ x ng c a các tr ng thái ứ ủ ạ
Phép đo heuristic (2)
Heuristic “S đ ố ườ ề ắ ấ ” áp d ng cho các ụ
TTNT. p.66
C 4 – Tìm ki m Heuristic ế
nút con đ u tien trong tic-tac-toe. ng th ng nhi u nh t ầ
KGTT càng thu nh khi áp d ng heuristic
ụ
ỏ
TTNT. p.67
C 4 – Tìm ki m Heuristic ế
i thu t Leo Núi
ả
ậ
Gi
ả
i và đánh giá các tr ng
Gi i thu t: ậ ở ộ
– M r ng tr ng thái hi n t ạ ệ ạ ạ
thái con c a nó b ng hàm đánh giá heuristic. ủ
Gi
t nh t” s đ ấ ằ ẽ ượ c ch n đ đi ti p. ể ế ọ
i tìm đ
– Gi i thu t có khuynh h ng b sa l y nh ng c c ướ ầ ở ữ ự ị
c không t i gi
i l
i gi
i
ả
i u ố ư ặ
ồ ạ ờ
ả
ượ c l ượ ờ ể ặ
– Con “t ố i h n: ớ ạ ậ ả đ i c c b : ạ ụ ộ L i gi ả ờ Không tìm đ
i m c dù có t n t ạ ệ
ư ậ
TTNT. p.68
C 4 – Tìm ki m Heuristic ế
– Gi i thu t có th g p vòng l p vô h n do không l u ặ ả thông tin v các tr ng thái đã duy t. gi ạ ữ ề
Gi
i thu t TK T t Nh t ấ
ố
ậ ả open = [A5]; closed = []
1. 2. Đánh giá A5; open = [B4,C4,D6];
closed = [A5] 3. Đánh giá B4;
open = [C4,E5,F5,D6]; closed = [B4,A5]
4. Đánh giá C4;
open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5]
5. Đánh giá H3;
open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5]
6.
Đánh giá O2;
open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] i gi
7. Đánh giá P3; tìm đ
i!
c l ượ ờ
ả
TTNT. p.69
C 4 – Tìm ki m Heuristic ế
ặ
Xét trò ch i 8-puzzle. Cho m i tr ng thái n m t giá tr f(n):
ơ
ộ
ị
n đ n tr ng thái b t đ u
ắ ầ
ả
ạ
g(n) = kho ng cách th c s t h(n) = hàm heuristic đánh giá kho ng cách t
tr ng thái n đ n
Cài Đ t Hàm Đánh Giá (Evaluation Function) ỗ ạ f(n) = g(n) + h(n) ế ự ự ừ ả
ừ ạ
ế
start
m c tiêu.
ụ
2
3
8
1
2
3
1
4
6
g(n) = 0
8
4
7
5
7
6
5
goal
2
3
8
2
3
8
2
3
8
1
4
6
1
4
1
4
6
g(n) = 1
h(n): s l
ố ượ
ng các v trí còn sai ị
5
7
7
5
6
7
5
6
f(n) =
4
6
TTNT. p.70
C 4 – Tìm ki m Heuristic ế
t k hàm
ế ế
Khó khăn trong thi heuristic
Ba heuristic áp d ng vào 3 tr ng thái c a trò ch i ô đ 8 s ạ
ụ
ủ
ơ
ố
ố
TTNT. p.71
C 4 – Tìm ki m Heuristic ế
ơ ố
Heuristic trong trò ch i đ i kháng Gi
:
ả
ậ
i thu t minimax – Hai đ u th trong trò ch i đ ủ
ế ế
ơ ượ ọ MIN và c g i là
ắ ắ ề
– Minimax s truy n các giá tr này lên cao d n trên ấ MAX. – M i nút lá có giá tr : ị ỗ • 1 n u là MAX th ng, • 0 n u là MIN th ng. ẽ ầ
ậ ị ẹ ế ế
ẹ MAX, gán cho nó giá tr ị l n ớ
ạ
ạ
• N u tr ng thái b , m là
ế
ạ
ẹ MIN, gán cho nó giá tr ị nh ỏ
ạ
TTNT. p.72
đ th , qua các nút cha m k ti p theo các lu t sau: ồ ị • N u tr ng thái cha m là ế
nh tấ có trong các tr ng thái con. ố nh t ấ có trong các tr ng thái con. C 4 – Tìm ki m Heuristic ế
Hãy áp d ng GT Minimax vào ụ Trò Ch i NIMơ
TTNT. p.73
C 4 – Tìm ki m Heuristic ế
ớ ộ
ớ ố ị đ nh.
Minimax v i đ sâu l p c đ nh Minimax đ i v i m t KGTT gi ố ớ
ả ị
ộ
c gán các giá tr
ượ
i các nút trong là các giá tr nh n
ị heuristic ị
ậ
ị ạ c d a trên gi
đ
i thu t Minimax
Các nút lá đ Còn giá tr t ượ ự
ả
ậ
TTNT. p.74
C 4 – Tìm ki m Heuristic ế
Heuristic trong trò ch i tic-tac-toe
ơ
Hàm Heuristic: Trong đó:
E(n) = M(n) – O(n) M(n) là t ng s đ ắ ố ườ ổ O(n) là t ng s đ ủ ắ ố ườ ổ E(n) là tr s đánh giá t ng c ng cho tr ng thái n ổ ị ố
ng th ng có th c a tôi ể ủ ng th ng có th c a đ i th ể ủ ố ạ
ộ
TTNT. p.75
C 4 – Tìm ki m Heuristic ế
c áp d ng vào ụ c đi m đ u trong tic-tac-toe
Minimax 2 l p đ ớ ượ n ở ầ
ướ
Trích t
Nilsson (1971).
ừ
TTNT. p.76
C 4 – Tìm ki m Heuristic ế
a
-b
Gi
i thu t c t t a
ả
ế
ể
ể ế
ậ ắ ỉ Tìm ki m theo ki u depth-first. Nút MAX có 1 giá tr ị a Nút MIN có 1 giá tr ị b TK có th k t thúc d a
– Nút MIN nào có b £
(luôn tăng) (luôn gi m)ả : i b t kỳ ướ ấ c a b t kỳ nút cha MAX ủ ấ
nào.
a -b
th hi n
ể ệ m i quan h ệ ố ạ
i đó toàn b ộ
– Nút MAX nào có a ‡ b c a b t kỳ nút cha MIN ủ ấ
i thu t c t t a ậ ắ ỉ , mà t l p n và n+2 ở ớ i l p n+1 có th c t b . ể ắ ỏ ố ạ ớ
TTNT. p.77
gi a các nút cây có g c t C 4 – Tìm ki m Heuristic ế
nào. Gi ả ữ
a
C t t a ắ ỉ S
MAX =
a ≥ a
A MIN Z =
a a - cut
TTNT. p.78
C 4 – Tìm ki m Heuristic ế
= z z ≤ a
b
C t t a ắ ỉ S
MIN =
b ≤ b
A MAX Z =
b b - cut
TTNT. p.79
C 4 – Tìm ki m Heuristic ế
= z z ≥ b
a
GT C t T a
ắ ỉ
-b gi
áp d ng cho KGTT ụ đ nh ả ị
ượ
Các nút không có giá tr là ị các nút không đ c duy t ệ qua
TTNT. p.80
C 4 – Tìm ki m Heuristic ế
ng 4
Bài T p Ch ậ
ươ
TTNT. p.81
