Tập bài giảng Nhập môn trí tuệ nhân tạo

Nội dung text: Tập bài giảng Nhập môn trí tuệ nhân tạo

1. DANH MỤC HÌNH VẼ 4 BẢNG KÝ HIỆU VIẾT TẮT 5 CHƢƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO 6 1.1. Lịch sử phát triển của TTNT 6 1.1.1. Lịch sử hình thành và phát triển 6 1.1.2. Đối tƣợng và mục tiêu nghiên cứu của TTNT 8 1.1.3. Những tiền đề cơ bản của TTNT 8 1.2. Khái niệm về TTNT 9 1.2.1. Trí tuệ của con ngƣời 9 1.2.2. Trí tuệ nhân tạo 10 1.3. Vai trò của TTNT trong công nghệ thông tin 11 1.4. Các kỹ thuật TTNT 11 1.5. Các thành phần trong hệ thống TTNT 12 1.6. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT 13 1.6.1. Trò chơi 13 1.6.2. Suy luận và chứng minh định lý tự động 14 1.6.3. Các hệ chuyên gia 15 1.6.4. Hiểu và mô hình hoá ngữ nghĩa ngôn ngữ tự nhiên 17 1.6.5. Mô hình hoá hoạt động của con ngƣời 18 1.6.6. Lập kế hoạch và robotics 19 1.6.7. Các ngôn ngữ và môi trƣờng dùng cho TTNT 20 1.6.8. Máy học 21 1.6.9. Xử lý phân tán song song 22 1.7. Những thách thức đối với TTNT 23 CÂU HỎI CHƢƠNG 1 25 CHƢƠNG 2: CÁC CHIẾN LƢỢC TÌM KIẾM 26 2.1. Biểu diễn vấn đề trong không gian trạng thái 26 2.1.1. Không gian trạng thái của bài toán 26 2.1.2. Các ví dụ 27 2.2. Giới thiệu các chiến lƣợc tìm kiếm 32 2.2.1. Các chiến lƣợc tìm kiếm mù 32 2.2.2. Các chiến lƣợc tìm kiếm kinh nghiệm (tìm kiếm heuristic) 33 2.3. Cây tìm kiếm 33 2.4. Các chiến lƣợc tìm kiếm mù 34 2.4.1. Tìm kiếm theo bề rộng 34 2.4.2. Tìm kiếm theo chiều sâu 38 2.4.3. Các trạng thái lặp 43 2.4.4. Tìm kiếm sâu lặp 43 2.4.5.Tìm kiếm trên đồ thị và/hoặc 47 2.5. Các chiến lƣợc tìm kiếm kinh nghiệm 56 2.5.1. Hàm đánh giá và tìm kiếm kinh nghiệm 56 2.5.2 Tìm kiếm tốt nhất đầu tiên 58 2.5.3. Tìm kiếm leo đồi 61 2.6. Các chiến lƣợc tìm kiếm tối ƣu 64 2.6.1. Thuật toán A* 66 2.6.2. Thuật toán nhánh_cận 70 2.7. Các giải thuật tìm kiếm lời giải cho trò chơi 74 2.7.1. Cây trò chơi đầy đủ 74 1
2. 2.7.2. Giải thuật Minimax 76 2.7.3. Giải thuật Minimax với độ sâu hạn chế 78 2.7.4. Giải thuật Minimax với cắt tỉa Alpha-Beta 80 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 83 CHƢƠNG 3. LOGIC MỆNH ĐỀ 95 3.1. Biểu diễn tri thức 95 3.2. Cú pháp và ngữ nghĩa của logic mệnh đề 96 3.2.1. Các ký hiệu 96 3.2.2. Các quy tắc xây dựng các công thức 97 3.2.2. Ngữ nghĩa 97 3.3. Dạng chuẩn tắc 99 3.3.1. Sự tƣơng đƣơng của các công thức 99 3.3.2. Dạng chuẩn tắc 100 3.3.3. Các câu Horn 101 3.4. Luật suy diễn 102 3.4. Luật phân giải. Thủ tục chứng minh bác bỏ bằng luật phân giải 105 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 113 CHƢƠNG 4: LOGIC VỊ TỪ 119 4.1. Cú pháp và ngữ nghĩa của logic vị từ 119 4.1.1. Cú pháp 119 4.1.2. Ngữ nghĩa 121 4.2. Các công thức tƣơng đƣơng 123 4.3. Chuẩn hóa các công thức 124 4.4. Các luật suy diễn 126 4.4.1. Luật thay thế phổ dụng 126 4.4.2. Hợp nhất 126 4.4.3. Luật Modus Ponens tổng quát 127 4.4.4. Luật phân giải tổng quát 128 4.5. Thuật toán hợp nhất 129 4.6. Chứng minh bằng luật phân giải 131 4.7. Các chiến lƣợc phân giải 137 4.7.1. Chiến lƣợc phân giải theo bề rộng 139 4.7.2. Chiến lƣợc phân giải sử dụng tập hỗ trợ 139 4.7.3. Chiến lƣợc tuyến tính 141 4.8. Xây dựng CSTT 141 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 4 144 CHƢƠNG 5. BIỂU DIỄN TRI THỨC 148 5.1. Các dạng mô tả tri thức 148 5.1.1. Biểu diễn tri thức bằng logic 148 5.1.2. Biểu diễn tri thức bằng mạng ngữ nghĩa 148 5.1.3. Biểu diễn tri thức bằng khung (Frame) 149 5.1.4. Biểu diễn tri thức bằng các luật nếu - thì 149 5.2. Lập luận tiến 151 5.2.1. Khái niệm 151 5.2.2. Thủ tục lập luận tiến 153 5.3. Lập luận lùi 158 5.3.1. Khái niệm lập luận lùi 158 5.3.2. Thủ tục lập luận lùi 160 2
3. 5.4. Lập trình Prolog 166 5.4.1. Giới thiệu ngôn ngữ Prolog 166 5.4.2. Cú pháp Prolog 167 5.4.3. Các kiểu dữ liệu sơ cấp của Prolog 169 5.4.4. Sự kiện và luật trong Prolog 170 5.4.5. Kiểu dữ liệu cấu trúc của Prolog 182 5.4.6. Ngữ nghĩa của chƣơng trình Prolog 184 5.4.7. Các phép toán 190 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 5 203 HƢỚNG DẪN GIẢI BÀI TẬP 205 1. Bài tập Chƣơng 2 205 2. Bài tập Chƣơng 3 238 3. Bài tập Chƣơng 4 248 4. Bài tập Chƣơng 5 256 TÀI LIỆU THAM KHẢO 259 3
4. DANH MỤC HÌNH VẼ Hình 1.1. Những tiền đề cơ bản của TTNT 9 Hình 2.1. Mô tả không gian trạng thái bằng đồ thị định hƣớng 27 Hình 2.2. Trò chơi 8 số 28 Hình 2.3. Đồ thị biểu diễn cách rót nƣớc 30 Hình 2.4. Biểu diễn không gian trạng của bài toán Tháp Hà Nội. 31 Hình 2.5. Một phần không gian trạng thái của bài toán với n=3 32 Hình 2.6. Đồ thị không gian trạng thái và cây tìm kiếm tƣơng ứng 34 Hình 2.7. Đồ thị không gian trạng thái 36 Hình 2.8. Đồ thị không gian trạng thái 40 Hình 2.9. Đồ thị không gian trạng thái ví dụ 2.13 45 Hình 2.10. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.13 46 Hình 2.11. Đồ thị không gian trạng thái ví dụ 2.14 46 Hình 2.12. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.14 47 Hình 2.13. Quy một tích phân về các tích phân cơ bản 48 Hình 2.14. Bản đồ nối các thành phố 48 Hình 2.15. Đồ thị và/hoặc và vấn đề tìm đƣờng đi 49 Hình 2.16. Đồ thị và hoặc biểu diễn toán tử a b, c, d 49 Hình 2.17. Minh họa đồ thị và/hoặc 50 Hình 2.18. Cây nghiệm 51 Hình 2.19. Đồ thị và/ hoặc trong Ví dụ 2.16 54 Hình 2.20. Cây nghiệm trong ví dụ 2.16 55 Hình 2.21. Cây nghiệm trong ví dụ 2.17 56 Hình 2.22. Hai hàm đánh giá trạng thái u 57 Hình 2.23. Đồ thị không gian trạng thái 58 Hình 2.24. Cây tìm kiếm tốt nhất – đầu tiên 59 Hình 2.25. Đồ thị không gian trạng thái 60 Hình 2.26. Một phần đồ thị không gian trạng thái của ví dụ 2.22 61 Hình 2.27. Đồ thị không gian trạng thái 63 Hình 2.28. Đồ thị không gian trạng thái 64 Hình 2.29. Đồ thị không gian trạng thái với hàm đánh giá 66 Hình 2.30. Cây tìm kiếm theo thuật toán A* 67 Hình 2.31. Đồ thị không gian trạng thái 69 Hình 2.32. Cây tìm kiếm nhánh _cận 72 Hình 2.33. Đồ thị không gian trạng thái 73 4
5. Hình 4.1. Đồ thị phân giải 138 Hình 4.2. Một cây chứng minh từ đồ thị phân giải trong Hình 4.2 139 Hình 4.3. Một cây chứng minh tìm đƣợc theo chiến lƣợc bề rộng 139 Hình 4.4. Đồ thị phân giải theo chiến lƣợc sử dụng tập hỗ trợ 140 Hình 5.1. Biểu diễn tri thức bằng mạng ngữ nghĩa. 148 Hình 5.2. Các kiểu dữ liệu trong Prolog 168 Hình 5.3. Cây gia hệ 170 Hình 5.4. Định nghĩa quan hệ chị em gái 176 Hình 5.5. (a) X là tổ tiên trực tiếp của Z, (b) X là tổ tiên gián tiếp của Z 179 Hình 5.6. Các cặp tổ tiên hậu duệ gián tiếp ở các mức khác nhau 180 Hình 5.7. Ngày tháng là một đối tƣợng có cấu trúc 182 Hình 5.8. Mô hình vào/ra của một thủ tục thực hiện một danh sách các đích 189 BẢNG KÝ HIỆU VIẾT TẮT STT Ký hiệu Ý nghĩa 1 TTNT Trí tuệ nhân tạo 2 CSTT Cơ sở tri thức 3 NSD Ngƣời sử dụng 5
6. CHƢƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO 1.1. Lịch sử phát triển của TTNT 1.1.1. Lịch sử hình thành và phát triển Trong lĩnh vực Công nghệ thông tin, Trí tuệ nhân tạo (Artificial Intelligence) là một ngành mới, nhƣng phát triển rất mạnh mẽ và đem lại nhiều kết quả to lớn. Lịch sử của TTNT cho thấy ngành khoa học này có nhiều kết quả đáng ghi nhận. Theo các mốc phát triển, ngƣời ta thấy TTNT đƣợc sinh ra từ những năm 50 của thế kỷ 20 với các sự kiện sau: Turing đƣợc coi là ngƣời khai sinh ngành TTNT bởi phát hiện của ông về máy tính có thể lƣu trữ chƣơng trình và dữ liệu. Phép thử Turing là một cách để trả lời câu hỏi „máy tính có biết nghĩ không?‟, đƣợc phát biểu dƣới dạng một trò chơi. Hình dung có ba ngƣời tham gia trò chơi, một ngƣời đàn ông (A), một ngƣời đàn bà (B) và một ngƣời chơi (C). Ngƣời chơi ngồi ở một phòng tách biệt với A và B, không biết gì về A và B (nhƣ hai đối tƣợng ẩn X và Y) và chỉ đặt các câu hỏi cũng nhƣ nhận trả lời từ A và B qua một màn hình máy tính. Ngƣời chơi cần kết luận trong X và Y ai là đàn ông ai là đàn bà. Trong phép thử này, A luôn tìm cách làm cho C bị nhầm lẫn và B luôn tìm cách giúp C tìm đƣợc câu trả lời đúng. Phép thử Turing thay A bằng một máy tính, và bài toán trở thành liệu C có thể phân biệt đƣợc trong X và Y đâu là máy tính đâu là ngƣời đàn bà. Phép thử Turing cho rằng máy tính là thông minh (qua đƣợc phép thử) nếu nhƣ biết cách làm sao cho C không thể chắc chắn kết luận của mình là đúng. Tuy phép thử Turing đến nay vẫn đƣợc xem có tầm quan trọng lịch sử và triết học hơn là giá trị thực tế (vì con ngƣời vẫn chƣa làm đƣợc máy hiểu ngôn ngữ và biết lập luận nhƣ vậy), ý nghĩa rất lớn của nó nằm ở chỗ đã nhấn mạnh rằng khả năng giao tiếp thành công của máy với con ngƣời trong một cuộc đối thoại tự do và không hạn chế là một biểu hiện chính yếu của trí thông minh nhân tạo. Tháng 8/1956 J.Mc Carthy, M. Minsky, A. Newell, Shannon. Simon đƣa ra khái niêm"Trí tuệ nhân tạo”. Vào khoảng năm 1960 tại Đại học MIT (Massachussets Institure of Technology) ngôn ngữ LISP ra đời, phù hợp với các nhu cầu xử lý đặc trƣng của TTNT - đó là ngôn ngữ lập trình đầu tiên dùng cho TTNT. Thuật ngữ TTNT đƣợc dùng đầu tiên vào năm 1961 cũng tại MIT. Những năm 60 là giai đoạn lạc quan cao độ về khả năng làm cho máy tính biết suy nghĩ. Trong giai đoạn này ngƣời ta đã đƣợc chứng kiến máy chơi cờ đầu tiên và các chƣơng trình chứng minh định lý tự động. Cụ thể: - 1961: Chƣơng trình tính tích phân bất định 6
7. - 1963: Các chƣơng trình Heuristics: Chƣơng trình chứng minh các định lý hình học không gian có tên là"tƣơng tự”, chƣơng trình chơi cờ của Samuel. - 1964: Chƣơng trình giải phƣơng trình đại số sơ cấp, chƣơng trình trợ giúp ELIZA (có khả năng làm việc giống nhƣ một chuyên gia phân tich tâm lý). - 1966: Chƣơng trình phân tích và tổng hợp tiếng nói. Tuy nhiên, do giới hạn khả năng của các thiết bị, bộ nhớ và đặc biệt là yếu tố thời gian thực hiện nên có sự khó khăn trong việc tổng quát hoá các kết quả cụ thể vào trong một chƣơng trình mềm dẻo thông minh. Vào những năm 70, máy tính với bộ nhớ lớn và tốc độ tính toán nhanh nhƣng các phƣơng pháp tiếp cận TTNT cũ vẫn thất bại (do sự bùng nổ tổ hợp trong quá trình tìm kiếm lời giải các bài toán đặt ra). Vào cuối những năm 70 một vài kết quả nhƣ xử lý ngôn ngữ tự nhiên, biểu diễn tri thức và giải quyết vấn đề. Những kết quả đó đã tạo điều kiện cho sản phẩm thƣơng mại đầu tiên của TTNT ra đời đó là Hệ chuyên gia, đƣợc đem áp dụng trong các lĩnh vực khác nhau (Hệ chuyên gia là một phần mềm máy tính chứa các thông tin và tri thức về một lĩnh vực cụ thể nào đó, có khả năng giải quyết những yêu cầu của ngƣời sử dụng trong một mức độ nào đó, ở một trình độ nhƣ một chuyên gia con ngƣời có kinh nghiệm khá lâu năm). Một sự kiện quan trọng vào những năm 70 là sự ra đời ngôn ngữ Prolog, tƣơng tự LISP nhƣng nó có cơ sở dữ liệu đi kèm. Vào những năm 80, thị trƣờng các sản phẩm dân dụng đã có khá nhiều sản phẩm ở trình độ cao nhƣ: máy giặt, máy ảnh sử dụng TTNT. Các hệ thống nhận dạng và xử lý ảnh, tiếng nói. Những năm 90, các nghiên cứu nhằm vào cài đặt thành phần thông minh trong các hệ thống thông tin, gọi chung là cài đặt TTNT, làm rõ hơn các ngành của khoa học TTNT và tiến hành các nghiên cứu mới, đặc biệt là nghiên cứu về cơ chế suy lý, về TTNT phân tạo, về các mô hình tƣơng tác. Hiện nay, nhiều lĩnh vực mới của TTNT đã ra đời và tiến triển sôi động theo sự thay đổi của môi trƣờng tính toán và tiến bộ khoa học. Chẳng hạn sự xuất hiện của những hệ dữ liệu lớn với quan hệ phức tạp nhƣ dữ liệu Web, dữ liệu sinh học, thƣ viện điện tử đã là động lực ra đời các ngành khai phá dữ liệu, Web ngữ nghĩa, tìm kiếm thông tin trên Web. Thêm nữa, TTNT đã thâm nhập từ các khoa học vi mô nhƣ góp phần giải các bài toán của sinh học phân tử (tin-sinh học) đến các khoa học vĩ mô nhƣ nghiên cứu vũ trụ, rồi cả khoa học xã hội và kinh tế nhƣ phát hiện các cộng đồng mạng trong xã hội hay phân tích các nhóm hành vi. Trong các thành công của TTNT giai đoạn này có sự kiện máy tính thông minh tranh tài với các kỳ thủ cờ vua, và đặc biệt máy tính 7
8. Deep Blue của IBM với trí tuệ nhân tạo đã đánh bại nhà vô địch cờ vua thế giới Garry Kasparov vào năm 1997, và cuối năm 2006 máy tính Deep Fritz lại đánh bại nhà vô địch Kramnik. Một lĩnh vực tiêu biểu của TTNT trong giai đoạn này là các tác nhân thông minh. Tác nhân (agent), theo nghĩa chung nhất, là một thực thể có khả năng hành động để thực hiện những nhiệm vụ đƣợc giao. Một ngƣời đƣa hàng, một luật sƣ hay một điệp viên là những tác nhân. Một robot cứu ngƣời sau động đất hay một robot hút bụi trong nhà là những tác tử. Một chƣơng trình đƣợc cài trên máy tính để lọc thƣ rác hay một chƣơng trình luôn xục xạo trên Internet để tìm những thông tin mới về một chủ đề là những tác tử. tác nhân thông minh là những tác nhân biết hành động với các phẩm chất của trí thông minh, tiêu biểu là biết nhận thức môi trƣờng xung quanh và biết hƣớng các hành động tới việc đạt mục đích. Một robot hút bụi sẽ là thông minh nếu biết tìm đến các chỗ bẩn trong phòng để hút bụi và không đi tới những chỗ đã làm. 1.1.2. Đối tượng và mục tiêu nghiên cứu của TTNT TTNT nghiên cứu về cách hành xử thông minh với mục tiêu là xây dựng lý thuyết đầy đủ để có thể giải thích đƣợc hoạt động thông minh của sinh vật và áp dụng đƣợc các hiểu biết vào các máy móc nói chung, nhằm phục vụ cho con ngƣời. - Về mặt kỹ thuật: Tạo ra các máy thông minh để giải quyết vấn đề thực tế dùng các kỹ thuật TTNT. - Về mặt khoa học: Phát triển các khái niệm và thuật ngữ để hiểu đƣợc các hành xử thông minh của sinh vật. 1.1.3. Những tiền đề cơ bản của TTNT Những tiền đề ban đầu cho sự ra đời của TTNT là những nghiên cứu lý thuyết sâu sắc của các chuyên gia về logic hình thức, tâm lý học nhận thức (cognitive Psychology) và điều khiển học (Cybernetics). A Turing, ngƣời đặt nền móng lý thuyết cho tin học, tác giả của mô hình máy tính vạn năng đã đƣa ra mô hình máy tính dựa trên những phép tính logic cơ bản: AND, OR và NOT. Khi đó dự án này không đƣợc chấp nhận. Do chịu ảnh hƣởng của các chuyên gia Mỹ, ngƣời ta đã tiến hành chế tạo ra những máy tính đầu tiên, thực hiện các phép tính số học cơ bản. Dầu vậy, một nhóm các chuyên gia tin học vẫn tiếp tục nghiên cứu khả năng của máy tính xử lý các dữ liệu phi số, các ký hiệu. Một cách độc lập, các chuyên gia tâm lý học nhận thức cũng đã tạo dựng những mô hình dùng máy tính để mô phỏng hành vi của con ngƣời khi giải quyết những bài toán đòi hỏi sự sáng tạo. Lúc đó, các chƣơng trình TTNT lại quá phức tạp, quá tốn kém nên không thể đƣa ra áp dụng trong thực tiễn. 8
9. Những tiến bộ trong kỹ thuật vi điện tử đã tạo nên tiền đề vật chất có tính chất quyết định, làm thay đổi toàn bộ sự phát triển và ứng dụng các kỹ thuật TTNT Hình 1.1. Những tiền đề cơ bản của TTNT 1.2. Khái niệm về TTNT 1.2.1. Trí tuệ của con người Trí tuệ con ngƣời (Human Intelligence): Cho đến nay có hai khái niệm về trí tuệ con ngƣời đƣợc chấp nhận và sử dụng nhiều nhất, đó là: Khái niệm trí tuệ theo quan điểm của Turing:"Trí tuệ là những gì có thể đánh giá đƣợc thông qua các trắc nghiệm thông minh”. Khái niệm trí tuệ đƣa ra trong từ điển Bách khoa toàn thƣ: “Trí tuệ là khả năng: - Phản ứng một cách thích hợp những tình huống mới thông qua hiệu chỉnh hành vi một cách thích đáng; - Hiểu rõ những mối liên hệ qua lại của các sự kiện của thế giới bên ngoài nhằm đƣa ra những hành động phù hợp đạt tới một mục đích nào đó". Những nghiên cứu các chuyên gia tâm lý học nhận thức chỉ ra rằng quá trình hoạt động trí tuệ của con ngƣời bao gồm 4 thao tác cơ bản: (1) Xác định tập đích (goals). (2) Thu thập các sự kiện (facts) và các luật suy diễn (inference rules) để đạt đƣợc đích đặt ra. 9
10. (3) Thu gọn (pruning) quá trình suy luận nhằm xác định tập các suy diễn có thể sử dụng đƣợc. (4) Áp dụng các cơ chế suy diễn cụ thể (inference mechanisms) để đƣa các sự kiện ban đầu đi đến đích. 1.2.2. Trí tuệ nhân tạo Có nhiều khái niệm được đưa ra về trí tuệ nhân tạo: •"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"(“The study of mental faculties through the use ò computational models"– Charniak and McDormott, 1985). •"Nghệ thuật tạo ra các máy thực hiện các chức năng đòi hỏi sự thông minh khi đƣợc thực hiện bởi con ngƣời"(“The art of creating machies that perform functions that require intelligence when performed by people"– Kurzweil, 1990). •"Lĩnh vực nghiên cứu tìm cách giải quyết và mô phỏng các hành vi thông minh trong thuật ngữ các quá trình tính toán"(“A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes"– Schalkoff, 1990). •"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"(“The study of computations that make it possible to perceive, reason, and act"– Winston, 1992). •"Một nhánh của khoa học máy tính liên quan tới sự tự động hoá các hành vi thông minh"(“The branch of computer science that is concerned with the automation of intelligent behavior"– Luger and Stubblefield, 1993) Sau đây là một số định nghĩa gần đây nhất: •"TTNT là sự thiết kế và nghiên cứu các chƣơng trình máy tính ứng xử một cách thông minh. Các chƣơng trình này đƣợc xây dựng để thực hiện các hành vi mà khi ở ngƣời hoặc động vật chúng ta xem là thông minh"(“Artificial Intelligence is the design and study of computer programs that behave intelligently.These programs are constructed to perform as would a human or an animal whose behvior we consider intelligent"– Dean, Allen and Aloimonos, 1995). •"TTNT là sự nghiên cứu các tác nhân tồn tại trong môi trƣờng, nhận thức và hành động"(“Artificial Intelligence is the design of agents that exists in an environment and act"– Russell and Norvig, 1995). •"TTNT là sự nghiên cứu ác thiết kế các tác nhân thông minh"(“Computational Intelligence is the study of the design of Intelligent agents"– Pulle, Mackworth and Goebel, 1998). 10
11. • Hiện nay nhiều nhà nghiên cứu quan niệm rằng, TTNT là lĩnh vực nghiên cứu sự thiết kế các tác nhân thông minh (intelligent agent). 1.3. Vai trò của TTNT trong công nghệ thông tin TTNT bao quát rất nhiều lĩnh vực nghiên cứu hẹp. Nó nghiên cứu từ các lĩnh vực tổng quát nhƣ máy nhận biết, suy luận logic, đến các bài toán nhƣ chơi cờ, chứng minh định lý. Thƣờng thì các nhà khoa học ở các lĩnh vực khác tìm đến với TTNT ở các kỹ thuật hệ thống hoá và tự động hoá các xử lý tri thức cũng nhƣ các phƣơng pháp thuộc lĩnh vực mang tính ngƣời. TTNT nghiên cứu kỹ thuật làm cho máy tính có thể"suy nghĩ một cách thông minh"và mô phỏng quá trình suy nghĩ của con ngƣời khi đƣa ra những quyết định, lời giải. Trên cơ sở đó, thiết kế các chƣơng trình cho máy tính để giải quyết bài toán. Sự ra đời và phát triển của TTNT đã tạo ra một bƣớc nhảy vọt về chất trong kỹ thuật và kỹ nghệ xử lý thông tin. TTNT chính là cơ sở của công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền thống dựa trên văn bản giấy tờ. Điều này đƣợc thể hiện qua các mặt sau: - Nhờ những công cụ hình thức hoá (các mô hình logic ngôn ngữ, logic mờ, ), các tri thức thủ tục và tri thức mô tả có thể biểu diễn đƣợc trong máy. Do vậy quá trình giải bài toán đƣợc tiến hành hữu hiệu hơn. - Mô hình logic ngôn ngữ đã mở rộng khả năng ứng dụng của máy tính trong lĩnh vực đòi hỏi tri thức chuyên gia ở trình độ cao, rất khó nhƣ: y học, sinh học, địa lý, tự động hóa. - Một số phần mềm TTNT thể hiện tính thích nghi và tính mềm dẻo đối với các lớp bài toán thuộc nhiều lĩnh vực khác nhau. - Khi máy tính đƣợc trang bị các phần mềm TTNT ghép mạng sẽ cho phép giải quyết những bài toán cỡ lớn và phân tán. 1.4. Các kỹ thuật TTNT Có nhiều kỹ thuật nghiên cứu, phát triển ngành khoa học TTNT. Tuy vậy, các kỹ thuật TTNT thƣờng khá phức tạp khi cài đặt cụ thể, lý do là các kỹ thuật này thiên về xử lý các ký hiệu tƣợng trƣng và đòi hỏi phải sử dụng những tri thức chuyên môn thuộc nhiều lĩnh vực khác nhau. Do vậy, các kỹ thuật TTNT hƣớng tới khai thác những tri thức về lĩnh vực đang quan tâm đƣợc mã hoá trong máy sao cho đạt đƣợc mức độ tổng quát, dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với ngôn ngữ tự nhiên; dễ sửa đổi, hiệu chỉnh; dễ sử dụng, khai thác nhằm thu hẹp các khả năng cần xét để đi tới lời giải cuối cùng. 11
12. Các kỹ thuật TTNT cơ bản bao gồm: Lý thuyết giải bài toán và suy diễn thông minh: Lý thuyết giải bài toán cho phép viết các chƣơng trình giải câu đố, chơi các trò chơi thông qua các suy luận mang tính ngƣời; các hệ thống chứng minh định lý. Ngoài ra các hệ thống hỏi đáp thông minh còn cho phép lƣu trữ và xử lý khối lƣợng lớn các thông tin. Lý thuyết tìm kiếm may rủi: Lý thuyết này bao gồm các phƣơng pháp và kỹ thuật tìm kiếm với sự hỗ trợ của thông tin phụ để giải bài toán một cách có hiệu quả. Các ngôn ngữ về TTNT: Để xử lý các tri thức ngƣời ta không chỉ sử dụng các ngôn ngữ lập trình dùng cho các xử lý dữ liệu số, mà cần có ngôn ngữ khác. Các ngôn ngữ chuyên dụng này cho phép lƣu trữ và xử lý thông tin ký hiệu. Một số ngôn ngữ đƣợc nhiều ngƣời biết đến là IPL.V, LISP, PROLOG. Lý thuyết thể hiện tri thức và hệ chuyên gia: TTNT là khoa học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, lƣợc đồ, logic vị từ, khung là các phƣơng pháp thể hiện tri thức thông dụng. Việc gắn liền cách thể hiện và sử dụng tri thức là cơ sở hình thành hệ chuyên gia. Lý thuyết nhận dạng và xử lý tiếng nói: Giai đoạn phát triển đầu của TTNT gắn với lý thuyết nhận dạng. Các phƣơng pháp nhận dạng chính gồm: nhận dạng hình học, nhận dạng dùng tâm lý học, nhận dạng theo phƣơng pháp hàm thế, dùng máy nhận dạng, ứng dụng của phƣơng pháp này trong việc nhận dạng chữ viết, âm thanh. Người máy: Ngƣời máy có bộ phận cảm nhận và các cơ chế hoạt động đƣợc nối ghép theo sự điều khiển thông minh. Khoa học về cơ học và TTNT đƣợc tích hợp trong khoa học ngƣời máy. Tâm lý học xử lý thông tin: Các kết quả nghiên cứu của tâm lý học giúp TTNT xây dựng các cơ chế trả lời theo hành vi, có ý thức; nó giúp cho việc thực hiện các suy diễn mang tính ngƣời. Xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui và xử lý cú pháp hình thức: là những kỹ thuật cơ bản của tin học truyền thống có liên quan trực tiếp đến TTNT. 1.5. Các thành phần trong hệ thống TTNT Hai thành phần cơ bản trong bất kỳ một hệ thống TTNT là: - 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. Hai khía cạnh này trong một hệ thống TTNT tƣơng hỗ với nhau rất chặt chẽ, Việc lựa chọn một phƣơng pháp biểu diễn tri thức sẽ quyết định phƣơng pháp giải quyết tƣơng ứng để có thể áp dụng đƣợc. Chẳng hạn, nếu tri thức đƣợc biếu diễn dƣới dạng các công thức của logic vị từ, khi đó phƣơng pháp hợp giải (resolution) của Robinson 12
13. khá phù hợp và thƣờng đƣợc dùng để suy diễn. Ngƣợc lại, nếu phƣơng pháp biễu diễn tri thức là mạng ngữ nghĩa thì các thủ tục tìm kiếm sẽ hiệu quả hơn. Mặc dù phƣơng pháp biểu diễn tri thức sử dụng cú pháp chặt chẽ thƣờng rất hiệu quả cho việc biểu diễn và điều khiển quá trình suy diễn, nhƣng chúng lại không đủ mạnh để khắc phục bùng nổ tổ hợp khi giải những bài toán khó. Trong trƣờng hợp đó, các thủ tục tìm kiếm heuristics dựa trên các tri thức đặc tả nảy sinh từ chính bản thân cấu trúc của bài toán trở nên rất cần thiết. Có thể phân chia các hệ thống TTNT nhƣ sau: 1. Các hệ tìm kiếm thông tin, các hệ thống hỏi đáp thông minh cho phép hội thoại giữa những ngƣời sử dụng đầu cuối không chuyên tin với CSTT và cơ sở dữ liệu thông qua ngôn ngữ chuyên ngành gần với ngôn ngữ tự nhiên. 2. Các hệ thống suy diễn – tính toán, cho phép giải quyết những bài toán phức tạp dựa trên các mô hình toán học và tri thức chuyên gia. 3. Các hệ chuyên gia, cho phép sử dụng các tri thức chuyên gia trong các lĩnh vực tri thức chuyên biệt. 1.6. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT Hai mối quan tâm nền tảng nhất của các nhà nghiên cứu TTNT là biểu diễn tri thức (knowledge representation) và tìm kiếm (search). Biểu diễn tri thức chú ý đến diễn tả vấn đề theo một ngôn ngữ hình thức, tức là một dạng thức thích hợp để máy tính vận hành, phạm vi tri thức đầy đủ mà hành vi thông minh đòi hỏi. Tìm kiếm là kỹ thuật giải quyết vấn đề theo cách khảo sát có hệ thống không gian trạng thái bài toán (problem state). Giống nhƣ hầu hết các ngành khoa học khác, TTNT cũng đƣợc phân thành những ngành con. Trong khi chia sẻ một tiếp cận giải quyết vấn đề cơ bản, các ngành con này có các mối quan tâm đến các ứng dụng khác nhau. Dƣới đây là tổng thể một vài lĩnh vực ứng dụng chính và những đóng góp của chúng cho TTNT. 1.6.1. Trò chơi Ngay từ thời kỳ đầu của việc nghiên cứu vấn đề tìm kiếm trong không gian trạng thái, ngƣời ta đã tiến hành nhiều thử nghiệm bằng cách sử dụng các trò chơi thông dụng có bàn cờ nhƣ cờ đam (checker), cờ vua và trò đố 15 ô (15 puzzule). Hầu hết các trò chơi đều sử dụng một tập hợp các luật chơi đƣợc xác định rõ ràng. Điều này làm cho việc phát sinh không gian tìm kiếm trở nên dễ dàng và giải phóng nhiều nghiên cứu khỏi những sự mơ hồ và phức tạp vốn có trong các bài toán ít cấu trúc hơn. Hình dạng của những bàn cờ sử dụng trong các trò chơi này đƣợc biểu diễn vào máy tính, 13
14. trong khi không đòi hỏi một hình thức khó hiểu cần thiết nào để nắm bắt những tinh tế và ngữ nghĩa trong những lĩnh vực bài toán phức tạp hơn. Các trò chơi có thể phát sinh ra một số lƣợng không gian tìm kiếm cực kỳ lớn. Những không gian này đủ lớn và phức tạp để đòi hỏi những kỹ thuật mạnh nhằm quyết định xem những chọn lựa nào cần đƣợc khảo sát trong không gian bài toán. Những kỹ thuật này đƣợc gọi là các heuristic và chúng tạo thành một lĩnh vực lớn trong nghiên cứu TTNT. Một heuristic là một chiến lƣợc giải quyết vấn đề tốt nhƣng tiềm ẩn khả năng thất bại, chẳng hạn nhƣ việc kiểm tra để biết chắc rằng một thiết bị không nhạy đã đƣợc cắm vào trƣớc khi giả định rằng nó bị hỏng, hay cố gắng bảo vệ quân cờ hoàng hậu khỏi bị bắt trong trò chơi cờ vua. Nhiều thứ mà chúng ta gọi là thông minh thuộc về các heuristic đƣợc ngƣời ta sử dụng để giải quyết các vấn đề. Hầu hết chúng ta đều có một số kinh nghiệm với những trò chơi đơn giản, nên chúng ta cũng có khả năng nghĩ ra và kiểm nghiệm tính hiệu quả của những heuristic của chính mình. Chúng ta không cần đi tìm và hỏi ý kiến chuyên gia trong một số lĩnh vực chuyên môn sâu nhƣ là y học hay toán học. Vì những lý do đó, các trò chơi cung cấp một không gian mênh mông cho việc nghiên cứu các tìm kiếm heuristic. Các chƣơng trình chơi trò chơi, trái ngƣợc với tính đơn giản của chúng, đƣa ra những thử thách riêng của chúng, bao gồm các đấu thủ mà các nƣớc đi của anh ta có thể không dự đoán trƣớc đƣợc một cách chắc chắn. Sự có mặt này của đấu thủ càng làm phức tạp hơn mô hình chƣơng trình do sự thêm vào một yếu tố không dự đoán trƣớc đƣợc và sự cần thiết phải tính đến những yếu tố tâm lý cũng nhƣ là chiến thuật trong chiến lƣợc của trò chơi. 1.6.2. Suy luận và chứng minh định lý tự động Chúng ta có thể cho rằng chứng minh định lý tự động là một nhánh nghiên cứu có từ lâu đời nhất của Trí tuệ nhân tạo khi tìm lại nguồn gốc của nó qua các tác phẩm"Nhà lý luận logic (logic theorist)"(Newell và Simon, 1963) và"Công cụ giải quyết vấn đề tổng quát (General problem solver)"(Newell và Simon, 1965) của Newell và Simon. Trong bất cứ trƣờng hợp nào, nó chắc chắn vẫn là một trong những ngành phong phú nhất của lĩnh vực này. Nghiên cứu chứng minh định lý đã đạt đƣợc nhiều thành tích trong thời kỳ đầu của việc hình thức hoá các giải thuật tìm kiếm và phát triển các ngôn ngữ biểu diễn hình thức nhƣ phép tính vị từ. Ngƣời ta có thể khảo sát một số lƣợng lớn những bài toán khác nhau, bằng cách biểu diễn mô tả của bài toán và những thông tin cơ sở liên quan nhƣ là tiên đề logic, và xem những trƣờng hợp bài toán là những định lý cần phải chứng minh. Sự hiểu biết thấu đáo này là cơ sở cho việc nghiên cứu chứng minh định lý tự động và các hệ suy luận toán học. Một lý do khác 14
15. cho việc tiếp tục quan tâm đến các máy chứng minh định lý tự động là sự nhận thức rằng một hệ thống kiểu nhƣ vậy không nhất thiết phải có khả năng giải quyết những bài toán cực kỳ phức tạp một cách độc lập mà không có sự trợ giúp nào của con ngƣời. Nhiều máy chứng minh định lý hiện đại hoạt động nhƣ những trợ lý viên thông minh khi chúng cho phép con ngƣời thực hiện những công tác đòi hỏi trình độ cao hơn là phân tích một bài toán lớn thành nhiều bài toán con và đặt ra những heuristic để tìm kiếm trong không gian những chứng minh có thể chọn. Máy chứng minh định lý sau đó thực hiện công tác đơn giản hơn nhƣng cũng quan trọng là chứng minh các bổ đề, kiểm chứng những giải quyết nhỏ hơn, và hoàn thành những khía cạnh hình thức của một chứng minh đã đƣợc phác thảo bởi sự hợp tác của nó với con ngƣời (Boyer và More, 1979). 1.6.3. Các hệ chuyên gia Kể từ lúc khoa học giải quyết vấn đề đƣợc nghiên cứu, ngƣời ta đã sớm ý thức một cách sâu sắc và cơ bản về tầm quan trọng của tri thức chuyên ngành. Lấy ví dụ một bác sĩ không thể chẩn đoán bệnh tốt chỉ nhờ vào một số kỹ năng giải quyết vấn đề tổng quát bẩm sinh; mà bác sĩ đã chẩn đoán tốt là vì có nhiều kiến thức y học. Tƣơng tự nhƣ thế, một nhà địa chất giỏi phát hiện các mỏ khoáng vì biết áp dụng một cách hiệu quả nhiều tri thức lý thuyết và thực nghiệm về địa lý. Tri thức chuyên gia về lĩnh vực là sự kết hợp giữa kiến thức lý thuyết về vấn đề đó và một tập hợp các quy tắc giải quyết vấn đề theo kiểu heuristic mà khi sử dụng những quy tắc này đã tỏ ra hiệu quả trong lĩnh vực đó. Các hệ chuyên gia đƣợc ngƣời ta xây dựng bằng cách thu thập các kiến thức từ chuyên gia ngƣời và mã hoá nó thành dạng thức mà máy tính có thể áp dụng cho những bài toán tƣơng tự. Sự tin cậy vào tri thức của chuyên gia chuyên ngành trong các chiến lƣợc giải quyết vấn đề của hệ là một đặc trƣng chính của các hệ chuyên gia. Ngƣời ta đã viết ra một số chƣơng trình mà ở đó ngƣời thiết kế cũng là nguồn tri thức chuyên ngành, nhƣng sẽ điển hình hơn nhiều nếu chúng ta xem xét những chƣơng trình đƣợc phát sinh từ sự cộng tác giữa một chuyên gia chuyên ngành chẳng hạn nhƣ một bác sĩ, một nhà hoá học, một nhà địa chất học hay một kỹ sƣ, với một chuyên gia riêng về trí tuệ nhân tạo. Chuyên gia chuyên ngành cung cấp kiến thức cần thiết về chuyên ngành thông qua những cuộc thảo luận tổng quát về các phƣơng pháp giải quyết vấn đề của anh ta, và bằng cách biểu diễn những kỹ năng đó trên một tập hợp các bài toán mẫu đƣợc chọn lựa cẩn thận. Chuyên gia TTNT, hay còn gọi là kỹ sƣ tri thức (knowledge engineer), nhƣ ngƣời ta vẫn thƣờng gọi là các nhà thiết kế hệ chuyên gia, có trách nhiệm thể hiện tri thức này vào một chƣơng trình mà chƣơng trình đó phải vừa hiệu quả vừa có vẻ 15
16. thông minh trong các hành vi của nó. Một chƣơng trình nhƣ thế vừa hoàn thành xong, cần phải tinh chế kiến thức chuyên môn của nó thông qua một quá trình cung cấp cho nó những bài toán mẫu để giải, để cho chuyên gia chuyên ngành phê bình hành vi của nó và thực hiện bất cứ thay đổi hay cải biến nào cần thiết đối với tri thức của chƣơng trình. Quá trình này lặp đi lặp lại cho đến khi chƣơng trình đạt đƣợc mức độ hoàn thiện mong muốn. Một trong các hệ chuyên gia sớm nhất khai thác tri thức chuyên ngành để giải quyết vấn đề là DENDRAL đƣợc phát triển tại Stanford vào cuối những năm 1960 (Lindsay et al,1980). DENDRAL đƣợc thiết kế để phỏng đoán cấu trúc của các phân tử hữu cơ từ công thức hoá học của chúng và các thông tin về khối quang phổ có liên quan đến các liên kết hoá học có mặt trong các phân tử. Vì các phân tử hữu cơ thƣờng rất lớn, nên số lƣợng cấu trúc có khả năng tồn tại đối với những phân tử này thƣờng là khổng lồ. DENDRAL chú ý vào bài toán của không gian tìm kiếm rộng lớn này bằng cách áp dụng tri thức heuristic của các chuyên gia hoá học vào bài toán làm sáng tỏ cấu trúc. Các phƣơng pháp của DENDRAL đã tỏ ra có một sức mạnh đáng kể. Khi thƣờng xuyên tìm thấy cấu trúc đúng trong hàng triệu khả năng khác nhau chỉ sau có vài phép thử. Phƣơng pháp này tỏ ra thành công đến mức ngƣời ta đã sử dụng những phiên bản của hệ chuyên gia nói trên trong các phòng thí nghiệm hoá học khắp nơi trên thế giới. Trong khi DENDRAL là một trong số những chƣơng trình đầu tiên sử dụng tri thức chuyên ngành một cách hiệu quả để đạt đƣợc khả năng giải quyết vấn đề cấp chuyên gia, thì MYCIN là hệ chuyên gia đã thiết lập nên phƣơng pháp luận cho các hệ chuyên gia hiện đại (contemporary expert systems) (Buchanan and Shortliff, 1984). MYCIN sử dụng tri thức y khoa chuyên gia để chẩn đoán và kê đơn điều trị cho bệnh viêm màng não tuỷ sống và những trƣờng hợp nhiễm trùng vi khuẩn trong máu. MYCIN, đƣợc các nhà nghiên cứu phát triển ở Stanford vào giữa những năm 1970, là một trong những chƣơng trình đầu tiên chú ý đến những bài toán suy luận bằng thông tin không chắc chắn hoặc không đầy đủ. MYCIN cung cấp những giải quyết rõ ràng và logic về quá trình suy luận của nó, sử dụng một cấu trúc kiểm tra thích hợp với lĩnh vực chuyên môn của vấn đề, và nhận biết đặc tính để đánh giá một cách tin cậy hoạt động của nó. Nhiều kỹ thuật xây dựng hệ chuyên gia đang dùng hiện nay đã đƣợc ngƣời ta phát triển lần đầu trong dự án MYCIN. Những hệ chuyên gia cổ điển khác bao gồm chƣơng trình PROSPECTOR dùng để tìm ra những nơi có chứa quặng mỏ và xác định loại quặng mỏ, dựa trên thông tin địa lý về một địa điểm nào đó, chƣơng trình INTERNIST dùng để chẩn đoán trong lĩnh vực nội khoa, Dipmeter Advisor dùng để phiên dịch các kết quả của các máy khoan 16
17. giếng dầu (Smith and Baker, 1983) và XCON dùng để định hình các máy tính hệ VAX. XCON đƣợc sử dụng từ năm 1981, tất cả các máy VAX và Digital Equipment Corporation bán thời bấy giờ đều đƣợc định hình bằng XCON. Rất nhiều hệ chuyên gia khác ngày nay đang giải quyết những bài toán trong nhiều lĩnh vực khác nhau nhƣ y học, giáo dục, kinh doanh, thiết kế và khoa học. Một điều thú vị mà chúng ta có thể nhận thấy là hầu hết các hệ chuyên gia đƣợc viết cho những lĩnh vực khá chuyên biệt và ở cấp độ chuyên gia. Nói chung những lĩnh vực này đều đƣợc nghiên cứu kỹ và chúng có những chiến lƣợc giải quyết vấn đề đã xác định một cách rõ ràng. Mặc dù còn tồn tại những hạn chế này các hệ chuyên gia vẫn đang chứng minh giá trị của chúng trong nhiều ứng dụng quan trọng. 1.6.4. Hiểu và mô hình hoá ngữ nghĩa ngôn ngữ tự nhiên Một trong những mục tiêu có từ lâu đời của Trí tuệ nhân tạo là tạo ra các chƣơng trình có khả năng hiểu ngôn ngữ của con ngƣời. Khả năng hiểu ngôn ngữ tự nhiên không chỉ là một trong những biểu hiện căn bản nhất của trí thông minh con ngƣời mà sự tự động hoá nó một cách thành công sẽ gây ra một tác động ngoài sức tƣởng tƣợng đối với năng lục và hiệu quả chính của những chiếc máy tính. Ngƣời ta đã bỏ ra nhiều công sức để viết các chƣơng trình có khả năng hiểu ngôn ngữ tự nhiên. Tuy những chƣơng trình này đã có đƣợc một số thành công trong những ngữ cảnh hạn chế, nhƣng các hệ thống có khả năng sử dụng ngôn ngữ tự nhiên một cách linh hoạt và tổng quát theo cách nhƣ con ngƣời vẫn còn ở ngoài tầm tay những phƣơng pháp luận hiện nay. Hiểu ngôn ngữ tự nhiên liên quan đến nhiều thứ hơn nhiều so với chỉ phân tích các câu thành các phần riêng rẽ những nhóm câu của chúng và tìm những từ đó trong từ điển. Khả năng hiểu thực sự tuỳ thuộc vào kiến thức nền tảng rộng lớn về lĩnh vực của bài văn và những thành ngữ dùng trong lĩnh vực đó, cũng nhƣ là khả năng ứng dụng những kiến thức tổng quát tuỳ thuộc theo ngữ cảnh để giải quyết những trƣờng hợp bỏ sót hay tối nghĩa, là một đặc điểm bình thƣờng trong lối nói con ngƣời. Công việc tập hợp và tổ chức kiến thức nền tảng này đƣợc tiến hành theo cách mà sao cho cách ấy có thể áp dụng đƣợc cho sự lĩnh hội ngôn ngữ, đã hình thành nên vấn đề chủ yếu của việc tự động hoá quá trình hiểu ngôn ngữ tự nhiên. Để đáp ứng yêu cầu này, các nhà nghiên cứu đã phát triển nhiều kỹ thuật dùng để cấu trúc hoá ý nghĩa ngữ nghĩa, các kỹ thuật này đƣợc dùng xuyên suốt khoa học TTNT. Do việc hiểu ngôn ngữ tự nhiên đòi hỏi những khối lƣợng kiến thức khổng lồ, hầu hết các công trình đƣợc ngƣời ta thực hiện trong những lĩnh vực vấn đề đã đƣợc hiểu rõ và chuyên môn hoá. Một trong những chƣơng trình khai thác sớm nhất phƣơng pháp luận"thế giới qui mô"này là SHRDLU của Winograd, một hệ ngôn ngữ tự nhiên 17
18. có khả năng"trò chuyện"về hình dáng đơn giản của các khối có nhiều hình dạng và màu sắc khác nhau (winograd, 1973). Mặc dù SHRDLU thành công với việc trò chuyện về sự sắp xếp của các khối, nhƣng phƣơng pháp của nó đã không đủ khái quát đƣợc để vƣợt ra khỏi thế giới các khối. Những kỹ thuật biểu diễn đƣợc sử dụng trong chƣơng trình này quá đơn giản nên không đủ để tổ chức nắm bắt ngữ nghĩa của nhiều lĩnh vực phong phú và phức tạp hơn một cách có kết quả. Nhiều sự đầu tƣ nghiên cứu về hiểu ngôn ngữ tự nhiên trong thời gian gần đây đƣợc ngƣời ta dành hết cho việc tìm ra những hình thức biểu diễn, mà về cơ bản đủ dùng trong một phạm vi rộng lớn các ứng dụng mà những ứng dụng này tự bản thân chúng còn chƣa thích nghi tốt với cấu trúc đặc thù của lĩnh vực đó. Ngƣời ta khảo sát một số lƣợng những kỹ thuật khác nhau (hầu hết đều là những mở rộng hay cải tiến của kỹ thuật mạng ngữ nghĩa) cho mục đích này và dùng chúng vào việc phát triển những chƣơng trình có khả năng hiểu ngôn ngữ tự nhiên trong những lĩnh vực tri thức cấp bách nhƣng lý thú. Chẳng hạn, chức năng trợ lý ảo"Siri"trên hệ điều hành IOS,"Cortana"trên hệ điều hành Windows phone là những minh chứng về khả năng hiểu ngôn ngữ tự nhiên (tiếng Anh) đã có nhiều tiến bộ vƣợt bậc. Tuy nhiên, hiểu ngôn ngữ tự nhiên một cách tổng quát là vấn đề vẫn còn vƣợt quá giới hạn hiện nay của chúng ta. 1.6.5. Mô hình hoá hoạt động của con người Mặc dù khá nhiều vấn đề đã nói ở trên dùng trí tuệ con ngƣời làm điểm tựa tham khảo để xem xét TTNT, thực tế đã không diễn biến theo cách mà những chƣơng trình cần phải lấy sự tổ chức của trí óc con ngƣời làm kiểu mẫu cho chúng. Thực ra nhiều chƣơng trình TTNT đƣợc thiết kế để giải một số bài toán cần thiết mà không cần chú ý đến tính tƣơng tự của chúng so với kiến trúc trí óc con ngƣời. Ngay cả các hệ chuyên gia, trong khi nhận đƣợc nhiều tri thức từ các chuyên gia con ngƣời, cũng không thực sự cố gắng bắt chƣớc những quá trình trí tuệ bên trong của con ngƣời. Nếu nhƣ sự hoạt động chỉ là những đặc tính mà theo đó một hệ thống sẽ đƣợc đánh giá, thì có thể là không có mấy lý do để mô phỏng các phƣơng pháp giải quyết vấn đề của con ngƣời. Trong thực tế, những chƣơng trình sử dụng các phƣơng pháp không theo kiểu con ngƣời để giải quyết các bài toán thƣờng thành công hơn những chƣơng trình theo kiểu con ngƣời. Tuy nhiên, mô hình của những hệ thống rõ ràng bắt chƣớc một số khía cạnh của cách giải quyết vấn đề theo kiểu con ngƣời vẫn là một mảnh đất màu mỡ trong nghiên cứu cho cả hai ngành khoa học TTNT và tâm lý học. Mô hình hóa hoạt động con ngƣời, ngoài việc cung cấp cho TTNT nhiều phƣơng pháp luận cơ bản, đã chứng tỏ đƣợc rằng nó là một dụng cụ mạnh để công thức hóa và thử nghiệm những lý 18
19. thuyết về sự nhận thức của con ngƣời. Những phƣơng pháp luận giải quyết vấn đề đƣợc các nhà khoa học máy tính phát triển đã đem đến cho các nhà tâm lý học một sự ẩn dụ mới để khảo sát trí tuệ con ngƣời. Hơn cả việc mở rộng đƣợc các lý thuyết về sự nhận thức trong thứ ngôn ngữ không rõ ràng sử dụng vào đầu thời kỳ nghiên cứu hay là từ bỏ đƣợc bài toán mô tả toàn bộ những hoạt động bên trong của trí óc con ngƣời (nhƣ đề nghị của các nhà hành vi học), nhiều nhà tâm lý học đã đƣa ngôn ngữ và lý thuyết khoa học máy tính vào để công thức hóa các mô hình trí tuệ con ngƣời. Những kỹ thuật này không chỉ cung cấp một vốn từ vựng cho việc mô tả trí tuệ con ngƣời mà sự thể hiện trên máy tính những lý thuyết này đã tạo cho các nhà tâm lý học một cơ hội để thử nghiệm, phê bình và cải tiến một cách thực nghiệm những ý tƣởng của họ (luger, 1994). 1.6.6. Lập kế hoạch và robotics Lập kế hoạch (planning) là một khía cạnh quan trọng trong những cố gắng nhằm chế tạo ra các robot có thể thực hiện đƣợc nhiệm vụ của chúng với một trình độ nhất định và khả năng linh hoạt và phản ứng với thế giới bên ngoài. Nói một cách khác ngắn gọn, việc lập kế hoạch giả định rằng robot có khả năng thực hiện những hành động sơ cấp (atomic action) nhất định. Nó cố gắng tìm ra một chuỗi các hành động cho phép hoàn thành một công tác ở cấp độ cao hơn, chẳng hạn nhƣ đi qua một căn phòng chứa đầy những chƣớng ngại vật. Có nhiều những lý do khiến cho việc lập kế hoạch trở thành một bài toán khó khăn. Ví dụ, chúng ta hãy tƣởng tƣợng rằng, một robot có khả năng di chuyển về phía trƣớc, phía sau, bên phải, bên trái và cần xem xét có bao nhiêu cách khác nhau mà robot đó có thể dùng để di chuyển quanh căn phòng đó và robot phải lựa chọn một đƣờng đi quanh chúng theo một phƣơng pháp nào đó có hiệu quả. Viết một chƣơng trình có khả năng tìm ra đƣờng đi tốt nhất một cách thông minh với điều kiện nhƣ vậy, mà không bị chôn vùi bởi khối lƣợng khổng lồ các khả năng dự kiến, đòi hỏi phải có những kỹ thuật phức tạp để biểu diễn tri thức về không gian và kiểm soát việc tìm kiếm trong môi trƣờng cho phép. Một phƣơng pháp mà con ngƣời vẫn áp dụng để lập kế hoạch là phân rã vấn đề từng bƣớc (hierarchical problem decoposition). Nếu bạn đang lập kế hoạch cho chuyến du lịch đến Pari, thì nói chung những vấn đề nhƣ sắp xếp chuyến bay, đến sân bay, liên hệ với hãng hàng không, vận chuyển đƣờng bộ tại Pari sẽ đƣợc bạn xem xét một cách riêng lẻ, cho dù tất cả chúng đều là bộ phận của một kế hoạch toàn thể lớn hơn. Từng vấn đề này có thể đƣợc tiếp tục phân rã thành những vấn đề con (subproblem) nhỏ hơn nhƣ tìm một bản đồ thành phố, xem xét hệ thống giao thông, và tìm một nơi ăn ở phù 19
20. hợp điều kiện về tài chính. Cách làm này không những làm giảm bớt một cách hiệu quả không gian tìm kiếm mà nó còn cho phép chúng ta tiết kiệm đƣợc những kế hoạch con có thể dùng trong tƣơng lai. Trong khi con ngƣời lập kế hoạch một cách chẳng mấy khó khăn, thì việc tạo ra một chƣơng trình máy tính có thể làm đƣợc công việc nhƣ vậy là một thách thức ghê gớm. Một công tác có vẻ đơn giản là phân rã một vấn đề lớn thành nhiều vấn đề con liên quan thực sự cần đến những heuristic phức tạp và kiến thức bao quát về lĩnh vực đang lập kế hoạch. Quyết định xem cần giữ lại những kế hoạch con nào và tổng quát hóa chúng nhƣ thế nào cho sự sử dụng trong tƣơng lai là một vấn đề phức tạp tƣơng đƣơng. Một robot thực hiện một dãy các hành động một cách mù quáng mà không biết phản ứng lại với những thay đổi trong môi trƣờng hoặc không có khả năng phát hiện và sửa chữa trong chính kế hoạch của nó khó có thể đƣợc ngƣời ta coi là thông minh. Thông thƣờng, một robot sẽ phải làm thành công thức một kế hoạch dựa trên thông tin không đầy đủ và sửa chữa hành vi của nó khi thi hành kế hoạch. Robot có thể không có những giác quan thích hợp để định vị tất cả những chƣớng ngại vật trên con đƣờng đi đã vạch ra. Một robot nhƣ vậy phải bắt đầu di chuyển qua căn phòng dựa vào những gì mà nó"nhận thức"đƣợc và điều chỉnh đƣờng đi của nó khi phát hiện ra những chƣớng ngại vật khác. Thiết lập cho các kế hoạch cho phép có thể phản ứng lại với những điều kiện của môi trƣờng là một nhiệm vụ chủ yếu khác trong lập kế hoạch. Nói chung, thiết kế robot là một trong những lĩnh vực nghiên cứu của TTNT đã mang lại nhiều hiểu biết sâu sắc hỗ trợ cho phƣơng pháp giải quyết vấn đề theo kiểu hƣớng tác nhân (agent - oriented). Bị thất bại bởi những phức tạp trong việc bảo đảm độ lớn của không gian biểu diễn cũng nhƣ bởi mô hình của các thuật toán tìm kiếm dùng cho việc lập kế hoạch theo kiểu truyền thống, các ngành nghiên cứu, gồm cả agre và chapman (1987) và brooks (1991), đã phát biểu lại vấn đề lớn hơn này dựa trên các thuật ngữ về sự tƣơng tác lẫn nhau giữa nhiều tác nhân (agent) theo kiểu bán tự quản. Mỗi thành viên chịu trách nhiệm về phần đóng góp của chính nó trong nhiệm vụ của bài toán và thông qua sự phối hợp giữa chúng lời giải tổng quát sẽ hiện ra. 1.6.7. Các ngôn ngữ và môi trường dùng cho TTNT Nghiên cứu TTNT đã tạo ra một số những tiến bộ trong các ngôn ngữ lập trình và các môi trƣờng phát triển phần mềm. Vì nhiều lý do, bao gồm cả qui mô tổng thể của hầu hết các chƣơng trình TTNT, khuynh hƣớng phát sinh ra các không gian khổng lồ của các thuật toán tìm kiếm, và những khó khăn trong việc tiên đoán các hành vi của các chƣơng trình điều khiển bằng heuristics, các nhà lập trình TTNT đã bị thúc ép phải xây dựng nên một tập hợp các phƣơng pháp lập trình. 20
21. Các môi trƣờng lập trình bao gồm cả các kỹ thuật cấu tạo tri thức (knowledge – structuring) nhƣ lập trình hƣớng đối tƣợng (object-oriented programming) và các cơ cấu tổ chức hệ chuyên gia. Các ngôn ngữ cấp cao nhƣ Lisp và Prolog, là các ngôn ngữ tích cực hỗ trợ kiểu phát triển theo module, khiến cho việc quản lý tính đồ sộ và phức tạp của chƣơng trình dễ dàng hơn. Các gói chƣơng trình lần tìm cho phép ngƣời lập trình tạo dựng lại quá trình thực thi của một thuật toán phức tạp và cho phép tháo gỡ những phức tạp khi tìm kiếm bằng điều khiển của heuristics. Không có công cụ kỹ thuật đó, khó mà tin đƣợc rằng ngƣời ta có thể xây dựng nên những hệ thống TTNT gây chú ý. 1.6.8. Máy học Tuy thành công trong vai trò những máy giải quyết vấn đề, học vẫn còn là một sự nan giải đối với các chƣơng trình TTNT. Khuyết điểm này dƣờng nhƣ rất nghiêm trọng, đặc biệt là khi khả năng học là một trong những thành phần quan trọng nhất làm nên hành vi thông minh. Một hệ chuyên gia có thể thực hiện những tính toán lớn và rất tốn kém nhằm giải quyết một bài toán. Tuy thế không giống nhƣ con ngƣời, nếu đƣa cho nó cùng bài toán ấy hoặc một bài toán tƣơng tự lần thứ hai, nó sẽ không nhớ lời giải lần trƣớc. Nó thực hiện lại chuỗi tính toán đó lần nữa. Điều này đúng cho cả lần thứ hai, thứ ba, thứ tƣ, và bất cứ khi nào nó giải quyết bài toán đó – hầu nhƣ không thể gọi đó là hành vi của một máy giải quyết vấn đề thông minh. Hầu hết các hệ chuyên gia đều bị cản trở bởi tính cứng nhắc trong các chiến lƣợc giải quyết vấn đề của chúng và sự khó khăn khi phải thay đổi khối lƣợng lớn mã chƣơng trình. Giải pháp dễ thấy đối với những khó khăn này là hoặc để cho các chƣơng trình học tập trên chính kinh nghiệm, sự tƣơng tự, và những ví dụ của chúng, hoặc là"nói"cho chúng biết phải làm gì. Tuy rằng học là một lĩnh vực khó khăn trong nghiên cứu, một vài chƣơng trình đƣợc viết đã đề xuất rằng đây không phải là một mục tiêu không thể đạt đƣợc. Có thể một chƣơng trình nhƣ thế gây chú ý nhất là AM - Automated Mathematician - đƣợc thiết kế để khám phá các quy luật toán học (lenat 1977, 1982). Ban đầu ngƣời ta đƣa cho AM các khái niệm và tiên đề của lý thuyết tập hợp, sau đó nó đã tìm ra những khái niệm toán học quan trọng nhƣ là lực lƣợng (cardinality) và số học số nguyên, và nhiều kết quả khác của lý thuyết số. AM đã phỏng đoán các lý thuyết mới bằng cách cập nhật cơ sở tri thức hiện hành của nó, và sử dụng các heuristic để theo đuổi"khả năng đáng quan tâm"nhất trong hàng loạt các lựa chọn có thể. Một nghiên cứu khác của winston về sự quy nạp các khái niệm cấu trúc, chẳng hạn nhƣ"hình cung"từ một tập hợp các ví dụ trong trò chơi thế giới của khối (winston, 21
22. 1975). Thuật toán ID3 đã tỏ ra thành công trong việc học các mẫu tổng quát từ các ví dụ (quinlan, 1986). Menta-dendral học các luật để phiên dịch dữ liệu quang phổ khối trong hóa học hữu cơ từ các mẫu dữ liệu về các hợp chất của cấu trúc đã biết. Teiresias, một đại diện khá thông minh của các hệ chuyên gia có thể chuyển đổi lời chỉ đạo cấp cao thành các luật mới cho cơ sở dữ liệu của nó (Davis, 1982). Hacke nghĩ ra các kế hoạch để thực hiện các thao tác trong trò thế giới các khối thông qua một quá trình lặp lại nhiều lần việc đặt ra một kế hoạch, thử nghiệm nó, và hiệu chỉnh bất cứ lỗ hỏng nào phát hiện ra trong kế hoạch dự tuyển (sussman 1975). Những nghiên cứu trong việc học trên cơ sở giải thích đã cho thấy tính hiệu quả của tri thức ƣu tiên trong quá trình học (mitchell et al. 1986, dejong and mooney 1986). Sự thành công của các chƣơng trình học máy thuyết phục rằng có thể tồn tại một tập hợp các nguyên tắc học tổng quát cho phép xây dựng nên các chƣơng trình có khả năng học tập trong nhiều lĩnh vực thực tế. 1.6.9. Xử lý phân tán song song Một cách tiếp cận khác là tìm cách xây dựng các chƣơng trình thông minh bằng cách sử dụng các mô hình tƣơng tự nhƣ cấu trúc nơ-ron (neuron) của bộ não con ngƣời. Một sơ đồ neuron đơn giản gồm có một thân tế bào có rất nhiều những chỗ nhô ra theo nhánh, gọi là các tổ chức cây (dendrite), và một nhánh đơn gọi là trục (axon). Các tổ chức cây nhận tín hiệu từ các neuron khác. Khi những xung lực kết hợp này vƣợt quá một ngƣỡng nhất định nào đó, thì neuron phát động và một xung lực, hay còn gọi là"cụm"(spike), chạy xuống trục. Các nhánh ở cuối trục hình thành nên các khớp thần kinh (synapse) với những tổ chức cây của các neuron; các khớp thần kinh có thể thuộc loại kích thích (excitatory) hay ngăn chặn (inhibitory). Một khớp thần kinh kích thích sẽ cộng thêm vào tổng số tín hiệu đi đến neuron; còn khớp thần kinh ngăn chặn thì trừ bớt đi tổng số này. Mô tả một neuron nhƣ vậy tuy khá đơn giản nhƣng nó thâu tóm tất cả những đặc trƣng liên quan đến các mô hình tính toán neuron. Đặc biệt mỗi nơ ron tính toán một số chức năng đầu vào của nó rồi chuyển kết quả đến các đơn vị liên hệ trong mạng. Thay vì sử dụng các ký hiệu và phép toán rõ ràng, tri thức của các hệ này nảy sinh ra khỏi toàn bộ mạng các kết nối neuron và các giá trị ngƣỡng. Vì nhiều lý do, cấu trúc neuron hiện đang hết sức hấp dẫn để dùng làm cơ chế cài đặt trí tuệ. Các chƣơng trình TTNT truyền thống có khuynh hƣớng dễ gãy vỡ và nhạy cảm quá đáng khi phải đƣơng đầu với sự nhiễu loạn: thay vì giảm giá trị một cách từ từ, những chƣơng trình nhƣ vậy thƣờng thành công hoàn toàn hoặc thất bại hoàn toàn. Trí tuệ con ngƣời linh hoạt hơn nhiều; chúng ta có thể tiếp nhận đƣợc tốt đầu vào 22
23. nhiễu loạn, chẳng hạn nhƣ nhận ra một khuôn mặt trong một căn phòng tối từ góc nhìn hẹp hay theo dõi duy nhất một cuộc đối thoại trong bữa tiệc ồn ào. Ngay cả khi không thể giải quyết đƣợc một số vấn đề, chúng ta nói chung vẫn có thể đƣa ra một sự phỏng đoán có lý và coi đó nhƣ lời giải của bài toán. Do các cấu trúc neuron thâu tóm tri thức vào trong một số lƣợng lớn các đơn vị đƣợc nghiền thật nhỏ, nên chúng tỏ ra có triển vọng hơn trong việc đối sánh một cách toàn phần các dữ liệu nhiễu loạn và không đầy đủ. Cấu trúc neuron cũng vững chắc hơn vì tri thức phân bố khá đồng đều xung quanh mạng. Kinh nghiệm của những ngƣời đã bị mất một phần não bộ do bệnh tật hay tai nạn đã cho thấy rằng họ không bị mất các vùng nhớ riêng biệt, mà đúng hơn là các quá trình trí não của họ phải chịu đựng nhiều sự giảm sút tổng thể. 1.7. Những thách thức đối với TTNT Những thành tựu nghiên cứu và ứng dụng các kỹ thuật TTNT đã khẳng định tính thực tiễn của các dự án xây dựng máy tính có khả năng suy nghĩ. Tuy vậy trong một số phạm vi, máy tính còn thua xa so với hoạt động của hệ thần kinh con người. Xử lý song song: mặc dù công nghệ điện tử hiện đại cho phép xây dựng các bộ đa xử lý, song máy tính chƣa thể hoạt động song song nhƣ bộ não con ngƣời đƣợc. Khả năng diễn giải: con ngƣời có thể xem xét cùng một vấn đề theo những phƣơng pháp khác nhau, từ đó diễn giải theo cách dễ hiểu nhất. Ngƣợc lại, sự linh hoạt này không dễ mô phỏng đƣợc trong các hệ thống TTNT. Lôgic rời rạc và tính liên tục: một thách đố lớn với các hệ thống TTNT là khả năng kết hợp các phƣơng pháp xử lý thông tin trong môi trƣờng liên tục với các thao tác xử lý thông tin rời rạc. Khả năng học: mặc dù hiện nay một số chƣơng trình máy tính có khả năng học nhƣng cũng chƣa thể mô phỏng đƣợc hoàn toàn khả năng học giống bộ não con ngƣời. Khả năng tự tổ chức: khó tạo lập đƣợc các hệ thống TTNT có khả năng tự tổ chức, tự điều khiển hoạt động của nó để thích nghi với môi trƣờng. Những nghiên cứu và ứng dụng của TTNT tập trung vào các vấn đề lớn sau: - Nghiên cứu và thử nghiệm các mạng Neuron, các hệ thống TTNT mô phỏng chức năng hoạt động của bộ não với các khả năng học, tự tổ chức, tự thích nghi, tổng quát hoá, xử lý song song, có khả năng diễn giải, xử lý thông tin liên tục và rời rạc; - Nghiên cứu và tạo lập các hệ thống có giao tiếp thân thiện giữa ngƣời và máy trên cơ sở nghiên cứu nhận thức máy, thu thập và xử lý tri thức, xử lý thông tin hình ảnh, tiếng nói; 23
24. - Nghiên cứu các phƣơng pháp biểu diễn tri thức và các phƣơng pháp suy diễn thông minh, các phƣơng pháp giải quyết vấn đề đối với những bài toán phụ thuộc không gian, thời gian; Ngày nay, thế giới đang chuyển mình trong những nghiên cứu về TTNT. Chắc chắn rằng máy tính với trí tuệ nhƣ con ngƣời sẽ tác động mạnh đến cuộc sống xã hội. 24
25. CÂU HỎI CHƢƠNG 1 1. Trình bày mục tiêu của TTNT. 2. Trình bày khái niệm cơ bản về TTNT. 3. Nêu các tiền đề cơ bản của TTNT. 4. Nêu các kỹ thuật trong TTNT. 5. Nêu vai trò của TTNT trong công nghệ thông tin. 6. Nêu các thành phần của TTNT. 7. Nêu những lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT. 8. Nêu những vấn đề đang đƣợc giải quyết của TTNT. 25
26. CHƢƠNG 2: CÁC CHIẾN LƢỢC TÌM KIẾM 2.1. Biểu diễn vấn đề trong không gian trạng thái Bài toá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ố yêu cầu trong một tập hợp các đối tƣợng. Có rất nhiều vấn đề mà việc giải quyết nó đƣợc quy về bài toán tìm kiếm, do đó cần 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. 2.1.1. Không gian trạng thái của bài toán Muốn biểu diễn một vấn đề trong không gian trạng thái, cần xác định các yếu tố sau: (1) Trạng thái ban đầu; (2) Một tập hợp các toán tử, trong đó mỗi toán tử R 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 u tới một trạng thái v. 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à uo (uo U). Mỗi toán tử R có thể xem nhƣ một ánh xạ R: U U. Một tập hợp T các trạng thái kết thúc (trạng thái đích) TU. Khi 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). Do đó, không gian trạng thái có thể biểu diễn 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 (trạng thái v đƣợc gọi là kề với trạng thái u). Khi đó một đƣờng đi trong không gian trạng thái sẽ là một đƣờng đi trong đồ thị này. Ví dụ 2.1: Xét không gian trạng thái có uo=A, T={B} và đƣợc miêu tả bằng đồ thị sau: 26
27. A G C E D F B Hình 2.1. Mô tả không gian trạng thái bằng đồ thị định hướng Trong đồ thị Hình 2.1, ta có: - uo =A - T={B} - Tập các toán tử: STT Tên toán tử Ý nghĩa 1 R1 A G 2 R2 A E 3 R3 C A 4 R4 C F 5 R5 E G 6 R6 E C 7 R7 G D 8 R8 D E 9 R9 D B 10 R10 F B 11 R11 B E 2.1.2. Các ví dụ Sau đây là các 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ụ 2.2: Trò chơi 8 số Trong bảng ô vuông 3 hàng, 3 cột, mỗi ô chứa một số nằm trong phạm vi từ 1 đến 8 sao cho không có 2 ô có cùng giá trị, có một ô trong bảng bị trống (không chứa giá trị nào). Xuất phát từ một sắp xếp nào đó các số trong bảng, hãy dịch chuyển ô trống sang 27
28. phải, sang trái, lên trên hoặc xuống dƣới sao cho ô trống không ra ngoài bảng để đƣa bảng A về bảng B (Hình 2.2). 1 2 3 1 2 3 4 5 4 5 6 6 7 8 7 8 Bảng A Bảng B Hình 2.2. Trò chơi 8 số Trong bài toán này, trạng thái ban đầu là Bảng A, còn trạng thái kết thúc là Bảng B. 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). Chẳng hạn, từ trạng thái ban đầu (bảng A), ta chỉ có thể áp dụng các toán tử down, left, up. 1 2 3 4 5 6 7 8 down up left 2 3 1 2 3 1 2 3 1 4 5 4 5 6 4 5 6 7 8 6 7 8 7 8 Trong Ví dụ 2.2. 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 đƣợ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 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.3: Nhà buôn và kẻ cƣớp Có ba nhà nhà buôn và ba kẻ cƣớp cùng một chiếc thuyền chở đƣợc một hoặc hai ngƣời ở bên bờ tả ngạn một con sông. Hãy tìm cách để chở 3 kẻ cƣớp và 3 nhà buôn đi thuyền từ tả ngạn sang hữu ngạn sông sao cho ở mỗi bờ sông, số nhà buôn ở mọi thời điểm luôn không nhỏ hơn số kẻ cƣớp (trừ trƣờng hợp bên một bờ sông không có nhà buôn nào). Nhà buôn và kẻ cƣớp có thể qua lại hai bên bờ sông nhiều lần. Để biểu diễn các trạng thái, ta sử dụng bộ ba (a, b, k), trong đó a là số nhà buôn, b là số kẻ cƣớp ở bên bờ tả ngạn, k = 1 nếu thuyền ở bờ tả ngạn và k = 0 nếu thuyền ở bờ 28
29. hữu ngạn. Nhƣ vậy, không gian trạng thái cho bài toán nhà buôn 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 nhà buôn, hoặc 1 kẻ cƣớp, hoặc 2 nhà buôn, hoặc 2 kẻ cƣớp, hoặc 1 nhà buôn và 1 kẻ cƣớp (do thuyền chỉ chở đƣợc tối đa 2 ngƣời). - Trạng thái kết thúc là (0, 0, 0). - Một lời giải cho bài toán nhƣ sau: STT Trạng thái Giải thích 1 (3, 3, 1) Bắt đầu 2 (3, 1, 0) Chở 2 kẻ cƣớp sang sông từ tả ngạn sang hữu ngạn 3 (3, 2, 1) Chở 1 kẻ cƣớp sang sông từ hữu ngạn sang tả ngạn 4 (3, 0, 0) Chở 2 kẻ cƣớp sang sông từ tả ngạn sang hữu ngạn 5 (3, 1, 1) Chở 1 kẻ cƣớp sang sông từ hữu ngạn sang tả ngạn 6 (1, 1, 0) Chở 2 nhà buôn sang sông từ tả ngạn sang hữu ngạn 7 (2, 2, 1) Chở 1 kẻ cƣớp, 1 nhà buôn sang sông từ hữu ngạn sang tả ngạn 8 (0, 2, 0) Chở 2 nhà buôn sang sông từ tả ngạn sang hữu ngạn 9 (0, 3, 1) Chở 1 kẻ cƣớp sang sông từ hữu ngạn sang tả ngạn 10 (0, 1, 0) Chở 2 kẻ cƣớp sang sông từ tả ngạn sang hữu ngạn 11 (0, 2, 1) Chở 1 kẻ cƣớp sang sông từ hữu ngạn sang tả ngạn 12 (0, 0, 0) Chở 2 kẻ cƣớp sang sông từ tả ngạn sang hữu ngạn Ví dụ 2.4: Cho 2 bình A và B lần lƣợt có dung tích 3 lít và 5 lít và không có vạch chia độ. Ban đầu 2 bình không có nƣớc. Có thể rót nƣớc đổ đầy các bình, có thể đổ hết nƣớc từ một bình đi, có thể rót nƣớc từ bình này sang bình khác. Hãy xây dựng không gian trạng thái của bài toán để rót đƣợc đúng 4 lít nƣớc trong bình B và hãy chỉ ra 1 cách rót. Sử dụng bộ (a, b) để biểu diễn mỗi trạng thái, trong đó a là lƣợng nƣớc của bình A, b là lƣợng nƣớc của bình B tại thời điểm đang xét. - Trạng thái ban đầu là (0, 0); - Tập trạng thái kết thúc là T={(x, 4), 0≤x≤3} - Các toán tử: 29
30. STT Toán tử Giải thích 1 (a, b) (0, b) (a>0) Đổ hết nƣớc ở bình A 2 (a, b) (a, 0) (b>0) Đổ hết nƣớc ở bình B 3 (a, b) (3, b) (a 3) Đổ một phần nƣớc từ bình B sang bình A sao cho bình A đầy nƣớc 8 (a, b) (a+b-5, 5) (b 5) Đổ một phần nƣớc từ bình A sang bình B sao cho bình B đầy nƣớc Không gian trạng thái có thể biểu diễn dạng đồ thị nhƣ sau: Hình 2.3. Đồ thị biểu diễn cách rót nước - Tìm một cách rót: STT Trạng thái Giải thích 1 (0, 0) Trạng thái ban đầu 2 (0, 5) Đổ đầy nƣớc vào bình B 30
31. STT Trạng thái Giải thích 3 (3, 2) Đổ 3 lít nƣớc từ bình B sang bình A 4 (0, 2) Đổ hết nƣớc từ bình A 5 (2, 0) Đổ 2 lít nƣớc từ bình B sang bình A 6 (2, 5) Đổ đầy nƣớc bình B 7 (3, 4) Đổ 1 lít nƣớc từ bình B sang bình A Nhƣ vậy, một cách rót là: (0,0) (3,0) (0,3) (3,3) (1,5) (1,0) (0,1) (0,1) (3,1) (0,4). Ngoài ra, còn một cách rót khác nhƣ sau: (0, 0) (0, 5) (3, 2) (0, 2) (2, 0) (2, 5) (3, 4). Ví dụ 2.5. Bài toán tháp Hà Nội Cho ba cọc 1, 2, 3. Ở cọc 1 ban đầu có 3 đĩa sắp xếp theo thứ tự to dần từ trên xuống dƣới. Hãy dịch chuyển 3 đĩa đó sang cọc thứ 3 sao cho: - Mỗi lần chỉ chuyển một đĩa; - Trong mỗi cọc không cho phép đĩa to nằm trên đĩa nhỏ hơn. Để biểu diễn các trạng thái, ta ký hiệu các đĩa là 1, 2, 3, trong đó đĩa 1 là lớn nhất và đĩa 3 là nhỏ nhất. Một trạng thái đƣợc biểu diễn bởi bộ (i, j, k) trong đó: đĩa 1 ở vị trí i, đĩa 2 ở vị trí j và đĩa 3 ở vị trí k. Trạng thái đầu uo = (1, 1, 1); Tập trạng thái kết thúc: T={(3, 3, 3)} Không gian trạng thái của bài toán có thể miêu tả dạng đồ thị nhƣ sau: Hình 2.4. Biểu diễn không gian trạng của bài toán Tháp Hà Nội. Ví dụ 2.6. Trò chơi tic-tac-toe Cho trƣớc một bàn cờ n x n ô (n 3). Bắt đầu ván đấu bằng bàn cờ trống, đấu thủ thứ nhất có thể đặt ký hiệu"X"vào bất cứ ô nào trong n2 ô trống của bàn cờ, tiếp theo, 31
32. đấu thủ thứ hai đến lƣợt mình đi sẽ có thể đặt ký hiệu"0"của mình vào ô trống và sẽ cứ luân phiên nhƣ thế. Ngƣời nào đặt đƣợc k ô (3 k) thẳng hàng, cột hoặc đƣờng chéo liền nhau là thắng (Hình 2.5). Hình 2.5. Một phần không gian trạng thái của bài toán với n=3 2.2. Giới thiệu các chiến lƣợc tìm kiếm Có thể phân các chiến lƣợc tìm kiếm thành hai loại: 2.2.1. 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 chiều sâu. Kỹ thuật tìm kiếm theo bề rộng là tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trƣớc khi chuyển sang các nút của mức tiếp theo. Tƣ tƣởng của tìm kiếm theo bề rộng là các trạng thái đƣợc phát triển theo thứ tự mà chúng đƣợc sinh ra, tức là trạng thái nào đƣợc sinh ra trƣớc sẽ đƣợc phát triển trƣớc. Kỹ thuật tìm kiếm theo bề rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hƣớng dẫn của luật trọng tài, chẳng hạn"đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục đến khi tìm đƣợc lời giải (nếu có). Kỹ thuật tìm kiếm sâu trong không gian bài toán đƣợc bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trọng tài, chẳng hạn,"đi theo nút cực trái”, hƣớng dẫn việc tìm. Nếu không đi tiếp đƣợc, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hƣớng khác, chẳng hạn, đến nút"sát nút cực trái”. Hành động này gọi là quay lui. Thuật toán tìm kiếm theo chiều 32
33. sâu đƣợc hình dung nhƣ việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể đƣợc, khi gặp cành cụt thì quay lại xét cành chƣa đi qua. Trong nhiều vấn đề, dù chúng ta phát triển các trạng thái theo hệ thống nào (theo bề rộng hoặc theo chiều sâu) thì số lƣợng các trạng thái đƣợc sinh ra trƣớc khi ta gặp trạng thái đích thƣờng là cực kỳ lớn. Do đó các thuật toán tìm kiếm mù kém hiệu quả, đòi hỏi rất nhiều không gian và thời gian. Trong thực tế, nhiều vấn đề không thể giải quyết đƣợc bằng tìm kiếm mù. 2.2.2. Các chiến lược tìm kiếm kinh nghiệm (tìm kiếm heuristic) Trong rất nhiều trƣờng hợp, chúng ta có thể dựa vào sự hiểu biết của chúng ta về vấn đề, dựa vào kinh nghiệm, trực giác, để đánh giá các trạng thái. Sử dụng sự đánh giá các trạng thái để hƣớng dẫn sự tìm kiếm: trong quá trình phát triển các trạng thái, ta sẽ chọn trong số các trạng thái chờ phát triển, trạng thái đƣợc đánh giá là tốt nhất để phát triển. Do đó tốc độ tìm kiếm sẽ nhanh hơn. Các phƣơng pháp tìm kiếm dựa vào sự đánh giá các trạng thái để hƣớng dẫn sự tìm kiếm gọi chung là các phƣơng pháp tìm kiếm kinh nghiệm. Nhƣ vậy chiến lƣợc tìm kiếm đƣợc xác định bởi chiến lƣợc chọn trạng thái để phát triển ở mỗi bƣớc. Trong tìm kiếm mù, trạng thái đƣợc chọn để phát triển theo thứ tự mà chúng đƣợc sinh ra; còn trong tìm kiếm kinh nghiệm việc chọn trạng thái dựa vào sự đánh giá các trạng thái. 2.3. Cây tìm kiếm Chúng ta có thể nghĩ đến quá trình tìm kiếm nhƣ quá trình xây dựng cây tìm kiếm. Cây tìm kiếm là cây mà các đỉnh đƣợc gắn bởi các trạng thái của không gian trạng thái. Gốc của cây tìm kiếm tƣơng ứng với trạng thái ban đầu. Nếu một đỉnh ứng với trạng thái u, thì các đỉnh con của nó ứng với các trạng thái v. Hình 2.6(a) là đồ thị biểu diễn một không gian trạng thái với trạng thái ban đầu là A, Hình 2.6(b) là cây tìm kiếm tƣơng ứng với không gian trạng thái đó. 33
34. Hình 2.6. Đồ thị không gian trạng thái và cây tìm kiếm tương ứng Mỗi chiến lƣợc tìm kiếm trong không gian trạng thái tƣơng ứng với một phƣơng pháp xây dựng cây tìm kiếm. Quá trình xây dựng cây bắt đầu từ cây chỉ có một đỉnh là trạng thái ban đầu. Giả sử tới một bƣớc nào đó trong chiến lƣợc tìm kiếm, ta đã xây dựng đƣợc một cây nào đó, các lá của cây tƣơng ứng với các trạng thái chƣa đƣợc phát triển. Bƣớc tiếp theo phụ thuộc vào chiến lƣợc tìm kiếm mà một đỉnh nào đó trong các lá đƣợc chọn để phát triển. Khi phát triển đỉnh đó, cây tìm kiếm đƣợc mở rộng bằng cách thêm vào các đỉnh con của đỉnh đó. Kỹ thuật tìm kiếm theo bề rộng (theo chiều sâu) tƣơng ứng với phƣơng pháp xây dựng cây tìm kiếm theo bề rộng (theo chiều sâu). 2.4. Các chiến lƣợc tìm kiếm mù 2.4.1. Tìm kiếm theo bề rộng a) Thuật toán Input: Không gian trạng thái có uo là trạng thái đầu, T là tập trạng thái kết thúc. Output: Tìm kiếm thành công (có đƣờng đi từ uo đến một trạng thái kết thúc) hoặc thất bại. Trong trƣờng hợp tìm kiếm thành công thi đƣa ra đƣờng đi. Procedure Breadth_First_Search; Begin 1. L ={uo} DD(uo)  true; DD(u) false mọi u khác uo 2. Loop do 2.1. if L =  then {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 T 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) and (DD(v) =false) do 34
35. { DD(v)  true; Đặt v vào cuối danh sách L; Father(v)  u} End; Ghi chú: - Mảng logic DD để đảm bảo mỗi đỉnh không đƣợc xét quá 1 lần; - Mảng Father để tìm lại 1 đƣờng đi trên con đƣờng từ uo đến đích; - Danh sách L đƣợc xử lý nhƣ hàng đợi; - Nếu bài toán có nghiệm (tồn tại đƣờng đi từ trạng thái ban đầu tới trạng thái đích), thì thuật toán tìm kiếm theo bề rộng sẽ tìm ra nghiệm, đồng thời đƣờng đi tìm đƣợc sẽ là ngắn nhất (qua ít đỉnh nhất). Trong trƣờng hợp bài toán vô nghiệm và không gian trạng thái hữu hạn, thuật toán sẽ dừng và cho thông báo vô nghiệm. b) Đánh giá độ phức tạp Giả sử mỗi trạng thái khi đƣợc phát triển sẽ sinh ra b trạng thái kề, b đƣợc gọi là nhân tố nhánh. Giả sử nghiệm của bài toán là đƣờng đi có độ dài d. Bởi nhiều nghiệm có thể đƣợc tìm ra tại một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh cần xem xét để tìm ra nghiệm là: 1 + b + b2 + + bd-1 + k, trong đó k có thể là 1, 2,  , bd. Do đó số lớn nhất các đỉnh cần xem xét là: 1 + b + b2 + + bd Nhƣ vậy, độ phức tạp thời gian của thuật toán tìm kiếm theo bề rộng là O(bd). Độ phức tạp không gian cũng là O(bd), bởi vì ta cần lƣu vào danh sách L tất cả các đỉnh của cây tìm kiếm ở mức d, số các đỉnh này là bd. c) Ưu và nhược điểm * Ƣu điểm: Kỹ thuật tìm kiếm theo bề rộng sẽ tìm đƣợc lời giải và đƣờng đi tìm đƣợc đi qua ít đỉnh nhất (nếu có). * Nhƣợc điểm: Không phù hợp với không gian bài toán kích thƣớc lớn. Đối với loại bài toán này, phƣơng pháp tìm kiếm theo bề rộng đối mặt với các thách thức: + Cần nhiều bộ nhớ theo số nút cần lƣu trữ; + Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài làm cho số nút tăng lên; + Dễ thực hiện các thao tác không thích hợp, thừa, đƣa đến việc tăng đáng kể số nút phải xử lý. + Không hiệu quả nếu lời giải ở mức quá sâu trên cây tìm kiếm. 35
36. Ví dụ 2.7: Cho đồ thị biểu diễn không gian trạng thái nhƣ sau (Hình 2.7): Hình 2.7. Đồ thị không gian trạng thái Hãy tìm đƣờng đi xuất phát từ trạng thái A đến trạng thái B bằng phƣơng pháp tìm kiếm theo bề rộng theo thứ tự bảng chữ cái của nhãn các đỉnh. Đỉnh kề với u và chƣa Bƣớc u L Father đánh dấu 0 Khởi tạo A 1 A E, G E, G Father(E) =A Father(G) =A 2 E C G, C Father(C) =E 3 G D C, D Father(D) =G 4 C F D, F Father(A) =C 5 D B T Father(B) =D Đƣờng đi tìm đƣợc là: B  D  G  A Ví dụ 2.8: Bài toán rót nƣớc (xem Ví dụ 2.4) với bình A có dung tích 5 lít, bình B có dung tích 4 lít, yêu cầu đong đƣợc 3 lít nƣớc. Trạng thái đầu (0;0) Tập trạng thái đích T={(x, 3) / 0 x 5} {(3, y) / 0 y 4} Quá trình tìm kiếm theo bề rộng thể hiện theo từng bƣớc sau: Đỉnh kề với u và Bƣớc u L Father chƣa đánh dấu 0 Khởi tạo (0, 0) 1 (0, 0) (5, 0) (0, 4) (5, 0) (0, 4) Father(5, 0) =(0, 0) Father(0, 4) =(0, 0) 36
37. Đỉnh kề với u và Bƣớc u L Father chƣa đánh dấu 2 (5, 0) (5, 4), (1, 4) (0, 4), (5, 4), (1, 4) Father(5, 4) =(5, 0) Father(1, 4) =(5, 0) 3 (0, 4) (4, 0) (5, 4), (1, 4), (4, 0) Father(4, 0) =(0, 4) 4 (5, 4) (1, 4), (4, 0) 5 (1, 4) (1, 0) (4, 0), (1, 0) Father(1, 0) =(1, 4) 6 (4, 0) (4, 4) (1, 0), (4, 4) Father(4, 4) =(4, 0) 7 (1, 0) (4, 4) 8 (4, 4) (5, 3) (5, 3) Father(5, 3) =(4, 4) 9 (5, 3) T Vì vậy có đƣợc lời giải nhƣ sau: (0, 0) (0, 4) (4, 0) (4, 4) (5, 3) Ví dụ 2.9: Xét bài toán 8 số, thực hiện tìm kiếm theo bề rộng với bảng xuất phát A và bảng kết thúc B: 2 8 3 2 8 3 1 6 4 6 4 7 5 1 7 5 Bảng A Bảng B Bƣớc u Đỉnh kề với u và chƣa đánh dấu L Father 0 Khởi tạo A 1 A 2 8 3 2 8 3 2 8 3 C, D, E Father(C) =A 1 4 1 6 4 1 6 4 Father(D) =A 7 6 5 7 5 7 5 Father(E) =A C D E 2 C 2 8 3 2 3 2 8 3 D, E, F, G, H Father(F) =C 1 4 1 8 4 1 4 Father(G) =C 7 6 5 7 6 5 7 6 5 Father(H) =C F G H 3 D 2 8 3 E, F, G, H, I Father(I) =D 6 4 1 7 5 I 4 E 2 8 3 F, G, H, I, J Father(J) =E 1 6 7 5 4 37
38. Bƣớc u Đỉnh kề với u và chƣa đánh dấu L Father J 5 F 8 3 2 8 3 G, H, I, J, K, Father(K) =F 2 1 4 7 1 4 L Father(L) =F 7 6 5 6 5 K L 6 G 2 3 2 3 H, I, J, K, L, Father(M) =G 1 8 4 1 8 4 M, O Father(O) =G 7 6 5 7 6 5 M O 7 H 2 8 2 8 3 I, J, K, L, M, Father(P) =H 1 4 3 1 4 5 O, P, Q Father(Q) =H 7 6 5 7 6 P Q 8 I=B Vậy lời giải của bài toán là: B  D  A 2.4.2. Tìm kiếm theo chiều sâu a) Thuật toán Input: Không gian trạng thái có uo là trạng thái đầu, T là tập trạng thái kết thúc. Output: Tìm kiếm thành công (có đƣờng đi từ uo đến một trạng thái kết thúc) hoặc thất bại. Trong trƣờng hợp tìm kiếm thành công thi đƣa ra đƣờng đi. Procedure Depth_First_Search Begin 1. L ={ uo}; DD(uo)  true; DD(u) false mọi u khác uo 2. Loop do 2.1. if L =  then {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 T 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) and (DD(v) =false) do { DD(v)  true; Đặt v vào đầu danh sách L; Father(v)  u} End; 38
39. Ghi chú: - Mảng logic DD để đảm bảo mỗi đỉnh không đƣợc xét quá 1 lần; - Mảng Father để tìm lại 1 đƣờng đi trên con đƣờng từ uo đến đích; - Danh sách L đƣợc xử lý nhƣ ngăn xếp. - Thuật toán tìm kiếm theo chiều sâu là hoàn toàn tƣơng tự nhƣ thuật toán tìm kiếm theo bề rộng, chỉ có một điều khác là, ta xử lý danh sách L các trạng thái chờ phát triển không phải nhƣ hàng đợi mà nhƣ ngăn xếp. Cụ thể là trong bƣớc 2.4 của thuật toán tìm kiếm theo bề rộng, ta cần sửa lại là"Đặt v vào đầu danh sách L”. Sau đây chúng ta sẽ đƣa ra các nhận xét so sánh hai chiến lƣợc tìm kiếm mù: Thuật toán tìm kiếm theo bề rộng luôn luôn tìm ra nghiệm nếu bài toán có nghiệm. Song không phải với bất kỳ bài toán có nghiệm nào thuật toán tìm kiếm theo độ sâu 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ì thuật toán tìm kiếm theo độ sâu sẽ tìm ra nghiệm. Tuy nhiên, trong trƣờng hợp không gian trạng thái vô hạn (chẳng hạn nhƣ độ thị trạng thái chứa chu trình), thì có thể nó không tìm ra nghiệm, lý do là nếu ta đ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. Do đó không nên áp dụng tìm kiếm theo dộ sâu cho các bài toán có cây tìm kiếm chứa các nhánh vô hạn. b) Đánh giá độ phức tạp của thuật toán tìm kiếm theo độ sâu Giả sử rằng, nghiệm của bài toán là đƣờng đi có độ dài d, cây tìm kiếm có nhân tố nhánh là b và có chiều cao là d. Có thể xảy ra, nghiệm là đỉnh ngoài cùng bên phải trên mức d của cây tìm kiếm, do đó độ phức tạp thời gian của tìm kiếm theo độ sâu trong trƣờng hợp xấu nhất là O(bd), tức là cũng nhƣ tìm kiếm theo bề rộng. Tuy nhiên, trên thực tế đối với nhiều bài toán, tìm kiếm theo độ sâu thực sự nhanh hơn tìm kiếm theo bề rộng. Lý do là tìm kiếm theo bề rộng phải xem xét toàn bộ cây tìm kiếm tới mức d- 1, rồi mới xem xét các đỉnh ở mức d. Còn trong tìm kiếm theo độ sâu, có thể ta chỉ cần xem xét một bộ phận nhỏ của cây tìm kiếm thì đã tìm ra nghiệm. Để đánh giá độ phức tạp không gian của tìm kiếm theo độ sâu ta có nhận xét rằng, khi ta phát triển một đỉnh u trên cây tìm kiếm theo độ sâu, ta chỉ cần lƣu các đỉnh chƣa đƣợc phát triển mà chúng là các đỉnh con của các đỉnh nằm trên đƣờng đi từ gốc tới đỉnh u. Nhƣ vậy đối với cây tìm kiếm có nhân tố nhánh b và độ sâu lớn nhất là d, ta chỉ cần lƣu ít hơn db đỉnh. Do đó độ phức tạp không gian của tìm kiếm theo độ sâu là O(db), trong khi đó tìm kiếm theo bề rộng đòi hỏi không gian nhớ O(bd)! c) Ưu và nhược điểm của phương pháp tìm kiếm sâu *Ưu điểm 39
40. - Nếu bài toán có lời giải, và không gian trạng thái là hữu hạn thì phƣơng pháp tìm kiếm sâu bảo đảm tìm ra lời giải. - Kỹ thuật tìm kiếm sâu tập trung vào đích, con ngƣời cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính. - Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu có thể sẽ tiết kiệm thời gian. * Nhược điểm Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải. d) Ví dụ Ví dụ 2.10: Cho đồ thị biểu diễn không gian trạng thái nhƣ Hình 2.8. Hình 2.8. Đồ thị không gian trạng thái Hãy tìm đƣờng đi xuất phát từ trạng thái A đến trạng thái B bằng phƣơng pháp tìm kiếm theo chiều sâu theo thứ tự tăng dần của nhãn các đỉnh. Đỉnh kề với u và chƣa Bƣớc u L Father đánh dấu 0 Khởi tạo A 1 A E, G G, E Father(E) =A Father(G) =A 2 G D D, E Father(D) =G 3 D B B, E Father(B) =D 4 B T Đƣờng đi tìm đƣợc là: B  D  G  A Ví dụ 2.11: Bài toán đong nƣớc với bình A có dung tích 5 lít, bình B có dung tích 4 lít, yêu cầu đong đƣợc 3 lít nƣớc 40
41. Trạng thái đầu (0;0) Tập trạng thái đích T={(x, 3) / 0 x 5} {(3, y) / 0 y 4} Quá trình tìm kiếm theo chiều sâu thể hiện theo từng bƣớc sau: Đỉnh kề với u và Bƣớc u L Father chƣa đánh dấu 0 Khởi tạo (0, 0) 1 (0, 0) (5, 0) (0, 4) (5, 0) (0, 4) Father(5, 0) =(0, 0) Father(0, 4) =(0, 0) 2 (5, 0) (5, 4), (1, 4) (5, 4), (1, 4), (0, 4) Father(5, 4) =(5, 0) Father(1, 4) =(5, 0) 3 (5, 4) (1, 4), (0, 4) 4 (1, 4) (1, 4), (4, 0) 5 (1, 4) (1, 0) (1, 0), (4, 0) Father(1, 0) =(1, 4) 6 (1, 0) (0, 1) (0, 1), (4, 0) Father(0, 1) =(1, 0) 7 (0, 1) (5, 1) (5, 1), (4, 0) Father(5, 1) =(0, 1) 8 (5, 1) (2, 4) (2, 4), (4, 0) Father(2, 4) =(5, 1) 9 (2, 4) (2, 0) (2, 0), (4, 0) Father(2, 0) =(2, 4) 10 (2, 0) (0, 2) (0, 2), (4, 0) Father(0, 2) =(2, 0) 11 (0, 2) (5, 2) (5, 2), (4, 0) Father(5, 2) =(0, 2) 12 (5, 2) (3, 4) (3, 4), (4, 0) Father(3, 4) =(5, 2) 13 (3, 4) T Lời giải của bài toán nhƣ sau: (3, 4) (5, 2) (0, 2) (2, 0) (2, 4) (5, 1) (0, 1)  (1, 0) (1, 4) (5, 0) (0, 0) Ví dụ 2.12: Xét bài toán 8 số, thực hiện tìm kiếm theo chiều sâu với bảng xuất phát A và bảng kết thúc B: 2 8 3 2 8 3 1 6 4 6 4 7 5 1 7 5 Bảng A Bảng B 41
42. Bƣớc u Đỉnh kề với u và chƣa đánh dấu L Father 0 Khởi A tạo 1 A 2 8 3 2 8 3 2 8 3 D, C, E Father(C) =A 1 4 1 6 4 1 6 4 Father(D) =A 7 6 5 7 5 7 5 Father(E) =A C D E 2 D 2 8 3 F, C, E Father(F) =D 6 4 1 7 5 F 3 F=B C, E Lời giải của bài toán nhƣ sau: BDA Ví dụ 2.13. Tìm kiếm theo chiều sâu bài toán tháp Hà Nội với n=3 Đỉnh kề với Bƣớc u u và chƣa L Father đánh dấu 0 Khởi tạo (1, 1, 1) 1 (1, 1, 1) (1, 1, 2) (1, 1, 3), (1, 1, 2) Father(1, 1, 2)=(1, 1, 1) (1, 1, 3) Father(1, 1, 3)=(1, 1, 1) 2 (1, 1, 3) (1, 1, 2) (1, 2, 3), (1, 1, 2) Father(1, 1, 2)=(1, 1, 3) (1, 2, 3) Father(1, 2, 3)=(1, 1, 3) 3 (1, 2, 3) (1, 2, 1) (1, 2, 2), (1, 2, 1), Father(1, 2, 1)=(1, 2, 3) (1, 2, 2) (1, 1, 2) Father(1, 2, 2)=(1, 2, 3) 4 (1, 2, 2) (3, 2, 2) (3, 2, 2), (1, 2, 1), Father(3, 2, 2)=(1, 2, 2) (1, 1, 2) 5 (3, 2, 2) (3, 2, 3) (3, 2, 1), (3, 2, 3), Father(3, 2, 1)=(3, 2, 2) (3, 2, 1) (1, 2, 1), (1, 1, 2) Father(3, 2, 3)=(3, 2, 2) 6 (3, 2, 1) (3, 3, 1) (3, 3, 1), (3, 2, 3), Father(3, 3, 1)=(3, 2, 1) (1, 2, 1), (1, 1, 2) 7 (3, 3, 1) (3, 3, 2) (3, 3, 3), (3, 3, 2), Father(3, 3, 2)=(3, 3, 1) (3, 3, 3) (3, 2, 3), (1, 2, 1), Father(3, 3, 3)=(3, 3, 1) (1, 1, 2) 42
43. Đỉnh kề với Bƣớc u u và chƣa L Father đánh dấu 8 (3, 3, 3) T Lời giải của bài toán: (1, 1, 1) (1, 1, 3) (1, 2, 3) (1, 2, 2) (3, 2, 2) (3, 2, 1) (3, 3, 1) (3, 3, 3) 2.4.3. Các trạng thái lặp Mảng logic DD trong các thuật toán tìm kiếm theo chiều sâu và theo bề rộng đảm bảo cho các đỉnh không đƣợc đi qua quá 1 lần trên đƣờng đi đến đích (nếu có). Tuy nhiên, khi không gian trạng thái quá lớn, việc sử dụng mảng DD trong tìm kiếm sẽ bị hạn chế bởi tốc độ tính toán và số phần tử của mảng. 2.4.4. Tìm kiếm sâu lặp Một giải pháp để tránh phải dùng mảng DD để đánh dấu các đỉnh đã thăm và cho phép một đỉnh có thể thăm nhiều lần, ta tìm kiếm theo độ sâu chỉ tới mức d; nếu không tìm ra nghiệm, ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên đƣợc lặp lại với d lần lƣợt là 1, 2 đến một độ sâu tối đa max nào đó. Nhƣ vậy, thuật toán tìm kiếm sâu lặp (iterative deepening search) sẽ sử dụng thủ tục tìm kiếm sâu hạn chế (depth_limited search) nhƣ thủ tục con. Đó là thủ tục tìm kiếm theo độ sâu, nhƣng chỉ đi tới độ sâu d nào đó rồi quay lên. Kỹ thuật tìm kiếm sâu lặp thƣờng đƣợc thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm. Trong thủ tục tìm kiếm sâu hạn chế, d là tham số độ sâu, hàm depth ghi lại độ sâu của mỗi đỉnh. Input: Không gian trạng thái có uo là trạng thái đầu, T là tập trạng thái kết thúc. Output: Tìm kiếm thành công (có đƣờng đi từ uo đến một trạng thái kết thúc) với độ sâu không quá d hoặc thất bại. Procedure Depth_Limited_Search(d) Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu uo; depth(uo)  0; 2. Loop do 2.1 if L rỗng then {thông báo thất bại; stop}; 43
44. 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 thành công; stop}; 2.4 if depth(u) < d then for mỗi trạng thái v kề u do {Đặt v vào đầu danh sách L; depth(v)  depth(u) + 1}; End; Input: Không gian trạng thái có uo là trạng thái đầu, T là tập trạng thái kết thúc. Độ sâu tối đa là max. Output: Tìm kiếm thành công (có đƣờng đi từ uo đến một trạng thái kết thúc) hoặc thất bại. Procedure Depth_Deepening_Search; Begin for d  0 to max do {Depth_Limited_Search(d) ; if thành công then exit} End; Kỹ thuật tìm kiếm sâu lặp kết hợp đƣợc các ƣu điểm của tìm kiếm theo bề rộng và tìm kiếm theo độ sâu. - Cũng nhƣ tìm kiếm theo bề rộng, tìm kiếm sâu lặp luôn luôn tìm ra nghiệm (nếu bài toán có nghiệm), miễn là ta chọn độ sâu max đủ lớn. - Tìm kiếm sâu lặp chỉ cần không gian nhớ nhƣ tìm kiếm theo độ sâu. - Trong tìm kiếm sâu lặp, ta phải phát triển lặp lại nhiều lần cùng một trạng thái. Điều đó làm cho ta có cảm giác rằng, tìm kiếm sâu lặp lãng phí nhiều thời gian. Thực ra thời gian tiêu tốn cho phát triển lặp lại các trạng thái là không đáng kể so với thời gian tìm kiếm theo bề rộng. Thật vậy, mỗi lần gọi thủ tục tìm kiếm sâu hạn chế tới mức d, nếu cây tìm kiếm có nhân tố nhánh là b, thì số đỉnh cần phát triển là: 1 + b + b2 + + bd Nếu nghiệm ở độ sâu d, thì trong tìm kiếm sâu lặp, ta phải gọi thủ tục tìm kiếm sâu hạn chế với độ sâu lần lƣợt là 0, 1, 2,  , d. Do đó các đỉnh ở mức 1 phải phát triển lặp d lần, các đỉnh ở mức 2 lặp d-1 lần,  , các đỉnh ở mức d lặp 1 lần. Nhƣ vậy tổng số đỉnh cần phát triển trong tìm kiếm sâu lặp là: 44
45. (d+1) 1 + db + (d-1) b2 + + 2bd-1 + 1bd Do đó thời gian tìm kiếm sâu lặp là O(bd). Tóm lại, tìm kiếm sâu lặp có độ phức tạp thời gian là O(bd) (nhƣ tìm kiếm theo bề rộng), và có độ phức tạp không gian là O (biểu diễn) (nhƣ tìm kiếm theo độ sâu). Nói chung, chúng ta nên áp dụng tìm kiếm sâu lặp cho các vấn đề có không gian trạng thái lớn và độ sâu của nghiệm không biết trƣớc. Ví dụ 2.13: Cho đồ thị không gian trạng thái với đỉnh bắt đầu là A, tập đỉnh kết thúc là {E}. Hình 2.9. Đồ thị không gian trạng thái ví dụ 2.13 Hãy thực hiện tìm kiếm sâu lặp từ đỉnh A đến đỉnh E theo trật tự bảng chữ cái của nhãn các đỉnh với độ sâu max=4. - Xét d=0: Gọi thủ tục Depth_Limited_Search(0) thì tập đỉnh đƣợc tìm thấy là {A} - Xét d=1: Gọi thủ tục Depth_Limited_Search(1) thì các đỉnh đƣợc tìm thấy là {A, B} - Xét d=2: Gọi thủ tục Depth_Limited_Search(2) thì các đỉnh đƣợc tìm thấy là {A, B, D} - Xét d=3: Gọi thủ tục Depth_Limited_Search(3) thì các đỉnh đƣợc tìm thấy là {A, B, D, A, C} (đỉnh A đƣợc xét 2 lần) - Xét d=4: Gọi thủ tục Depth_Limited_Search(4) thì các đỉnh đƣợc tìm thấy là {A, B, D, A, B, C, A, E} (đỉnh A đƣợc xét 3 lần, đỉnh B đƣợc xét 2 lần). Kết luận: đỉnh E đƣợc tìm thấy. Cây tìm kiếm trong ví dụ này là: 45
46. Hình 2.10. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.13 Ví dụ 2.14: Cho đồ thị không gian trạng thái với đỉnh bắt đầu là A, tập đỉnh kết thúc là {E}. Hình 2.11. Đồ thị không gian trạng thái ví dụ 2.14 Hãy thực hiện tìm kiếm sâu lặp từ đỉnh A đến đỉnh E theo trật tự tăng dần của nhãn các đỉnh với độ sâu max=3. - Xét d=0: Gọi thủ tục Depth_Limited_Search(0) thì tập đỉnh đƣợc tìm thấy là {A} - Xét d=1: Gọi thủ tục Depth_Limited_Search(1) thì các đỉnh đƣợc tìm thấy là {A, B, C} - Xét d=2: Gọi thủ tục Depth_Limited_Search(2) thì các đỉnh đƣợc tìm thấy là {A, B, A, D, C, D} - Xét d=3: Gọi thủ tục Depth_Limited_Search(3) thì các đỉnh đƣợc tìm thấy là {A, B, A, B, C, } (đỉnh A đƣợc xét 2 lần) - Xét d=4: Gọi thủ tục Depth_Limited_Search(4) thì các đỉnh đƣợc tìm thấy là {A, B, D, A, B, C, A, E} (đỉnh A đƣợc xét 3 lần, đỉnh B đƣợc xét 2 lần). Kết luận: Không tìm thấy đỉnh E. 46
47. Cây tìm kiếm trong ví dụ này là: Hình 2.12. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.14 2.4.5.Tìm kiếm trên đồ thị và/hoặc a) Qui vấn đề về các vấn đề con Trong mục này chúng ta sẽ nghiên cứu một phƣơng pháp luận để giải quyết vấn đề tìm kiếm dựa trên việc quy vấn đề về các vấn đề con. Quy vấn đề về các vấn đề con (còn gọi là rút gọn vấn đề) là một phƣơng pháp đƣợc sử dụng rộng rãi nhất để giải quyết các vấn đề. Trong đời sống hàng ngày, cũng nhƣ trong khoa học kỹ thuật, mỗi khi gặp một vấn đề cần giải quyết, ta vẫn thƣờng cố gắng tìm cách đƣa nó về các vấn đề đơn giản hơn. Quá trình rút gọn vấn đề sẽ đƣợc tiếp tục cho tới khi ta dẫn tới các vấn đề con có thể giải quyết đƣợc dễ dàng. Sau đây chúng ta xét một số vấn đề. 1) Vấn đề tính tích phân bất định Giả sử ta cần tính một tích phân bất định, chẳng hạn (xex + x3) dx. Quá trình chúng ta vẫn thƣờng làm để tính tích phân bất định là nhƣ sau. Sử dụng các quy tắc tính tích phân (quy tắc tính tích phân của một tổng, quy tắc tính tích phân từng phần ), sử dụng các phép biến đổi biến số, các phép biến đổi các hàm (chẳng hạn, các phép biến đổi lƣợng giác) để đƣa tích phân cần tính về tích phân của các hàm số sơ cấp mà chúng ta đã biết cách tính. Chẳng hạn, đối với tích phân (xex + x3) dx, áp dụng quy tắc tích phân của tổng ta đƣa về hai tích phân xexdx và x3dx. Áp dụng quy tắc tích phân từng phần ta đƣa tích phân xexdx về tích phân exdx. Quá trình trên có thể biểu diễn bởi đồ thị trong hình 2.10. 47
48. Các tích phân exdx và x3dx là các tích phân cơ bản đã có trong bảng tích phân. Kết hợp các kết quả của các tích phân cơ bản, ta nhận đƣợc kết quả của tích phân đã cho (Hình 2.10) Hình 2.13. Quy một tích phân về các tích phân cơ bản Chúng ta có thể biểu diễn việc quy một vấn đề về các vấn đề con cơ bởi các trạng thái và các toán tử. Ở đây, bài toán cần giải là trạng thái ban đầu. Mỗi cách quy bài toán về các bài toán con đƣợc biểu diễn bởi một toán tử, toán tử A B, C biểu diễn việc quy bài toán A về hai bài toán B và C. Chẳng hạn, đối với bài toán tính tích phân bất định, ta có thể xác định các toán tử dạng: (f1 + f2) dx f1 dx, f2 dx và u dv v du Các trạng thái kết thúc là các bài toán sơ cấp (các bài toán đã biết cách giải). Chẳng hạn, trong bài toán tính tích phân, các tích phân cơ bản là các trạng thái kết thúc. Một điều cần lƣu ý là, trong không gian trạng thái biểu diễn việc quy vấn đề về các vấn đề con, các toán tử có thể là đa trị, nó biến đổi một trạng thái thành nhiều trạng thái khác. 2) Vấn đề tìm đƣờng đi trên bản đồ giao thông Hình 2.14. Bản đồ nối các thành phố Bài toán này đã đƣợc phát triển nhƣ bài toán tìm đƣờng đi trong không gian trạng thái, trong đó mỗi trạng thái ứng với một thành phố, mỗi toán tử ứng với một con đƣờng nối, nối thành phố này với thành phố khác. Bây giờ ta đƣa ra một cách biểu diễn khác dựa trên việc quy vấn đề về các vấn đề con. Giả sử ta có bản đồ giao thông 48
49. trong một vùng lãnh thổ (xem Hình 2.11). Giả sử ta cần tìm đƣờng đi từ thành phố A tới thành phố B. Có con sông chảy qua hai thành phố E và G và có cầu qua sông ở mỗi thành phố đó. Mọi đƣờng đi từ A đến B chỉ có thể qua E hoặc G. Nhƣ vậy bài toán tìm đƣờng đi từ A đến B đƣợc quy về: 1) Bài toán tìm đƣờng đi từ A đến B qua E (hoặc) 2) Bài toán tìm đƣờng đi từ A đến b qua G. Mỗi một trong hai bài toán trên lại có thể phân nhỏ nhƣ sau: 1) Bài toán tìm đƣờng đi từ A đến B qua E đƣợc quy về: - Tìm đƣờng đi từ A đến E (và) - Tìm đƣờng đi từ E đến B. Hình 2.15. Đồ thị và/hoặc và vấn đề tìm đường đi 2) Bài toán tìm đƣờng đi từ A đến B qua G đƣợc quy về: - Tìm đƣờng đi từ A đến G (và) - Tìm đƣờng đi từ G đến B. Quá trình rút gọn vấn đề nhƣ trên có thể biểu diễn dƣới dạng đồ thị (đồ thị và/hoặc) trong Hình 2.12. Ở đây mỗi bài toán tìm đƣờng đi từ một thành phố tới một thành phố khác ứng với một trạng thái. Các trạng thái kết thúc là các trạng thái ứng với các bài toán tìm đƣờng đi, chẳng hạn từ A đến C, hoặc từ D đến E, bởi vì đã có đƣờng nối A với C, nối D với E. b) Đồ thị và / hoặc Hình 2.16. Đồ thị và hoặc biểu diễn toán tử a b, c, d 49
50. Không gian trạng thái mô tả việc quy vấn đề về các vấn đề con có thể biểu diễn dƣới dạng đồ thị định hƣớng đặc biệt đƣợc gọi là đồ thị và/hoặc. Đồ thị này đƣợc xây dựng nhƣ sau: Mỗi bài toán ứng với một đỉnh của đồ thị. Nếu có một toán tử quy một bài toán về một bài toán khác, chẳng hạn R a b, thì trong đồ thị sẽ có cung gán nhãn R đi từ đỉnh a tới đỉnh b. Đối với mỗi toán tử quy một bài toán về một số bài toán con, chẳng hạn R a b, c, d đƣợc biểu diễn bởi đồ thị trong Hình 2.13. Ví dụ 2.15: Giả sử chúng ta có a, b, c, d, e, f, g, h, i, j, k, l là các bài toán. Trạng thái ban đầu (bài toán cần giải) là a. Tập các toán tử gồm: R1 a d, e, f R2 a d, k R3 a g, h R4 d b, c R5 f i R6 f c, j R7 k e, l R8 k h Tập các trạng thái kết thúc (các bài toán sơ cấp) là T = {b, c, g, e, j, l}. Câu hỏi đặt ra là bài toán a có giải đƣợc hay không và chỉ la một cách giải (nếu có). Khi đó, d, e, f là các đỉnh kề đỉnh a theo toán tử R1, còn d, k là các đỉnh kề a theo toán tử R2. Tại đỉnh a, ta có các toán tử R1, R2, R3 quy bài toán a về các bài toán con khác nhau, do đó a đƣợc giải quyết nếu hoặc {d, e, f}, hoặc {d, k}, hoặc {g, h} đƣợc giải quyết. Hình 2.17. Minh họa đồ thị và/hoặc 50
51. trong Hình 2.14. bằng cách áp dụng liên tiếp các toán tử, ta có thể đƣa bài toán cần giải về một tập các bài toán con. Chẳng hạn, trong ví dụ trên nếu ta áp dụng các toán tử R1, R4, R6, ta sẽ quy bài toán a về tập các bài toán con {b, c, e, f}, tất cả các bài toán con này đều là sơ cấp. Từ các toán tử R1, R4 và R6 ta xây dựng đƣợc một cây trong hình 2.15(a), cây này đƣợc gọi là cây nghiệm. Cây nghiệm đƣợc định nghĩa nhƣ sau: Cây nghiệm là một cây, trong đó: Hình 2.18. Cây nghiệm Gốc của cây ứng với bài toán cần giải. Tất cả các lá của cây là các đỉnh kết thúc (đỉnh ứng với các bài toán sơ cấp). Nếu u là đỉnh trong của cây, thì các đỉnh con của u là các đỉnh kề u theo một toán tử nào đó. Các đỉnh của đồ thị và/hoặc sẽ đƣợc gắn nhãn giải đƣợc hoặc không giải đƣợc. Các đỉnh giải được đƣợc xác định đệ quy nhƣ sau: Các đỉnh kết thúc là các đỉnh giải được. Nếu u không phải là đỉnh kết thúc, nhƣng có một toán tử R sao cho tất cả các đỉnh kề u theo R đều giải đƣợc thì u giải được. Các đỉnh không giải được đƣợc xác định đệ quy nhƣ sau: Các đỉnh không phải là đỉnh kết thúc và không có đỉnh kề, là các đỉnh không giải được. Nếu u không phải là đỉnh kết thúc và với mọi toán tử R áp dụng đƣợc tại u đều có một đỉnh v kề u theo R không giải đƣợc, thì u không giải được. Ta có nhận xét rằng, nếu bài toán a giải được thì sẽ có một cây nghiệm gốc a, và ngƣợc lại nếu có một cây nghiệm gốc a thì a giải được. Hiển nhiên là, một bài toán giải đƣợc có thể có nhiều cây nghiệm, mỗi cây nghiệm biểu diễn một cách giải bài toán đó. Chẳng hạn trong ví dụ đã nêu, bài toán a có hai cây nghiệm trong Hình 2.15. Thứ tự giải các bài toán con trong một cây nghiệm là nhƣ sau. Bài toán ứng với đỉnh u chỉ đƣợc giải sau khi tất cả các bài toán ứng với các đỉnh con của u đã đƣợc giải. 51
52. Chẳng hạn, với cây nghiệm trong Hình 2.15(a), thứ tự giải các bài toán có thể là b, c, d, j, f, e, a. Với cây nghiệm trong Hình 2.15(b), thứ tự giải các bài toán có thể là b, c, d, e, l, k, a. Vấn đề là tìm kiếm trên đồ thị và/hoặc để xác định đƣợc đỉnh ứng với bài toán ban đầu là giải đƣợc hay không giải đƣợc, và nếu nó giải đƣợc thì xây dựng một cây nghiệm cho nó. c) Tìm kiếm trên đồ thị và/hoặc Ta sẽ sử dụng kỹ thuật tìm kiếm theo độ sâu trên đồ thị và/hoặc để đánh dấu các đỉnh. Các đỉnh sẽ đƣợc đánh dấu giải đƣợc hoặc không giải đƣợc theo định nghĩa đệ quy về đỉnh giải đƣợc và không giải đƣợc. Xuất phát từ đỉnh ứng với bài toán ban đầu, đi xuống theo độ sâu, nếu gặp đỉnh u là đỉnh kết thúc thì nó đƣợc đánh dấu giải đƣợc. Nếu gặp đỉnh u không phải là đỉnh kết thúc và từ u không đi tiếp đƣợc, thì u đƣợc đánh dấu không giải đƣợc. Khi đi tới đỉnh u, thì từ u ta lần lƣợt đi xuống các đỉnh v kề u theo một toán tử R nào đó. Nếu đánh dấu đƣợc một đỉnh v không giải đƣợc thì không cần đi tiếp xuống các đỉnh v còn lại. Tiếp tục đi xuống các đỉnh kề u theo một toán tử khác. Nếu tất cả các đỉnh kề u theo một toán tử nào đó đƣợc đánh dấu giải đƣợc thì u sẽ đƣợc đánh dấu giải đƣợc và quay lên cha của u. Còn nếu từ u đi xuống các đỉnh kề nó theo mọi toán tử đều gặp các đỉnh kề đƣợc đánh dấu không giải đƣợc, thì u đƣợc đánh dấu không giải đƣợc và quay lên cha của u. Ta sẽ biểu diễn thủ tục tìm kiếm theo độ sâu và đánh dấu các đỉnh đã trình bày trên bởi hàm đệ quy Solvable(u). Hàm này nhận giá trị true nếu u giải đƣợc và nhận giá trị false nếu u không giải đƣợc. Trong hàm Solvable(u), ta sẽ sử dụng Biến Ok. Với mỗi toán tử R áp dụng đƣợc tại u, biến Ok nhận giá trị true nếu tất cả các đỉnh v kề u theo R đều giải đƣợc, và Ok nhận giá trị false nếu có một đỉnh v kề u theo R không giải đƣợc. Hàm Operator(u) ghi lại toán tử áp dụng thành công tại u, tức là Operator(u) = R nếu mọi đỉnh v kề u theo R đều giải đƣợc. function Solvable(u) Input: - Đồ thị và/ hoặc; - Bài toán u Output: Solvable(u) =true: u giải đƣợc Solvable(u) =false: u không giải đƣợc Begin 52
53. 1. if u là đỉnh kết thúc then {Solvable true; stop}; 2. if u không là đỉnh kết thúc và không có đỉnh kề then {Solvable(u)  false; stop}; 3. for mỗi toán tử R áp dụng đƣợc tại u do {Ok  true; for mỗi v kề u theo R do if Solvable(v) = false then {Ok  false; exit}; if Ok then {Solvable(u)  true; Operator(u)  R; stop}} 4. Solvable(u)  false; End; Mô tả hoạt động của hàm Solvable(u) với u=a nhƣ sau: Solvable(a) Xét R1 tại a - Xét Solvable(d) Xét R4 áp dụng tại d - Solvable(b) ta có b T Solvable(b) = true - Solvable(c) ta có c T Solvable(c) = true - Do đó Solvable(d) = true, Operator(d) =R4 - Xét Solvable(e) do e T Solvable(e) =true - Xét Solvable(f) Xét R5 áp dụng tại f, xét Solvale(i)=false (do i T) Xét R6 áp dụng tại f, xét Solvale(c)=true (do c T), Solvale(j)=true (do j T) Solvale(f)= true và Operator(f)=R6 Solvable(a)=true, Operator(a)=R1 Kết luận: a giải đƣợc Để tìm phƣơng án giải, ta tính Operator(a)=R1, Operator(d) =R4 và Operator(f)=R6 và kết quả chính là Hình 2.15(a) Ví dụ 2.16: Cho các bài toán và toán tử sau: R1 a →c, l R2 c →g, e, b R3 a →h, c R4 l →b, j 53
54. R5 l→j, d R6 g →i Tập các trạng thái kết thúc T = {h, i, b, d, j} Bài toán gốc là a. - Xây dựng đồ thị và/hoặc tƣơng ứng với các bài toán và toán tử. - Thực hiện từng bƣớc giải thuật tìm kiếm trên đồ thị và/hoặc để trả lời câu hỏi bài toán a có giải đƣợc hay không và tìm lời giải nếu có. Hình 2.19. Đồ thị và/ hoặc trong Ví dụ 2.16 *Tìm kiếm trên đồ thị và/hoặc Solvable(a) Xét R1 tại a Solvable(c) Xét R2 áp dụng tại c Solvable(h)=true do h T Solvable(g) Solvable(i)=true do i T Solvable(g)= true và Operator(g)=R6 Solvable(b)=true do b T Solvable(c) = true và Operator(c)=R2 Solvable(l) Xét R4 tại l Solvable(b)=true do b T Solvable(j)=true do j T Solvable(l) = true và Operator(l)=R4 Solvable(a) = true và Operator(a)=R1 Kết luận: a giải đƣợc Cây nghiệm tƣơng ứng: 54
55. Hình 2.20. Cây nghiệm trong ví dụ 2.16 Ví dụ 2.17: Tƣơng tự Ví dụ 2.16, tập các trạng thái kết thúc T = {h, i, b, d}. Thực hiện từng bƣớc giải thuật tìm kiếm trên đồ thị và/hoặc để trả lời câu hỏi bài toán a có giải đƣợc hay không và tìm lời giải nếu có. Solvable(a) Xét R1áp dụng tại a Solvable(c) Xét R2 áp dụng tại c Solvable(h)=true do h T Solvable(g) Solvable(i)=true do i T Solvable(g)= true và Operator(g)=R6 Solvable(b)=true do b T Solvable(c) = true và Operator(c)=R2 Solvable(l) Xét R4 tại l Solvable(b)=true do b T Solvable(j)=false do j T Xét R5 tại l Solvable(d)=true do b T Solvable(j)=false do j T Do xét cả R4 và R5 đều không giải đƣợc nên Solvable(l) = false Vậy R1 áp dụng tại a không giải đƣợc Xét R3 áp dụng tại a Solvable(c) = true (tƣơng tự nhƣ xét R1 áp dụng tại a) 55
56. Solvable(h) = true do h T Solvable(a) = true và Operator(a)=R3 Kết luận: a giải đƣợc Cây nghiệm tƣơng ứng: Hình 2.21. Cây nghiệm trong ví dụ 2.17 Nhận xét Hoàn toàn tƣơng tự nhƣ thuật toán tìm kiếm theo độ sâu trong không gian trạng thái, thuật toán tìm kiếm theo độ sâu trên đồ thị và/hoặc sẽ xác định đƣợc bài toán ban đầu là giải đƣợc hay không giải đƣợc, nếu cây tìm kiếm không có nhánh vô hạn. Nếu cây tìm kiếm có nhánh vô hạn thì chƣa chắc thuật toán đã dừng, vì có thể nó bị xa lầy khi đi xuống nhánh vô hạn. Trong trƣờng hợp này ta nên sử dụng thuật toán tìm kiếm sâu lặp. Nếu bài toán ban đầu giải đƣợc, thì bằng cách sử dụng hàm Operator ta sẽ xây dựng đƣợc cây nghiệm. 2.5. Các chiến lƣợc tìm kiếm kinh nghiệm Các kỹ thuật tìm kiếm mù rất kém hiệu quả và trong nhiều trƣờng hợp không thể áp dụng đƣợc. Trong chƣơng này, chúng ta sẽ nghiên cứu các phƣơng pháp tìm kiếm kinh nghiệm (tìm kiếm heuristic), đó là các phƣơng pháp sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm. 2.5.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 về vấn đề để đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u, chúng ta sẽ xác định một giá trị số h(u), số này đánh giá"sự gần đích"của trạng thái u. Hàm h(u) đƣợc gọi là hàm đánh giá. Chúng ta sẽ sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm. Trong quá trình tìm kiếm, tại mỗi bƣớc ta sẽ chọn trạng thái để phát triển là trạng thái có giá trị 56
57. hàm đánh giá nhỏ nhất, trạng thái này đƣợc xem là trạng thái có nhiều hứa hẹn nhất hƣớng tới đích. Các kỹ thuật tìm kiếm sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm đƣợc gọi chung là các kỹ thuật tìm kiếm kinh nghiệm (heuristic search). Các giai đoạn cơ bản để giải quyết vấn đề bằng tìm kiếm kinh nghiệm nhƣ sau: - Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử của vấn đề; - Xây dựng hàm đánh giá; - Thiết kế chiến lƣợc chọn trạng thái để phát triển ở mỗi bƣớc; - Xây dựng hàm đánh giá. Trong tìm kiếm kinh nghiệm, hàm đánh giá đóng vai trò cực kỳ quan trọng. Chúng ta có xây dựng đƣợc hàm đánh giá cho ta sự đánh giá đúng các trạng thái thì tìm kiếm mới hiệu quả. Nếu hàm đánh giá không chính xác, nó có thể dẫn ta đi chệch hƣớng và do đó tìm kiếm kém hiệu quả. Hàm đánh giá đƣợc xây dựng tùy thuộc vào vấn đề. Sau đây là một số ví dụ về hàm đánh giá: Ví dụ 2.18: Trong bài toán tìm kiếm đƣờng đi trên bản đồ giao thông, ta có thể lấy độ dài của đƣờng chim bay từ một thành phố tới một thành phố đích làm giá trị của hàm đánh giá. Ví dụ 2.19: Xét bài toán 8 số, có thể đƣa ra hai cách xây dựng hàm đánh giá: - Hàm h1: Với mỗi trạng thái u thì h1(u) là số quân không nằm đúng vị trí của nó trong trạng thái đích. Chẳng hạn trạng thái đích ở bên phải Hình 2.17, và u là trạng thái ở bên trái Hình 2.17, thì h1(u) = 4, vì các quân không đúng vị trí là 3, 8, 6 và 1. Hình 2.22. Hai hàm đánh giá trạng thái u - Hàm 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. ở đây khoảng cách đƣợc hiểu là số ít nhất các dịch chuyển theo hàng hoặc cột để đƣa một quân tới vị trí của nó trong trạng thái đích. Chẳng hạn với trạng thái u và trạng thái đích nhƣ trong Hình 2.17, ta có: h2(u) = 2 + 3 + 1 + 3 = 9 (vì quân 3 cần ít nhất 2 dịch chuyển, quân 8 cần ít nhất 3 dịch chuyển, quân 6 cần ít nhất 1 dịch chuyển và quân 1 cần ít nhất 3 dịch chuyển). 57
58. Hai chiến lƣợc tìm kiếm kinh nghiệm quan trọng nhất là tìm kiếm tốt nhất - đầu tiên (best-first search) và tìm kiếm leo đồi (hill-climbing search). Có thể xác định các chiến lƣợc này nhƣ sau: Tìm kiếm tốt nhất đầu tiên = 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á 2.5.2 Tìm kiếm tốt nhất đầu tiên Tìm kiếm tốt nhất - đầu tiên (best-first search) là tìm kiếm theo bề rộng đƣợc hƣớng dẫn bởi hàm đánh giá. Nhƣng nó khác với tìm kiếm theo bề rộng ở chỗ, trong tìm kiếm theo bề rộng ta lần lƣợt phát triển tất cả các đỉnh ở mức hiện tại để sinh ra các đỉnh ở mức tiếp theo, còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển là đỉnh tốt nhất đƣợc xác định bởi hàm đánh giá (tức là đỉnh có giá trị hàm đánh giá là nhỏ nhất), đỉnh này có thể ở mức hiện tại hoặc ở các mức trên. Hình 2.23. Đồ thị không gian trạng thái Ví dụ 2.20: Xét không gian trạng thái đƣợc biểu diễn bởi đồ thị trong Hình 2.18, trong đó trạng thái ban đầu là A, trạng thái kết thúc là B. Giá trị của hàm đánh giá là các số ghi cạnh mỗi đỉnh. Quá trình tìm kiếm tốt nhất - đầu tiên diễn ra nhƣ sau: Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C, D và E. Trong ba đỉnh này, đỉnh D có giá trị hàm đánh giá nhỏ nhất, nó đƣợc chọn để phát triển và sinh ra F, I. Trong số các đỉnh chƣa đƣợc phát triển C, E, F, I thì đỉnh E có giá trị đánh giá nhỏ nhất, nó đƣợc chọn để phát triển và sinh ra các đỉnh G, K. Trong số các đỉnh chƣa đƣợc phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc. Cây tìm kiếm tốt nhất - đầu tiên đƣợc biểu diễn trong Hình 2.19. 58
59. Hình 2.24. Cây tìm kiếm tốt nhất – đầu tiên Sau đây là thủ tục tìm kiếm tốt nhất - đầu tiên. Trong thủ tục này, chúng ta sử dụng danh sách L để lƣu các trạng thái chờ phát triển, danh sách đƣợc sắp theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái có giá trị hàm đánh giá nhỏ nhất ở đầu danh sách. Input: Không gian trạng thái có uo là trạng thái đầu, T là tập trạng thái kết thúc. Output: Tìm kiếm thành công (có đƣờng đi từ uo đến một trạng thái kết thúc) hoặc thất bại. Trong trƣờng hợp tìm kiếm thành công thi đƣa ra đƣờng đi. Procedure Best_First_Search; 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 {thông báo 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 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 L sao cho L đƣợc sắp theo thứ tự tăng dần của hàm đánh giá; Father(v)u; } End; Ví dụ 2.21: 59