L i nói đ uờ ầ
Trong các năm qua, nhi u tài li u c a ngành công ngh thông tin đã đ cề ệ ủ ệ ượ
gi i thi u nhi u cho các cán b nghiên c u, ng d ng và sinh viên b cớ ệ ề ộ ứ ứ ụ ở ậ
đ i h c. Tuy nhiên các giáo trình c a ngành h c này ch a đáp ng d c nhuạ ọ ủ ọ ư ứ ượ
c u c a sinh viên các tr ng đ i h c, đ c bi t đ i v i sinh viên khu v cầ ủ ườ ạ ọ ặ ệ ố ớ ự
mi n Trung. ề
Vì v y, chúng tôi biên so n giáo trình “Trí tu nhân t o”, m t môn c sậ ạ ệ ạ ộ ơ ở
chuyên ngành trong ch ng trình đào t o C nhân Tin h c, ngoài m c đíchươ ạ ử ọ ụ
xây d ng nhi u giáo trình trên m t khung ch ng trình đào t o, mà còn giúpự ề ộ ươ ạ
cho sinh viên có tài li u h c t p phù h p v i hoàn c nh th c t c a Đ iệ ọ ậ ợ ớ ả ự ế ủ ạ
h c Hu .ọ ế
Trong cu n sách này, sinh viên đ c làm quen v i m t s ki n th c c b nố ượ ớ ộ ố ế ứ ơ ả
nh t v các ph ng pháp tìm ki m l i gi i và các ph ng pháp x lý triấ ề ươ ế ờ ả ươ ử
th c. Ngoài ra, cu n sách cũng gi i thi u m t s ch ng trình cài đ t,ứ ố ớ ệ ộ ố ươ ặ
nh m giúp sinh viên có th hi u m t cách t ng t n các gi i thu t, đ ngằ ể ể ộ ườ ậ ả ậ ồ
th i tin t ng r ng các gi i thu t này có th áp dung th c t và cài đ tờ ưở ằ ả ậ ể ự ế ặ
đ c trên máy tính m t cách d dàng.ượ ộ ễ
Các n i dung trình bày trong cu n sách đã t ng đ c gi ng cho sinh viênộ ố ừ ượ ả
ngành Công ngh Thông tin t i Đ i h c Hu trong nh ng năm v a qua.ệ ạ ạ ọ ế ữ ừ
Cu n sách ra đ i d i s giúp đ v m t v t ch t cũng nh tinh th n c aố ờ ướ ự ỡ ề ặ ậ ấ ư ầ ủ
Đ i h c Hu , Tr ng Đ i h c Khoa h c và đ c bi t là Ban ch nhi mạ ọ ế ườ ạ ọ ọ ặ ệ ủ ệ
Khoa Công ngh Thông tin và các đ ng nghi p thu c B môn Khoa h cệ ồ ệ ộ ộ ọ
Máy tính. Chúng tôi xin g i t i h lòng bi t n. Xin chân thành cám n cácử ớ ọ ế ơ ơ
b n bè đã c cũ và gíup cho cu n sách s m đ c hoàn thành.ạ ổ ố ớ ượ
M c dù đã h t s c c g ng, tuy nhiên cu n sách cũng không tránh kh iặ ế ứ ố ắ ố ỏ
nh ng thi u sót. Chúng tôi r t mong đ c s góp ý c a các đ c gi , đ cữ ế ấ ượ ự ủ ộ ả ặ
bi t đ i v i các đ ng nghi p và sinh viên đ cu n sách ngày càng hoànệ ố ớ ồ ệ ể ố
thi n.ệ
Hu , tháng 7 năm 2004ế
Tác giả
Tài li u tham kh oệ ả
1. B ch H ng Khang, Hoàng Ki mạ ư ế
Trí tu nhân t o: Các ph ng pháp và ng d ng. Nhà xu t b n Khoaệ ạ ươ ứ ụ ấ ả
h c và K thu t, 1989.ọ ỹ ậ
2. Đinh M nh T ngạ ườ
Giáo trình Trí tu nhân t o, Đ i h c Qu c gia Hà n i.ệ ạ ạ ọ ố ộ
3. Nguy n Thanh Thuễ ỷ
Trí tu nhân t o: Các ph ng pháp gi i quy t v n đ và k thu t x lýệ ạ ươ ả ế ấ ề ỹ ậ ử
tri th c. Nhà xu t b n Giáo d c, 1996.ứ ấ ả ụ
4. N. Nilson
Artificial Intelligence. Ed. McGrawhill, 1971
5. Patrick Henry Winston
Artificial Intelligence. Ed. Addison Wesley, 1992.
.
M c l cụ ụ
Ch ng 0. M đ uươ ở ầ 2
1. T ng quan v Khoa h c Trí ru nhân t oổ ề ọ ệ ạ 2
2. L ch s phát tri n c a Trí tu nhân t oị ử ể ủ ệ ạ 5
3. M t s v n đ Trí tu nhân t o quan tâmộ ố ấ ề ệ ạ 8
4. Các khái niêm c b nơ ả 10
Ch ng 1. Bi u di n bài toán trong không gian tr ng tháiươ ể ễ ạ 12
1. Đ t v n đặ ấ ề 12
2. Mô t tr ng tháiả ạ
12
3. Toán t chuy n tr ng tháiử ể ạ 14
4. Không gian tr ng thái c a bài toánạ ủ 17
5. Bi u di n không gian tr ng thái d i d ng đ thể ễ ạ ướ ạ ồ ị
18
6. Bài t pậ21
Ch ng 2. ươ
Các ph ng pháp tìm ki m l i gi i trong không gian tr ng thái ươ ế ờ ả ạ 23
1. Ph ng pháp tìm ki m theo chi u r ngươ ế ề ộ 23
2. Ph ng pháp tìm ki m theo chi u sâuươ ế ề 30
3. Ph ng pháp tìm ki m sâu d nươ ế ầ 34
4. Ph ng pháp tìm ki m t t nh t đ u tiênươ ế ố ấ ầ 36
5. Tìm ki m đ ng đi có giá thành c c ti u - Thu t toán ATế ườ ự ể ậ 39
6. Tìm ki m c c ti u s d ng hàm đánh giá - Thu t toán A*ế ự ể ử ụ ậ 43
7. Ph ng pháp tìm ki m leo đ iươ ế ồ 46
8. Ph ng pháp sinh và thươ ử 49
9. Ph ng pháp tho mãn ràng bu cươ ả ộ 51
10. Cài đ t m t s gi i thu t.ặ ộ ố ả ậ 53
11. Bài t pậ72
Ch ng 3ươ
Phân rã bài toán – Tìm ki m l i gi i trên đ th Và/Ho cế ờ ả ồ ị ặ 90
1. Đ t v n đặ ấ ề 90
2. Đ th Và/Ho cồ ị ặ 92
3. Các ph ng pháp tìm ki m l i gi i trên đ th Và/Ho cươ ế ờ ả ồ ị ặ 94
4. Cây tìm ki m và các đ u thế ấ ủ
104
Ch ng 4. ươ
Bi u di n bài toán b ng logic và các ph ng pháp ch ng minhể ễ ằ ươ ứ 107
1. Bi u di n v n đ h logic hình th cể ễ ấ ề ờ ứ
108
2. M t s gi i thu t ch ng minhộ ố ả ậ ứ
130
3. Ví d và bài t pụ ậ 138
Ch ng 5. Tri th c và các ph ng pháp suy di nươ ứ ươ ễ 148
1. Tri th c và d li uứ ữ ệ 148
2. Các d ng mô t tri th cạ ả ứ 149
3. Suy di n trên lu t s n xu tễ ậ ả ấ 152
Tài li u tham kh oệ ả 163
Đ I H C HUẠ Ọ Ế
TR NG Đ I H C KHOA H CƯỜ Ạ Ọ Ọ
Giáo trình
TRÍ TU NHÂN T OỆ Ạ