Bài giảng học về Trí tuệ Nhân tạo

BÀI M Đ U

Ở Ầ

- Trí tu nhân t o là gì

ệ

ạ

- L i ích mà trí tu nhân t o mang l ệ

ợ

ạ

i ạ

c đ c p trong môn

ấ

ề ẽ ượ ề ậ

- Các v n đ s đ h cọ

1

Trí tu nhân t o là gì

ệ

ạ

ệ ữ

ộ

• Tr ừ

ươ

ằ

ươ t h n ng ơ ố ơ ả ể ọ ườ ể

• Thu t ng trí tu nhân t o (artificial intelligence) ạ ậ đ c John McCarthy đ a ra trong h i th o ả ở ư ượ Dartmouth mùa hè năm 1956 c h i th o này, t năm 1952 Arthur Samuel ả ộ ướ ng trình ch i c . Samuel đã bác b t ch đã vi ỏ ơ ờ ế t c ng cho r ng máy tính ch có th làm đ t ượ ể ỉ ư ưở ng trình nh ng cái mà ng i ta b o nó làm vì ch ờ ữ i c a Samuel có th h c đ ch i t ủ làm ra nó

2

i h i th o ả ở ạ ộ

ệ ớ

ậ ậ ọ

ứ ế ầ

lý Dartmouth mùa hè năm 1956, i thi u ng trình l p lu n v i tên g i “the logic theorist”. ng trình này có kh năng ch ng minh h u h t ng 2 cu n “Principia ị

•Cũng t Allen Newell và Herbert Simon cũng đã gi ch ớ ươ Ch ả ươ các đ nh trong ch ố ươ Mathematics” c a Russell và Whitehead ủ

ả

ứ ủ ả ự

ệ

ờ

•Cũng t i h i th o này các nhà nghiên c u đã th o ạ ộ lu n và v ch ra các h ng nghiên c u c a lĩnh v c ứ ướ ạ ậ i Dartmouth mùa trí tu nhân t o. Vì v y h i th o t ả ạ ộ ậ ạ c xem là th i đi m ra đ i th c s hè năm 1956 đ ự ự ể ượ ạ c a lĩnh v c nghiên c u trí tu nhân t o ủ ờ ệ ự ứ

3

ộ ố ị

ổ ế M t s đ nh nghĩa ph bi n

ệ ự ự ứ

ệ ử ụ

ệ

ứ ệ ự

ậ ạ ỏ ự ườ

i- Kurzweil, 1990 ứ ả

ỏ

+ S nghiên c u các năng l c trí tu thông qua vi c s d ng các mô hình tính toán – Charniak and McDormott, 1985 + Ngh thu t t o ra các máy th c hi n các ch c ệ ự c th c hi n năng đòi h i s thông minh khi đ ượ b i con ng ở i thích và mô + Lĩnh v c nghiên c u tìm cách gi ự ph ng các hành vi thông minh trong thu t ng ữ ậ các quá trình tính toán – Schalkoff, 1990

4

ứ ể ể ậ

ậ

ủ ọ

ự ự ộ

+ S nghiên c u các tính toán đ có th nh n ự th c, l p lu n và hành đ ng – Winston, 1992 ứ ậ ộ + M t nhánh c a khoa h c máy tính liên quan ộ đ n s t đ ng hoá các hành vi thông minh – ế Luger and Stubblfield, 1993

5

M t s đ nh nghĩa g n đây

ộ ố ị

ầ

ạ ệ ứ

ệ

ng t k và nghiên c u các ự ế ế ng trình máy tính ng x m t cách thông minh. ứ ử ộ c xây d ng đ th c hi n các ể ự ự ượ i ho c đ ng v t chúng ta xem là ặ ộ ng trình này đ ườ ở ậ

+ Trí tu nhân t o là s thi ch ươ Các ch ươ hành vi mà khi thông minh – Dean, Allen and Aloimonos, 1995

ệ ồ ạ ự ứ

i ạ ng nh n th c và hành đ ng, Rusell and ườ ậ ộ

+ Trí tu nhân t o là s nghiên c u các tác nhân t n t trong môi tr ứ Norvig, 1995

t k các tác ệ ế ế ứ ự ạ

+ Trí tu nhân t o là s nghiên c u thi nhân thông minh, Poole, Mackworth and Goebel, 1998

6

Tóm l

ươ ứ

c các hành vi thông minh i, trí tu nhân t o đ t m c tiêu làm th ệ ế ạ ặ ụ ạ nào th hi n đ c các hành vi thông minh ượ ể ệ b ng thu t toán, r i nghiên c u các ph ng ồ ậ ằ pháp cài đ t các ch ng trình có th th c hi n ệ ể ự ươ ặ đ ượ

7

L i ích mà trí tu nhân t o mang l ệ

ợ

ạ

i ạ

• Trí tu nhân t o ạ ệ • Trí tu th t ệ ậ

8

SO SÁNH VUI

+Chi phí s n xu t ấ ả rẻ r t đ t ấ ắ

+Th i gian làm vi c ệ ờ r t dài ấ r t ng n ắ ấ

+Chi phí v n hành ậ r t rấ ẻ quá đ tắ

??? +Hi u qu công vi c ệ ả ệ r t hi u qu ệ ấ ả

9

N i dung ch

ng trình

ộ

ươ

ả ế

+ Gi

ế ấ ậ

i quy t v n đ b ng tìm ki m ề ằ + Tri th c và l p lu n ậ ứ + M ng n ron nhân t o ạ ơ ạ + Logic mờ + Gi ậ ả i thu t di truy n ề

10

Ph n 1: Gi

i quy t v n đ b ng tìm

ầ

ả

ế ấ

ề ằ

ki mế

ng 1: Các chi n l

ế ượ

ề

ế ấ ế

ế

t c các đ i t

ố ượ ể ầ ặ ờ

c tìm ki m mù Ch ế ươ 1. Bi u di n v n đ trong không gian tr ng thái ạ ễ ấ ể i quy t v n đ b ng tìm ki m, đi u quan Đ gi ề ề ằ ể ả c không gian tìm ki m, tr ng là ph i xác đ nh đ ượ ọ ị ả ng mà ta c n không gian này là t ấ ả quan tâm tìm ki m, nó có th liên t c ho c r i ụ ế r cạ

11

Ví d 1: Xét bài toán tìm đ ụ ng đi trên b n đ giao ả ồ

ườ thông

ệ

+Ta quan ni m các nút A, B,.. là các tr ng thái ạ

ạ

ạ

+A tr ng thái đ u, B tr ng thái ầ k t thúc ế

ở ộ

ể

m t nút ta có th +Khi đang ể đi sang m t nút khác. Các con ộ ng n i 2 nút đ đ c bi u ườ ượ ố - Rõ ràng di n b i m t toán t ử ộ ở ễ bi n đ i tr ng thái này toán t ổ ạ ử ế thành tr ng thái khác ạ

ầ

ạ ế

ng đi lúc này +Bài toán tìm đ ườ tr thành tìm m t dãy các toán ộ ở đ đ a tr ng thái đ u thành t ử ể ư tr ng thái k t thúc ạ 12

Ví d 2: Xét trò ch i c vua ơ ờ ụ

ỗ

ờ

ệ ộ ạ

ầ ứ

ộ

ỗ ướ ố

ổ

ộ

+ Bài toán ch i c rõ ràng là tìm 1 dãy các toán t

c

(n ử ướ

đi) đ đ a tr ng thái ban đ u v tr ng thái k t thúc

+ Ta quan ni m m i cách b trí các quân c trên bàn c ờ ố cho ta m t tr ng thái. Tr ng thái ban đ u ng v i s s p ạ ớ ự ắ c đi h p x p các quân c lúc b t đ u cu c ch i. M i n ờ ế ợ ơ ắ ầ là m t toán t - nó bi n đ i m t tình hu ng trên bàn c l ờ ế ử ộ ệ thành m t tình hu ng khác ố ộ ơ ờ ạ

ầ ề ạ

ể ư

ế

13

ễ

ể ể

ộ ấ

ề

tr ng thái c n xác đ nh nh ng y u t

sau

ế ố

ữ

ạ

ầ

ị

Đ bi u di n m t v n đ trong không gian

ệ

ệ

+ Tr ng thái đ u, ký hi u là u ầ + T p tr ng thái k t thúc, ký hi u T, T có th có ể m t tr ng thái ho c nhi u tr ng thái – VD1,2 ề ợ ấ ả

ử ẽ ộ

ạ ế ạ ậ ặ ạ ộ ạ , t p h p t + T p các toán t t c các tr ng thái có ậ ạ ử ậ tr ng thái ban đ u b ng cách áp i t th đ t t ằ ầ ể ạ ớ ừ ạ d ng m t dãy các toán t s cho ta m t không ộ ụ gian tr ng thái, ký hi u là R ệ

ườ ữ ạ ợ

ể ể ộ ồ ị

ạ ng h p không gian tr ng thái là h u + Trong tr h n ta có th bi u di n b ng m t đ th có ằ ễ ạ ngướ h

14

Ví d v xây d ng không gian tr ng thái cho

ụ ề

ự

ạ

các v n đấ

ề

Ví d 1: Bài toán 8 s

ụ

ố

ơ ậ ố

c d ch các s vào ô tr ng ố ỉ ượ ị ị ộ ể ế ể

ế ạ ầ

Lu t ch i: Ch đ Yêu c u: Tìm ra m t dãy các d ch chuy n đ bi n ầ đ i tr ng thái đ u thành tr ng thái k t thúc ổ ạ 15

Không gian tr ng thái

ạ

: Up, Down, Left, Right • TTĐ: • TTKT: • T p các toán t ậ ử

16

Ví d 2: Xét bài toán tri u phú và k c

p ẻ ướ

ụ

ệ

Có 3 tri u phú và 3 tên c ộ

ế ỉ ở ượ

ườ ệ

p không đ p và m t chi c thuy n ề ở c m t ề ộ ộ i. Hãy tìm cách đ a 3 tri u phú sang ư c m i b sông s k c ố ẻ ướ ở ỗ ờ ượ

ướ ệ bên b t c a m t con sông, thuy n ch ch đ ờ ả ủ ho c hai ng ặ sông sao cho l n h n s tri u phú ơ ố ệ ớ

17

ố ộ ộ ể ể ạ

Dùng m t b 3 s (a,b,k) đ bi u di n các tr ng thái a - s tri u phú, b - s k c ố ệ k=1 thuy n đang , ng ề Không gian tr ng thái đ ễ p b t ố ẻ ướ ở ờ ả i k=0 c l ượ ạ c xác đ nh nh sau ị ượ b t ở ờ ả ạ

ư

TTĐ:(3,3,1) TTKT:(0,0,0) T p các toán t : ử

p ẻ ướ

bao g m các toán t ậ ồ ử p +Thuy n ch 1 k c ẻ ướ ở +Thuy n ch 1 tri u phú ệ ở +Thuy n ch 1 tri u phú, 1 k c ệ ở +Thuy n ch 2 k c p ở ẻ ướ +Thuy n ch 2 tri u phú ệ ở ề ề ề ề ề

18

2. Các chi n l

c tìm ki m

ế ượ

ế

ế ụ

ượ ử ề ủ Cho u là m t tr ng thái, n u áp d ng toán t ượ

ừ ở

ọ ượ ử ể

ế

i ta tr ng thái đ u, phát tri n nó ộ ạ thu đ c v thì v đ b i toán t R ho c v đ ặ ở ử trình áp d ng các toán t ụ k c a u đ ề ủ Thông th ườ R ta c g i là tr ng thái k c a u ạ u b i R – Quá c sinh t đ sinh ra các tr ng thái ạ c g i là quá trình phát tri n u ể i quy t bài toán ng ng đ gi ầ ườ ể

th cho đ n khi g p tr ng thái đích ượ ọ ườ ể ả ng xu t phát t ừ ạ ấ ạ ế ặ

19

ế

ế c này đ Có nhi u chi n l ề ế ượ

c tìm ki m nh tìm ki m mù, ư ế ượ tìm ki m kinh nghi m, các chi n l c ế ượ ệ hình dung nh sau: ư

+Chi n l ế

ế ể ẫ ầ ế ượ ự

ặ ạ

ế ậ ế

ế ể ự ế ủ ể

ạ ẽ ọ ể

ộ ạ

ượ ế ụ ố

ng d n c tìm ki m mù: Không có s h ự ướ nào cho s tìm ki m, ta ch phát tri n tr ng thái đ u ạ ỉ i khi g p tr ng thái đích, có 2 k thu t cho cho t ỹ ớ c này đó là tìm ki m r ng và tìm ki m sâu chi n l ộ ế ượ +Chi n l c tìm ki m kinh nghi m: Trong r t ượ ệ ấ ế t c a chúng nhi u v n đ ta có th d a vào hi u bi ề ấ ề ta v v n đ đó đ đánh giá các tr ng thái. Trong ể ề ề ấ quá trình phát tri n các tr ng thái ta s ch n 1 trong ạ s các tr ng thái ch phát tri n m t tr ng thái đ c ạ ố t nh t đ phát tri n,.. quá trình ti p t c đánh giá t cho t ặ ớ ể ờ ấ ể ể i khi g p tr ng thái đích ạ

20

2.1 Chi n l

ế ượ

ề ộ : c tìm ki m theo b r ng

ế

• T i m i b ỗ ướ ể ể

ạ ạ c ta ch n tr ng thái đ phát tri n là c các tr ng thái ch ờ ạ ọ c sinh ra tr ướ ạ

tr ng thái đ ượ phát tri n khác ể

ể ư ử ụ ượ

• S d ng danh sách L đ l u các tr ng thái đ ủ ể

ế ừ ạ ế ạ

ng đi t ầ ư ế ủ

ể ư ạ ng đi, father(v)=u n u u là cha c a v sinh ra và ch đ ờ ượ ki m là tìm đ ườ thái đích nên ta c n l u v t c a đ th dùng hàm father đ l u l ể trên đ ế c ạ c phát tri n, m c tiêu c a tìm ụ tr ng thái đ u đ n tr ng ầ ng đi, ta có ườ i cha c a m I đ nh ỗ ỉ ủ ủ ườ

21

ỉ ứ ạ

Procedure TimKiemRong begin 1. Kh i t o danh sách L ch ch a tr ng thái ban đ u ầ 2. 2.1 if L r ng then ở ạ loop do ỗ

ấ ạ

{thông báo tìm ki m th t b i; stop}; ế 2.2 Lo i tr ng thái u đ u danh sách L; ở ầ ạ ạ 2.3 if u là tr ng thái k t thúc then ế ạ {thông báo tìm ki m thành công; stop}; ế

2.4 for m i tr ng thái v k u do ỗ ạ ề

{đ t v vào cu i danh sách L; father(v)=u}; ặ ố

end;

22

ụ ạ

Ví d : Cho không gian tr ng thái TTĐ: A TTKT:H

23

Mô t quá trình tìm ki m ả ế

H

24

Nh n xét ậ

c sinh ra tr ượ

c, do đó danh sách L đ ướ c s ướ ẽ c ượ • Trong TKR tr ng thái nào đ ạ ể

• N u bài toán có nghi m (t n t i đ ạ ườ ệ ồ

ng đi t ậ

ượ

ầ ớ ạ ồ ấ ườ

ệ ạ

ẽ ừ ậ

c phát tri n tr đ ượ ợ x lý nh hàng đ i ư ử ừ ế i tr ng thái đích), thì thu t toán tr ng thái đ u t ạ c ng đi tìm đ s tìm ra nghi m, đ ng th i đ ờ ườ ệ ẽ ng h p bài toán ng đi ng n nh t, trong tr là đ ợ ườ ắ vô nghi m và không gian tr ng thái h u h n, ữ ạ thu t toán s d ng và thông báo vô nghi m ệ đánh giá • Đ ph c t p thu t toán: Sinh viên t ậ ộ ứ ạ ự

25

2.2 Chi n l

c tìm ki m theo đ sâu

ế ượ

ộ

ế

T i m i b ọ ạ ỗ ướ ể ể

ượ ạ ạ ạ

ế ề ế ỉ

c ta ch n tr ng thái đ phát tri n là c sinh ra sau cùng trong các tr ng tr ng thái đ thái ch phát tri n khác. Thu t toán tìm ki m sâu ể ờ s t nh tìm ki m r ng, ch có đi u danh ng t ư ự ẽ ươ c xây d ng nh m t ngăn x p sách L đ ế ượ ậ ộ ư ộ ự

26

ạ ỉ ứ

ỗ

{thông báo tìm ki m th t b i; stop}; ế

ấ ạ đ u danh sách L;

Procedure TimKiemSau begin 1. Kh i t o danh sách L ch ch a tr ng thái ban đ u ầ ở ạ 2. loop do 2.1 if L r ng then 2.2 Lo i tr ng thái u ạ ạ 2.3 if u là tr ng thái k t thúc then ạ

ở ầ ế {thông báo tìm ki m thành công; stop}; ế

2.4 for m i tr ng thái v k u do ỗ ạ ề

{đ t v vào đ u danh sách L; father(v)=u}; ặ ầ

end;

27

Xét ví d trên, k t qu c a quá trình tìm ki m sau ả ủ ụ ế ế

th hi n b ng sau ể ệ ở ả

28

ả ậ ậ ế

ệ ế

ệ ữ

ạ ườ ệ ợ

ạ ạ

ệ ế ộ ộ

ố ạ ậ ằ

Nh n xét: Thu t toán tìm ki m sâu không ph i lúc nào cũng tìm ra nghi m, n u bài toán có nghi m và không gian tr ng thái h u h n thì nó ạ ng h p luôn tìm ra nghi m, tuy nhiên trong tr không gian tr ng thái là vô h n thì nó có th ể không tìm ra nghi m, lý do là nó luôn đi xu ng theo đ sâu, và n u nó đi theo m t nhánh vô h n mà nghi m không n m trên nhánh đó thì thu t ệ toán s không d ng. ừ ẽ

29

ặ

ạ

ạ ỏ ạ

ạ

2.3 Tr ng thái l p và lo i b tr ng thái l pặ Xét đ th không gian tr ng thái ồ ị TTĐ: A, TTKT:G

30

ữ

i nó t ồ ị ng đi d n t

ượ ọ ẽ ặ

ạ ề ặ ữ ể ờ

ạ ồ ị ể ặ

Trong đ th này ta th y có nh ng đ nh có nhi u ề ỉ ấ đ tr ng thái ban đ u.Ví d ẫ ớ ườ ụ ầ ừ ạ c g i là các tr ng C, E, F – Các tr ng thái này đ ạ thái l p, quá trình tìm ki m s lãng phí r t nhi u ấ ế th i gian đ phát tri n nh ng tr ng thái đã g p ể t khi đ th có chu trình và đã phát tri n, đ c bi ệ quá trình tìm ki m s không d ng. ẽ ế

Vì v y trong quá trình tìm ki m tránh sinh ra các ậ ừ ế

tr ng thái mà ta đã phát tri n ể ạ

31

Ph

ng pháp

ươ

ớ

ỉ

ỉ

+Khi phát tri n đ nh u, không sinh ra các đ nh trùng v i cha u +Khi phát tri n đ nh u, không sinh ra các đ nh trùng v i m t ộ

ớ

ỉ

ỉ

ng đi d n t

ể ể ằ

c sinh ra, t c là ch ỉ

ứ

đ nh nào đó n m trên đ ườ ỉ ỉ

i u ượ

ỉ

ẫ ớ +Không sinh ra các đ nh mà nó đã đ sinh ra các đ nh m i ớ ầ

ả

ạ

c các tr ng thái l p. Đ th c hi n gi ặ

ệ

ả

ạ

ạ ạ

c sinh ra n u nó không n m trong v

i pháp đ u khá đ n gi n tuy nhiên không tránh h t Hai gi ế ơ ả i pháp th 3 ta s đ ẽ ứ ể ự ượ l u các tr ng thái đã sinh ra vào danh sách Q và các tr ng ư thái ch phát tri n vào danh sách L và đ ng nhiên tr ng ờ thái v l n đ u đ ầ

ể ầ ượ

ươ ằ

ế

32

ụ ể ệ ế

Xét ví d trên:Quá trình tìm ki m th hi n theo b ngả

33

ứ ế ế

ế theo đ sâu ta có th b m c k t

2.4 Tìm ki m sâu l p ặ ế N u cây tìm ki m ch a nhánh vô h n, khi tìm ki m ạ nhánh đó. ể ị ắ ẹ ở

ộ

34

ế ể ụ

ộ i tăng đ sâu lên d+1 và l ượ ế ộ ạ

Đ kh c ph c ta ch tìm ki m đ n đ sâu d nào đó, ỉ ắ i n u không tìm đ c ta l ạ ế tìm ki m theo đ sâu này. ộ c l p v i d=1..max. Khi ch n max đ ủ ớ ượ ặ đây ta xây d ng 2 th c nghi m - ủ ệ ượ ọ ự ở

ế Quá trình trên đ l n ta s tìm đ ẽ ớ t cụ

35

Tìm ki m sâu h n ch v i d=3 ạ ế ớ ế

36

Procedure TKSHC(d) Begin

0;

ứ ầ ỉ

1. Kh i t o danh sách L ch ch a TT ban đ u u ở ạ depth(u0)=0; 2. Loop do 2.1 if L r ng then ỗ

{Thông báo th t b i; stop}

ấ ạ đ u danh sách L ở ầ 2.2 Lo i tr ng thái u ạ ạ

ế

2.3 if u là tr ng thái k t thúc then ạ {Thông báo thành công; stop}

2.4 if depth(u)<=d then ỗ ạ

ề {Đ t v vào đ u danh sách L; depth(v)=depth(u)+1} for m i tr ng thái v k u do ầ ặ

37

end;

Procedure TKSL Begin For d=0 to max do { TKSHC(d);

if thành công then exit}

End;

38

ự ộ ồ ị

ng đi t

BÀI T PẬ + Xây d ng m t đ th không gian tr ng thái có ng đ sâu >3, không có chu trình. S d ng ph ươ ộ pháp tìm ki m sâu và tìm ki m r ng đ xác đ nh ị đ ườ

ạ ử ụ ế ể ộ i tr ng thái k t thúc ầ ớ ạ ế tr ng thái đ u t ừ ạ ế

ự

ử ụ

ế ể ị

+ Xây d ng m t đ th không gian tr ng thái có ạ ộ ồ ị đ sâu >3, có chu trình. S d ng ph ng pháp ươ ộ tìm ki m sâu h n ch đ xác đ nh đ ng đi t ừ ườ ế tr ng thái đ u t ạ i tr ng thái k t thúc ầ ớ ạ ế ạ

39

Ch

ng 2: Các chi n l

c tìm ki m

ươ

ế

ế ượ kinh nghi mệ

ế

ề ệ ể ử ụ

ệ ấ ứ ủ

ể

ủ ạ

3.1 Hàm đánh giá và tìm ki m kinh nghi m Trong nhi u v n đ ta có th s d ng kinh ề nghi m, tri th c c a chúng ta trong lĩnh v c bài ự toán đ đánh giá các tr ng thái c a bài toán. ạ Thông qua vi c đánh giá các tr ng thái ta có th ể i th c a các tr ng thái trong ạ ệ ứ ộ ợ ế ủ ị

xác đ nh m c đ l quá trình tìm ki mế

40

Ví d : Tìm đ ng đi t ụ ườ ừ A đ n B ế

ườ ả ử ứ

s ng ả i đi đang đ ng ắ

Gi ở A và ph i cân nh c xem đi đ n C, D hay E ế

ng chim bay t t đ

ơ

Bi ườ ế đ n B g n h n đ ế ầ D đ n B và t bay t ừ ế ườ ừ C ừ ng chim E đ n B ế

Ng ườ i đi s ch n ??? ẽ ọ

Câu tr l i: theo t ả ờ ự ẽ ọ

nhiên ng ườ C i đi s ch n cách đi sang 41

• Nh v y, kinh nghi m c a con ng i đã đ c ệ ở ủ ườ ượ

ư ậ s d ng ử ụ

• Tuy nhiên kinh nghi m sai có th d n ta đi ch ch ệ

h ệ ướ

ể ẫ ệ ng, do đó tìm ki m kém hi u qu ả ế • Trong bài toán tìm ki m, kinh nghi m đ ệ ượ

ệ ệ

ừ

ượ ụ ề ộ ố

c th ế ể hi n qua vi c xây d ng hàm đánh giá, tuỳ thu c ộ ự c xây vào t ng bài toán mà hàm đánh giá đ d ng khác nhau, sau đây là m t s ví d v xây ự d ng hàm đánh giá tr ng thái ự ạ

ng đi trên b n đ ồ ả ng chim bay VD1: Trong bài toán tìm đ ườ ộ ể ấ ườ

m t nút đ n nút đích làm giá tr hàm đánh giá giao thông, ta có th l y đ dài đ t ị ừ ộ ế

42

VD2: Bài toán 8 số

ớ ố

1(u) là s quân không 0)=4 ụ

+ Hàm h1: V i m i tr ng thái u thì h ỗ ạ n m đúng v trí c a nó trong tr ng thái đích, ví d h1(u ủ ằ ạ ị

ị ổ ữ ủ

ạ ủ ạ

đây kho ng cách đ ả ể ố

ặ ộ ể ư ị ủ

ụ ạ

ấ ầ ấ ị

43

+ Hàm h2: h2(u) là t ng kho ng cách gi a v trí c a các ả quân trong tr ng thái u và v trí c a nó trong tr ng thái ị đích. c hi u là s ít nh t các d ch ấ ượ Ở i v trí c a chuy n theo hàng ho c c t đ đ a m t quân t ớ ị ộ ể 0) = 1+1+1+2 = 5, vì nó trong tr ng thái đích, ví d h2(u quân 1, 2, 6 c n ít nh t 1 d ch chuy n, quân 8 c n ít nh t 2 ầ ể d ch chuy n ể ị

ế ệ

ế ượ ố

• Có hai chi n l c tìm ki m kinh nghi m đó là t nh t đ u tiên + Tìm ki m t ấ ầ ế = Tìm ki m theo b r ng + Hàm đánh giá ế ề ộ

+ Tìm ki m leo đ i ồ ế = Tìm ki m theo đ sâu + Hàm đánh giá ộ ế

44

TÌM KI M T T NH T Đ U TIÊN Ố Ầ Ấ Ế

• Là tìm ki m theo b r ng đ c h ề ộ ế ượ ướ ng d n b i ẫ ở

t: ể

hàm đánh giá • Đi m khác bi + Trong tìm ki m theo b r ng ta l n l

m c hi n t ề ộ ệ ạ ể t phát ầ ượ i đ sinh ra các đ nh ỉ ỉ

ệ ế tri n các đ nh ở ứ ở ứ ế

ế

ể m c ti p theo + Trong tìm ki m t ể ỉ ỉ ở ị

ấ ỏ ỉ

ấ ầ t nh t đ ấ ượ ị m c hi n t i ho c m c trên t nh t đ u tiên, ta ch n đ nh đ ể ọ ố phát tri n là đ nh t c xác đ nh b i hàm ố đánh giá (đ nh có giá tr hàm đánh giá nh nh t), đ nh này có th ỉ ể ở ứ ệ ạ ứ ặ

45

ụ ạ

Ví d : Cho đ th không gian tr ng thái v i TTĐ A, TTKTB, giá tr đánh giá tr ng thái ghi t ạ ớ i m i nút ỗ ồ ị ị ạ

46

ế ế ậ ỹ ố t nh t đ u ấ ầ

Quá trình tìm ki m b ng k thu t tìm ki m t ằ tiên

47

ạ ỉ ứ

ở ạ loop do ỗ

{thông báo tìm ki m th t b i; stop}; ế ấ ạ

đ u danh sách L;

Procedure TimKiemTotNhatDauTien begin 1. Kh i t o danh sách L ch ch a tr ng thái ban đ u ầ 2. 2.1 if L r ng then 2.2 Lo i tr ng thái u ạ ạ 2.3 if u là tr ng thái k t thúc then ạ

ở ầ ế {thông báo tìm ki m thành công; stop}; ế

2.4 for m i tr ng thái v k u do ỗ ạ ề

c s p theo ượ ắ

Xen v vào danh sách L sao cho L đ tăng d n c a hàm đánh giá; ầ ủ ứ ự

th t end;

48

TÌM KI M LEO Đ I Ồ Ế

Tìm ki m leo đ i là tìm ki m theo đ sâu đ c ế ồ ộ ượ

h ế ẫ

ng d n b i hàm đánh giá ướ ể ở ớ ộ

ế ể

ỉ ề ủ ọ ẹ

ứ c xác đ nh b i hàm đánh giá ở ị

ể ề ỹ ư

Đi m khác v i tìm ki m theo đ sâu là khi ta phát ế c ti p theo ta ch n trong s tri n m t đ nh u thì b ố ướ ộ ỉ các đ nh con c a u, đ nh có nhi u h a h n nh t đ ỉ ấ ể phát tri n, đ nh này đ ượ ử ụ ể ỉ ậ ờ

ộ ử ụ ề ủ ể ờ

ứ ự ủ

t nh t k u đ ng đ u danh sách L V k thu t ta s d ng m t danh sách L l u các tr ng thái ch phát tri n, s d ng danh sách L1 đ ể ạ l u t m th i các tr ng thái k c a u khi phát tri n u. ạ ư ạ Danh sách L1 đ tăng d n c a c s p theo th t ắ ầ ượ c chuy n vào danh sách L sao hàm đánh giá r i đ ồ ượ cho tr ng thái t ố ạ ể ứ ở ầ ấ ề

49

Cho đ ồ th ị không gian tr ng ạ thái, TTĐ: A TTKT: B

Quá trình tìm ki m theo PP leo đ i ồ ế

50

ạ ỉ ứ

ở ạ loop do ỗ

{thông báo tìm ki m th t b i; stop}; ế ấ ạ

đ u danh sách L;

Procedure TimKiemLeoDoi begin 1. Kh i t o danh sách L ch ch a tr ng thái ban đ u ầ 2. 2.1 if L r ng then 2.2 Lo i tr ng thái u ạ ạ 2.3 if u là tr ng thái k t thúc then ạ

ở ầ ế {thông báo tìm ki m thành công; stop}; ế

2.4 for m i tr ng thái v k u do ỗ ạ ề

Xen v vào danh sách L1 sao cho L1 đ ượ c s p ắ

ầ ủ

51

tăng d n c a hàm đánh giá; ứ ự ể ầ

theo th t 2.5 Chuy n danh sách L1 vào đ u danh sách L end;