Bài Giảng về môn Trí Tuệ Nhân Tạo

Ệ

TRÍ TU NHÂN T O Ạ Artificial Intelligence (AI)

N i Dung

ộ

i thi uTTNT

ớ

 Ch  Ch  Ch

c dùng cho

ấ

ế ượ ạ

Tìm ki m heuristic

ng 4.

 Ch

ng 1 . Gi ươ ệ ng 2. Phép tính v tị ừ ươ ng 3. C u trúc và chi n l ươ tìm ki m trên không gian tr ng thái (TK- ế KGTT) ươ

ế

NG I ƯƠ

GI

I THI U V TRÍ TU NHÂN T O

Ớ

Ạ

Ệ

L ch s hình thành và phát tri n c a trí tu nhân

ể ủ

ử

ệ

ị t o ạ

CH Ề

ạ

ệ ủ

ế s ự

t .

Trí Tu Nhân T o là gì?  Là m t ngành c a khoa h c máy tính liên quan đ n ọ ộ ự ộ

 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 ộ ệ ừ ệ ộ ơ ế ệ ủ

C.1 – Gi

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? ớ

ằ i thi u ệ

i: đ ng hóa các hành vi thông minh Trí tu là gì? ệ ư ỏ

Turing Test

Interrogator

C.1 – Gi

i thi u

ớ

ệ

 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ứ

ệ

– Lo i tr đ nh ki n thiên v c a ng ế ị ủ ườ i th m v n ấ ẩ

ả ệ

i quy t v n đ b ng ký ạ ừ ị  Các ý ki n ph n đ i ố ế ị ề ằ ế ấ ụ ả

ộ ự ể

ớ ớ ạ

- Thiên v các nhi m v gi hi uệ - Trói bu c s thông minh máy tính theo ki u con ng i, trong khi con ng ườ ườ + B nh gi i h n ộ + Có khuynh h ướ ắ

ấ

ng nh m l 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 ự ự ề ơ ở ng trình TTNT hi n đ i. cho các ch

ươ

ệ

ạ

i có:

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

ớ

ệ

M t s t ng k t v TTNT

ộ ố ổ

ế ề

 S d ng máy tính vào nh ng

suy lu n trên các ký hi u, nh n

ữ

ậ

ệ

ậ

…

ẫ

ọ

ậ  T p trung vào các v n đ “khó”

không thích h p v i các l

ợ

ớ

ờ

ử ụ d ng qua m u, h c, và các suy lu n khác ạ ấ ậ gi ả

ậ

ề . i mang tính thu t toán  Quan tâm đ n các k thu t gi

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 xác hay

ủ ố ch không ph i là l

ứ

ả

i quy t v n đ s d ng ế ấ ầ ủ ơ ồ… ờ

ả

ố ượ

ứ

 S d ng nh ng kh i l ữ i quy t v n đ . ế ấ

. ề Đây là c s cho các h chuyên gia

ệ

ng l n tri th c chuyên ngành trong ớ ơ ở tri th c c p meta đ tăng thêm s tinh vi cho vi c ự ể ứ ấ i quy t v n đ . c gi ki m soát các chi n l ề ế ấ ả

ế ượ

 Cho l ờ i uố ư . t ử ụ ả  S d ng ử ụ ể  …

C.1 – Gi

i thi u

ớ

ệ

Nh ng v n đ ch a đ

c gi

ề ư ượ

ữ

ấ

ả

i quy t ế

ư ự

ượ

 Ch sinh ra đ  Ch a có kh năng x lý song song c a con ử

ng trình ch a t ả

c heuristic ủ

i m t v n đ theo

ả

ễ

ươ

ộ ấ ư

ề ườ

 Ch a có kh năng x lý thông tin trong mô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 = Bi u Di n + tìm ki m ễ

ế

ể

TTNT »

bi u di n và tìm ki m

ể

ễ

ế

ư

ễ

TTNT nh là s bi u di n và tìm ự ể ki mế

ự ể

ự ộ ệ

ữ ệ nhiên đ th hi n tri ể ầ ủ => Tính bi u ể

ả : S bi u di n ph i ễ • Cung c p m t c c u t ể ơ ấ ấ th c/thông tin/ d li u m t cách đ y đ ộ ứ đ tạ

• H tr vi c th c thi m t cách hi u qu vi c tìm ki m

ỗ ợ ệ ả ệ ệ ộ

=> Tính hi u quệ ế ả ự ộ ấ

đá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 gi i gi i không? i t i u không?

ệ ế ắ ắ

TTNT »

bi u di n và tìm ki m

ễ

ế

ể

ắ ẽ ắ ẽ 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

ế

ể

ễ

KGTT c a Trò Ch i Tic-Tac-Toe

ủ

ơ

Ch n đoán tr c tr c máy móc trong ô tô ặ

ụ

ẩ

Ch

ng 2 – Logic hình th c ứ

ươ  Logic hình th cứ

ứ ễ ễ

– Logic hình th c = Bi u di n + suy lu n ậ – Logic hình th c nh là m t c ch bi u di n tri ộ ơ ế ễ ứ ư ễ

th cứ

– Logic hình th c nh là tìm ki m không gian tr ng ế ạ

ứ thái trong các đ th And/Or ư ồ ị

– Logic hình th c đ hình th c hóa các lu t heuristic ứ ể ứ ậ

 Có hai ngôn ngữ: – Phép tính m nh đ – Phép tính v tị ừ

ệ ề

Phép tính m nh đ (1)

ề

ệ

ề là m t câu kh ng đ nh có th đúng (true) ị ể ẳ ộ

ho c sai (false).

 M nh đ : ệ ặ  Ví dụ:

ồ ỗ

Đúng Sai Sai

ạ => => =>

ứ

ệ

Đ 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 đ : ề ệ P, Q, R, S,... true, false (cid:217) (h i), ộ (cid:218) (tuy n), ể

(cid:216)

(ph đ nh), ủ ị

ng đ

ng)

(cid:222)

– Ký hi u m nh đ : ề ệ – Ký hi u chân lý: ệ – Các phép toán logic: (kéo theo) , = (t ươ

ươ

Phép tính m nh đ (2)

ệ

ề

ệ

ệ ủ ị

), t

 Đ nh nghĩa câu trong phép tính m nh đ : ệ ề ị – M i ký hi u m nh đ (P, Q, …) là m t câu. ộ ề ệ ỗ – Ký hi u chân lý (true, false) là m t câu. ộ (cid:216) P ) – Ph đ nh c a m t câu là m t câu. ( ộ ộ ủ – H i (ộ (cid:217) ), tuy n (ể (cid:218) ), kéo theo ((cid:222) ng đ ươ

ươ

ng (=) c a hai câu ủ

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)

là m t câu. ộ  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 ụ

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 or s di n gi

i

ự ễ

ị ự – Là s ự gán giá tr chân lý

ả (Intepretation): (T / F) cho các câu m nh ệ

ị

đ .ề

ng đ

ượ

ự

ườ

xác đ nh b ng

ị

ị ằ

– Là m t s kh ng đ nh chân lý c a các câu m nh đ . ề ộ ự ẳ ủ ệ ị

 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

P(cid:217) Q P(cid:218) Q P(cid:222) Q P=Q T F F

Q T F T

P T T F

T T T

T F F

T F 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)  Lu t t ậ ươ  Lu t De Morgan:

(cid:222) Q) = ((cid:216) Q (cid:222) (cid:216) P) ng ph n: (P ả

(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), ậ ố

P (cid:217) (Q (cid:218) R) = (P (cid:217) Q) (cid:218) (P (cid:217) R)

Phép TínhV T (1) ồ

ị ừ ữ

ợ

ấ

ữ ố .

_ ), và đ

ệ ị ừ là t p h p g m các ch cái, ch s hay d u ậ c ượ b t đ u b ng ch cái ố

ắ ầ ằ

ữ

 Ký hi u v t

 Ký hi u v t g ch n i ( ạ VD: X3, tom_and_jerry có th là: ể

ộ

ế ớ

ệ

ằ

ị ừ ệ

– ký hi u chân lý ệ : true, false – H ngằ : dùng đ ch m t đ i t ể ỉ ộ ố ượ ữ th • Ký hi u b t đ u b ng ch ắ ầ

ngườ :

ng / thu c

ng / thu c tính trong th gi VD: helen, yellow, rain ộ

ố ượ

– Bi nế : dùng đ ch m t l p t ng quát các đ i t ể ỉ ộ ớ ổ

tính.

VD: X, People,

• Ký hi u b t đ u b ng ch ắ ầ

ệ

ằ

ữ HOA

Students

ể ỉ ộ

ệ

– Hàm: dùng đ ch m t hàm trên các đ i t ằ

ữ th

ỗ

ng. ố ượ VD: father, plus ng các đ i s c a hàm ố ố ủ ệ ữ

ặ

ngườ : ỉ ố ượ – V tị ừ: dùng đ đ nh nghĩa m t m i quan h gi a không ho c ố ộ

nhi u đ i t

ề

VD: likes, equals,

• Ký hi u b t đ u b ng ch ắ ầ • M i ký hi u hàm có n ngôi ,ch s l ệ ể ị ng. b t đ u b ng ch ị ừ ắ ầ

ằ

ữ th

ngườ .

ố ượ • Ký hi u v t ệ part_of

 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 đ ơ ấ

ể

expression), nguyên t

c g i là: bi u th c s c p (atomic ứ ơ ấ ượ ọ (atom) hay m nh đ (proposition) ệ ử

ề

VD: friends(helen, marry).

likes(hellen, mary).

likes(helen, sister(mary)).

likes( X, ice-cream).

Ký hi u v t

trong các câu này là

friends, likes.

ệ ị ừ

: 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 d ng:

ơ ấ ử ụ

ượ ạ

 Câu: đ

ế ợ , (cid:217) , (cid:218) , (cid:222)

, =

: dùng đ ch m t câu là đúng v i m i giá tr ị

ể ỉ ộ

ớ

ọ

ể ỉ ộ

ộ ố

ớ

: dùng đ ch m t câu là đúng v i m t s giá tr ị ng giá.

ằ : (cid:216) – Các phép k t n i logic ế ố – Các l ử ế : bi n ng t ượ ử ổ ế " • L ph bi n ng t ượ ng giá c a bi n l ế ượ ủ ử ồ ạ $ • L ng t i t n t ượ nào đó c a bi n l ế ượ ủ

VD: (m i đ a tr đ u thích Chocolat)

ẻ ề

ọ ứ " X, thich(dua_tre(X), chocolat).

i b n)

ườ ạ

(tom có không ít h n m t ng ộ - $ Y, friends(Y, tom).

Ng Nghĩa c a Phép Tính V T

ị ừ

ủ

ữ

 S thông d ch

ị ự ả ợ

i) c a m t t p h p các ộ ậ ể ự

ệ

ề

ế

ằ

ỗ

: ề ậ

c xác đ nh qua s ự

ượ

(cách di n gi ễ ủ câu phép tính v t ị ừ là m t s gán các th c th trong mi n ề ộ ự c a v n đ đang đ c p cho m i ký hi u h ng, bi n, v t ị ừ ủ ấ và hàm.

ị ơ ấ

 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.

X là true n u là T cho t ế ể ượ

i m t phép gán

– Giá tr c a câu ị ủ

ế ồ ạ

ộ

cho X làm cho có giá tr T.

X là true n u t n t ị

Phép Tính V T B c Nh t ấ

ị ừ ậ

ế

ề ậ

ế ư

 Phép tính v t đ n các đ i t ế ố ượ KHÔNG đ

b c nh t ị ừ ậ

ị ừ

ượ

ế

ề và hàm.

ấ cho phép các bi n tham chi u ng trong mi n c a v n đ đang đ c p nh ng ề ủ ấ c tham chi u đ n các v t

(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(tomorrow, rain) (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)

" (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

C2 – Phép tính v tị ừ

Các lu t suy di n

ễ

ậ  Lu t Modus Ponens

ậ

 Lu t Modus Tolens

ậ

(MP): P (cid:222) P Q (MT): P (cid:222) (cid:216) Q (cid:216) P

 Lu t tri n khai ph bi n

ổ ế (Universal

ể

ậ

Instantiation):

ủ ề ị

" X P(X) a thu c mi n xác đ nh c a X ộ P(a)

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)

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 ế

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) ớ

ế

ớ

ố

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:

ế

ượ

man(X) => mortal(X) N u ta th X b i socrates thì ta đ ở ế man(socrates) => mortal(socrates)

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 : ấ ớ

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) )

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}

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 ấ ợ ử ổ

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 ườ

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)

investment(stocks)

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)

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)

C2 – Phép tính v tị ừ

(cid:222)

ng 2

Bài T p Ch ậ

ươ

Ch

ế

ấ

ươ l

c cho TK - KGTT

ng 3 - C u trúc và chi n ượ

ễ ộ ấ ộ ồ ị ề ư

ể ạ

ể ử ụ ộ ứ ạ ủ

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. ề

ủ ụ ư ế

Riverbank 1

i2

4

2

3 i1

1 Island 2

Island 1

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

ế

ạ

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

search with iterative deepening) ử ụ lu n v i phép tính v t ớ ậ Graph) ế

ạ

Đ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

c a đ th . ủ ồ ị

ộ ạ

 A (arc) là t p các

ậ

cung (hay các liên k tế ) gi a các nút.

ữ

 S (solution) là m t t p ch a các

tr ng thái ban đ u

ộ ậ

ứ

ầ c a bài toán

ủ

ạ

 GD (Goal Description) là m t t p ch a các

ạ

c a ủ

ứ theo m t trong hai đ c tính:

c mô t

tr ng thái đích ặ

ộ ậ ộ

ả

ượ

bài toán và đ – Đ c tính có th đo l

ng đ

c các tr ng thái g p trong quá trình tìm

ể

ườ

ượ

ạ

ặ

ki m. VD: Tic-tac-toe, 8-puzzle,…

ặ ế

– Đ c tính c a đ

ng đi đ

c hình thành trong quá trình tìm ki m. VD:

ủ ườ

ượ

ế

ặ TSP

i gi

i

ng đi qua

ộ

 Đ ng đi c a l ủ ờ ả (solution path) là m t con đ ườ ườ đ th này t m t nút thu c S đ n m t nút thu c GD. ế ừ ộ ồ ị

ộ

C 3 – Tìm ki m không gian tr ng thái

ế

ạ

ầ

ộ

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

ế

ạ

ố

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

ế

ạ

ủ

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

ế

ạ

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

ế

ạ

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

ế

ạ

Các Chi n L

c cho TK-KGTT

ế

ượ

d li u (Data-driven Search)

 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

ế

ạ

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

ế

ạ

ụ

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

ế

ạ

ợ ể ư ề

Các ph

ươ

ng pháp tìm ki m trên đ ồ

ế

th KGTT:

ị

i thu t quay lui

ậ

ể ừ ả

(back – tracking)

gi ộ (breath-first search) (depth-first search)

Phát tri n t  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

ằ

ề ầ (depth-first

search with iterative deepening)

C 3 – Tìm ki m không gian tr ng thái

ế

ạ

Tìm Ki m R ng ế

ộ

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

ế

ạ

Tìm ki m Sâu ế

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

ế

ạ

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

tr ng thái m c tiêu. ầ ư

ờ

ả hay ch là l

ỉ

ờ

ấ ả c đ u tiên.

 Yêu c u đ a ra t i tìm đ ượ ầ

ả

C 3 – Tìm ki m không gian tr ng thái

ế

ạ

ằ

ế

ề

 Đ 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

ế

ạ

đ 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

ế

ạ

Đ 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. ế ủ ễ ậ

ế

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: ớ

ệ

ề

ố

 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

ế

ạ

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 ể

Đ 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)

ễ

ng 3

Bài T p Ch ậ

ươ

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 ữ ệ ờ ứ ẵ

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: ế ậ

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 đ ủ ố

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 ụ

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

ụ

ỏ

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 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 ạ ệ

ư ậ

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]

Đánh giá O2;

open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] i gi

7. Đánh giá P3; tìm đ

c l ượ ờ

ả

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.

ụ

g(n) = 0

goal

g(n) = 1

h(n): s l

ố ượ

ng các v trí còn sai ị

6

f(n) =

6

4

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 ạ

ủ

ụ

ố

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 ỏ

ạ

đ 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ơ

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 ượ ự

ả

ậ

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 ể ủ ố ạ

ộ

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).

ừ

C 4 – Tìm ki m Heuristic ế

-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 . ể ắ ỏ ố ạ ớ

gi a các nút cây có g c t C 4 – Tìm ki m Heuristic ế

nào.  Gi ả ữ

C t t a ắ ỉ S

MAX =

a ≥ a

A MIN Z =

a a - cut

C 4 – Tìm ki m Heuristic ế

= z z ≤ a

C t t a ắ ỉ S

MIN =

b ≤ b

A MAX Z =

b b - cut

C 4 – Tìm ki m Heuristic ế

= z z ≥ b

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

C 4 – Tìm ki m Heuristic ế