Chương I - Các chiến lược tìm kiếm mù pdf

http://blogthuthuat.com

Mục lục

Ph n I : Gi i quy t v n đ b ng tìm ki m ầ ả ế ấ ề ằ ế

1.1 Ch ng I - Các chi n l c tìm ki m mù ươ ế ượ ế

1.1 Bi u di n v n đ trong không gian tr ng thái ể ễ ấ ề ạ

1.2 Các chi n l c tìm ki m ế ượ ế

1.3 Các chi n l c tìm ki m mù ế ượ ế

1.3.1 Tìm ki m theo b r ng ế ề ộ

1.3.2 Tìm ki m theo sâu ế độ

1.3.3 Các tr ng thái l p ạ ặ

1.3.4 Tìm ki m sâu l p ế ặ

1.4 Quy v n v các v n con. Tìm ki m trên th v /ho c ấ đề ề ấ đề ế đồ ị à ặ

1.4.1 Quy v n v các v n con ấ đề ề ấ đề

1.4.2 th v /ho c Đồ ị à ặ

1.4.3 Tìm ki m trên th v /ho c ế đồ ị à ặ

Ch ng II - Các chi n l c tìm ki m kinh nghi m ươ ế ượ ế ệ

2.1 H m ánh giá v tìm ki m kinh nghi m à đ à ế ệ

2.2 Tìm ki m t t nh t - u tiên ế ố ấ đầ

2.3 Tìm ki m leo i ế đồ

2.4 Tìm ki m beam ế

1.2 Ch ng III - Các chi n l c tìm ki m t i u ươ ế ượ ế ố ư

3.1 Tìm ng i ng n nh t đườ đ ắ ấ

3.1.1 Thu t toán A* ậ

3.1.2 Thu t toán tìm ki m Nhánh-v -C n ậ ế à ậ

1.2.1 3.2 Tìm i t ng t t nh t đố ượ ố ấ

1.2.1.1 3.2.1 Tìm ki m leo i ế đồ

3.2.2 Tìm ki m gradient ế

3.2.3 Tìm ki m mô ph ng luy n kim ế ỏ ệ

1.2.2 3.3 Tìm ki m mô ph ng s ti n hóa. Thu t toán di truy n ế ỏ ự ế ậ ề

1.3 Ch ng IV - Tìm ki m có i th ươ ế đố ủ

4.1 Cây trò ch i v tìm ki m trên cây trò ch i ơ à ế ơ

4.2 Chi n l c Minimax ế ượ

4.3 Ph ng pháp c t c t Alpha-Beta ươ ắ ụ

Ph n II: Tri th c v l p lu n ầ ứ à ậ ậ

Đinh Mạnh Tường Trang 1

http://blogthuthuat.com

Đinh Mạnh Tường Trang 2

Đ ạ ườ inh M nh T ng

Giáo trình

Trí tu Nhân t o ệ ạ

Khoa CNTT - i H c Qu c Gia H N i Đạ ọ ố à ộ

http://blogthuthuat.com

Ph n I ầ

Gi i quy t v n đ b ng tìm ki m ả ế ấ ề ằ ế

-----------------------------------

V n tìm ki m, m t cách t ng quát, có th hi u l tìm m t i t ng th a mãn ấ đề ế ộ ổ ể ể à ộ đố ượ ỏ

m t s òi h i n o ó, trong m t t p h p r ng l n các i t ng. Chúng ta có th k ra ộ ố đ ỏ à đ ộ ậ ợ ộ ớ đố ượ ể ể

r t nhi u v n m vi c gi i quy t nó c quy v v n tìm ki m. ấ ề ấ đề à ệ ả ế đượ ề ấ đề ế

Các trò ch i, ch ng h n c vua, c carô có th xem nh v n tìm ki m. Trong s ơ ẳ ạ ờ ờ ể ư ấ đề ế ố

r t nhi u n c i c phép th c hi n, ta ph i tìm ra các n c i d n t i tình th k t ấ ề ướ đ đượ ự ệ ả ướ đ ẫ ớ ế ế

cu c m ta l ng i th ng. ộ à à ườ ắ

Ch ng minh nh lý c ng có th xem nh v n tìm ki m. Cho m t t p các tiên ứ đị ũ ể ư ấ đề ế ộ ậ

đề à ậ ễ ườ ợ à ụ ủ à ộ ứ v các lu t suy di n, trong tr ng h p n y m c tiêu c a ta l tìm ra m t ch ng minh

(m t dãy các lu t suy di n c áp d ng) c a n công th c m ta c n ch ng ộ ậ ễ đượ ụ để đượ đư đế ứ à ầ ứ

minh.

Trong các l nh v c nghiên c u c a ĩ ự ứ ủ Trí Tu Nhân T o ệ ạ , chúng ta th ng xuyên ườ

ph i i u v i v n tìm ki m. c bi t trong l p k ho ch v h c máy, tìm ki m ả đố đầ ớ ấ đề ế Đặ ệ ậ ế ạ à ọ ế

đ ọ óng vai trò quan tr ng.

Trong ph n n y chúng ta s nghiên c u các k thu t tìm ki m c b n c áp ầ à ẽ ứ ỹ ậ ế ơ ả đượ

d ng gi i quy t các v n v c áp d ng r ng rãi trong các l nh v c nghiên c u ụ để ả ế ấ đề à đượ ụ ộ ĩ ự ứ

khác c a ủ Trí Tu Nhân T o ệ ạ . Chúng ta l n l t nghiên c u các k thu t sau: ầ ượ ứ ỹ ậ

• Các k thu t tìm ki m mù, trong ó chúng ta không có hi u bi t gì v các i ỹ ậ ế đ ể ế ề đố

t ng h ng d n tìm ki m m ch n thu n l xem xét theo m t h th ng n o ó t t ượ để ướ ẫ ế à ỉ đơ ầ à ộ ệ ố à đ ấ

c các i t ng phát hi n ra i t ng c n tìm. ả đố ượ để ệ đố ượ ầ

• Các k thu t tìm ki m kinh nghi m (tìm ki m heuristic) trong ó chúng ta d a ỹ ậ ế ệ ế đ ự

v o kinh nghi m v s hi u bi t c a chúng ta v v n c n gi i quy t xây d ng nên à ệ à ự ể ế ủ ề ấ đề ầ ả ế để ự

h m ánh giá h ng d n s tìm ki m. à đ ướ ẫ ự ế

• Các k thu t tìm ki m t i u. ỹ ậ ế ố ư

• Các ph ng pháp tìm ki m có i th , t c l các chi n l c tìm ki m n c i ươ ế đố ủ ứ à ế ượ ế ướ đ

trong các trò ch i hai ng i, ch ng h n c vua, c t ng, c carô. ơ ườ ẳ ạ ờ ờ ướ ờ

Đinh Mạnh Tường Trang 3

http://blogthuthuat.com

Ch ng I ươ

Các chi n l c tìm ki m mù ế ượ ế

---------------------------------

Trong ch ng n y, chúng tôi s nghiên c u các chi n l c tìm ki m mù (blind ươ à ẽ ứ ế ượ ế

search): tìm ki m theo b r ng (breadth-first search) v tìm ki m theo sâu (depth- ế ề ộ à ế độ

first search). Hi u qu c a các ph ng pháp tìm ki m n y c ng s c ánh giá. ệ ả ủ ươ ế à ũ ẽ đượ đ

1.4 Bi u di n v n trong không gian tr ng thái ể ễ ấ đề ạ

M t khi chúng ta mu n gi i quy t m t v n n o ó b ng tìm ki m, u tiên ta ộ ố ả ế ộ ấ đề à đ ằ ế đầ

ph i xác nh không gian tìm ki m. ả đị ế Không gian tìm ki m bao g m t t c các i t ng ế ồ ấ ả đố ượ

m ta c n quan tâm tìm ki m. Nó có th l không gian liên t c, ch ng h n không gian à ầ ế ể à ụ ẳ ạ

các véct th c n chi u; nó c ng có th l không gian các i t ng r i r c. ơ ự ề ũ ể à đố ượ ờ ạ

Trong m c n y ta s xét vi c bi u di n m t v n trong không gian tr ng thái ụ à ẽ ệ ể ễ ộ ấ đề ạ

sao cho vi c gi i quy t v n c quy v vi c tìm ki m trong không gian tr ng thái. ệ ả ế ấ đề đượ ề ệ ế ạ

M t ph m vi r ng l n các v n , c bi t các câu , các trò ch i, có th mô t ộ ạ ộ ớ ấ đề đặ ệ đố ơ ể ả

b ng cách s d ng khái ni m tr ng thái v toán t (phép bi n i tr ng thái). Ch ng ằ ử ụ ệ ạ à ử ế đổ ạ ẳ

h n, m t khách du l ch có trong tay b n m ng l i giao thông n i các th nh ph trong ạ ộ ị ả đồ ạ ướ ố à ố

m t vùng lãnh th (hình 1.1), du khách ang th nh ph A v anh ta mu n tìm ng ộ ổ đ ở à ố à ố đườ

đ ớ ă à ố à à à ố ả đồ à i t i th m th nh ph B. Trong b i toán n y, các th nh ph có trong các b n l các

tr ng thái, th nh ph A l tr ng thái ban u, B l tr ng thái k t thúc. Khi ang m t ạ à ố à ạ đầ à ạ ế đ ở ộ

th nh ph , ch ng h n th nh ph D anh ta có th i theo các con ng n i t i các à ố ẳ ạ ở à ố ể đ đườ để ố ớ

th nh ph C, F v G. Các con ng n i các th nh ph s c bi u di n b i các toán t . à ố à đườ ố à ố ẽđượ ể ễ ở ử

M t toán t bi n i m t tr ng thái th nh m t tr ng thái khác. Ch ng h n, tr ng thái ộ ử ế đổ ộ ạ à ộ ạ ẳ ạ ở ạ

D s có ba toán t d n tr ng thái D t i các tr ng thái C, F v G. V n c a du khách ẽ ử ẫ ạ ớ ạ à ấ đề ủ

bây gi s l tìm m t dãy toán t a tr ng thái ban u A t i tr ng thái k t thúc B. ờ ẽ à ộ ửđểđư ạ đầ ớ ạ ế

M t ví d khác, trong trò ch i c vua, m i cách b trí các quân trên b n c l ộ ụ ơ ờ ỗ ố à ờ à

m t tr ng thái. Tr ng thái ban u l s s p x p các quân lúc b t u cu c ch i. M i ộ ạ ạ đầ à ự ắ ế ắ đầ ộ ơ ỗ

n c i h p l l m t toán t , nó bi n i m t c nh hu ng trên b n c th nh m t c nh ướ đ ợ ệ à ộ ử ế đổ ộ ả ố à ờ à ộ ả

hu ng khác. ố

Nh v y mu n bi u di n m t v n trong không gian tr ng thái, ta c n xác nh ư ậ ố ể ễ ộ ấ đề ạ ầ đị

các y u t sau: ế ố

• Tr ng thái ban u. ạ đầ

• M t t p h p các toán t . Trong ó m i toán t mô t m t h nh ng ho c m t ộ ậ ợ ử đ ỗ ử ả ộ à độ ặ ộ

phép bi n i có th a m t tr ng thái t i m t tr ng thái khác. ế đổ ểđư ộ ạ ớ ộ ạ

T p h p t t c các tr ng thái có th t t i t tr ng thái ban u b ng cách áp ậ ợ ấ ả ạ ể đạ ớ ừ ạ đầ ằ

d ng m t dãy toán t , l p th nh không gian tr ng thái c a v n . ụ ộ ử ậ à ạ ủ ấ đề

Ta s ký hi u không gian tr ng thái l U, tr ng thái ban u l u ẽ ệ ạ à ạ đầ à 0 (u0 ∈ U). M i ỗ

toán t R có th xem nh m t ánh x R: U ử ể ư ộ ạ →U. Nói chung R l m t ánh x không xác à ộ ạ

đị ắ ơ nh kh p n i trên U.

• M t t p h p T các tr ng thái k t thúc (tr ng thái ích). T l t p con c a không ộ ậ ợ ạ ế ạ đ à ậ ủ

gian U. Trong v n c a du khách trên, ch có m t tr ng thái ích, ó l th nh ph B. ấ đề ủ ỉ ộ ạ đ đ à à ố

Nh ng trong nhi u v n (ch ng h n các lo i c ) có th có nhi u tr ng thái ích v ta ư ề ấ đề ẳ ạ ạ ờ ể ề ạ đ à

không th xác nh tr c c các tr ng thái ích. Nói chung trong ph n l n các v n ể đị ướ đượ ạ đ ầ ớ ấ

đề ỉ ể ả ạ đ à ạ ỏ ộ ố đ ề hay, ta ch có th mô t các tr ng thái ích l các tr ng thái th a mãn m t s i u

ki n n o ó. ệ à đ

Đinh Mạnh Tường Trang 4

http://blogthuthuat.com

Khi chúng ta bi u di n m t v n thông qua các tr ng thái v các toán t , thì ể ễ ộ ấ đề ạ à ử

vi c tìm nghi m c a b i toán c quy v vi c tìm ng i t tr ng thái ban u t i ệ ệ ủ à đượ ề ệ đườ đ ừ ạ đầ ớ

tr ng thái ích. (M t ng i trong không gian tr ng thái l m t dãy toán t d n m t ạ đ ộ đườ đ ạ à ộ ử ẫ ộ

tr ng thái t i m t tr ng thái khác). ạ ớ ộ ạ

Chúng ta có th bi u di n không gian tr ng thái b ng th nh h ng, trong ó ể ể ễ ạ ằ đồ ị đị ướ đ

m i nh c a th t ng ng v i m t tr ng thái. N u có toán t R bi n i tr ng thái u ỗ đỉ ủ đồ ị ươ ứ ớ ộ ạ ế ử ế đổ ạ

th nh tr ng thái v, thì có cung gán nhãn R i t nh u t i nh v. Khi ó m t ng i à ạ đ ừ đỉ ớ đỉ đ ộ đườ đ

trong không gian tr ng thái s l m t ng i trong th n y. ạ ẽ à ộ đườ đ đồ ị à

Sau ây chúng ta s xét m t s ví d v các không gian tr ng thái c xây d ng đ ẽ ộ ố ụ ề ạ đượ ự

cho m t s v n . ộ ố ấ đề

Ví d 1: ụ B i toán 8 s . Chúng ta có b ng 3x3 ô v tám quân mang s hi u t 1 à ố ả à ố ệ ừ

đế đượ ế à ạ ộ ố ẳ ạ ư n 8 c x p v o tám ô, còn l i m t ô tr ng, ch ng h n nh trong hình 2 bên trái.

Trong trò ch i n y, b n có th chuy n d ch các quân c ch ô tr ng t i ô tr ng ó. V n ơ à ạ ể ể ị ở ạ ố ớ ố đ ấ

đề ủ ạ à ộ ể ị để ế đổ ả ố đầ c a b n l tìm ra m t dãy các chuy n d ch bi n i c nh hu ng ban u (hình 1.2

bên trái) th nh m t c nh hu ng xác nh n o ó, ch ng h n c nh hu ng trong hình 1.2 à ộ ả ố đị à đ ẳ ạ ả ố

bên ph i. ả

Trong b i toán n y, tr ng thái ban u l c nh hu ng bên trái hình 1.2, còn à à ạ đầ à ả ố ở

tr ng thái k t thúc bên ph i hình 1.2. T ng ng v i các quy t c chuy n d ch các ạ ế ở ả ươ ứ ớ ắ ể ị

quân, ta có b n toán t : ố ử up ( y quân lên trên), đẩ down ( y quân xu ng d i), đẩ ố ướ left ( y đẩ

quân sang trái), right ( y quân sang ph i). Rõ r ng l , các toán t n y ch l các toán đẩ ả à à ử à ỉ à

t b ph n; ch ng h n, t tr ng thái ban u (hình 1.2 bên trái), ta ch có th áp d ng ử ộ ậ ẳ ạ ừ ạ đầ ỉ ể ụ

các toán t ửdown, left, right.

Trong các ví d trên vi c tìm ra m t bi u di n thích h p mô t các tr ng thái ụ ệ ộ ể ễ ợ để ả ạ

c a v n l khá d d ng v t nhiên. Song trong nhi u v n vi c tìm hi u c bi u ủ ấ đề à ễ à à ự ề ấ đề ệ ể đượ ể

di n thích h p cho các tr ng thái c a v n l ho n to n không n gi n. Vi c tìm ra ễ ợ ạ ủ ấ đề à à à đơ ả ệ

d ng bi u di n t t cho các tr ng thái óng vai trò h t s c quan tr ng trong quá trình ạ ể ễ ố ạ đ ế ứ ọ

Đinh Mạnh Tường Trang 5

http://blogthuthuat.com

gi i quy t m t v n . Có th nói r ng, n u ta tìm c d ng bi u di n t t cho các ả ế ộ ấ đề ể ằ ế đượ ạ ể ễ ố

tr ng thái c a v n , thì v n h u nh ã c gi i quy t. ạ ủ ấ đề ấ đề ầ ưđ đượ ả ế

Ví d 2 ụ : V n tri u phú v k c p. Có ba nh tri u phú v ba tên c p bên ấ đề ệ à ẻ ướ à ệ à ướ ở

b t ng n m t con sông, cùng m t chi c thuy n ch c m t ho c hai ng i. Hãy tìm ờ ả ạ ộ ộ ế ề ở đượ ộ ặ ườ

cách a m i ng i qua sông sao cho không l i bên b sông k c p nhi u h n đư ọ ườ để ạ ở ờ ẻ ướ ề ơ

tri u phú. ng nhiên trong b i toán n y, các toán t t ng ng v i các h nh ng ch ệ Đươ à à ử ươ ứ ớ à độ ở

1 ho c 2 ng i qua sông. Nh ng ây ta c n l u ý r ng, khi h nh ng x y ra (lúc ặ ườ ư ở đ ầ ư ằ à độ ẩ

thuy n ang b i qua sông) thì bên b sông thuy n v a d i ch , s k c p không ề đ ơ ở ờ ề ừ ờ ỗ ố ẻ ướ

đượ ề ơ ố ệ ế ầ ế đị à ạ ủ ấ đề c nhi u h n s tri u phú. Ti p theo ta c n quy t nh cái gì l tr ng thái c a v n .

ởđ ầ ệ à ệ à ướ à ỉ ố ượ ủ ọ ây ta không c n phân bi t các nh tri u phú v các tên c p, m ch s l ng c a h

ở ờ à ọ Để ể ễ ạ ử ụ ộ bên b sông l quan tr ng. bi u di n các tr ng thái, ta s d ng b ba (a, b, k),

trong ó a l s tri u phú, b l s k c p bên b t ng n v o các th i i m m đ à ố ệ à ố ẻ ướ ở ờ ả ạ à ờ đ ể à

thuy n b n y ho c b kia, k = 1 n u thuy n b t ng n v k = 0 n u thuy n b ề ở ờ à ặ ờ ế ề ở ờ ả ạ à ế ề ở ờ

h u ng n. Nh v y, không gian tr ng thái cho b i toán tri u phú v k c p c xác ữ ạ ư ậ ạ à ệ à ẻ ướ đượ

đị ư nh nh sau:

• Tr ng thái ban u l (3, 3, 1). ạ đầ à

• Các toán t . Có n m toán t t ng ng v i h nh ng thuy n ch qua sông 1 ử ă ử ươ ứ ớ à độ ề ở

tri u phú, ho c 1 k c p, ho c 2 tri u phú, ho c 2 k c p, ho c 1 tri u phú v 1 k ệ ặ ẻ ướ ặ ệ ặ ẻ ướ ặ ệ à ẻ

c p. ướ

• Tr ng thái k t thúc l (0, 0, 0). ạ ế à

1.5 Các chi n l c tìm ki m ế ượ ế

Nh ta ã th y trong m c 1.1, gi i quy t m t v n b ng tìm ki m trong ư đ ấ ụ để ả ế ộ ấ đề ằ ế

không gian tr ng thái, u tiên ta c n tìm d ng thích h p mô t các tr ng thái c u v n ạ đầ ầ ạ ợ ả ạ ả ấ

đề đ ầ đị . Sau ó c n xác nh:

• Tr ng thái ban u. ạ đầ

• T p các toán t . ậ ử

• T p T các tr ng thái k t thúc. (T có th không c xác nh c th g m các ậ ạ ế ể đượ đị ụ ể ồ

tr ng thái n o m ch c ch nh b i m t s i u ki n n o ó). ạ à à ỉ đượ ỉ đị ở ộ ố đ ề ệ à đ

Gi s u l m t tr ng thái n o ó v R l m t toán t bi n i u th nh v. Ta s g i ả ử à ộ ạ à đ à à ộ ử ế đổ à ẽ ọ

v l tr ng thái k u, ho c v c sinh ra t tr ng thái u b i toán t R. Quá trình áp d ng à ạ ề ặ đượ ừ ạ ở ử ụ

các toán t sinh ra các tr ng thái k u c g i l phát tri n tr ng thái u. Ch ng h n, ửđể ạ ề đượ ọ à ể ạ ẳ ạ

trong b i toán toán s , phát tri n tr ng thái ban u (hình 2 bên trái), ta nh n c ba à ố ể ạ đầ ậ đượ

tr ng thái k (hình 1.3). ạ ề

Khi chúng ta bi u di n m t v n c n gi i quy t thông qua các tr ng thái v các ể ễ ộ ấ đề ầ ả ế ạ à

toán t thì vi c tìm l i gi i c a v n c quy v vi c tìm ng i t tr ng thái ban ử ệ ờ ả ủ ấ đề đượ ề ệ đườ đ ừ ạ

đầ ớ ộ ạ ế à đ u t i m t tr ng thái k t thúc n o ó.

Có th phân các chi n l c tìm ki m th nh hai lo i: ể ế ượ ế à ạ

• Các chi n l c tìm ki m mù. Trong các chi n l c tìm ki m n y, không có m t ế ượ ế ế ượ ế à ộ

s h ng d n n o cho s tìm ki m, m ta ch phát tri n các tr ng thái ban u cho t i ự ướ ẫ à ự ế à ỉ ể ạ đầ ớ

khi g p m t tr ng thái ích n o ó. Có hai k thu t tìm ki m mù, ó l tìm ki m theo ặ ộ ạ đ à đ ỹ ậ ế đ à ế

b r ng v tìm ki m theo sâu. ề ộ à ế độ

Đinh Mạnh Tường Trang 6