›
›

Bài giảng Trí tuệ nhân tạo

ppt 234 trang ngocly 2190
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_tri_tue_nhan_tao_chuong_1_den_4.ppt

Nội dung text: Bài giảng Trí tuệ nhân tạo

  1. TRÍ TUỆ NHÂN TẠO Khoa Công nghệ Thông tin Trường Đại học Kinh tế Kỹ thuật công nghiệp 1
  2. NỘI DUNG ▪ TỔNG QUAN VỀ KHOA HỌC TTNT ▪ CÁC PHƯƠNG PHÁP BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ ▪ NGÔN NGỮ TTNT PROLOG 2
  3. TÀI LIỆU THAM KHẢO 1. 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 (1999) Nguyễn Thanh Thuỷ 2. Lập trình lôgic trong Prolog (2004) Phan Huy Khánh 3. Artificial Intelligence: A Modern Approach (2nd edition, 2002) Stuart Russell & Peter Norvig 3
  4. KHỐI LƯỢNG & CẤU TRÚC HỌC PHẦN ▪ Số tín chỉ: 2 ▪ Lý thuyết: 26 tiết ▪ Thực hành, bài tập: 10 tiết 4
  5. TỔNG QUAN VỀ KHOA HỌC TTNT 5
  6. NỘI DUNG ▪ CÁC KHÁI NIỆM CƠ BẢN ▪ CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT ▪ LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ CÁC THÀNH TỰU CỦA KHOA HỌC TTNT ▪ CÁC XU HƯỚNG MỚI TRONG TTNT 6
  7. CÁC KHÁI NIỆM CƠ BẢN: TTNT là gì? ▪ Trí tuệ nhân tạo là khoa học liên quan đến việc làm cho máy tính có những khả năng của trí tuệ con người, tiêu biểu như các khả năng“suy nghĩ”, “hiểu ngôn ngữ”, và biết “học tập”. 7
  8. CÁC KHÁI NIỆM CƠ BẢN: TTNT là gì? ▪ Intelligence: trí thông minh “ability to learn, understand and think” (Oxford dictionary) ▪ Artificial Intelligence (AI): trí thông minh nhân tạo “attempts to understand intelligent entities” “strives to build intelligent entities” (Stuart Russell & Peter Norvig) 8
  9. CÁC KHÁI NIỆM CƠ BẢN: TTNT là gì? 9
  10. CÁC KHÁI NIỆM CƠ BẢN: TTNT và lập trình truyền thống 10
  11. CÁC KHÁI NIỆM CƠ BẢN: Các yêu cầu của TTNT Thinking humanly Thinking rationally (Suy nghĩ như con người) (Suy nghĩ hợp lý) Acting humanly Acting rationally (Hành động như con người) (Hành động hợp lý) 11
  12. CÁC KHÁI NIỆM CƠ BẢN: Hành động như con người:Phép thử Turing ▪ Alan Turing (1912-1954) ▪ “Computing Machinery and Intelligence” (1950) Phép thử Người Người kiểm tra Hệ thống TTNT 12
  13. CÁC KHÁI NIỆM CƠ BẢN: Hành động như con người ▪ Chỉ ra các lĩnh vực cần nghiên cứu trong AI: ▪ Xử lý ngôn ngữ tự nhiên: để giao tiếp ▪ Biểu diễn tri thức: để lưu trữ và phục hồi các thông tin được cung cấp trước/trong quá trình thẩm vấn ▪ Suy diễn tự động: để sử dụng các thông tin đã được lưu trữ trả lời các câu hỏi và đưa ra các kết luận mới ▪ Học máy: thích nghi với các tình huống mới, phát hiện và suy ra các mẫu 13
  14. CÁC KHÁI NIỆM CƠ BẢN: Suy nghĩ như con người: Mô hình nhận thức ▪ Con người suy nghĩ ntn ? ▪ Nhờ tâm lý học, khoa học nhận thức. ▪ Người thuộc trường phái này, yêu cầu: ▪ Chương trình chẳng những giải đúng ▪ Còn so sánh từng bước giải với sự giải của 1 người. ▪ VD: General Problem Solver (GPS), Newell & Simon. 14
  15. CÁC KHÁI NIỆM CƠ BẢN: Suy nghĩ có lý: Luật của suy nghĩ ▪ Aristole: ~420 BC. ▪ Tiến trình suy nghĩ đúng là gì? ▪ Mở ra nhánh: quá trình suy luận. ▪ VD: “Socrates is a man, all men are mortal; therefore Socrates is mortal” ▪ Theo sau Aristole -> 20th: ▪ Logic hình thức (formal logic) ra đời. ▪ Hình thức hoá về mặt ký hiệu và quá trình suy diễn với các đối tượng trong thế giới tự nhiên. 15
  16. CÁC KHÁI NIỆM CƠ BẢN: Hành động có lý ▪ Hành động có lý ~ hành động để đạt được mục tiêu. ▪ Ưu thế: ▪ Tổng quát hơn luật suy nghĩ: Xử lý thông tin không chắc chắn 16
  17. CÁC KHÁI NIỆM CƠ BẢN: Các phương pháp và kỹ thuật ▪ Các phương pháp biểu diễn tri thức và kỹ thuật xử lý tri thức ▪ Các phương pháp giải quyết vấn đề ▪ Các phương pháp Heuristic ▪ Các phương pháp học ▪ Các ngôn ngữ TTNT 17
  18. CÁC KHÁI NIỆM CƠ BẢN: Các thành phần trong hệ thống ▪ Hai thành phần cơ bản: ▪ Các phương pháp biểu diễn vấn đề, các phương pháp biểu diễn tri thức ▪ Các phương pháp tìm kiếm trong không gian bài toán, các chiến lược suy diễn 18
  19. NỘI DUNG ▪ CÁC KHÁI NIỆM CƠ BẢN ▪ CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT ▪ LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ CÁC THÀNH TỰU CỦA KHOA HỌC TTNT ▪ CÁC XU HƯỚNG MỚI TRONG TTNT 19
  20. CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT TTNT kế thừa nhiều ý tưởng, quan điểm và các kỹ thuật từ các ngành khoa học khác Nghiên cứu tâm trí con người Các lý thuyết của lập luận và học TTNT Ngôn ngữ học Toán học Nghiên cứu ý nghĩa và Các lý thuyết xác suất logic, cấu trúc của ngôn ngữ Khoa học tạo quyết định và tính toán máy tính Làm cho TTNT trở thành hiện thực 20
  21. NỘI DUNG ▪ CÁC KHÁI NIỆM CƠ BẢN ▪ CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT ▪ LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ CÁC THÀNH TỰU CỦA KHOA HỌC TTNT ▪ CÁC XU HƯỚNG MỚI TRONG TTNT 21
  22. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ Bắt đầu của AI (1943 - 1956): ▪ 1943: McCulloch & Pitts: Mô hình chuyển mạch logic. ▪ 1950: Bài báo “Computing Machinery and Intelligence” của Turing. ▪ 1956: McCarthy đề xuất tên gọi “Artificial Intelligence”. 22
  23. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ “birth day”: Hội nghị ở Dartmouth College mùa hè 1956, do Minsky và McCarthy tổ chức, và ở đây McCarthy đề xuất tên gọi “artificial intelligence”. Có Simon và Newell trong những người tham dự. Marvin Minsky John McCarthy 23
  24. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ Trông mong nhất (1952 - 1969): ▪ Một số chương trình TTNT thành công: ▪ Samuel’s checkers ▪ Newell & Simon’s Logic Theorist ▪ Gelernter’s Geometry Theorem Prover. ▪ Thuật giải của Robinson cho lập luận logic. 24
  25. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ Thực tế (1966 − 1974): ▪ Phát hiện được các khó khăn về độ phức tạp tính toán. ▪ Quyến sách của Minsky & Papert năm 1969. ▪ Hệ thống dựa trên tri thức (1969 − 1979): ▪ 1969: DENDRAL by Buchanan et al. Đưa ra cấu trúc phân tử từ thông tin của quang phổ kế ▪ 1976: MYCIN by Shortliffle. Chuẩn đoán nhiểm trùng máu ▪ 1979: PROSPECTOR by Duda et al. Chuẩn đoán vị trí khoan dầu 25
  26. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ TTNT trở thành ngành công nghiệp (1980 - 1988): ▪ Bùng nổ về các hệ chuyên gia. ▪ 1981: Đề án máy tính thế hệ thứ năm của Nhật Bản. ▪ Sự trở lại của các mạng nơron và lý thuyết TTNT (1986 - nay) 26
  27. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT 27
  28. NỘI DUNG ▪ CÁC KHÁI NIỆM CƠ BẢN ▪ CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT ▪ LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ CÁC THÀNH TỰU CỦA KHOA HỌC TTNT ▪ CÁC XU HƯỚNG MỚI TRONG TTNT 28
  29. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 29
  30. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 30
  31. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 31
  32. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT SONY AIBO 32
  33. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT Đi bộ Quay Honda Humanoid Robot & Asimo Lên xuống cầu thang 33
  34. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 34
  35. CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 35
  36. NỘI DUNG ▪ CÁC KHÁI NIỆM CƠ BẢN ▪ CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT ▪ LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT ▪ CÁC THÀNH TỰU CỦA KHOA HỌC TTNT ▪ CÁC XU HƯỚNG MỚI TRONG TTNT 36
  37. CÁC XU HƯỚNG MỚI TRONG TTNT 37
  38. CÁC XU HƯỚNG MỚI TRONG TTNT 38
  39. CÁC XU HƯỚNG MỚI TRONG TTNT 39
  40. CÁC XU HƯỚNG MỚI TRONG TTNT 40
  41. CÁC XU HƯỚNG MỚI TRONG TTNT 41
  42. CÁC XU HƯỚNG MỚI TRONG TTNT 42
  43. CÁC XU HƯỚNG MỚI TRONG TTNT 43
  44. CÁC XU HƯỚNG MỚI TRONG TTNT 44
  45. CÁC XU HƯỚNG MỚI TRONG TTNT 45
  46. CÁC XU HƯỚNG MỚI TRONG TTNT 46
  47. CÁC XU HƯỚNG MỚI TRONG TTNT 47
  48. CÁC XU HƯỚNG MỚI TRONG TTNT 48
  49. CÁC XU HƯỚNG MỚI TRONG TTNT 49
  50. CÁC XU HƯỚNG MỚI TRONG TTNT 50
  51. CÁC XU HƯỚNG MỚI TRONG TTNT 51
  52. CÁC XU HƯỚNG MỚI TRONG TTNT 52
  53. Một số chủ đề nghiên cứu ▪ Giải thuật di truyền và ứng dụng ▪ Mạng Nơron nhân tạo và ứng dụng ▪ Công nghệ tác tử và ứng dụng ▪ KDD và ứng dụng ▪ Phân lớp - học có thầy ▪ Lý thuyết tập thô ▪ Cây quyết định ▪ ▪ Phân cụm - học không có thầy ▪ Luật kết hợp ▪ ▪ . . . 53
  54. CÁC PHƯƠNG PHÁP BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ 54
  55. NỘI DUNG ▪ BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT ▪ CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀ ▪ CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ 55
  56. BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT ▪ Giải quyết vấn đề và khoa học TTNT ▪ Giải quyết vấn đề của con người ▪ Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề ▪ Các thành phần cơ bản trong hệ thống giải quyết vấn đề 56
  57. Giải quyết vấn đề và khoa học TTNT ▪ Hoạt động trí tuệ: vận dụng các kỹ thuật giải quyết vấn đề ▪ Giải quyết vấn đề: tìm kiếm trong không gian các lời giải bộ phận có thể có được. ▪ Phương pháp biểu diễn vấn đề => Phương pháp giải quyết vấn đề. ▪ VD: Biểu diễn bằng logic vị từ => Phương pháp hợp giải ▪ VD: Biểu diễn bằng mạng ngữ nghĩa => Các thủ tục tìm kiếm 57
  58. Giải quyết vấn đề và khoa học TTNT ▪ Giải quyết vấn đề: duyệt-tìm kiếm trong không gian lời giải => bùng nổ tổ hợp => các thủ tục tìm kiếm Heuristic ▪ Phân chia các hệ thống TTNT: ▪ Các hệ tìm kiếm thông tin, các hệ hỏi đáp thông minh ▪ Các hệ suy diễn – tính toán: dựa vào các mô hình toán học và tri thức chuyên gia ▪ Các hệ chuyên gia 58
  59. Giải quyết vấn đề và khoa học TTNT Bµi to¸n (VÊn ®Ò) Ph¸t biÓu bµi to¸n-X¸c ®Þnh ph¬ng ph¸p bd bµi to¸n S¶n sinh kh«ng gian bµi to¸n C«ng nghÖ X¸c ®Þnh lêi § lËp tr×nh gi¶i nhê c¸c Bµi to¸n cã thÓ gi¶i nhê thuËt to¸n ®a thøc truyÒn ng«n ng÷ lËp thèng tr×nh S X¸c ®Þnh c¸c tri thøc ®Æc biÖt ®Ó rót gän kh«ng gian TK X©y dùng c¸c ph¬ng ph¸p biÓu diÔn tri thøc vµ suy diÔn C«ng nghÖ xö lý tri thøc Lùa chän ng«n ng÷, c«ng cô phï hîp C¸c hÖ gi¶i quyÕt vÊn ®Ò dùa vµo tri thøc Sơ đồ: Những khía cạnh khác nhau của TTNT 59
  60. Giải quyết vấn đề của con người ▪ Cách giải quyết vấn đề của con người là mô hình thực tiễn quan trọng để các chuyên gia TTNT tìm cách mô phỏng lại trên máy tính quá trình giải quyết bài toán. ▪ Khoa học về nhận thức: Nghiên cứu quá trình tổ chức, lưu trữ, truy nhập, xử lý và thu nạp tri thức trong bộ não người. ▪ Tâm lý học nhận thức và khoa học điều khiển: Tạo ra các mô hình tổ chức bộ não. 60
  61. Giải quyết vấn đề của con người ▪ Quá trình xử lý thông tin của con người KÝch HÖ thèng thô c¶m HÖ thèng nhËn thøc HÖ thèng hµnh ®éng Tr¶ thÝch C¬ quan Bé nhí Bé nhí dµi h¹n Bé nhí C¬ quan lêi thô c¶m ®Öm Bé nhí lµm viÖc ®Öm hµnh ®éng Bé xö lý nhËn thøc hÖ thèng xö lý th«ng tin cña con ngêi 61
  62. Giải quyết vấn đề của con người ▪ Giải quyết vấn đề của con người là một trường hợp riêng của quá trình xử lý thông tin trong bộ não. Đó là việc tìm cách đi từ tình huống ban đầu nào đó đến đích. Giải quyết vấn đề là một hoạt động đặc biệt của hệ thần kinh cần tới quá trình suy nghĩ, tìm kiếm trong không gian lời giải bộ phận để đi đến lời giải cuối cùng. ▪ Tuy nhiên, cần lưu ý rằng không phải mọi hoạt động xử lý thông tin đều là giải quyết vấn đề. 62
  63. Giải quyết vấn đề của con người Các chiến lược giải quyết vấn đề: ▪ Ước lượng mức độ phức tạp của vấn đề đặt ra: ▪ Nếu đơn giản, giải quyết vấn đề nhờ vào một thuật toán tiền định nào đó với các thao tác cơ sở. ▪ Nếu phức tạp, các cơ quan não tìm cách hiểu chi tiết nội dung của vấn đề để mã hoá, tìm phương pháp phù hợp. ▪ Nới lỏng một vài ràng buộc của bài toán. 63
  64. Giải quyết vấn đề của con người Các chiến lược giải quyết vấn đề: ▪ Phương pháp thử - sai: Xuất phát từ tình huống ban đầu, người ta đưa ra các tình huống mới, sau đó so sánh với các ràng buộc để tìm ra các lời giải hợp lý. ▪ Phương pháp chia bài toán thành các bài toán con: Từ bài toán phức tạp, con người chia thành các bài toán nhỏ, ít phức tạp cho đến khi gặp các bài toán sơ cấp, giải quyết được ngay. ▪ Tổng quát hoá bài toán : Chuyển các thông tin bên ngoài thành các kí hiệu làm cho bài toán dễ giải hơn. Quá trình này tạo ra một mô hình trí tuệ của bài toán, mô hình này thường được gọi không gian bài toán. 64
  65. Giải quyết vấn đề của con người Không gian bài toán bao gồm: ▪ Các dạng mẫu ký hiệu, mỗi dạng biểu diễn một trạng thái hay một tình huống bài toán. ▪ Các mối liên kết giữa các dạng mẫu ký hiệu, mỗi mối liên kết tương ứng với các phép biến đổi từ dạng này sang dạng khác. 65
  66. Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề ▪ Bài toán 1: Bài toán trò chơi n2-1 số (n N, n>2). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 66
  67. Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề ▪ Bài toán 2: Bài toán Tháp Hà nội 1 1 2 2 3 3 A B C A B C 67
  68. Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề Phân loại vấn đề: ▪ Vấn đề (bài toán) phát biểu chỉnh (well-formed problems): Là các bài toán có thể biết được hình trạng đầu, hình trạng đích và có thể quyết định khi nào vấn đề được coi là giải quyết xong. Các bài toán 1 - 2 là những vấn đề được phát biểu chỉnh. ▪ Vấn đề (bài toán) phát biểu không chỉnh (ill-formed problems): Là các vấn đề được phát biểu chưa đầy đủ, thiếu dữ kiện. Các bài toán chẩn đoán và điều trị bệnh, bài toán xác định chất lượng sản phẩm là các bài toán phát biểu không chỉnh. 68
  69. Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề ▪ Các đặc trưng cơ bản của vấn đề ▪ Bài toán có thể phân tích thành các bài toán dễ giải hơn không? ▪ Các bước giải của bài toán có thể bỏ qua hay huỷ bỏ hay không? ▪ Không gian bài toán có thể đoán trước hay không? ▪ Có tiêu chuẩn để xác định lời giải nào đó là tốt đối với bài toán không? ▪ Có cần tri thức để giải quyết bài toán hay điều khiển quá trình tìm kiếm không? ▪ Cơ sở tri thức để giải quyết bài toán có nhất quán với nội dung không? ▪ Có cần tương tác người máy trong quá trình giải quyết không? 69
  70. Các thành phần cơ bản trong hệ thống giải quyết vấn đề ▪ Giải quyết vấn đề: Biểu diễn bài toán và tìm kiếm lời giải trong không gian bài toán ▪ Hệ thống giải quyết vấn đề: Bµi to¸n D÷ liÖu + Tri thøc Gi¶i thuËt ChiÕn l•îc Kü thuËt Kü thuËt C¬ së C¬ së t×m kiÕm ®iÒu khiÓn Heuristic suy diÔn tri thøc d÷ liÖu HÖ thèng gi¶i quyÕt vÊn ®Ò 70
  71. NỘI DUNG ▪ BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT ▪ CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀ ▪ CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ 71
  72. CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀ ▪ Phương pháp biểu diễn nhờ không gian trạng thái ▪ Phương pháp qui bài toán về các bài toán con ▪ Phương pháp biểu diễn vấn đề nhờ logic hình thức ▪ Lựa chọn phương pháp biểu diễn thích hợp ▪ Biểu diễn vấn đề trong máy tính ▪ Biểu diễn tri thức và giải quyết vấn đề 72
  73. Phương pháp biểu diễn nhờ KGTT ▪ Trạng thái (State) là hình trạng của bài toán ▪ Toán tử (Operator) là các phép biến đổi từ trạng thái này sang trạng thái khác ▪ Hình trạng đầu, hình trạng cuối của bài toán được gọi là trạng thái đầu, trạng thái cuối ▪ Tập tất cả các trạng thái được sinh ra do xuất phát từ trạng thái đầu và áp dụng các toán tử được gọi là không gian trạng thái (state space). 73
  74. Phương pháp biểu diễn nhờ KGTT ▪ Mét c¸ch biÓu diÔn trùc quan ®èi víi kh«ng gian tr¹ng th¸i vµ c¸c to¸n tö lµ sö dông ®å thÞ, trong ®ã, c¸c ®Ønh cña ®å thÞ t¬ng øng víi c¸c tr¹ng th¸i cßn c¸c cung t¬ng øng víi c¸c to¸n tö ▪ VD: Bài toán trò chơi n2-1 số (n N, n>2) ▪ n = 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 74
  75. Phương pháp biểu diễn nhờ KGTT 75
  76. Phương pháp biểu diễn nhờ KGTT ▪ Mỗi trạng thái là một sắp xếp nào đó của các con số từ 1 đến 15 sao cho không có hai ô nào có cùng giá trị ▪ Hình trạng đầu và cuối tương ứng với các trạng thái đầu và cuối ▪ Không gian trạng thái đạt được từ trạng thái đầu bao gồm tất cả các hình trạng được sinh ra nhờ áp dụng những phép dịch chuyển chấp nhận được của ô trống ▪ Đối với bài toán này số trạng thái chấp nhận được xấp xỉ (1/2). 16 ! 10.5.1012 ▪ Các toán tử chính là các phép biến đổi từ trạng thái này sang trạng thái khác bao gồm: dịch ô trống sang phải, sang trái, lên trên, xuống dưới. Đối với một số trạng thái có một số toán tử không áp dụng được. ▪ Lời giải của bài toán có thể nhận được nhờ sử dụng quá trình tìm kiếm sau: áp dụng các toán tử vào trạng thái đầu để nhận được những trạng thái mới, sau đó áp dụng các toán tử vào các trạng thái mới này và cứ như vậy cho đến khi đạt đến trạng thái đích. 76
  77. Phương pháp qui bài toán về các bài toán con ▪ Tách bài toán thành các bài toán con sao cho lời giải của tập các bài toán con cho phép xác định lời giải của bài toán ban đầu. ▪ Cách tiếp cận này dẫn đến phương pháp biểu diễn vấn đề bằng đồ thị Và /Hoặc. A Và C Hoặc B G E F H I J 77
  78. Phương pháp qui bài toán về các bài toán con ▪ VD: Bài toán Tháp Hà nội (n=3) 1 1 2 2 3 3 A B C A B C Hµ Néi (2, A, C, B) Hµ Néi (3, A, B, C) Hµ Néi (1, A, B, C) Hµ Néi (2, B, A, C) 78
  79. Phương pháp qui bài toán về các bài toán con ▪ n = 3 ▪ n = 4 79
  80. Phương pháp biểu diễn vấn đề nhờ logic hình thức ▪ Thông thường, để giải quyết vấn đề người ta cần phân tích logic để thu gọn quá trình tìm kiếm và đôi khi nhờ phân tích logic có thể chứng tỏ được rằng một bài toán nào đó không thể giải được. ▪ VD: Bài toán trò chơi n2-1 số 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 80
  81. Phương pháp biểu diễn vấn đề nhờ logic hình thức ▪ Các dạng logic hình thức được sử dụng để biểu diễn bài toán gồm: ▪ Logic mệnh đề ▪ Logic vị từ ▪ Phương pháp biểu diễn bài toán nhờ logic hình thức cho phép: ▪ Kiểm tra điều kiện kết thúc trong khi tìm kiếm đối với không gian trạng thái ▪ Kiểm tra tính áp dụng được đối với các toán tử ▪ Chứng minh không tồn tại lời giải ▪ Mục đích giải quyết vấn đề dựa trên logic hình thức là chứng minh một phát biểu nào đó trên cơ sở những tiền đề và luật suy diễn đã có. 81
  82. Lựa chọn phương pháp biểu diễn thích hợp ▪ Trong nhiều trường hợp, việc giải quyết bài toán dựa trên các thuật ngữ đã được dùng để phát biểu nó là rất khó khăn. Người ta thường lựa chọn một dạng biểu diễn phù hợp nào đó đối với các dữ liệu của bài toán, làm cho bài toán trở nên dễ giải hơn. 82
  83. Lựa chọn phương pháp biểu diễn thích hợp ▪ Việc lựa chọn phương pháp biểu diễn thích hợp nhằm: ▪ Tránh giải trực tiếp bài toán đặt ra ban đầu do những khó khăn liên quan tới kích cỡ, trọng số, tầm quan trọng và chi phí xử lý dữ liệu của bài toán. ▪ Bỏ bớt những thông tin thừa hoặc không quan trọng trong bài toán ▪ Tận dụng những phương pháp giải đã có đối với bài toán nhận được sau khi phát biểu lại ▪ Cách phát biểu mới có thể cho phép thể hiện một vài tương quan nào đó giữa các yếu tố của bài toán nhằm thu gọn quá trình giải ▪ Sau khi đã giải quyết xong bài toán theo cách biểu diễn mới, cần phải diễn giải lời giải nhận được cho sát với bài toán thực tế và chứng minh rằng cách diễn giải đó thực sự giải quyết được bài toán đặt ra. 83
  84. Biểu diễn vấn đề trong máy tính Để có thể giải quyết vấn đề trên máy tính, trước hết ta phải tìm cách biểu diễn lại vấn đề sao cho máy tính có thể “hiểu” được. Điều này có nghĩa là ta phải đưa các dữ liệu của bài toán về dạng có thể xử lý được trên máy tính. ▪ Cách biểu diễn dùng bảng: Sử dụng bảng để biểu diễn các hình trạng của bài toán. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 84
  85. Biểu diễn vấn đề trong máy tính ▪ Cách biểu diễn dùng xâu ký hiệu TgT ToĐ VĐ MĐ TgT VT 85
  86. Biểu diễn vấn đề trong máy tính ▪ Cách biểu diễn dùng cấu trúc danh sách b2 − 4ac 2a / * 2 a - * 4 a c  b 2 86
  87. Biểu diễn tri thức và giải quyết vấn đề Có hai cách tiếp cận trong giải quyết vấn đề: ▪ Tổng quát hoá để đưa ra mô hình bài toán ▪ Cụ thể hoá trên cơ sở sử dụng các tri thức đặc tả Trên thực tế, có những bài toán không thể giải được nhờ sử dụng mô hình, hơn nữa lời giải nhận được còn khá xa với lời giải thực tế. Trong trường hợp đó, người ta áp dụng cách tiếp cận sử dụng tri thức đặc tả. Các phương pháp biểu diễn tri thức bao gồm: Frame, logic hình thức, mạng ngữ nghĩa và các hệ sản xuất. 87
  88. NỘI DUNG ▪ BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT ▪ CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀ ▪ CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ 88
  89. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ ▪ Biểu diễn vấn đề trong không gian trạng thái và các chiến lược tìm kiếm trên đồ thị ▪ Qui bài toán về bài toán con và các chiến lược tìm kiếm trên đồ thị Và/Hoặc ▪ Biểu diễn vấn đề nhờ logic hình thức và phương pháp suy diễn logic ▪ Một số phương pháp giải quyết vấn đề khác 89
  90. Biểu diễn vấn đề trong KGTT và các chiến lược tìm kiếm trên đồ thị ▪ Các mô tả trạng thái và toán tử ▪ Biểu diễn vấn đề dưới dạng đồ thị ▪ Các phương pháp tìm kiếm trong không gian trạng thái 90
  91. Các mô tả trạng thái và toán tử ▪ Khi giải quyết bài toán trong không gian trạng thái, chúng ta cần phải xác định dạng mô tả các trạng thái của bài toán. ▪ VD: Bài toán n2 - 1 số (n = 4) ▪ Mỗi trạng thái là bảng có kích thước 4 x 4 ▪ Toán tử: phép biến đổi từ trạng thái này sang trạng thái khác (chuyển ô trống lên trên, xuống dưới, sang trái, sang phải nếu có thể). 91
  92. Các mô tả trạng thái và toán tử ▪ VD: Biến đổi biểu thức đại số: (A x B + C x D)/(B * C) thành A/C + D/B. ▪ Mỗi trạng thái là biểu thức đại số. ▪ Toán tử: Biến đổi được từ biểu thức này sang biểu thức khác. ▪ Dùng cấu trúc cây nhị phân. ▪ Dùng ký pháp nghịch đảo Ba lan (Hậu tố, tiền tố). ▪ Các toán tử trong không gian trạng thái là những phép biến đổi đưa trạng thái này về trạng thái khác 92
  93. Các mô tả trạng thái và toán tử ▪ Có hai cách biểu diễn các toán tử: ▪ Cách 1: Sử dụng kí hiệu hàm, có nghĩa là xem các toán tử như là các hàm xác định trên tập các trạng thái và nhận giá trị cũng trong tập này ▪ VD: Với bài toán trò chơi 15 số, ta có 4 loại toán tử có thể mô tả được dưới dạng kí hiệu hàm như sau dl: Dịch ô trống lên trên; dx: Dịch ô trống xuống dưới; df: Dịch ô trống sang phải; dt: Dịch ô trống sang trái; dl(A) = B, Giả sử A = (aij). B = (bij) và ô trống trong A ở vị trí (i0, j0)). Khi đó ứng với phép dịch ô trống lên trên ta có thể viết B =  dl(A) = (bij) với aij (i, j) nÕu i0 = 1 bij = nÕu (i, j) (i0, j0) vµ (i, j) (i0-1, j0), i0>1 ai0j0 nÕu (i, j) = (i0-1, j0) vµ i0>1 ai0-1j0 nÕu (i, j) = (i0, j0) vµ i0>1 93
  94. Các mô tả trạng thái và toán tử ▪ Cách 2: Sử dụng các quy tắc sản xuất (Production Rules) si → sj. Nghĩa là, mỗi khi xuất hiện trạng thái si thì có thể dẫn tới trạng thái sj. ▪ VD: Với bài toán trò chơi 15 số, ta có sản xuất sau: 11 9 4 15 11 9 4 15 1 3 12 1 3 12 7 5 8 6 7 5 8 6 13 2 10 14 13 2 10 14 94
  95. Các mô tả trạng thái và toán tử ▪ Các thủ tục tìm kiếm trong không gian trạng thái thường bao gồm quá trình xây dựng các trạng thái mới xuất phát từ các trạng thái cũ và kiểm tra xem trạng thái mới này có thoả mãn những điều kiện áp dụng cho trạng thái đích không. 95
  96. Các mô tả trạng thái và toán tử ▪ Kết luận: Để biểu diễn bài toán trong không gian trạng thái cần phải xác định: ▪ Dạng mô tả của các trạng thái. ▪ Tập các toán tử và tác động của chúng lên các mô tả trạng thái . ▪ Các trạng thái đầu, các trạng thái đích . 96
  97. Các mô tả trạng thái và toán tử Một cách hình thức ta có thể phát biểu bài toán như sau: ▪ Bài toán P1: Cho trạng thái đầu s0, tập trạng thái ĐICH. Hãy tìm dãy trạng thái s0, s1, s2, . . ., sn sao cho sn ĐICH, thoả mãn một số điều kiện nào đó và với mọi i (i=0, ,n-1), từ trạng thái si có thể áp dụng toán tử biến đổi nào đó để nhận được trạng thái si+1 (i oi O sao cho oi(si) = si+1 hoặc i pi P sao cho si → si+1 ) 97
  98. Các mô tả trạng thái và toán tử Hay dưới dạng khác: Bài toán P2: Cho trạng thái đầu s0, tập trạng thái đích ĐICH. - Tìm dãy toán tử o1, . . ., on sao cho on(on-1(. . .(o1(s0). . .)) = sn ĐICH - Tìm dãy sản xuất p1, p2, . . ., pn sao cho p1 p2 pn s0 ⎯ ⎯ → s1 ⎯ ⎯ → s2 ⎯ ⎯ → sn ĐICH 98
  99. Biểu diễn vấn đề dưới dạng đồ thị ▪ Đồ thò: là một cấu trúc G = (N,A) bao gồm: ▪ Tập các nút N ▪ Tập các cung A nối các cặp nút, có thể có nhiều cung trên một cặp nút A B A B C D E D C E Nút: {A,B,C,D,E} Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), (d,e)},e), (d,e) } 99
  100. Biểu diễn vấn đề dưới dạng đồ thị ▪ Đồ thò có hướng:là đồ thò với các cung có đònh hướng, nghĩa là cặp nút có quan hệ thứ tự trước sau theo từng cung. Cung (Ni,Nj) có hướng từ Ni đến Nj, Khi đó Ni là nút cha và Nj là nút con. ▪ Nút lá: là nút không có nút con. ▪ Đường đi: là chuoãi có thứ tự các nút mà 2 nút kế tiếp nhau tồn tại một cung. ▪ Đồ thò có gốc: Trên đồ thò tồn tại nút X sao cho tất cả các đường đi đều đi qua nút đó. X là gốc. 100
  101. Biểu diễn vấn đề dưới dạng đồ thị ▪ Không gian trạng thái là một hệ thống gồm 4 thành phần [N,A,S,DICH]. Trong đó: ▪ N là tập nút của ồ thò. Moãi nút là một trạng thái của quá trình giải quyết vấn ề ▪ A: Tập các cung nối giưõa các nút N. Moãi cung là một bước (toán tử) trong giải quyết vấn ề. Cung có thể có hướng ▪ S: Tập các trạng thái bắt đầu. S khác roãng. ▪ DICH: Tập các trạng thái đích. DICH khác roãng. ▪ Lời giải: Là một đường đi đi từ một nút bắt đầu Si đến một nút kết thúc DICHj . ▪ Mục tiêu của các giải thuật tìm kiếm là tìm ra một lời giải và/hay lời giải tốt nhất. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 101
  102. Các phương pháp tìm kiếm trong KGTT ▪ Tìm kiếm theo chiều rộng (Breath – first search) ▪ Tìm kiếm theo chiều sâu (Depth –first search ) ▪ Tìm kiếm sâu dần (Depthwise search) ▪ Tìm kiếm cực tiểu hoá giá thành (Cost minimization search) ▪ Tìm kiếm cực tiểu hoá giá thành với tri thức bổ sung (Heuristic search: Cost minimization search with knowledge) Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 102
  103. Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR) Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N * Ra : Đường đi p từ đỉnh n0 tới đỉnh n ĐICH Phương pháp: /* Sử dụng hai danh sách kiểu FIFO là MO và ĐONG, trong đó MO là danh sách chứa các đỉnh chưa xét còn ĐONG là danh sách chứa các đỉnh đã xét */ {MO  n0 /* Cho đỉnh n0 vào cuối danh sách MO */ While MO  do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n} if B(n)  then /* B(n) là tập các nút con của nút n {MO  MO  B(n) /* Cho B(n) vào cuối danh sách MO */ if B(n)  ĐICH  then {exit(thành công); Xây dựng đường đi p} } } write(không thành công); } Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 103
  104. Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR) ▪ VD: Áp dụng thuật toán tìm kiếm theo chiều rộng với cây sau, tập ĐICH = {r, p} Thứ tự duyệt là: a b c d e f g h k l Đường đi: a c f l p 104
  105. Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR) ▪ Nếu trong cây G tồn tại ít nhất một đường đi từ n0 tới tập ĐICH thì thủ tục tìm kiếm theo chiều rộng dừng và cho ta đường đi p có độ dài ngắn nhất (thậm chí cây G vô hạn). Nếu không tồn tại đường đi như vậy thuật toán dừng nếu và chỉ nếu đồ thị cây G là hữu hạn. 105
  106. Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS) Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N * Ra : Đường đi p từ đỉnh n0 tới đỉnh n ĐICH Phương pháp: /* Sử dụng danh sách MO kiểu LIFO và danh sách ĐONG kiểu FIFO */ {MO  n0 /* Cho đỉnh n0 vào đầu danh sách MO */ While MO  do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n} if B(n)  then {MO  MO  B(n) /* Cho B(n) vào đầu danh sách MO */ if B(n)  ĐICH  then {exit(thành công); Xây dựng đường đi p} } } write(không thành công); } 106
  107. Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS) ▪ VD: Áp dụng thuật toán tìm kiếm theo chiều sâu với cây sau, tập ĐICH = {o, p} Thứ tự duyệt: a b d h Đường đi: a b d h o 107
  108. Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS) ▪ Nếu cây G hữu hạn thì thủ tục tìm kiếm theo chiều sâu sẽ dừng và cho kết quả là một đường đi từ n0 đến tập ĐICH ▪ Đường đi nhận được theo thuật toán TKR (nếu có) sẽ là đường đi ngắn nhất còn đường đi nhận được theo thuật toán TKS (nếu có) có thể không phải là đường đi ngắn nhất. Hơn nữa, nếu đồ thị vô hạn thì thủ tục TKS có thể lặp vô hạn, thậm chí trong đồ thị G tồn tại đường đi từ n0 tới tập ĐICH. 108
  109. Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS) ▪ Khắc phục bằng cách giới hạn ộ sâu của giải thuật. ▪ Chiến lược giới hạn: ▪ Cố đònh một ộ sâu D ▪ Theo cấu hình tài nguyên của máy tính ▪ Tri thức trong việc đònh giới hạn ộ sâu. ▪ Giới hạn ộ sâu => co hẹp không gian trạng thái => có thể mất nghiệm. 109
  110. Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD) ▪ Tìm kiếm theo chiều sâu đối với lớp các đỉnh tuỳ thuộc vào mức sâu k đã cho ban đầu. ▪ Cách thực hiện: Ta ký hiệu độ sâu hiện tại là DS, ban đầu gán DS = k, duyệt các đỉnh trong phạm vi độ sâu DS, nếu chưa tìm được đường đi thì tăng DS = DS + k và tiếp tục duyệt. ▪ Độ sâu d(n) của đỉnh n được định nghĩa: - d(n0) = 0 - d(n) = d(m) +1 nếu n B(m) 110
  111. Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD) Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N, mức sâu k * Ra: Đường đi p từ đỉnh n0 tới đỉnh n ĐICH Phương pháp: /* Sử dụng ds MO kiểu lai LIFO và FIFO, ds DONG kiểu FIFO */ {MO  n0; DS = k; While MO  do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ DONG  ĐONG  {n} if B(n)  then {if B(n)  ĐICH  then {exit(thành công); Xây dựng đường đi p} case d(n) do { [0 DS - 1]: đặt B(n) vào đầu MO DS: đặt B(n) vào cuối MO DS + 1: {DS = DS + k; if k =1 then đặt B(n) vào cuối MO else đặt B(n) vào đầu MO }}} write(không thành công); } 111
  112. Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD) ▪ VD: Áp dụng thuật toán TKSD với cây sau: Tập ĐICH = {r, p}, độ sâu k = 2. ▪ Thứ tự duyệt: a b d e c f g h n o k l ▪ Đường đi: a c f l p 112
  113. Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD) ▪ Khi k =1 thủ tục TKSD trở thành thủ tục TKR ▪ Khi k>=2 thủ tục TKSD tìm theo chiều sâu đối với các đỉnh có độ sâu nằm trong khoảng từ tk + 1 đến (t + 1)k với t bắt đầu từ 0 và mỗi lần tăng lên 1 ▪ Nếu trong cây G tồn tại ít nhất một đường đi từ đỉnh n0 đến ĐICH thì thủ tục TKSD sẽ dừng và cho kết quả là đường đi có độ dài khác đường đi ngắn nhất không quá k - 1. Nếu không tồn tại đường đi như vậy thì thủ tục TKSD dừng khi và chỉ khi G hữu hạn 113
  114. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT) ▪ Giả sử C: A→R+ là hàm giá (cost) tương ứng mỗi cung a A với giá chi phí c(a) R+. Với một đường đi p trong G, p = k −1 n , , n ta có: c(P) = c(ni ,ni+1 ) 1 k i=1 Xác định p: n0→nk DICH sao cho: c(p) → min Kí hiệu g(n) là giá của đường đi cực tiểu từ n0 đến n. Khi đó, bài toán trên được phát biểu thành: Tìm đường đi p0 từ đỉnh gốc n0 đến đỉnh nk DICH sao cho g(nk)=min{g(n)| n DICH}. 114
  115. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT) + Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH N, c: A → R * Ra: Đường đi p từ đỉnh n0 tới đỉnh n ĐICH sao cho c(p) min Phương pháp: /* Sử dụng 2 danh sách MO và DONG */ 0 0 {MO  n0; g (n0)=0; /*g (n): giá của đường đi hiện tại từ n0 đến n*/ While MO  do {n  get(MO) /* Lấy đỉnh n MO sao cho g0(n) min */ ĐONG  ĐONG  {n} if n ĐICH then exit(thành công) if B(n)  then {MO  B(n)  MO for each m B(n) do g0(m) = g0(n) + c(n, m)} } write(không thành công); } 115
  116. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT) ▪ VD: Áp dụng thuật toán TKCT đối với cây sau Tập ĐICH = {n, p} Thứ tự duyệt: a c b f l m d g h p Đường đi: a c f l p Có giá: 10 116
  117. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT) ▪ Thủ tục TKR là trường hợp riêng của thuật toán TKCT khi c(a) =1 a A. ▪ Thủ tục TKS cũng là trường hợp riêng của thủ tục TKCT khi lấy tiêu chuẩn chọn n MO là d(n) max thay cho điều kiện g0(n) min ▪ Nếu trong cây G tồn tại đường đi p từ n0 đến ĐICH thì thủ tục TKCT sẽ dừng và cho kết quả là đường đi p sao cho c(p) min. Hơn nữa, thủ tục TKCT tối ưu theo nghĩa số đỉnh cho vào tập ĐONG là nhỏ nhất so với các thủ tục tìm kiếm chỉ dựa vào giá các cung. 117
  118. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT) Các Heuristic áp dụng cho thủ tục TKCT : ▪ Chỉ xét các đỉnh trong B(n) có triển vọng đạt tới tập ĐICH. ▪ Sắp xếp các đỉnh trong MO trước mỗi lần xử lý nhờ các hàm đánh giá. 118
  119. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ “Heuristics là các quy tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối lượng tìm kiếm lời giải trong không gian bài toán cực lớn.” ▪ Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau: ▪ Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất) ▪ Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn. ▪ Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. 119
  120. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau: ▪ Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. ▪ Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. 120
  121. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt. ▪ Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Đó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải. 121
  122. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ Thủ tục TKCT là thuật giải tìm kiếm đường đi tối ưu khi chỉ xét tới các thông tin về các đỉnh, các cung và giá thành của chúng. ▪ Trong nhiều trường hợp việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu được dựa trên các hiểu biết về tình huống vấn đề ở mỗi bước. 122
  123. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ Các Heuristic trong việc tìm kiếm cực tiểu hoá giá thành: ▪ Chọn toán tử xây dựng cung B sao cho có thể loại bớt những đỉnh không liên quan đến bài toán hoặc ít có triển vọng nằm trên đường đi tối ưu. ▪ Sử dụng thông tin bổ sung nhằm xây dựng tập MO và cách lấy các đỉnh trong tập MO. Muốn vậy, ta phải đưa ra độ đo, tiêu chuẩn nào đó để tìm ra các đỉnh có triển vọng, thường gọi là các hàm đánh giá. Một số phương pháp xây dựng hàm đánh giá: - Dựa vào xác suất của đỉnh trên đường đi tối ưu. - Dựa vào khoảng cách, sự sai khác giữa một đỉnh nào đó với tập các đỉnh đích. 123
  124. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* Vào: Đồ thị G=(N,A) tuỳ ý, đỉnh gốc n0. tập đỉnh đích ĐICH. Hàm f0: N→R+. /*f0 là hàm ước lượng heuristic nào đó*/ * Ra: Đường đi p từ đỉnh n0 tới đỉnh n ĐICH Phương pháp: 0 { MO{n0}; Tính f (n0) ; While MO  do {n  get(MO); /* Lấy n MO sao cho f0 (n) → min */ ĐONG  ĐONG  {n}; if n ĐICH then exit(“ thành công”); if B(n)  then for each m B(n) do if m ĐONG  MO then { MO MO  {m}; Tính f0(m)} 0 else if f cũ(m) >fmới(m) then MO MO  {m}}; Write(“ không thành công”) } 124
  125. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ f0=g0+h0 , trong đó: h0(n) là tri thức bổ sung chỉ ra triển vọng của đỉnh n nằm trên đường tối ưu. ▪ f0(n) là ước lượng của hàm: f(n)=g(n)+h(n) , trong đó: g(n) là giá đường đi tối ưu từ n0 tới n h(n) là giá đường đi tối ưu từ n tới tập ĐICH 0 ▪ f (n) là xấp xỉ của giá đường đi tối ưu từ n0 tới tập ĐICH và đi qua đỉnh n. ▪ Thủ tục TKCT là trường hợp riêng của thủ tục TKCT* khi lấy h0=0 125
  126. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ Kết quả 1: (Tính đúng đắn) Nếu đối với mỗi đỉnh n N ta có 0 h0(n) h(n) và tồn tại >0 sao cho a A c(a)  thì thủ tục TKCT* dừng và cho đường đi p: n0→n* ĐICH sao cho g(n*) min. ▪ Kết quả 2: (Tính tối ưu) * Giả sử thủ tục TKCT i sử dụng hàm đánh giá 0 0 0 f i(n)=g (n)+h i(n), i=1,2 và giả sử h2 thoả mãn điều kiện 0 0 h 2(m) – h 2(n) h(m, n), (h(m,n) là độ dài đường đi ngắn 0 0 nhất từ m đến n) và n 0 h 1(n) h 2(n) h(n) thì số nút * đưa vào tập DONG của thuật toán TKCT2 bao giờ cũng * nhỏ hơn số nút đối với thuật toán TKCT1 . 126
  127. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* ▪ VD: Xét bài toán tháp Hà Nội với n=2, lấy hàm f0=g0+h0, trong đó h0(n) là thông tin nói thêm về mối liên hệ giữa n và trạng thái đích. Chẳng hạn: h0=2 nếu ở cọc C chưa có đĩa nào, h0=1 nếu ở cọc C có đĩa to, h0=3 nếu ở cọc C có đĩa nhỏ, h0=0 nếu ở cọc C đã có hai đĩa. 127
  128. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* g0 =0 h0 = 2, f0=2 h0 = 3, 0 0 g0 =1 h = 2, f =3 f0=4 0 0 0 h0 = 1 h = 3 h = 2 g =2 0 f0=3 f =5 f0=4 0 0 0 0 h = 2 h = 0 g =3 h = 1 f0=5 f0=3 f0=4 ĐICH 128
  129. Qui bài toán về các bài toán con và các chiến lược tìm kiếm trên đồ thị Và/Hoặc ▪ Qui bài toán về các bài toán con ▪ Thể hiện dưới dạng đồ thị VÀ/HOẶC ▪ Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC 129
  130. Qui bài toán về các bài toán con ▪ Ý tưởng cơ bản là xuất phát từ bài toán đặt ra, tách bài toán này thành các bài toán con cho đến khi bài toán ban đầu trở thành các bài toán sơ cấp. ▪ Bài toán sơ cấp được hiểu là bài toán mà lời giải của chúng có thể nhận được ngay. VD: Với bài toán n2 – 1 số, bài toán sơ cấp chính là bài toán chuyển ô trống 1 lần để nhận được trạng đích. Với bài toán tháp Hà Nội, bài toán sơ cấp là chuyển 1 đĩa từ cọc này sang cọc khác. 130
  131. Thể hiện dưới dạng đồ thị VÀ/HOẶC ▪ Đồ thị (định hướng) VÀ/HOẶC là cặp G = (N,A), sao cho n N, tất cả các đỉnh m B(n) cùng thuộc vào một trong hai kiểu: đỉnh VÀ, đỉnh HOẶC. Khi các đỉnh con m của n là đỉnh VÀ thì cung (n,m) (m B(n)) được nối bởi ngoặc lớn. ▪ VD: 131
  132. Thể hiện dưới dạng đồ thị VÀ/HOẶC Quy bµi to¸n vÒ c¸c bµi to¸n con §å thÞ vµ/hoÆc Bµi to¸n §Ønh To¸n tö quy bµi to¸n vÒ bµi to¸n con Cung Bµi to¸n ban ®Çu §Ønh ®Çu (®Ønh gèc) C¸c bµi to¸n s¬ cÊp §Ønh cuèi, ®Ønh kÕt thóc C¸c bµi to¸n con phô thuéc §Ønh vµ C¸c bµi to¸n con ®éc lËp §Ønh hoÆc Gi¶i bµi to¸n ban ®Çu. T×m ®å thÞ con lêi gi¶i. 132
  133. Thể hiện dưới dạng đồ thị VÀ/HOẶC ▪ Đỉnh giải được: ▪ Các đỉnh kết thúc (cuối) là đỉnh giải được. ▪ Nếu đỉnh n có các đỉnh con là đỉnh VÀ thì nó là đỉnh giải được khi và chỉ khi tất cả các đỉnh con của nó giải được. ▪ Nếu đỉnh n có các đỉnh con là đỉnh HOẶC thì nó là đỉnh giải được khi và chỉ khi tồn tại 1 đỉnh con của nó giải được. ▪ Đỉnh không giải được: ▪ Nếu đỉnh n không là đỉnh kết thúc và không có các đỉnh con thì nó là đỉnh không giải được. ▪ Nếu đỉnh n không là đỉnh kết thúc và có các đỉnh con là đỉnh VÀ thì nó là đỉnh không giải được khi và chỉ khi tồn tại một đỉnh con không giải được. ▪ Nếu đỉnh n không là đỉnh kết thúc mà có các đỉnh con là đỉnh HOẶC thì nó là đỉnh không giải được khi và chỉ khi tất cả các đỉnh con là không giải được 133
  134. Thể hiện dưới dạng đồ thị VÀ/HOẶC ▪ Đồ thị lời giải: Là đồ thị con của đồ thị VÀ/HOẶC chỉ chứa các đỉnh giải được và đỉnh đầu. ▪ Nhận xét: ▪ Nếu trên đồ thị VÀ/HOẶC không có đỉnh VÀ nào thì đồ thị VÀ/HOẶC trở thành đồ thị thông thường và khi đó đồ thị con lời giải sẽ suy biến thành đường đi từ đỉnh đầu tới một đỉnh kết thúc nào đó. ▪ Mục đích của quá trình tìm kiếm trên đồ thị VÀ/HOẶC là ta phải xác định xem đỉnh đầu có giải được hay không. Trong trường hợp giải được thì ta phải đưa ra cây lời giải thoả mãn điều kiện nào đó. 134
  135. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC 135
  136. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC Thủ tục gđ(n N) { if nhan(n)= “kxđ” then if kt(n) then nhan(n)="gđ" else if n MO ĐONG then nhan(n)=”kxđ” else if kieu(n) then {bien=True; While B(n)  and bien do {m  get(B(n)); gđ(m); bien=(nhan(m)=”gđ”)} if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”} else {bien=false; repeat {m get(B(n)); gđ(m); bien=(nhan(m)=”gđ”)} until bien or B(n)= if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”}} 136
  137. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC ▪ Thủ tục tìm kiếm theo chiều rộng TKRM ▪ Thủ tục tìm kiếm theo chiều sâu TKSM 137
  138. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRM Vào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} N Ra: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải. Phương pháp: /* sử dụng hai danh sách FIFO: MO, ĐONG */ {MO ={n0}; While MO  do {n get(MO); /*Lấy đỉnh n đầu danh sách MO*/ ĐONG{n}  ĐONG; bool = false; if B(n)  and bool = false then {MO MO B(n); /* đưa B(n) vào cuối danh sách MO */ For each m B(n) do {if kt(m) then {nhan=”gđ”; bool=true}} if bool then {gđ(n0); if nhan(n0)=”gđ” then exit(“thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được}} else {nhan(n)=”kgđ”; kgđ(n0); if nhan(n0) = “kgđ” then exit (“không thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} 138
  139. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRM ▪ VD:Áp dụng thuật toán TKRM đối với cây sau Tập T = {t1,t2,t3,t4} Thứ tự duyệt: a abcdefgijk b c Cây lời giải: d e g các cung tô đậm f D i j k E B C t3 t4 F A t1 t2 ▪ Nhận xét: Nếu cây lời giải tồn tại thì thủ tục TKRM sẽ dừng và cho kết quả là cây lời giải có độ cao nhỏ nhất 139
  140. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKSM Vào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} N. Giới hạn sâu D. Ra: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải. Phương pháp: /* sử dụng hai danh sách FIFO: DONG, LIFO: MO */ {MO ={n0}; While MO  do {n get(MO); /*Lấy đỉnh n đầu danh sách MO*/ ĐONG{n}  ĐONG; bool = false; if d(n)<= D and B(n)  and bool = false then {MO MO B(n); /* đưa B(n) vào đầu danh sách MO */ For each m B(n) do {if kt(m) then {nhan=”gđ”; bool=true}} if bool then {gđ(n0); if nhan(n0)=”gđ” then exit(“thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được}} else {nhan(n)=”kgđ”; kgđ(n0); if nhan(n0) = “kgđ” then exit (“không thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} 140
  141. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKSM ▪ VD: Áp dụng thuật toán TKSM đối với cây sau Tập T = {t1,t2,t3,t4} a b c Thứ tự duyệt: d e abdAfceg C E f g Cây lời giải: A t3 D t4 các cung tô đậm B t1 t2 ▪Nếu một đỉnh kết thúc nào đó có độ sâu vượt quá giới hạn độ sâu D thì nó sẽ bị bỏ qua trong quá trình tìm kiếm. Do vậy, trên thực tế có thể tồn tại cây lời giải, song thuật toán lại thông báo không thành công. Để khắc phục tình trạng này, người ta có thể cải biên thủ tục tìm kiếm theo chiều sâu thành thủ tục tìm kiếm sâu dần, trong đó các nút được duyệt từng mức một. 141
  142. Biểu diễn vấn đề nhờ logic hình thức và phương pháp suy diễn logic ▪ Logic mệnh đề ▪ Logic vị từ ▪ Chứng minh định lý nhờ logic hình thức ▪ Áp dụng phép tính vị từ trong giải quyết vấn đề 142
  143. Logic mệnh đề ▪ Mệnh đề p là một phát biểu chỉ có thể nhận giá trị đúng (True, 1) hoặc sai (False, 0). ▪ VD: Phát biểu "1+1=2" có giá trị đúng. Phát biểu "Mọi loại cá có thể sống trên bờ" có giá trị sai ▪ Các biểu thức trong logic mệnh đề được xây dựng trên cơ sở các tên mệnh đề (thường ký hiệu bằng các chữ cái la tinh như a,b,p,q, . . .) và các phép toán logic theo những quy tắc cú pháp nhất định. Các phép toán logic bao gồm: ▪ Hội: (, and, và). ▪ Tuyển: (, or, hoặc). ▪ Phủ định: (, not, không). ▪ Kéo theo: ( ). ▪ Tương đương: ( ). 143
  144. Logic mệnh đề ▪ Giá trị chân lý của một biểu thức được tính dựa theo bảng chân lý: a b ab ab a a b a b 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 ▪ Dễ thấy a b ab ▪ Mọi biểu thức logic mệnh đề đều có thể đưa về dạng biểu thức tương đương chỉ chứa các phép toán , ,  ▪ Các phép toán ,  có tính giao hoán, kết hợp, phân phối và luỹ đẳng 144
  145. Logic mệnh đề ▪ Các phép biến đổi tương đương: R1. a  b  b  a; a  b  b  a R2. a → b  b → a R3. a  a  a; a  a  a R4. a  (b  c)  (a  b)  c; a  (b  c)  (a  b)  c R5. a  b  (a  b); a  b  (a b) R6. a → b  a  b R7. a  (b  c)  (a  b)  (a  c); a  (b  c)  (a  b)  (a  c) R8. a  (a  b)  a; a  (a  b)  a R9. a  a R10. (a  b)  a  b; (a  b)  a  b R11. a  a  0 R12. a  0  0; a  1  1; a  0  a; a  1  a R13. 1  0; 0  1 145
  146. Logic vị từ ▪ Biểu diễn vấn đề bằng mệnh đề gặp phải một trở ngại cơ bản là ta không thể can thiệp vào cấu trúc của một mệnh đề. Hay nói một cách khác là mệnh đề không có cấu trúc. Điều này làm hạn chế rất nhiều thao tác suy luận. Do đó, ngoài các phép  , , , , , người ta đã đưa vào khái niệm vị từ và lượng từ ( - với mọi,  - tồn tại) để tăng cường tính cấu trúc của một mệnh đề. ▪ Vị từ p(x, ,y) là một phát biểu chứa các biến x, ,y sao cho khi x, ,y nhận các giá trị cụ thể thì nó nhận giá trị hoặc đúng hoặc sai. ▪ VD: p(x, y, z) được phát biểu x.y = z là một vị từ 3 biến x, y, z trên tập các số thực. Khi đó tính chất giao hoán của phép nhân được diễn tả như sau: x, y p(x, y, z) → p(y, x, z) 146
  147. Logic vị từ ▪ Lượng từ : x p(x, y, z,. . .) có nghĩa là tồn tại một giá trị x0 sao cho p(x0, y, z,. . .) đúng với mọi y, z, . . . ▪ Lượng từ : x p(x, y, z,. . .) có nghĩa là với mọi giá trị của x p(x, y, z,. . .) đúng với mọi y, z,. . . ▪ Logic vị từ cho phép diễn đạt hầu hết các khái niệm và nguyên lý của các khoa học cơ bản, nhất là toán học và vật lý. ▪ Hai phạm vi ứng dụng chính của logic hình thức: ▪ Chứng minh định lý ▪ Giải quyết vấn đề 147
  148. Chứng minh định lý nhờ logic hình thức: Giải thuật Wong.H (Vương Hạo) ▪ Bài toán: Cho các giả thiết dưới dạng các biểu thức mệnh đề (vị từ) GT1, GT2,. . ., GTm. Hãy rút ra một trong các kết luận KL1, KL2,. . ., KLn ▪ Giải thuật Wong .H (Vương Hạo) Vào: GT1, GT2,. . ., GTm; KL1, KL2,. . ., KLn . Ra: Thông báo “thành công” nếu GT1  GT2  . . .  GTm → KL1  KL2  . . .  KLn Phương pháp: { for i=1 to m do {trans(GTi); VT  GTi  VT} for i=1 to n do {trans(KLi);VP  KLi  VP} P  {(VT, VP)}; while P  do {(VT, VP)  get(P); if VT  VP =  then {chuyen(VT, VP); if VT  VP =  then if not tach(VT, VP) then exit(“không thành công”) else P  {(VT, VP)};}}write(“thành công”)} 148
  149. Chứng minh định lý nhờ logic hình thức: Giải thuật Wong.H (Vương Hạo) ▪ trans(BT): Đưa biểu thức BT về biểu thức tương đương mà chỉ chứa các phép toán , ,  dưới 1 trong 2 dạng chuẩn sau: k ni k ni hoặc , lij = pij hoặc lij = pij với pij là các mệnh đề đơn   lij   lij i=1 j=1 i=1 j=1 VD: (a → b)  (c  d) có thể đưa về thành: (a  b)  (c  d) ▪ chuyen(VT, VP): chuyển vế các GTi và các KLj ở dạng phủ định. Thay dấu  bên trong GTi và dấu  trong KLj bằng dấu phẩy. VD: (a  b) → (c  d) được biến đổi thành: c, d → a, b ▪ tach(VT, VP): tách VT, VP thành hai danh sách con nếu có dấu  trong một GTi hoặc dấu  trong một KLj nào đó. Nếu tách được thì thủ tục tach(VT, VP) nhận giá trị True. ngược lại nhận giá trị False VD: p  q, p → q được tách thành p, p → q và q, p → q ▪ Kết quả: Thuật toán Wong.H dừng sau một số bước hữu hạn và cho ra thông báo “thành công” nếu và chỉ nếu từ GT1, GT2,. . ., GTmcó thể suy ra một trong các kết luận KL1, KL2,. . ., KLn. 149
  150. Chứng minh định lý nhờ logic hình thức: Giải thuật Wong.H (Vương Hạo) ▪ VD: CMR từ a  b → c, b  c → d, a, b suy ra d Dạng chuẩn:VT = a  b  c, b  c  d, a, b; VP = d 150
  151. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ Thuật giải này hoạt động dựa trên phương pháp chứng minh phản chứng. Có nghĩa là, để chứng minh rằng từ GT1, GT2,. . ., GTm suy ra một trong các kết luận KL1, KL2,. . ., KLn ta lấy phủ định của các kết luận hợp với giả thiết suy ra mâu thuẫn. 151
  152. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ Thủ tục Resolution1 (Dùng cho logic mệnh đề) Vào: GT1, , GTm; KL1, , KLn Ra: Thông báo “thành công” nếu GT1 GTm→KL1 KLn. Phương pháp: { For i=1 to m do { Trans(GTi); PGTi;} For i=1 to n do {Trans(KLi); P KLi;} /* P=MĐ1, ,MĐk , k=m+n*/ If mt(P) then exit(“Thành công”); P1=; While P P1 and mt(P) do {P1=P; hopgiai(P);} If mt(P) then exit (“Thành công”) else exit (“Không thành công”)} Procedure mt(P); {mt=false; for each p P do for each q P and q p do if p=q or q=p then return (true)} Procedure hopgiai(P); {for each p P do for each q P and q p do if p=ab and q=ac then P P{bc}} 152
  153. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ VD: CMR từ a  b → c, b  c → d, a, b suy ra d Đưa các GTi và KLj về dạng chuẩn và xây dựng P ta có: P ={a  b  c, b  c  d, a, b, d}. Để đơn giản, ta viết các xâu trong P dưới dạng: 1. a  b  c 2. b  c  d 3. a 4. b 5. d Quá trình hợp giải như sau: 6.  b  c Res(1A,3) 7.  a  c Res(1B, 4) 8.  c  d Res(2A, 4) 9.  b   c Res(2C, 5) 10. c Res(3, 7A) 11. c Res(4, 9A). Mâu thuẫn giữa 10, 11, thông báo “thành công”. 153
  154. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ Kết quả: Thuật giải Resolution1 sẽ dừng và đưa ra thông báo “thành công” khi và chỉ khi GT1 GTm→KL1 KLn. ▪ Thuật giải Resolution1 có thể mở rộng để giải quyết các bài toán chứng minh định lý tự động sử dụng logic vị từ. Mấu chốt của phương pháp là hợp giải hai vị từ: A= P  Q1 Q2  Qk và B=P  R1  R2  Rt thành vị từ C = Q1 Q2  Qk  R1  R2  Rt. ▪ Do các vị từ Pi, Qi và Rj phụ thuộc và các biến nên để tạo ra các cặp đối ngẫu thực sự P và P ta phải thực hiện các phép gán. Cách chọn phép gán: Để đưa vị từ P(x1, x2, ,xn) về dạng P(t1, t2, ,tn) ta chọn phép gán q= { t1/x1, t2/x2, ,tn/xn} để thay thế mỗi biến xi bởi ti, trong đó ti có thể là biến, hằng hoặc biểu thức. 154
  155. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ Thủ tục Resolution2 (Dùng cho logic vị từ) k ni P Bước 1: Đưa các GTi và KLj về dạng chuẩn: x1x2 . . .xk  ij i=1 j=1 sao cho mọi biến có mặt trong Pij đều thuộc vào tập {x1, x2 ,. . .,xk}. Muốn vậy ta thực hiện các thao tác sau: 1. Khử bỏ các dấu kéo theo và tương đương nhờ A B  AB 2. Đưa dấu phủ định vào trong cùng chừng nào có thể, nhờ các phép biến đổi: · (AB)  AB (AB)  AB · A  A x A   x A ·   x A  xA 3. Thay tên biến để cho mỗi lượng từ chỉ có một tên biến riêng. 4. Khử bỏ các lượng từ tồn tại: x P(x) chuyển thành P(a), x y P(x,y) chuyển thành P(x,g(x)). Hàm g(x) được gọi là hàm Scholem. 5. Chuyển mọi lượng từ  về đầu biểu thức, phần biểu thức gọi là ma trận. 6. Đưa ma trận về dạng chuẩn hội nhờ áp dụng A(BC)  (AB) (AC) 7. Loại bỏ các lượng từ  8. Thay thế các liên kết  bởi các dấu phẩy, mỗi dòng được gọi là một câu. 155
  156. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ VD: Xét x {P(x) {y {P(y) P(f(x,y))}   y {Q(x,y) P(y)}}}. Áp dụng các bước để đưa về dạng chuẩn như sau: 1. x { P(x) {y { P(y)  P(f(x,y))}   y {Q(x,y)  P(y)}}} 2. x { P(x) {y { P(y)  P(f(x,y))}  y {Q(x,y)  P(y)}}} 3. x { P(x) {y { P(y)  P(f(x,y))}   {Q(x, )  P()}}} 4. x { P(x) {y { P(y)  P(f(x,y))}  {Q(x, g(x))  P(g(x))}}} 5. xy { P(x) {{ P(y)  P(f(x,y))}  {Q(x, g(x))  P(g(x))}}} 6. xy{{P(x)P(y)P(f(x,y))}{P(x)Q(x,g(x))}{P(x)P(g(x))}} 7. {P(x)P(y)P(f(x,y))}{P(x)Q(x,g(x))}{P(x)P(g(x))} 8. Tách câu và viết thành các dòng P(x)P(y)P(f(x,y)) P(x)Q(x,g(x)) P(x)P(g(x)) 156
  157. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson Bước 2. Nếu tìm được một cặp câu P1, P2 và một phép gán q sao cho P1q=P2q thì thông báo “Thành công” và thuật toán dừng. Ngược lại sang bước 3. Bước 3: Tìm cặp câu P = P0  P1 Pk và Q = Q0  Q1  Q2  Qt và phép gán q sao cho P0q = Q0q. Thực hiện hợp giải câu P với câu Q được câu R= P1 Pk  Q1  Q2  Q2  Qt và bổ sung câu R vào danh sách các câu. Bước 4: Nếu không thể xây dựng thêm được các hợp giải và không có cặp câu đối ngẫu thì bài toán sai, ngược lại bài toán được giải quyết xong và thông báo “Thành công”. Kết quả: Nếu từ GT1 GT2 GTm KL1  KL2  KLn thì thủ tục Resolution2 dừng và đưa ra thông báo “thành công”. 157
  158. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ VD: Biết rằng: Ngón tay là bộ phận của bàn tay, bàn tay là bộ phận của cánh tay, cánh tay là bộ phận của cơ thể. CMR: Ngón tay là bộ phận của cơ thể. Đặt vị từ P(x,y): “ x là bộ phận của y ”. Ta có: P(nt,bt), P(bt,ct), P(ct,cothe). P(x,y) có tính bắc cầu: P(x,y)  P(y,z) → P(x,z)  P(x,y)  P(y,z)  P(x,z) CMR P(nt, cothe) Mỗi câu được cho trên một dòng, trong mỗi dòng các dấu  được thay bởi dấu phấy: 1. P(x,z),  P(x,y), P(y,z) 2. P(nt,bt) 3. P(bt,ct) 4. P(ct,cothe) 5. P(nt, cothe) 6. P(nt,z), P(bt,z) Res(1B,2) q1 = {nt /x, bt /y} 7. P(nt,ct) Res(3,6B) q2 = {ct /z} 8. P(nt,z), P(ct,z) Res(1B,7) q3 = {nt/x, ct/y} 9. P(nt,cothe) Res(4,8B) q4 = {cothe/z} 10. Mâu thuẫn Res(5,9) 158
  159. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson ▪ VD: Nếu xem một ai đó đi lừa dối người khác là kẻ bịp bợm và bất kỳ ai đồng tình với kẻ bịp bợm cũng là bịp bợm, hơn nữa trong tập thể có một người nhút nhát đồng tình với kẻ lừa dối thì chắc chắn là có một kẻ bịp bợm tính tình nhút nhát. Ta sử dụng các vị từ sau: BB(x): x là kẻ bịp bợm. LD(x): x là kẻ lừa dối. NN(x): x là kẻ nhút nhát. ĐT(x,y): x đồng tình với y. 159
  160. Chứng minh định lý nhờ logic hình thức: Thủ tục của Robinson Khi đó ta có: 1. LD(x), BB(x) 2. ĐT(x,y), BB(y), BB(x) 3. NN(a) 4. LD(b) 5. ĐT(a,b) 6. BB(x), NN(x) 7. BB(b) Res(1A, 4), q1 ={b/x} 8. BB(b), BB(a) Res(2A, 5), q2 ={a/x, b/y} 9. BB(a) Res(3, 6B), q3 ={a/x} 10. NN(b) Res(6A, 7), q4 ={b/x} 11. BB(b) Res(8B, 9), 12. Mâu thuẫn Res(7,11). 160
  161. Áp dụng phép tính vị từ trong giải quyết vấn đề ▪ Phần này sẽ nghiên cứu việc xác định các phép gán trị cho các biến để từ GT1 GTm suy ra KL1 KLn. Có hai cách giải quyết: ▪ Lưu lại vết các phép gán giá trị nhận được cho đến khi đưa đến mâu thuẫn. Ta đưa vào khái niệm hợp các phép gán. Giả sử ,  là hai phép gán trị, hợp của chúng được kí hiệu bởi o sao cho đối với mọi biểu thức P ta có: P o=(P ). ▪ VD: Giả sử Mai và Dương rất thân nhau. Đi đâu Mai và Dương cũng có nhau. Hơn nữa ta biết rằng hiện nay Mai đang ở thư viện. Hỏi Dương đang ở đâu? Ta đưa vào vị từ: P(x,y): x đang ở vị trí y. Khi đó, ta có: x P(Mai, x) P(Dương, x) P(Mai, Thư viện). Cần tìm giá trị của P(Dương,x). 161
  162. Áp dụng phép tính vị từ trong giải quyết vấn đề 162
  163. Áp dụng phép tính vị từ trong giải quyết vấn đề ▪ Cải biên đồ thị lời giải Bên cạnh biểu thức là phủ định của kết luận KLj cần chứng minh ta thêm vào phủ định của chính nó (tức là KLj) và giữ nguyên các phép hợp giải giống như ở trong đồ thị hợp giải. 163
  164. Một số phương pháp giải quyết vấn đề khác ▪ Phương pháp tạo - kiểm tra ▪ Phương pháp leo đồi ▪ Phương pháp thoả mãn ràng buộc 164
  165. NGÔN NGỮ TTNT PROLOG 165
  166. NỘI DUNG ▪ GIỚI THIỆU ▪ CẤU TRÚC CHƯƠNG TRÌNH ▪ ĐỐI TƯỢNG DỮ LIỆU ▪ CÁC KIỂU DỮ LIỆU VÀ CÁC PHÉP TOÁN ▪ CÁC BƯỚC XÂY DỰNG CHƯƠNG TRÌNH ▪ CẤU TRÚC DANH SÁCH ▪ KỸ THUẬT LẬP TRÌNH PROLOG 166
  167. GIỚI THIỆU ▪ Prolog là một ngôn ngữ lập trình dùng cho tính toán ký hiệu. ▪ Thích hợp giải quyết các bài toán liên quan đến đối tượng và quan hệ giữa các đối tượng 167
  168. GIỚI THIỆU ▪ Cho quan hệ gia đình minh mai qua cây gia phả ▪ Node : đối tượng hoàng lan ▪ Cung : quan hệ ▪ Đặt tên quan hệ : chame. lê tâm ▪ chame(X,Y) có nghĩa X là cha/mẹ của Y. hạnh 168
  169. GIỚI THIỆU ▪ Thể hiện bằng Prolog minh mai chame(minh, hoàng). chame(mai, lan). hoàng lan chame(mai, hoàng). chame(hoàng, lê). chame(hoàng, tâm). lê tâm chame(tâm, hạnh). ▪ Có 6 mệnh đề (clause) hạnh 169
  170. GIỚI THIỆU ▪ Làm được gì với đoạn chương trình trên ? ▪ Hỏi các câu hỏi. ▪ Cho phép hỏi về những quan hệ đã được thiết lập trong chương trình. ▪ Loại 1 : Có hay không ? ▪ hoàng có phải là cha/mẹ của tâm không ? ▪ lan có phải là cha/mẹ của hoàng không ? ▪ Loại 2 : Xác định (tìm tất cả) ▪ Ai là cha/mẹ của hạnh ? ▪ Ai là con của mai ? ▪ Xác định các cặp cha/mẹ con ? ▪ 170
  171. GIỚI THIỆU ▪ Loại 1 : Có hay không ? ▪ hoàng có phải là cha/mẹ của tâm không ? ▪ ?- chame(hoàng, tâm). minh mai ▪ lan có phải là cha/mẹ của hoàng không ? ▪ ?- chame(lan, hoàng). ▪ Loại 2 : Xác định. hoàng lan ▪ Ai là cha/mẹ của hạnh ? ▪ ?-chame(X, hạnh). lê tâm ▪ Ai là con của mai ? ▪ ?-chame(mai, X). ▪ Xác định tất cả các cặp cha/mẹ con ? hạnh ▪ ?-chame(X,Y). 171
  172. GIỚI THIỆU ▪ Các đối tượng trong một quan hệ có thể là : đối tượng cụ thể hoặc đối tượng chung. ▪ hoàng, tâm trong chame(hoàng, tâm) : đối tượng cụ thể, gọi là atom (nguyên tố). ▪ X trong chame(X, hạnh) hoặc X, Y trong chame(X, Y) : đối tượng chung, gọi là variable (biến). ▪ Biến bắt đầu bằng chữ IN HOA. ▪ Nguyên tố bắt đầu bằng chữ thường. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 172
  173. GIỚI THIỆU ▪ Mở rộng câu hỏi: ▪ Ai là ông/bà của hạnh ? X ▪ Giải quyết: chame ▪ Giả sử X là kết quả cần tìm. ▪ Khi đó, X là cha/mẹ của Y và Y là cha/mẹ của hạnh. Y ▪ Vậy : cần tìm X, Y thoả : chame ongba ▪ chame (X,Y) and chame(Y, hạnh) ▪ Thể hiện bằng Prolog : hạnh ▪ ?-chame(X, Y), chame(Y, hạnh) ▪ Tương tự : Ai là cháu của mai ? Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 173
  174. GIỚI THIỆU ▪ Chương trình bao gồm các mệnh đề (clause), kết thúc bằng dấu chấm (.). ▪ Tham số của quan hệ có thể là : đối tượng đã biết (nguyên tố, atom) hoặc đối tượng chung (biến, variable). ▪ Biến bắt đầu bằng chữ in hoa. ▪ Các câu hỏi có thể có một hoặc nhiều mục tiêu (goal). ▪ Các câu hỏi có thể có dạng (1): có/không (thoả hay không thoả) ; (2) tìm tất cả (nếu thoả). Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 174
  175. GIỚI THIỆU ▪ Với đoạn chương trình bên cạnh, hãy trả lời : ▪ Đoạn chương trình: ▪ ?-chame(hoàng,X). chame(minh, hoàng). ▪ ?-chame(X, lan). chame(mai, lan). ▪ ?-chame(minh, X), chame(X, tâm). chame(mai, hoàng). ▪ ?-chame(minh,X), chame(X,Y), chame(hoàng, lê). chame(Y, hạnh) chame(hoàng, tâm). ▪ Viết dạng Prolog các câu hỏi sau: chame(tâm, hạnh). ▪ Ai là cha/mẹ của tâm ? ▪ tâm có con không ? ▪ hạnh có con không ? ▪ Ai là ông/bà của lê ? 175
  176. GIỚI THIỆU ▪ Bổ sung 2 quan hệ mới : nam, nu. ▪ Ví dụ : ▪ nam(minh). ▪ nam(hoàng). ▪ nu(lan). ▪ nu(mai). ▪ ▪ Quan hệ nam, nu là các quan hệ một ngôi. (Chỉ thuộc tính của đối tượng) ▪ Quan hệ chame là quan hệ hai ngôi. (Chỉ mối liên hệ giữa các đối tượng) 176
  177. GIỚI THIỆU ▪ Bổ sung thêm quan hệ con(X,Y). (X là con của Y). (Quan hệ ngược của quan hệ chame). ▪ Ta biết được Với mọi X, Y Y là con của X nếu X là cha/mẹ của Y. ▪ Có thể định nghĩa quan hệ con dựa trên quan hệ chame. ▪ con(Y,X) :- chame(X,Y). ▪ Mệnh đề trên được gọi là quy tắc (rule). 177
  178. GIỚI THIỆU ▪ Quy tắc chỉ đúng khi điều kiện được thoả. ▪ 1 quy tắc có 2 phần : ▪ Phần điều kiện (hay là thân quy tắc (body)) ▪ Phần kết luận (hay là đầu quy tắc (head)) ▪ Ví dụ : ▪ con(Y,X) :- chame(X,Y). Kết luận Điều kiện 178
  179. GIỚI THIỆU ▪ Giả sử có câu hỏi : ?-con(tâm, hoàng) ▪ Prolog giải quyết ra sao ? ▪ 1) Tìm kiếm sự kiện con(tâm, hoàng) ? ▪ (Không có) ▪ 2) Áp dụng quy tắc con(X,Y). ▪ Khởi tạo X = tâm, Y = hoàng. ▪ Sau khởi tạo, ta có quy tắc đặc biệt : ▪ con(tâm, hoàng):- chame(hoàng, tâm) ▪ Phần điều kiện trở thành chame(hoàng,tâm). ▪ Nếu phần điều kiện thoả thì phần kết luận đúng. ▪ chame(hoàng, tâm) là một sự kiện nên có thể kết luận con(tâm, hoàng) đúng. 179
  180. GIỚI THIỆU ▪ Bổ sung các quan hệ mới : cha, nam me, chiemgai, ongba. X ▪ Quan hệ cha Với mọi X, Y chame cha X là cha của Y nếu X là cha/mẹ của Y và X thuộc phái nam. Y ▪ cha(X,Y) :- chame(X,Y), nam(X). 180
  181. GIỚI THIỆU ▪ Chương trình Prolog được mở rộng bằng cách thêm các mệnh đề mới. ▪ Mệnh đề gồm phần đầu (head) và phần thân (body). Dấu , trong phần thân chỉ phép và. ▪ Phân loại mệnh đề : sự kiện, quy tắc, câu hỏi ▪ Sự kiện luôn đúng . ▪ Quy tắc chỉ đúng khi điều kiện được thoả. ▪ Người sử dụng hỏi chương trình qua câu hỏi. ▪ Sự kiện chỉ gồm phần đầu. Câu hỏi chỉ có phần thân. Quy tắc có cả phần đầu lẫn phần thân. ▪ Biến có thể thay thế bằng một đối tượng cụ thể. Ta nói biến được khởi tạo. 181
  182. CẤU TRÚC CHƯƠNG TRÌNH ▪ Chương trình Prolog thường gồm các phần : domains predicates clauses goal ▪ Không nhất thiết có đầy đủ các phần 182
  183. CẤU TRÚC CHƯƠNG TRÌNH ▪ domains : phần định nghĩa các kiểu dữ liệu ▪ predicates : phần khai báo các quan hệ (vị từ) ▪ clauses : phần thể hiện các mệnh đề (có thể) của vị từ ▪ goal : đích cần đạt được của chương trình. ▪ goal được viết trong chương trình được gọi là internal goal. ▪ goal thực hiện lúc thực thi (cửa sổ Run) được gọi là external goal. ▪ Các ghi chú trong Prolog nằm trong cặp /* */ hoặc sau dấu % ▪ Trong SWI-Prolog, người sử dụng không cần khai báo kiểu dữ liệu, cấu trúc chương trình không cần các từ khóa trên. 183
  184. ĐỐI TƯỢNG DỮ LIỆU ▪ Gồm các loại : Đối tượng dữ liệu ▪ Nguyên tố (atoms) Đối tượng cơ bản Cấu trúc ▪ Số (numbers) ▪ Biến (variables) Hằng số Biến ▪ Cấu trúc (structures) Nguyên tố Số 184
  185. ĐỐI TƯỢNG DỮ LIỆU – Nguyên tố ▪ Là chuỗi các ký tự ▪ Chữ hoa từ A đến Z ▪ Chữ thường từ a đến z ▪ Chữ số 0, ,9 ▪ Ký tự đặc biệt : + - * / = : . & _ ~ ▪ Dựa trên quy tắc ▪ Chuỗi các chữ cái, chữ số, dấu _ ,bắt đầu bằng một chữ thường (VD : anna, x25, x__y, alpha_beta, ) ▪ Chuỗi các ký tự đặc biệt (VD : , === > , ) ▪ Chuỗi các ký tự nằm trong cặp dấu ‘ ’ (VD : ‘Hoàng’, ‘Hoa’, ) 185
  186. ĐỐI TƯỢNG DỮ LIỆU - Số ▪ Gồm số nguyên và số thực ▪ Ví dụ : Số nguyên : -3, -100, 1, 5 ,2, Số thực : 1.25, -3.25, ▪ Số thực ít được sử dụng trong lập trình Prolog 186
  187. ĐỐI TƯỢNG DỮ LIỆU - Biến ▪ Biến ▪ Chuỗi các chữ cái, chữ số và dấu _, bắt đầu bằng một chữ viết HOA hoặc dấu _. ▪ Ví dụ : X, Result, Object2, _23 ▪ Biến vô danh ▪ Ký hiệu : _ ▪ Nếu biến chỉ xuất hiện một lần, không cần đặt tên. Sử dụng biến vô danh ▪ Ví dụ : haschild(X) :- parent(X,Y). %Biến Y chỉ xuất hiện một lần haschild(X) :- parent(X,_). %Thay thế bằng biến vô danh 187
  188. ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc ▪ Các đối tượng có nhiều thành phần. ▪ Ví dụ : ▪ Đối tượng date có thể xem là một cấu trúc với các thành phần : day, month, year. ▪ Thể hiện bằng Prolog: ▪ Ví dụ : date ▪ date(1,may, 2005) 1 may 2005 188
  189. ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc ▪ Term (hạng) ▪ Tất cả các đối tượng dữ liệu trong Prolog được gọi là term. ▪ Ví dụ : thangnam, ngay(1, thangchin,2005) là các term. ▪ So khớp (matching) ▪ Là thao tác quan trọng nhất trên các term. ▪ Là quá trình kiểm tra xem hai term có khớp nhau hay không. 189
  190. ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc ▪ Hai term được xem là khớp (match) nhau nếu: ▪ Giống nhau hoàn toàn ▪ Các biến trong cả hai term được khởi tạo thành các đối tượng sao cho sau khi thay thế chúng bằng các đối tượng này thì chúng giống nhau hoàn toàn. ▪ Ví dụ ▪ Cho hai term date(D,M, 2005) và date(D1, thangchin, Y1) được coi là khớp nhau ▪ Ta có : D khởi tạo thành D1, M khởi tạo thành thangchin, còn Y1 khởi tạo thành 2005. 190
  191. ĐỐI TƯỢNG DỮ LIỆU – Cấu trúc ▪ Xác định hai term có khớp nhau hay không? ▪ Nếu S, T là hằng số thì chúng khớp nhau khi chúng cùng một đối tượng. ▪ Nếu S là biến và T bất kỳ. Nếu chúng khớp nhau thì S được khởi tạo thành T và ngược lại. ▪ Nếu S và T là cấu trúc. Chúng khớp nhau khi tất cả các thành phần trong S và T khớp nhau. 191
  192. KIỂU DỮ LIỆU & PHÉP TOÁN KIỂU DỮ LIỆU ▪ char : ký tự ở giữa cặp dấu ‘’. ▪ Ví dụ : ‘a’, ‘b’, ‘1’, ▪ integer : số nguyên (từ -32768 đến 32767) ▪ Ví dụ : 200, -521, 322, ▪ real : số thực ▪ Ví dụ : 25.18, -78.3e+21, 25.5e-20, ▪ string : chuỗi dài tối đa 64KB, nằm cặp dấu “”. ▪ Ví dụ : “chào các bạn”, “Prolog” ▪ symbol : chuỗi dài tối đa 80 ký tự, có thể không có dấu “”. ▪ Ví dụ : prolog, “Prolog”, chao_cac_ban, 192
  193. KIỂU DỮ LIỆU & PHÉP TOÁN PHÉP TOÁN TRONG SWI-PROLOG ▪ Phép toán số học : +, -, *, /, mod, //, ▪ Biểu thức số học: được xây dựng nhờ vị từ is Number is Expr Number: đối tượng cơ bản Expr: biểu thức số học được xây dựng từ các phép toán số học, các số và các biến. ▪ Phép so sánh số học : >, =, <=, =\= ▪ Các hàm số học: sin, cos, tan, arctan, ln, log, exp, sqrt, round, trunc, abs 193
  194. KIỂU DỮ LIỆU & PHÉP TOÁN Trong SWI-Prolog, có các vị từ xác định kiểu dữ liệu: ▪ var(V) V là một biến? ▪ nonvar(X) X không phải là một biến? ▪ atom(A) A là một nguyên tố? ▪ integer(I) I là một số nguyên? ▪ float(R) R là một số thực(dấu chấm động)? ▪ number(N) N là một số (nguyên hoặc thực)? ▪ atomic(A) A là một nguyên tố hoặc một số? ▪ compound(X) X là một term có cấu trúc? Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 194
  195. CÁC BƯỚC XÂY DỰNG ▪ Tìm USCLN của 2 số a,b >0 Sử dụng thuật toán Euclide ▪ USCLN của X và X là X. ▪ USCLN của X và Y là USCLN của X – Y và Y nếu X>Y. ▪ USCLN của X và Y là USCLN của Y-X và X nếu X<Y. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 195
  196. CÁC BƯỚC XÂY DỰNG (1) Đặc tả bài toán => xác định mục tiêu cần giải P (2) Biểu diễn bài toán dưới dạng chuẩn => P i(jqij). (3) Chuyển sang mệnh đề Horn (luật, sự kiện) (4) Chuyển sang Prolog Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 196
  197. CÁC BƯỚC XÂY DỰNG (1) uscln(X,Y,Z) Z là USCLN của X,Y. (2) uscln(X,Y,Z) [(X>Y)  (T=X-Y)  uscln(T,Y,Z)]  [(X Y)  (T=X-Y)  uscln(T,Y,Z). uscln(X,Y,Z)  (X<Y)  uscln(X,T,Z)  (T=Y-X). uscln(X,Y,Z)  (Y=X)  (Z=X). Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo 197
  198. CÁC BƯỚC XÂY DỰNG (4) Chuyển sang Prolog uscln (X,Y,Z):-X>Y, T is X-Y, uscln(T,Y,Z). uscln (X,Y,Z):-X Y, is(T, X-Y), uscln(T,Y,Z). uscln (X,Y,Z):-X<Y, is(T, Y-X), uscln(X,T,Z). Thỏa mãn các ràng buộc? 198
  199. CÁC BƯỚC XÂY DỰNG ▪ Tính giai thừa của số N ? 199
  200. CẤU TRÚC DANH SÁCH ▪ Cấu trúc dữ liệu đơn giản, được sử dụng rộng rãi. ▪ Là dãy các phần tử ▪ Ví dụ ▪ Các phần tử : ann, tennis, tom, skiing được biểu diễn thành danh sách [ann, tennis, tom, skiing] 200
  201. CẤU TRÚC DANH SÁCH ▪ Biểu diễn ở 1 trong 2 dạng ▪ Danh sách rỗng : [] ▪ Danh sách không rỗng, gồm 2 phần ▪ Phần tử đầu tiên, gọi là Head ▪ Phần còn lại là một danh sách, gọi là Tail ▪ Ví dụ : ▪ L0 = [] ▪ L1 = [a,b,c] // L1 = [H|T], H = a, T = [b,c] ▪ L2 = [5] // L2 = [H|T], H = 5, T = [] 201
  202. CẤU TRÚC DANH SÁCH ▪ Trong Prolog, danh sách tồn tại dưới các dạng : ▪ [PT1, PT2, , PTn] ▪ [Head| Tail] ▪ [PT1, PT2, | [ ,PTn-1, PTn] ] ▪ Ví dụ ▪ [1,2,3,4,5] ▪ [1|[2,3,4,5]] ▪ [1,2,3|[4,5]] 202
  203. CẤU TRÚC DANH SÁCH ▪ Một số vị từ xử lý danh sách trong SWI-Prolog: append(L1,L2,L3): ghép hai danh sách L1,L2 thành L3 member(E,L): kiểm tra E có phải là phần tử của danh sách L hay không. nextto(X,Y,L): kiểm tra phần tử Y có đứng ngay sau phần tử X trong danh sách L hay không. delete(L1,E,L2): xóa khỏi danh sách L1 những phần tử hợp nhất được với E để trả về kết quả L2. select(E,L,R): lấy phần tử E ra khỏi danh sách L để trả về những phần tử còn lại trong R. nth0(I,L,E): kiểm tra phần tử thứ I(tính từ 0) của danh sách L có phải là E hay không. nth1(I,L,E): kiểm tra phần tử thứ I(tính từ 1) của danh sách L có phải là E hay không. 203
  204. CẤU TRÚC DANH SÁCH last(L,E): kiểm tra phần tử đứng cuối cùng trong danh sách L có phải là E hay không. reverse(L1,L2): nghịch đảo thứ tự các phần tử của danh sách L1 để trả về kết quả L2. permutation(L1,L2): hoán vị danh sách L1 thành danh sách L2. flatten(L1,L2): chuyển danh sách L1 chứa các phần tử bất kỳ thành danh sách phẳng L2. sumlist(L,S): tính tổng các phần tử của danh sách L chứa toàn số để trả về kết quả S. 204
  205. KỸ THUẬT LẬP TRÌNH PROLOG ▪ Bài toán 8 Hậu ▪ Điều khiển quay lui và lát cắt 205
  206. Bài toán 8 Hậu ▪ Bàn cờ vua gồm 8x8 ô ▪ Đặt các con Hậu trên bàn cờ sao cho các con Hậu không tấn công lẫn nhau (theo luật cờ vua). ▪ Hai con Hậu không thể tấn công nhau nếu : ▪ Không cùng dòng ▪ Không cùng cột ▪ Không cùng đường chéo (chính, phụ) 206
  207. Bài toán 8 Hậu X ▪ Vị trí các con Hậu (X) không tấn công lẫn nhau X ▪ (1,5) X ▪ (2,7) X ▪ (3,2) X ▪ (4,6) X ▪ (5,3) X ▪ (6,1) ▪ (7,4) X ▪ (8,8) 207
  208. Bài toán 8 Hậu ▪ Vị trí Hậu : pos(Dong,Cot) ▪ Kết quả thực hiện lưu trong danh sách [pos(X1, Y1), pos(X2, Y2), pos(X3, Y3), pos(X4, Y4), pos(X5, Y5), pos(X6, Y6), pos(X7, Y7), pos(X8, Y8)] ▪ Do các con Hậu không cùng dòng nên ta có thể cố định dòng của chúng như sau : ▪ [pos(1, Y1), pos(2, Y2), pos(3, Y3), pos(4, Y4), pos(5, Y5), pos(6, Y6), pos(7, Y7), pos(8, Y8)] 208
  209. Bài toán 8 Hậu ▪ Danh sách kết quả chấp nhận được nếu : ▪ Các pos(X,Y) trong danh sách không vi phạm điều kiện : cùng cột, cùng đường chéo (chính, phụ) 209
  210. Bài toán 8 Hậu ▪ Kiểm tra lời giải cho bài toán solution(Plist) ▪ Plist = [] là một lời giải hợp lệ ▪ Plist = [pos(X,Y)|Others] là lời giải hợp lệ nếu ▪ Không có hai vị trí Hậu trong Others tấn công lẫn nhau (hay Others cũng là một lời giải hợp lệ) ▪ X,Y có giá trị nằm trong [1,8] ▪ Con Hậu tại vị trí pos(X,Y) không tấn công bất cứ con Hậu nào trong Others. 210
  211. Bài toán 8 Hậu ▪ Kiểm tra lời giải cho bài toán solution([]). solution([pos(X,Y) | Others]):- solution(Others), member(Y,[1,2,3,4,5,6,7,8]), noattack(pos(X,Y), Others). 211
  212. Bài toán 8 Hậu ▪ Hai con Hậu ở pos(X1,Y1) và pos(X2, Y2) không tấn công nhau nếu : ▪ Khác dòng : hiển nhiên (không cần kiểm tra) ▪ Khác cột : Y1 =\= Y2 ▪ Khác đường chéo: ▪ Y2 – Y1 =\= X2 – X1 ▪ Khác đường chéo phụ : ▪ Y2 – Y1 =\= X1 – X2 212
  213. Bài toán 8 Hậu ▪ Tạo danh sách kết quả “mẫu” template([pos(1,_), pos(2,_), pos(3,_), pos(4,_), pos(5,_), pos(6,_), pos(7,_), pos(8,_)]). ▪ Kiểm tra một vị trí đặt hậu pos(X,Y) thật sự không tấn công những con Hậu khác noattack(P, Plist) ▪ Plist = [] => true ▪ Plist = [P1|Plist1] => true nếu P không tấn công P1 và P không tấn công các vị trí trong Plist1 213
  214. Bài toán 8 Hậu ▪ Kiểm tra một vị trí đặt hậu pos(X,Y) thật sự không tấn công những con Hậu khác noattack(_, []). noattack(pos(X,Y), [pos(X1,Y1) | Others]) :- Y =\= Y1, Y1-Y =\= X1-X, Y1-Y=\=X-X1, noattack(pos(X,Y),Others). ▪ Chương trình? 214
  215. Điều khiển quay lui và lát cắt ▪ Prolog tự động quay lui để thoả mãn mục tiêu. ▪ Đây là một công việc hữu ích nhưng có những lúc lại không hiệu quả. ▪ Cần có những cách điều khiển (ngăn) quay lui. 215
  216. Điều khiển quay lui và lát cắt ▪ Mối quan hệ giữa X và Y được xác lập qua 3 luật: ▪ Luật 1: Nếu X < 3 Thì Y = 0 ▪ Luật 2: Nếu 3<=X và X < 6 Thì Y = 2 ▪ Luật 3: Nếu 6<=X Thì Y = 4 216
  217. Điều khiển quay lui và lát cắt ▪ Thể hiện quan hệ X và Y bằng Prolog f(X,0) :- X<3. f(X,2) :- 3<=X, X<6. f(X,4) :- 6<=X. ▪ Dĩ nhiên, khi vị từ f(X,Y) được thực hiện thì giá trị của X đã được khởi tạo. 217
  218. Điều khiển quay lui và lát cắt ▪ Đưa vào một câu hỏi cho đoạn chương trình trên ?- f(1,Y), Y>2. ▪ Kết quả của câu hỏi trên? 218
  219. Điều khiển quay lui và lát cắt ▪ f(1,Y) sẽ cho kết quả Y=0. ▪ Khi đó, Y>2 trở thành 0>2 (=> false). ▪ Vì vậy, goal cho kết quả là : No. ▪ Prolog phải duyệt qua cả 3 mệnh đề của vị từ f. 219
  220. Điều khiển quay lui và lát cắt ▪ Lát cắt: Ký hiệu: ! ▪ Dùng để ngăn Prolog quay lui trong trường hợp đã tìm ra lời giải hoặc sẽ không tìm ra lời giải thêm nếu tiếp tục. 220
  221. Điều khiển quay lui và lát cắt ▪ Thêm lát cắt : f(X,0) :- X 2. ▪ Prolog sẽ cho kết quả ra sao? Thực thi như thế nào? 221
  222. Điều khiển quay lui và lát cắt ▪ Prolog sẽ cho ra cùng kết quả: No. ▪ Không có sử dụng đến mệnh đề (luật) 2 và 3. =>đỡ tốn kém thời gian thực hiện. => tăng hiệu quả cho chương trình. 222
  223. Điều khiển quay lui và lát cắt ▪ Với đoạn chương trình: f(X,0) :- X<3, !. f(X,2) :- 3<=X, X<6, !. f(X,4) :- 6<=X, !. ▪ Cho câu hỏi: ?- f(8, Y). ▪ Cho biết kết quả và phân tích cách thức Prolog thực hiện? 223
  224. Điều khiển quay lui và lát cắt ▪ Dễ dàng nhận thấy kết quả: Y = 4. ▪ Prolog sẽ phải thực hiện cả 3 mệnh đề (luật) của vị từ f. 224
  225. Điều khiển quay lui và lát cắt ▪ Thử luật 1: 8<3 sai, quay lui, thử luật 2 (không bị lát cắt tác dụng). ▪ Thử luật 2: 3<=8 đúng nhưng 8<6 sai, quay lui, thử luật 3 ▪ Thử luật 3: 6<=8 đúng. 225
  226. Điều khiển quay lui và lát cắt ▪ Cải tiến: Nếu X<3 Thì Y=0 Ngược lại, Nếu X < 6 Thì Y=2 Ngược lại, Y=4 ▪ Thể hiện bằng Prolog: f(X,0) :- X<3, !. f(X,2) :- X<6, !. f(X,4). 226
  227. Điều khiển quay lui và lát cắt ▪ Tìm sự khác nhau giữa hai đoạn: f(X,0) :- X<3, !. f(X,2) :- X<6, !. f(X,4). và f(X,0) :- X<3. f(X,2) :- X<6. f(X,4). 227
  228. Điều khiển quay lui và lát cắt ▪ Giả sử goal G có dạng: ▪ P1, P2, P3, ,Pi, !, Pi+1, , Pn ▪ Prolog chỉ tìm một lời giải duy nhất cho các sub- goal P1, P2, P3, ,Pi. ▪ Các sub-goal Pi+1, , Pn vẫn thực hiện (quay lui) bình thường. 228
  229. Điều khiển quay lui và lát cắt ▪ Ví dụ: C :- P, Q, R, !, S, T, U. C :- V. A :- B, C, D. Goal: A ▪ Lát cắt chỉ có tác dụng đối với vị từ C, “ẩn” đối với A. (Trong A, việc quay lui tự động vẫn thực hiện trên B, C, D). 229
  230. Điều khiển quay lui và lát cắt ▪ Tìm số lớn hơn giữa hai số max(A,B,A):-A>B,!. max(A,B,B). 230
  231. Điều khiển quay lui và lát cắt ▪ Thuận lợi: ▪ Lát cắt làm tăng hiệu quả chương trình (tiết kiệm không gian, thời gian, ) ▪ Loại bỏ được những chọn lựa chắc chắn sai. ▪ Có thể thực hiện các luật có dạng: if ĐK1 then KL1 else KL2 231
  232. Điều khiển quay lui và lát cắt ▪ Khó khăn: ▪ Trật tự các mệnh đề trong vị từ có thể ảnh hưởng đến kết quả (khi sử dụng lát cắt) ▪ Ví dụ: Với p :- a,b. p :- c. ▪ p (a  b)  c 232
  233. Điều khiển quay lui và lát cắt ▪ Ví dụ: Trong khi với p :- a, !, b. p :- c. ▪ p (a  b)  ( a  c) Còn p :- c. p :- a, !, b. ▪ p c  (a  b) 233
  234. ÔN TẬP 234