Giáo trình Trí tuệ nhân tạo

102 trang phuongnguyen 150

Download

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

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

giao_trinh_tri_tue_nhan_tao.doc

Nội dung text: Giáo trình Trí tuệ nhân tạo

o0o GIÁO TRÌNH TRÍ TUỆ NHÂN TẠO
NÓI ĐẦU Trí tuệ nhân tạo là môn cơ sở chuyên ngành trong chương trình đào tạo kỹ sư và cử nhân Tin học. Mục đích của môn học này là trang bị cho sinh viên những kiến thức cơ bản nhất về các phương pháp giải quyết vấn đề và các kỹ thuật xử lý tri thức. Trên cơ sở các kiến thức tiếp thu được học sinh có thể đi sâu tìm hiểu về các chuyên đề khác như hệ chuyên gia, hệ hỗ trợ ra quyết định, phần mềm dạy học thông minh Nội dung giáo trình được trình bày thành ba chương: Chương 1: Nội dung chương này trình bày các khái niệm cơ bản về khoa học Trí tuệ nhân tạo. Chương 2: Đây là chương trọng tâm của giáo trình. Ở đây chúng tôi giới thiệu các phương pháp biểu diễn vấn đề, các kỹ thuật tìm kiếm lời giải. Chương 3. Trình bày các kỹ thuật biểu diễn tri thức và xử lý tri thức. Vì thời lượng của môn học quá ít nên trong chương này chúng tôi chỉ trình bày những nét hết sức cơ bản và không đi sâu vào các vấn đề cụ thể. Giáo trình này được biên soạn để làm tài liệu giảng dạy cho giáo viên và học tập cho sinh viên đồng thời là tài liệu tham khảo cho những ai quan tâm đến Trí tuệ nhân tạo. Trong quá trình biên soạn tác giả đã nhận được ý kiến đóng góp và động viên của bạn bè, đồng nghiệp và đặc biệt là các cán bộ có kinh nghiệm trong khoa CNTT Đại học Vinh và ĐHBK Hà nội về lĩnh vực này. Nhân đây tác giả muốn bày tỏ lòng biết ơn tới TS Nguyễn Thanh Thuỷ (ĐHBK Hà nội) người đã giúp đỡ tác giả trong suốt quá trình biên soạn giáo trình này. Để hoàn thành tập giáo trình này, mặc dù đã cố gắng rất nhiều nhưng tác giả tin rằng vẫn không tránh khỏi các sai sót và hạn chế. Hy vọng rằng tác giả sẽ tiếp tục nhận được các ý kiến góp ý quý báu của bạn đọc và đồng nghiệp. 2
Vinh, tháng 7 năm 2000 Tác giả Chương I TỔNG QUAN VỀ TÌNH HÌNH NGHIÊN CỨU VÀ ỨNG DỤNG CỦA TRÍ TUỆ NHÂN TẠO 1.1. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT Những năm gần đây, ta thường gặp các thuật ngữ: Máy tính thông minh, máy tính thế hệ thứ 5, trí tuệ nhân tạo, hệ chuyên gia Sự xuất hiện của các ngôn ngữ lập trình: LISP (List Processing), PROLOG đã mở đường cho việc xây dựng và áp dụng vào thực tế hàng loạt các chương trình có khả năng xử lý "thông minh". Trước đây, thuật ngữ trí tuệ nhân tạo (TTNT) thường được hiểu như là các máy có khả năng "suy nghĩ", có khả năng cạnh tranh với bộ óc con người. Ý tưởng về mô hình các máy thông minh đã được đưa ra hàng trăm năm trước đây, song mãi đến năm 1930, vấn đề này mới được nghiên cứu một cách nghiêm túc, sau khi Allen Turing công bố các kết quả đầu tiên. Phát hiện của Turing: - Xây dựng máy tính dựa trên các phép toán cơ sở của logic như AND, OR, NOT. - Máy tính được điều khiển bởi các chương trình lưu ở bộ nhớ trong. Năm 1956: Chương trình dẫn xuất kết luận trong hệ hình thức được công bố. Năm 1959: Chương trình chứng minh các định lý hình học phẳng và chương trình giải quyết bài toán tổng quát GPS (General Problem Solving ) được đưa ra. Năm 1960: Mcathy đưa ra ngôn ngữ lập trình LISP. Thuật ngữ TTNT do Marvin Minsky (của MIT- Massachussets Institute of Technology) đưa ra năm 1961. Đến đây các nghiên cứu về trí tuệ nhân tạo bắt 3
đầu phát triển mạnh. Trong thời gian này, các chương trình tính tích phân, chơi cờ, chứng minh định lý toán học cũng được công bố. Năm 1961: Chương trình tính tích phân bất định. Năm 1963: Các chương trình Heuristics (suy nghiệm, phát hiện), chương trình chứng minh định lý hình học không gian có tên "Tương tự", chương trình chơi cờ của Samuel. Năm 1964: Chương trình giải phương trình đại số sơ cấp, chương trình trợ giúp ELIZA (phân tích tâm lý). Năm 1966: Chương trình phân tích và tổng hợp tiếng nói. Năm 1968: Chương trình nhận dạng hình ảnh, Robot chế tạo dựa theo đồ án mắt- tay, chương trình học nói. Hạn chế của giai đoạn này là khả năng của máy tính bị hạn chế về cả bộ nhớ và thời gian thực hiện. Sang những năm 70, máy tính phát triển đáng kể về chất (bộ nhớ, tốc độ), song TTNT chưa có thành công đáng kể vì trong quá trình tìm kiếm lời giải bài toán thường gặp phải sự bùng nổ tổ hợp. Cuối những năm 70 các nhà nghiên cứu đã đạt được những thành công đáng kể trong các lĩnh vực: - Xử lý ngôn ngữ tự nhiên - Biểu diễn tri thức - Lý thuyết giải quyết vấn đề - Hệ chuyên gia. Năm 1972, ngôn ngữ Prolog ra đời là một sự kiện quan trọng trong sự phát triển của khoa học TTNT. Năm 1981, ngôn ngữ Prolog được chọn làm ngôn ngữ cơ sở trong dự án xây dựng máy tính thế hệ thứ 5 của Nhật. Điều này đã làm thay đổi khá nhiều tình hình phát triển TTNT ở Mỹ và Châu Âu. 4
Cuối những năm 80, đầu những năm 90 có khá nhiều sản phẩm dân dụng trình độ cao sử dụng TTNT như: máy giặt, máy ảnh. Những năm 90, một số lĩnh vực trí tuệ nhân tạo được phát triển mạnh như: + Các hệ thống nhận dạng và xử lý hình ảnh + Mạng Neuron + Kỹ thuật xử lý tri thức, dữ liệu hỗn hợp + Hệ hỗ trợ ra quyết định dựa trên tri thức + Biểu diễn tri thức và dữ liệu hướng đối tượng + Kỹ thuật Multimedia (đa phương tiện), Hypertext (siêu văn bản). 1.2. 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 và điều khiển học. Tuy vậy những tiến bộ trong kỹ thuật vi điện tử cũng là một yếu tố tạo tiền đề cho sự thành công của các chương trình TTNT. Những tiền đề hình thành và các hướng nghiên cứu, ứng dụng cơ bản và các hướng phát triển chính của trí tuệ nhân tạo được thể hiện bởi sơ đồ sau: Điều khiển học Logic hình Xử lý NN thức tự nhiên Trí tuệ nhân Tâm lý học Các hệ xử tạo Người nhận thức lý ký hiệu (Artificial máy Intelligence) Xử lý danh Hệ chyên sách gia Các kỹ thuật và môi Kỹ thuật vi điện trường lập trình tử hiện đại nâng cao 5 Hình 1.1. Những tiền đề để hình thành TTNT
Các hệ thông máy tính phát triển 1.3. CÁC KHÁI NIỆM CƠ BẢN CỦA KHOA HỌC TTNT 1.3.1 Trí tuệ của con người (Human Intelligence) Hiện nay chưa có định nghĩa thống nhất về trí tuệ con người. Sau đây là một số định nghĩa được chú ý nhiều nhất: A.Turing: "Trí tuệ là những gì có thể đánh giá được thông qua các phép kiểm tra (test) thông minh". Từ điển bách khoa toàn thư Webster: "Trí tuệ là khả năng: 1. Phản ánh một cách thích hợp lại 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. 2. Hiểu rõ những mối liên hệ qua lại giữ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ục đích nào đó". Các chuyên gia tâm lý học nhận thức chỉ ra rằng hoạt động trí tuệ của con người bao gồm 4 thao tác: 1. Xác định tập các đích (goals) cần đạt tới. 2. Thu tập sự kiện (facts) và các luật suy diễn (interence) để đạt tới các đích đặt ra. 3. Thu gọn quá trình suy luận nhằm xác định nhanh chóng tập những luật suy diễn có thể sử dụng được để đạt tới một đích trung gian nào đó. 6
4. Áp dụng các cơ chế suy diễn cụ thể, dựa trên các thao tác thu gọn quá trình suy luận và các sự kiện trung gian mới được tạo ra để dẫn dắt từ những sự kiện ban đầu đi tới những đích đặt ra. Ví dụ 1.1. * Thao tác1. Cần xác định cách đi tốt nhất từ nhà tới cơ quan. * Thao tác2. + Các sự kiện: Thời tiết, sức khoẻ, ngày nghỉ hay làm việc, loại phương tiện, khoảng cách, giá cả từng loại phương tiện, thời gian, tình hình kinh tế, giá cả nhiên liệu, + Các luật suy diễn: Giả sử ta thu nạp được các luật suy diễn sau: Luật 1: Nếu hôm đó là ngày nghỉ Thì không phải đi làm Luật 2: Nếu thời tiết xấu Thì công viên không có người Luật 3: Nếu thời tiết xấu Thì nên đi đường nhựa Luật 4: Nếu thời tiết đẹp Thì đi đường tắt Luật 5: Nếu tình hình chính trị xấu Thì tình hình kinh tế xấu Luật 6: Nếu giá cả tăng Thì tình hình kinh tế xấu Luật 7: Nếu thời tiết xấu và đi bằng xe Thì đi bằng xe buýt Luật 8: Nếu thời tiết đẹp và đi bằng xe Thì đi xe đạp Luật 9: Nếu đường xa Thì đi bằng xe Luật 10: Nếu đường gần Thì đi bộ Luật 11: Nếu đi đường nhựa Thì đi bằng xe. * Thao tác 3: Giả sử hôm đó thời tiết xấu, khi đó cơ chế thu gọn quá trình suy luận cho phép chỉ xét các luật liên quan tới thời tiết xấu (luật 2, 3, 7) hoặc chỉ các luật có liên quan tới đích đặt ra (luật 1, 3, 4, 7, 8, 9, 10, 11). * Thao tác 4: Chú ý tới các luật thoả mãn điều kiện "thời tiết xấu", chỉ có luật 2, 3. Tuy nhiên chỉ có luật 3 được lưu lại và ta có sự kiện khẳng định mới là "đi đường nhựa". Sự kiện này được nạp thêm vào tập các sự kiện đã biết. Tiếp tục 7
quá trình, ta đi đến kết luận để đi từ nhà tới cơ quan, nếu thời tiết xấu, nên đi bằng xe buýt (xem sơ đồ trên). 1.3.2. Trí tuệ máy (Machine Intellgence) Trí tuệ máy chưa có định nghĩa, song có một số dấu hiệu quan trọng để đánh giá trí tuệ máy là: 1. Khả năng học. 2. Khả năng mô phỏng các hành vi sáng tạo của con người, nghĩa là có thể giải quyết một bài toán sáng tạo nào đó giống như một chuyên gia (chương trình chơi cờ). 3. Khả năng trừu tượng hoá, khái quát hoá và suy diễn. 4. Khả năng tự giải thích hành vi. 5. Khả năng thích nghi với tình huống mới trong đó gồm có khả năng thu nạp tri thức và dữ liệu. 6. Khả năng xử lý các biểu diễn hình thức như các kí hiệu tượng trưng, danh sách. 7. Khả năng sử dụng các tri thức, Heuristics. 8. Khả năng xử lý các thông tin không đầy đủ, không chính xác. 1.3.3. Vai trò của TTNT trong CNTT Khoa học TTNT có nhiệm vụ: - Nghiên cứu các kỹ thuật làm cho máy tính có thể "suy nghĩ một cách thông minh" . - 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 nhờ tìm kiếm trong không gian bài toán hay phân rã bài toán con, do vậy nó chia nhỏ quá trình suy nghĩ này thành những bước cơ bản. - Tạo nên cách tiếp cận đơn giản và có cấu trúc để xây dựng các chương trình ra quyết định phức hợp đòi hỏi phải dựa trên những tri thức nhất định. 8
- TTNT làm cho máy tính có khả năng suy nghĩ. Có thể mô phỏng quá trình học của con người, trên cơ sở đó thu nạp được những thông tin mới phục vụ cho quá trình suy diễn sau đó. Sự ra đời và phát triễn của trí tuệ nhân tạo tạo nên những bước nhảy vọt về chất trong kỹ thuật và kỹ nghệ xử lý thông tin. Nó 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ờ. Những đặc điểm của công nghệ xử lý thông tin mới dựa trên nền tảng TTNT bao gồm: 1. Nhờ những công cụ hình thức hoá, các tri thức thủ tục và tri thức mô tả có thể biểu diễn được trong máy tính, quá trình giải quyết bài toán được tiến hành hữu hiệu hơn. 2. Các hệ thống TTNT có tính thích nghi cao, 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. 3. Các hệ thống trí tuệ nhân tạo hoạt động dựa trên tri thức và các Heuristics, trong khi đó các hệ thống xử lý thông tin truyền thống dựa trên các thuật giải. 4. Việc bảo trì các hệ thống TTNT do các kỹ sư xử lý tri thức đảm nhận, trong khi đó việc bảo trì các chương trình do các lập trình viên chịu trách nhiệm. Ta có thể so sánh kỹ thuật lập trình truyền thống và kỹ thuật xử lý ký hiệu trong TTNT như sau: Lập trình truyền thống Xử lý ký hiệu - Định hướng xử lý các dữ liệu - Định hướng xử lý các ký hiệu tượng trưng. (số, văn bản). - CSDL được đánh địa chỉ số. - Cơ sở tri thức được cấu trúc theo theo các ký hiệu. - Xử lý theo thuật toán. - Xử lý theo các thuật giải Heuristic, cơ chế lập luận. - Xử lý tuần tự hay theo mẻ. - Xử lý theo chế độ tương tác cao (hội thoại ngôn ngữ tự nhiên). 9
- Không giải thích trong quá - Có thể giải thích hành vi hệ thống trong quá trình trình thực hiện. thực hiện. 1.3.4. Các kỹ thuật TTNT Các kỹ thuật TTNT thường thiên về xử lý các ký hiệu tượng trưng, vì vậy nó thường khá phức tạp khi cài đặt cụ thể. Hơn nữa nó đòi hỏi phải sử dụng những tri thức chuyên môn thuộc vào các lĩnh vực khác nhau. Những tri thức này có các đặc điểm sau: - Khối lượng tri thức cần để giải quyết bài toán có thể rất lớn. - Khó có thể đặc trưng hoá và biểu diễn tri thức chuyên gia một cách chính xác. - Tri thức đối với bài toán thường xuyên bị thay đổi. Do vậy các đặc tính quan trọng của kỹ thuật TTNT: - Đạt được mức tổng quát. - Dễ hiểu đối với các chuyên gia con người cung cấp tri thức cho hệ thống. - Dễ sửa đổi, dễ hiệu chỉnh lỗi và dễ đưa vào những thay đổi cần thiết. - Dễ sử dụng trong nhiều tình huống khác nhau, kể cả khi các tri thức không chính xác và đầy đủ. - Dễ thu hẹp khả năng cần xét để đi tới lời giải cuối cùng. Với các yêu cầu trên ta có các phương pháp và kỹ thuật trí tuệ nhân tạo cơ bản sau: - Các phương pháp biểu diễn tri thức và kỹ nghệ xử lý tri thức - Các phương pháp giải quyết vấn đề - Các phương pháp Heuristics - Các phương pháp học - Các ngôn ngữ TTNT. Ngoài ra, các kỹ thuật của tin học truyền thống như: Xử lý danh sách, đệ quy, quay lui, sử dụng cú pháp hình thức cũng có liên quan trực tiếp đến TTNT. 10
1.3.5. Các thành phần trong hệ thống TTNT Mỗi hệ thống TTNH gồm hai thành phần cơ bản sau: + 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 thành phần này có quan hệ chặt chẽ với nhau. Thể hiện ở chỗ việc lựa chọn phương pháp biểu diễn tri thức sẽ quyết định phương pháp giải quyết vấn đề tương ứng có thể áp dụng. Ngược lại, phương pháp tìm kiếm sẽ có hiệu quả nếu phương pháp biểu diễn tri thức thích hợp. Dựa trên các thành phần của các hệ thống TTNT, có thể chia các hệ thống TTNT thành các loại sau: 1. Các hệ thống 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 cơ sở tri thức 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 tản mạn. 1.3.6. Các cách tiếp cận trong TTNT Từ đầu, các công trình nghiên cứu về TTNT được chia thành 2 hướng cơ bản: + Hướng phỏng sinh học: Mô phỏng hoàn toàn các hoạt động của bộ não, các tính chất tâm sinh lý của nó, trên cơ sở đó tái tạo trong máy tính hoặc các thiết bị kỹ thuật những khía cạnh khác nhau của TTNT. + Hướng phỏng vật lý: Định hướng vào các khía cạnh thực hành trong đó máy tính là công cụ thử nghiệm các chương trình cho phép đạt tới kết quả giống như hoạt động sáng tạo của con người. 11
Tuy nhiên, trong những năm gần đây hai hướng nghiên cứu này đã xích lại gần nhau. Bốn cách tiếp cận khác nhau trong TTNT: - Tạo lập các mạng thông minh - Tái tạo quá trình tiến hoá nhân tạo - Lập trình Heuristics - Biểu diễn và xử lý tri thức. Ở đây ta hiểu Mạng thông minh nhân tạo bao gồm một số lượng lớn các phần tử đơn giản (máy tính hoặc thiết bị vật lý khác) và mối liên hệ giữa chúng. Chẳng hạn mạng neuron nhân tạo nhằm tái tạo những phương thức tổ chức và cơ chế hoạt động của các neuron trong bộ não người. Ưu điểm của mạng neuron là khả năng thích nghi và khả năng học. Khó khăn của nó là khó tạo ra được 1010 neuron như bộ não người. Tái tạo quá trình tiến hoá nhân tạo là cách tiếp cận hướng tới xây dựng các hệ thống chương trình có khả năng mô phỏng quá trình tiến hoá tự nhiên thông qua hai hoạt động cơ bản là đột biến và lựa chọn. Các nghiên cứu về lập trình Heuristics có những mục đích: Giải thích bản chất của trí tuệ tự nhiên Sử dụng "trí tuệ máy" để giải quyết các bài toán sáng tạo khó. Biểu diễn và xử lý tri thức là cách tiếp cận dựa trên những đặc tả chính của bài toán đặt ra. Cách tiếp cận này thường sử dụng trong các hệ chuyên gia. 1.4. CÁC LĨNH VỰC NGHIÊN CỨU VÀ ỨNG DỤNG CƠ BẢN CỦA TTNT Có thể phân chia các lĩnh vực nghiên cứu và ứng dụng quan trọng trong TTNT theo bốn hướng cơ bản sau: 1. Mô hình hoá trên máy tính các chức năng khác nhau trong quá trình sáng tạo: Các trò chơi, chứng minh định lý tự động, tổng hợp các chương trình, phân tích và tổng hợp các tác phẩm nghệ thuật, 12
2. Nâng cao khả năng trí tuệ "bên ngoài" của máy tính, bao gồm các nghiên cứu cơ bản và ứng dụng, gắn liền với các giao tiếp, hội thoại bằng cách sử dụng các kỹ thuật tìm kiếm và suy diễn. 3. Nâng cao trí tuệ "bên trong" của máy tính trên cơ sở chế tạo các máy tính thế hệ mới với các kiến trúc vật lý mới dựa trên các nguyên lý của TTNT. 4. Chế tạo người máy thông minh, có khả năng thực hiện các thao tác phức tạp, biết" suy nghĩ" và "hành động" để đạt được đích đặt ra. 1.4.1. Các lĩnh vực nghiên cứu cơ bản của TTNT 1. Lý thuyết giải quyết vấn đề và các kỹ thuật suy diễn thông minh Các phương pháp giải quyết vấn đề bao gồm: - Phương pháp biểu diễn bài toán trong không gian trạng thái - Phương pháp quy bài toán về các bài toán con - Phương pháp GPS - Phương pháp hình thức sử dụng cách tiếp cận logic. 2. Lý thuyết tìm kiếm Heuristics Bao gồm các phương pháp và kỹ thuật tìm kiếm, sử dụng các tri thức nảy sinh từ bản thân bài toán để rút ngắn quá trình giải, nhanh chóng thu được kết quả. 3. Lý thuyết biểu diễn tri thức và kỹ thuật xử lý tri thức Bốn phương pháp biểu diễn tri thức: - Dùng logic mệnh đề, logic vị từ - Dùng các hệ sản xuất - Dùng frame - Dùng mạng ngữ nghĩa. 4. Lý thuyết nhận dạng Phát triển theo các hướng tiếp cận: - Lý thuyết thống kê về nhận dạng 13
- Lý thuyết cấu trúc về nhận dạng - Lý thuyết đại số về nhận dạng - Lý thuyết Heuristics về nhận dạng. * Hiện nay, vấn đề nhận dạng thông tin hình ảnh và tiếng nói đang là một thách thức đối với các chuyên gia TTNT. * Cách tiếp cận sử dụng mạng Neuron nhân tạo đang có nhiều hứa hẹn. 5. Các ngôn ngữ trí tuệ nhân tạo - Ngôn ngữ LISP (List Processing) - 1960 - PROLOG (Programinig for Logics) - 1972 - CLIPS - 1980. 1.4.2. Các ứng dụng cơ bản của TTNT Các ứng dựng cơ bản của TTNT bao gồm các lĩnh vực: 1. Kỹ thuật người máy 2. Các chương trình trò chơi 3. Xử lý ngôn ngữ tự nhiên 4. Các hệ thống xử lý tri thức và dữ liệu tích hợp. 1.4.3. Những nghiên cứu hiện đại xung quanh TTNT Những năm gần đây các nghiên cứu TTNT tập trung vào các lĩnh vực sau: - Lập trình logic, xử lý phép phủ định trong lập luận - Các phương pháp học, thu nạp tri thức - Giải thuật di truyền - Mạng neuron - Các hệ hỗ trợ quyết định dựa trên tri thức. 1.5. NHỮNG VẤN ĐỀ CHƯA ĐƯỢC GIẢI QUYẾT TRONG TTNT Hai vấn đề thách thức còn mở đối với các nhà nghiên cứu TTNT trong giai đoạn hiện nay là: 14
1. Trí tuệ nhân tạo có mô phỏng được phần lớn hoạt động của bộ não con người? 2. Liệu có tồn tại những khía cạnh trí tuệ con người về nguyên tắc là không mô phỏng được trên máy tính? Với các thành tựu đạt được cho thấy rằng các dự án xây dựng máy tính có khả năng suy nghĩ là có tính thực tiễn, song trong nhiều lĩnh vực máy tính còn thua xa so với hoạt động của hệ thần kinh con người. 1.5.1. Sự khác nhau cơ bản trong hoạt động giữa máy tính và bộ não người Sự khác nhau cơ bản trong hoạt động giữa máy tính và bộ não người được thể hiện rõ nét nhất ở các điểm sau: - Khả năng xử lý song song: Khả năng xử lý song song của bộ não rất lớn, máy tính chưa thể đạt đến được. Khả năng diễn giải: Con người có khả năng xem xét cùng một vấn đề theo nhiều phương pháp khác nhau, để từ đó diễn giải theo cách dể hiểu nhất. Các hệ thống TTNT tạo không thể mô phỏng được điều này. - Xử lý các đại lượng rời rạc và liên tục: Bộ não xử lý thông tin liên tục một cách dễ dàng như là một hoạt động bản năng. Nó dễ dàng kết hợp việc xử lý thông tin liên tục với thao tác xử lý thông tin rời rạc. Đối với Máy tính, xử lý thông tin liên tục còn là một thách đố ghê gớm. - Khả năng học: Đối với con người, khả năng học như là bản năng của bộ não. Con người có thể tiếp thu các tri thức từ thế giới bên ngoài, có khả năng học khi thông tin về thế giới xung quanh không đầy đủ, không chính xác, phụ thuộc vào tình huống. Máy tính chưa có những khả năng này. - Khả năng tự tổ chức: Khả năng tự tổ chức, điều chỉnh hành vi là điểm nổi bật trong hoạt động của bộ não con người. Nó cùng với khả năng học tạo nên khả năng thích nghi làm cho con người có thể hoà nhập với nhiều tình huống 15
khác nhau. Với máy tính, để thực hiện được khả năng này đòi hỏi phải có những đột biến trong chế tạo phần cứng. Đến nay chưa đáp ứng được. 1.5.2. Những vấn đề đặt ra trong tương lai 1. Nghiên cứu và thử nghiệm 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. 2. 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ới 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, thu thập và xử lý thông tin hình ảnh và tiếng nói. 3. 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 các bài toán phát biểu không đầy đủ, không chính xác, các bài toán phụ thuộc không gian, thời gian đòi hỏi xử lý tích hợp các tri thức và dữ liệu 16
Chương II CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ 2.1. GIẢI QUYẾT VẤN ĐỀ VÀ KHOA HỌC TTNT Từ đây cho hết giáo trình này các thuật ngữ "vấn đề" và "bài toán" được dùng tương đương. Có thể xem lịch sử phát triển của TTNT gắn liền với sự bùng nổ các kỹ thuật giải quyết vấn đề, từ các kỹ thuật Heuristics đến các kỹ thuật xử lý tri thức (xem hình vẽ 2.1). Nhiều hoạt động trong thực tiễn của con người (tính toán, quản lý, trò chơi, giải đáp câu đố, ) đều đòi hỏi sự tham gia của trí tuệ. Bài toán Phát biểu bài toán-Xác định phương pháp biểu diễn bài toán Sản sinh không gian bài toán Công Xác định lời nghệ Đ giải nhờ các lập Bài toán có thể giải nhờ thuật toán đa thức ngôn ngữ lập trình trình truyền thống S Xác định các tri thức đặc biệt để rút gọn không gian tìm kiếm Xây dựng các phương pháp biểu diễn tri thức và suy diễn Cài đặt hệ thống, lựa chọn ngôn ngữ, công cụ phù hợp Các hệ giải quyết vấn đề dựa vào tri thức Hình 2.1. Những khía cạnh khác nhau của trí tuệ nhân tạo 17
Máy tính trở thành công cụ đắc lực giúp con người trong công việc xử lý thông tin và giải quyết các nhiệm vụ ở mức độ trí tuệ ngày càng cao. Theo một nghĩa nào đó các máy tính hiện nay đã được trang bị trí tuệ nhân tạo. Trong một số lĩnh vực, máy tính vượt quá khả năng của con người. Tuy nhiên, có những bài toán con người giải quyết đơn giản thì máy tính chưa làm được. Cốt lõi của mọi hoạt động trí tuệ diễn ra trong máy tính cũng như bộ não con người là sự vận dụng linh hoạt các kỹ thuật giải quyết vấn đề. Trong chương này, chúng ta quan tâm đến các phương pháp giải quyết bài toán dựa trên một cách biểu diễn bằng mô hình hoá bài toán nào đó. 2.2. GIẢI QUYẾT VẤN ĐỀ CỦA CON NGƯỜI Cách giải quyết vấn đề của con người là mô hình thực tiễn quan trọng để các chuyên gia TTNT tìm cách mô phỏng lại trên máy tính quá trình giải quyết bài toán. Có hai bộ phận nghiên cứu quá trình giải quyết vấn đề của con người: + Khoa học về nhận thức: Nghiên cứu quá trình tổ chức, lưu trữ, truy nhập, xử lý và thu nạp tri thức trong bộ não người. + Tâm lý học nhận thức và khoa học điều khiển: Tạo ra các mô hình tổ chức bộ não. 2.2.1. Quá trình xử lý thông tin của con người Mô hình xử lý thông tin trong bộ não gồm 3 hệ thống con sau: - Hệ thống cảm nhận (perception subsystem) - Hệ thống nhận thức (cognitive subsystem) - Hệ thống hoạt động(action subsystem). Ta có thể mô tả quá trình xử lý thông tin của con người như sau: HỆ THỐNG XỬ LÝ THÔNG TIN CỦA CON NGƯỜI Kích Hệ thống thụ cảm Hệ thống nhận thức Hệ thống hành động Trả Cơ Bộ nhớ Bộ nhớ dài hạn Bộ nhớ Cơ quan thích lời quan đệm Bộ nhớ làm việc đệm hành thụ cảm động Bộ xử lý nhận thức Hình 2.2. Tổng quan về hệ thống xử lý thông tin của con người 18
2.2.2. Giải quyết vấn đề của con người Giải quyết vấn đề của con người là một trường hợp riêng của quá trình xử lý thông tin trong bộ não. Thực chất, đó là việc tìm cách đi từ tình huống ban đầu nào đó đến đích. Giải quyết vấn đề là một hoạt động đặc biệt của hệ thần kinh cần tới quá trình suy nghĩ, tìm kiếm trong không gian lời giải bộ phận để đi đến lời giải cuối cùng. Tuy nhiên, cần lưu ý rằng không phải mọi hoạt động xử lý thông tin đều là giải quyết vấn đề. Các chiến lược giải quyết vấn đề của con người: + Ước lượng mức độ phức tạp của vấn đề đặt ra: - Nếu đơn giản, giải quyết ngay bằng các thao tác cơ sở. - Nếu phức tạp, các cơ quan não tìm cách hiểu chi tiết nội dung của vấn đề để mã hoá, tìm phương pháp phù hợp. + Nới lỏng một vài ràng buộc của bài toán. + Phương pháp chia thành các bài toán con: Từ bài toán phức tạp, con người chia thành các bài toán nhỏ, ít phức tạp cho đến khi gặp các bài toán sơ cấp, giải quyết được ngay. + Tổng quát hoá bài toán : Chuyển các thông tin bên ngoài thành các kí hiệu làm cho bài toán dễ giải hơn. Quá trình này tạo ra một mô hình trí tuệ của bài toán, mô hình này thường được gọi không gian bài toán. * Không gian bài toán bao gồm: - Các dạng mẫu kí hiệu, mỗi dạng biểu diễn một trạng thái hay một tình huống bài toán. - Các mối liên kết giữa các dạng mẫu ký hiệu, mỗi mối liên kết tương ứng với các phép biến đổi từ dạng này sang dạng khác. 2.3. PHÂN LOẠI VẤN ĐỀ, CÁC ĐẶC TRƯNG CƠ BẢN CỦA VẤN ĐỀ Trước khi xem xét việc phân loại vấn đề, ta xét các bài toán sau: Bài toán 2.1. Bài toán trò chơi n2-1 số (n N, n>2). 19
Trong bảng ô vuông n hàng, n cột, mỗi ô chứa 1 số nằm trong phạm vi từ 1 đến n2-1 sao cho không có 2 ô có cùng giá trị. Có một ô trong bảng bị bỏ trống. Xuất phát từ một cách sắp xếp nào đó các số trong bảng hãy dịch chuyển ô trống sang phải, sang trái, lên trên, xuống dưới (nếu có thể ) để đưa về dạng sau: 1 2 3 1 2 3 4 4 5 6 5 6 7 8 7 8 9 10 11 12 13 14 15 a) b) Hình 2.3. Hình trạng đích trong trò chơi n2-1 số a) n=3 b) n= 4 Bài toán 2.2. Bài toán tháp Hà Nội. Cho 3 cọc 1, 2, 3. Ở cọc 1 ban đầu có n đĩa sắp theo thứ tự nhỏ dần từ dưới lên trên. Hãy tìm cách chuyển n đĩa đó sang cọc 3 với điều kiện: - Mỗi lần chỉ chuyển 1 đĩa - Chỉ sử dụng cọc trung gian 2 - Trong mỗi cọc, ở mỗi bước không cho phép đĩa to nằm trên đĩa nhỏ. 1 2 3 1 2 3 A A B A B B C C C C Hình 2.4. Bài toán tháp Hà Nội với n=3 Bài toán 2.3. Đố chữ Hãy thay các chữ cái bằng các chữ số từ 0 đến 9 sao cho không có 2 chữ cái được thay bởi cùng 1 số và thoả mãn: 20
S END + MORE MONEY 2.3.1. Phân loại vấn đề Các vấn đề được phân ra làm hai loại: + Vấn đề (bài toán) phát biểu chỉnh (well-formed problems): Đó là các bài toán có thể biết được hình trạng đầu, hình trạng đích và có thể quyết định khi nào vấn đề được coi là giải quyết xong. Các bài toán 2.1-2.3 trên đây là những vấn đề được phát biểu chỉnh. + Vấn đề (bài toán) phát biểu không chỉnh (ill-formed problems): Đó là các vấn đề được phát biểu chưa đầy đủ, thiếu dữ kiện. Các bài toán chẩn đoán và điều trị bệnh, bài toán xác định chất lượng sản phẩm là các bài toán phát biểu không chỉnh. 2.3.2. Các đặc trưng cơ bản của vấn đề Các vấn đề có các đặc trưng cơ bản sau: - Bài toán có thể phân tích thành các bài toán dễ giải hơn không? - Các bước giải của bài toán có thể bỏ qua hay huỷ bỏ hay không? - Không gian bài toán có thể đoán trước hay không? - Có tiêu chuẩn để xác định lời giải nào đó là tốt đối với bài toán không? - Có cần tri thức để giải quyết bài toán hay điều khiển quá trình tìm kiếm không? - Cơ sở tri thức để giải quyết bài toán có nhất quán về nội dung không? - Có cần tương tác người máy trong quá trình giải quyết không? Để chọn lựa phương pháp phù hợp nhất đối với một bài toán cụ thể, cần phân tích bài toán theo các đặc trưng nói trên. 2.4. CÁC THÀNH PHẦN CƠ BẢN TRONG MỘT HỆ GIẢI QUYẾT VẤN ĐỀ Một hệ giải quyết vấn đề bao gồm các thành phần cơ bản sau: - Các phương pháp biểu diễn vấn đề 21
- Các giải thuật tìm kiếm - Các chiến lược điều khiển - Các kỹ thuật Heuristics - Các kỹ thuật suy diễn. Bài toán Dữ liệu + Tri thức Giải thuật Chiến lược Kỹ thuật Kỹ thuật Cơ sở Cơ sở tìm kiếm điều khiển Heuristic suy diễn tri thức dữ liệu HỆ THỐNG GIẢI QUYẾT VẤN ĐỀ Hình 2.5. Những thành phần cơ bản trong hệ thống giải quyết vấn đề 2.5. CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀ Các phương pháp biểu diễn vấn đề bao gồm: - Phương pháp biểu diễn nhờ không gian trạng thái - Phương pháp quy bài toán về các bài toán con - Phương pháp sử dụng logic hình thức - Phương pháp lựa chọn phương pháp biểu diễn thích hợp. 2.5.1. Phương pháp biểu diễn nhờ không gian trạng thái Phương pháp biểu diễn vấn đề nhờ không gian trạng thái là phương pháp biểu diễn dựa trên hai khái niệm chính là trạng thái (state) và toán tử (operator). Trong đó mỗi trạng thái là một hình trạng của bài toán. Các toán tử là các phép biến đổi từ trạng thái này sang trạng thái khác. Mỗi phép biến đổi cho phép chuyển từ hình trạng này sang hình trạng khác ứng với các toán tử. Các hình trạng đầu, hình trạng cuối của bài toán được gọi là trạng thái đầu, trạng thái 22
cuối. Tập tất cả các trạng thái được sinh ra do xuất phát từ các trạng thái đầu và nhờ áp dụng các toán tử được gọi là không gian trạng thái (state space). Một cách biểu diễn trực quan đối với không gian trạng thái và các toán tử là sử dụng đồ thị trong đó các đỉnh của đồ thị tương ứng với các trạng thái, còn các cung tương ứng với các toán tử. 2.5.2. Phương pháp quy bài toán về các bài toán con Phương pháp giải quyết vấn đề quy bài toán về các bài toán con là một trong các phương pháp tiếp cận khá tinh tế, dựa vào khái niệm bài toán con. Theo cách này, ta có thể phân chia bài toán thành các bài toán con, các bài toán con lại được phân rã tiếp cho đến khi gặp được các bài toán sơ cấp cho phép xác định lời giải của bài toán ban đầu trên cơ sở lời giải của các bài toán con. Ví dụ: Phương pháp tinh dần từng bước trong công nghệ lập trình. 2.5.3. Phương pháp sử dụng logic hình thức Một trong các công cụ biểu diễn vấn đề hay được sử dụng là logic hình thức. Sở dĩ như vậy là vì để giải quyết vấn đề người ta cần tiến hành phân tích logic để thu gọn quá trình tìm kiếm và đôi khi nhờ phân tích logic có thể chứng tỏ được rằng một bài toán nào đó không thể giải được. Các dạng logic hình thức được sử dụng để biểu diễn vấn đề gồm: - Logic mệnh đề - Logic vị từ cấp 1. Phương pháp biểu diễn vấn đề nhờ logic hình thức cho phép: - Kiểm tra điều kiện kết thúc trong tìm kiếm đối với không gian trạng thái - Kiểm tra tính áp dụng được của các toán tử - Chứng minh không tồn tại lời giải. Mục đích giải quyết vấn đề dựa trên logic hình thức là chứng minh một phát biểu nào đó trên cơ sở những tiền đề và luật suy diễn đã có. 2.5.4. Lựa chọn phương pháp biểu diễn thích hợp 23
Trong nhiều trường hợp, việc giải quyết bài toán dựa trên các thuật ngữ đã được dùng để phát biểu nó rất khó khăn. Trong trường hợp đó, thường người ta lựa chọn một dạng biểu diễn phù hợp nào đó đối với các dữ liệu của bài toán, làm cho bài toán trở nên dễ giải hơn. Việc lựa chọn phương pháp biểu diễn thích hợp nhằm: - Tránh giải trực tiếp bài toán đặt ra ban đầu do những khó khăn liên quan tới kích cỡ, trọng số, tầm quan trọng và chi phí xử lý các dữ liệu của bài toán - Bỏ bớt những thông tin thừa hoặc không quan trọng trong bài toán - Tận dụng những phương pháp giải đã có đối với bài toán nhận được sau khi phát biểu lại. - Cách phát biểu mới có thể cho phép thể hiện một vài tương quan nào đó giữa các yếu tố của bài toán nhằm thu gọn quá trình giải. Sau khi đã giải quyết xong bài toán theo cách biểu diễn mới, ta diễn giải lời giải nhận được cho sát với bài toán ban đầu và chứng tỏ rằng cách diễn giải đó thực sự giải quyết được bài toán đặt ra. 2.5.5. Biểu diễn vấn đề trong máy tính Để có thể giải quyết vấn đề trên máy tính, trước hết ta phải tìm cách biểu diễn lại vấn đề sao cho máy tính có thể hiểu được. Điều này có nghĩa là ta phải đưa các dữ liệu của bài toán về dạng có thể xử lý được trên máy tính. Sau đây là các cách biểu diễn vấn đề trong máy tính: a. Cách biểu diễn dùng bảng (Array) Sử dụng bảng để biểu diễn các hình trạng của bài toán. Chẳng hạn, đối với trò chơi 15 số, hình trạng đích (hình 2.3 b) tương ứng ma trận: A = (aij) = 4(i-1) + j với (i, j) (4, 4) 0 với (i, j) = (4, 4). 24
hoặc véc tơ A=(ai), phần tử thứ 4(i -1) + j của nó nhận giá trị 4(i-1)+j, phần tử thứ 16 nhận giá trị 0. b. Cách biểu diễn xâu ký hiệu Sử dụng các xâu kí hiệu để biểu diễn các hình trạng của bài toán. Ví dụ 2.1: Với bài toán tích phân bất định, hàm  được cho dưới dạng xâu ký tự (x)=x 2*cos(x+a) . Ví dụ 2.2. Với hình trạng của một bàn cờ vua sau: TgT ToĐ HĐ MĐ TgT HT Hình 2.6. Bàn cờ vua Ta có thể biểu diễn hình trạng bàn cờ trong hình trên bởi các xâu ký tự: “T, X, X , X, X, X, X, X, X, X, TgT, X, X, X, X, X, X, X, X, X, X, X, X, X, ToĐ X, X, X, X, HĐ,X, X, X, X, X, X,MĐ, X, X, X, X, X, X, X, X, X, X, X, X, 25
X, X, TgT,X, X, X, X,HT “. Ở đây X là ô trống, TgT là tượng trắng, ToĐ là tốt đen, HT, HĐ là hậu trắng, hậu đen, T có nghĩa là quân trắng đến lượt đi. c. Cách biểu diễn dùng cấu trúc danh sách Một cách khác đễ biểu diễn vấn đề là sử dụng cấu trúc danh sách hoặc cấu b (b 2 4ac)1/ 2 trúc cây. Ví dụ biểu thức có thể biểu diễn dạng cây như sau: 2a / + * -  2 a b - /  * 1 2 b 2 4 * a c Hình 2.7. Cây biểu diễn biểu thức số học Hoặc biểu diễn bằng cấu trúc danh sách như sau: / * 2 a + - b 26
- / 1 2 b 2 * 4 * a c Hình 2.8. Cấu trúc danh sách biểu diễn biểu thức số học 2.5.6. Biểu diễn tri thức và giải quyết vấn đề Có hai cách tiếp cận trong giải quyết vấn đề: - Tổng quát hoá để đưa ra mô hình bài toán (xem mục 2.4.1, 2.4.2, 2.4.3). - Cụ thể hoá trên cơ sở sử dụng các tri thức đặc tả (Chương 3). Trên thực tế, có những bài toán không thể giải được nhờ sử dụng mô hình hoặc lời giải nhận được quá xa với lời giải thực tế. Trong trường hợp đó người ta sử dụng cách tiếp cận sử dụng tri thức đặc tả. Các phương pháp biểu diễn tri thức bao gồm: Frame, logic hình thức, mạng ngữ nghĩa và các hệ sản xuất. 2.6. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ CƠ BẢN 2.6.1. Biểu diễn bài toán trong không gian trạng thái. Các chiến lược tìm kiếm trên đồ thị a. Các mô tả trạng thái và toán tử Phát biểu bài toán P1: Cho trạng thái đầu s0 và tập trạng thái đích ĐICH. Hãy tìm dãy trạng thái s0, s1, , sn, sao cho sn ĐICH và với mỗi i=1, n-1, từ trạng thái si có thể áp dụng toán tử biến đổi để nhận được si+1. Có hai cách viết phép biến đổi trạng thái: * Cách viết dùng các sản xuất Ví dụ 2.3: Với bài toán phân tích cú pháp xem xâu  có thuộc ngôn ngữ L(G) không, ở đây G = (N, T, P, S). Ta có: - Mỗi trạng thái là một xâu nào đó trên tập N  T - Các toán tử là các sản xuất p:  P , chẳng hạn: 27
S AB A Aa|a B Bb|b Ví dụ 2.4: Với bài toán 8 số ta có: - Mỗi cách viết các số trong bảng ứng với một trạng thái - Các sản xuất có dạng: x1 x2 x3 x1 x3 x4 x5 x4 x2 x5 x6 x7 x8 x6 x7 x8 Ví dụ 2.5: Với bài toán tháp Hà Nội (n=3) ta có - Mỗi trạng thái là một bộ ba (i j k), có nghĩa là đĩa C ở cọc i, đĩa B ở cọc j, đĩa A ở cọc k. - Các toán tử dịch chuyển: (i j k) ( i j j ) hoặc (i j k) (i j i) * Cách viết dùng ký hiệu hàm: Ví dụ 2.6: Với bài toán 8 số, ta có 4 loại toán tử ký hiệu là: - dl: Dịch ô trống lên trên. - dx: Dịch ô trống xuống dưới. - df: Dịch ô trống sang phải. - dt: Dịch ô trống sang trái. Giả sử A=(aij), ai0j0= 0 (ô trống ở vị trí (i 0,j0). Khi đó ứng với thao tác dịch ô tróng lên trên ta có thể viết: B=dl(A)=(bij), ở đây: aij nếu (i, j) (i0, j0) và (i, j) (i0-1, j0), bij= 0 nếu (i, j)=(i0-1, j0 ) và i0>1 ai0-1 j0 nếu (i, j)=(i0,j0) và i0>1 Phát biểu lại bài toán P1 (Bài toán P2). 1. Tìm dãy trạng thái s1, s2, ,sn sao cho sn ĐICH và mỗi i thì si si+1 (hay là  toán tử o: o(si)=si+1. 28
2. Tìm dãy toán tử o1, o2, , on-1, on sao cho : on(on-1( o1(s0) ))=sn ĐICH hay tìm dãy sản xuấtp 1, p2, , pn sao cho: p1 p2 p3 S0 S1 Sn ĐICH. b. Biểu diễn vấn đề nhờ đồ thị Đồ thị G là cặp G=(N,A), ở đây N là tập các nút (node), A là tập các cung. Với mỗi n N, ký hiệu: B(n) ={m N | (n,m) A}. B1(n) = B(n) Bk(n) = B(Bk-1(n)) = B(m) m B k 1(n) Phát biểu lại bài toán P1 và P2 (Bài toán P3). Cho đỉnh đầu s và tập đỉnh đích ĐICH. Hãy tìm một đường đi p (tối ưu) nào đó từ s tới một đỉnh s* ĐICH. Cách biểu diễn Không gian trạng thái Đồ thị Trạng thái (đầu, đích) Nút (đầu, đích) Toán tử (sản xuất) Cung Dãy trạng thái liên tiếp Đường đi Dãy toán tử Bài toán P1, P2 Tìm đường đi trên đồ thị từ đỉnh đầu n 0 (tương ứng với s0) tới đỉnh thuộc ĐICH. Ví dụ 2.7. Không gian trạng thái của bài toán tháp Hà Nội với n=3 được thể hiện bằng hình vẽ sau: (111) Đầu (112) (113) (132) (123) 29
(133) (122) (131 (121 ) ) (233) (322) (231) (232) (323) (321) (212) (221) (313) (331) ĐICH (222) (223) (213) (311) (333) (211) (312) (332) Hình 2.9. Không gian trạng thái của bài toán Tháp Hà Nội c. Các phương pháp tìm kiếm trong không gian trạng thái Thực chất của việc giải quyết vấn đề trong không gian trạng thái là quá trình tìm kiếm đường đi từ trạng thái đầu tới các trạng thái đích sao cho thoả mãn một số điều kiện nào đó. Các phương pháp tìm kiếm trong không gian trạng thái điển hình mà ta sẽ xem xét gồm: - Tìm kiếm theo chiều rộng (breath-first search) - Tìm kiếm theo chiều sâu (depth-first search) - Tìm kiếm sâu dần (depthwise search) - Tìm kiếm cực tiểu hóa giá thành (cost minimization search) - Tìm kiếm với tri thức bổ sung (heuristics search). Thủ tục tìm kiếm theo chiều rộng Thủ tục TKR Vào: Cây G=(N, A) với đỉnh gốc n0. Tập các đỉnh đích ĐICH N Ra: Một đường đi p: n0 n* ĐICH. Phương pháp: /* Sử dụng hai danh sách kiểu FIFO là MO, ĐONG*/ {MO{n0}; /* Cho n0 vào cuối MO */ While MO  do { n  get(MO) ; /* lấy đỉnh n ở đầu danh sách MO */ 30
ĐONG  ĐONG  {n}; if B(n)  then { MO  MO B(n) ; /* cho tập B(n) vào cuối danh sách MO*/ If B(n) ĐICH  then { exit (“thành công”); Xây dựng đường p;}} } Write (“không thành công”); } Kết quả 2.1. Nếu trong cây G tồn tại ít nhất một đường đi từ n 0 tới tập ĐICH thì thủ tục TKR dừng và cho ra đường đi p có độ dài ngắn nhất. Nếu không tồn tại đường đi như vậy thì thuật toán dừng nếu và chỉ nếu đồ thị hữu hạn. Ví dụ 2.8. Hãy chuyển trạng thái đầu (hình 2.10, a) về trạng thái đích (hình 2.10, b). Hình 2.11 là phần đồ thị đã duyệt cho đến khi tìm thấy trạng thái đích. Thứ tự các nút đã duyệt được chỉ ra bởi các số nằm bên cạnh các nút, còn đường đi tìm được tô nét kép. 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 a) b) Hình 2.10. Trạng thái đầu và trạng thái đích của bài toán 8 số 1 2 8 3 1 6 4 7 5 2 3 4 2 8 3 2 8 3 2 8 3 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 5 6 7 8 9 2 8 3 2 8 3 2 3 2 8 3 2 8 3 1 4 6 4 1 8 4 1 4 1 6 7 6 5 1 7 5 7 6 5 7 6 5 7 5 4 10 11 12 13 14 15 16 17 18 19 8 3 2 8 3 8 3 2 8 3 2 3 2 3 2 8 2 8 3 2 8 3 2 8 2 6 4 6 4 2 1 4 7 1 4 1 8 4 1 8 4 1 4 3 1 4 5 1 6 1 6 3 1 7 5 1 7 5 7 6 5 6 5 7 6 5 7 6 5 7 6 5 7 6 7 5 4 7 5 4 31
20 21 22 23 24 25 26 27 28 29 30 31 32 33 8 3 2 3 2 8 3 2 8 3 8 3 2 8 3 1 2 3 2 3 4 2 8 2 8 3 2 8 3 2 3 2 8 3 2 8 2 6 4 6 8 4 6 4 6 7 4 2 1 4 7 1 4 8 4 1 8 1 4 3 1 4 5 1 6 1 8 6 1 5 6 1 6 3 1 7 5 1 7 5 1 7 5 1 5 7 6 5 6 5 7 6 5 7 6 5 7 6 5 7 6 7 5 4 7 5 4 7 4 7 5 4 5 5 4 8 3 8 6 3 2 3 2 3 2 8 2 8 3 2 8 3 2 8 3 8 3 8 1 3 2 8 3 2 8 3 1 2 3 2 6 4 2 4 6 8 4 6 8 4 6 4 3 6 4 5 6 7 4 6 7 4 2 1 4 2 4 7 4 7 1 4 8 4 1 7 5 1 7 5 1 7 5 1 7 5 1 7 5 1 7 1 5 1 5 7 6 5 7 6 5 6 1 5 6 5 7 6 5 ĐICH 34 35 36 37 38 39 40 41 42 43 44 45 46 Hình 2.11. Phần đồ thị trong trò chơi 8 số Thủ tục tìm kiếm theo chiều sâu Thủ tục TKS Vào: Cây G=(N,A) với đỉnh gốc n0. Tập các đỉnh ĐICH. Ra: Một đường đi p : n0 ĐICH Phương pháp: /* Sử dụng dánh sách kiểu FIFO tên là ĐONG và */ /* danh sách kiểu LIFO tên là MO/* {MO{n0}; /* Cho n0 vào cuối MO */ While MO  do {n  get(MO) ; /* lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n}; if B(n)  then { MO  MO B(n) ; /* cho tập B(n) vào đầu danh sách MO*/ If B(n) ĐICH  then { exit (“thành công”); Xây dựng đường p; } } } Write (“không thành công”); 32
} Kết quả 2.2. Nếu cây G là hữu hạn và có đường đi từ n 0 tới tập ĐICH thì thuật toán TKS sẽ dừng và sẽ cho một đường đi từ nút đầu tới tập ĐICH. Nhận xét: Đường đi nhận được theo thủ tục TKS có thể không ngắn nhất. Hơn nữa, nếu đồ thi vô hạn, thủ tục TKS có thể lặp vô hạn mặc dù trong đồ thị tồn tại đường đi từ n0 tới tập ĐICH. Để khắc phục tình trạng này, ta xem xét thủ tục tìm kiếm sâu dần. Ví dụ 2.9. Thủ tục duyệt cây theo chiều sâu trong đồ thị của bài toán ở ví dụ 2.8 được chỉ ra trên hình vẽ 2.12 sau: 1 2 8 3 1 6 4 7 5 2 10 2 8 3 2 8 3 1 6 4 1 4 7 5 7 6 5 3 11 16 2 8 3 2 8 3 2 3 6 4 1 4 1 8 4 1 7 7 6 7 6 5 5 5 4 6 12 14 17 8 3 2 8 3 8 3 2 8 3 2 3 2 6 4 6 4 2 1 4 7 1 4 1 8 4 1 7 5 1 7 5 7 6 5 6 5 7 6 5 5 7 8 9 13 15 18 8 3 2 3 2 8 3 2 8 3 8 3 2 8 3 1 2 3 2 6 4 6 8 4 6 4 6 7 4 2 1 4 7 1 4 8 4 1 7 5 1 7 5 1 7 5 1 5 7 6 5 6 5 7 6 5 8 3 8 6 3 2 3 2 3 2 8 2 8 3 2 8 3 2 8 3 8 3 8 1 3 2 8 3 2 8 3 1 2 3 2 6 4 2 4 6 8 4 6 8 4 6 4 3 6 4 5 6 7 4 6 7 4 2 1 4 2 4 7 4 7 1 4 8 4 1 7 5 1 7 5 1 7 5 1 7 5 1 7 5 1 7 1 5 1 5 7 6 5 7 6 5 6 1 5 6 5 7 6 5 33
Hình 2.12. Đồ thị biểu diễn trò chơi 8 số Thủ tục tìm kiếm sâu dần Gọi d(n) là độ sâu của đỉnh n được xác định bởi. 0 nÕu n n0 d(n) d(m) 1 nÕu n B(m) Ta đưa vào giá trị k gọi là mức sâu cho mỗi lần duyệt. Thủ tục TKSD Vào: Cây G=(N,A) với đỉnh đầu n0, tập các đỉnh ĐICH. Mức sâu k. Ra: Một đường đi p : n0 ĐICH Phương pháp: /*Sử dụng danh sách kiểu FIFO: ĐONG và */ /* và danh sách lai kiểu FIFO & LIFO MO*/ { MO  {n0 }; ĐS = k; /* ĐS là giới hạn sâu hiện tại */ While MO  do { n  get(MO); /* Lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n}; if B(n)  then { if B(n)  ĐICH  then exit (“Thành công “); Case d(n) do [0 . . ĐS-1]: Đặt B(n) vào đầu danh sách MO; ĐS : Đặt B(n) vào cuối danh sách MO; ĐS+1 : { ĐS = ĐS + k; if k=1 then đặt B(n) vào cuối danh sách MO else đặt B(n) vào đầu danh sách MO; }}} 34
Write(“không thành công”) } Nhận xét: * Khi k =1 thủ tục TKSD trở thành TKR. * Khi k 2 thủ tục TKSD tìm kiếm theo chiều sâu đối với các đỉnh có độ sâu nằm trong khoảng tk+1 và (t+1)k, t là số tự nhiên nào đó. Kết quả 2.3. Nếu trong cây tồn tại ít nhất một đường đi từ n 0 đến ĐICH thì thủ tục TKSD sẽ dừng và cho đường đi có độ dài khác đường đi ngắn nhất không quá k-1. Nếu không tồn tại đường đi như vậy thì thủ tục TKSD dừng khi và chỉ khi đồ thị G hữu hạn. A đỉnh đầu B C D E F G H K L M N O P Q R S T U V X Y ĐICH Hình 2.13. Ví dụ đồ thị duyệt theo thứ tự sâu dần Ví dụ 2.10. Xét thủ tục TKSD với đồ thị trên hình vẽ 2.17 khi k=2, thứ tự duyệt các đỉnh là : ABDECFGHQRKSTLMUVN. Thủ tục tìm kiếm đường đi với giá thành nhỏ nhất Giả sử c: A R+ là hàm giá (cost) c:a c(a) R+. Một đường đi p trong G là k 1 dãy các đỉnh n1, , nk có giá c(P) c(ni ,ni 1 ) . i 1 35
Kí hiệu g(n) là giá cực tiểu của đường đi từ n 0 đến n ĐICH. Khi đó, bài toán trên được phát biểu thành: Tìm đường đi p 0 từ đỉnh gốc n 0 đến đỉnh n k ĐICH sao cho g(nk)=min{g(n)| n ĐICH}. 0 Để tìm ra đường đi p0 có giá g(n*) min, ta sử dụng kí hiệu g (n), xem như một ước lượng của g(n). Ta có thủ tục sau: Thủ tục TKCT Vào: Cây G=(N,A) với đỉnh gốc n0. Tập đỉnh đích ĐICH. Hàm c: A R+ Ra: Đường đi p: n0 n* ĐICH sao cho c(p)= g(minn* ) n* DICH Phương pháp: /* sử dụng hai danh sách MO, ĐONG*/ {MO{n0}; 0 g (n0) = 0; While MO  do { n get(MO); /* Lấy n MO sao cho g0(n) min */; ĐONG  ĐONG {n}; if n ĐICH then exit(“thành công”); if B(n)  then { MO B(n)  MO ; for each m B(n) do g0(m)=g0(n)+ c(n,m) }} Write(“không thành công”) } Nhận xét: Thủ tục TKR là trường hợp riêng của thủ tục TKCT khi c=1. Kết quả 2.4: Nếu trong cây tồn tại đường đi p: n 0 nk ĐICH thì thủ tục * * TKCT sẽ dừng và cho đường đi p sao cho c(p ) =g(nk)=min{g(n)| n ĐICH}, nk ĐICH. Hơn nữa, thủ tục tối ưu theo nghĩa số đỉnh cho vào danh sách ĐONG là nhỏ nhất trong số các thủ tục tìm kiếm chỉ dựa trên giá các cung. Ví dụ 2.11. Xét cây với giá các cung được cho như trên hình vẽ sau: A 36 Hình 2.14. Ví dụ về tìm đường đi với giá cực tiểu
2 4 C 6 F 2 B 5 8 1 G H E D Với tập các đỉnh đích là {D, H}. Khi đó thuật toán TKCT cho ra đường đi AFH. Các Heuristics áp dụng cho thủ tục TKCT : - Chỉ xét các đỉnh trong B(n) có triển vọng đạt tới tập ĐICH. - Sắp các đỉnh trong MO trước mỗi lần xử lý nhờ các hàm đánh giá. Thuật toán tìm đường đi có giá nhỏ nhất với tri thức bổ sung Đây là phương pháp tìm kiếm đường đi tối ưu dựa trên các thông tin đặc tả về bài toán. Các thông tin này dược gọi là các heuristic. Các kỹ thuật sử dụng heuristic được gọi là các mẹo giải. Các mẹo giải có thể là: - Chọn toán tử xây dựng cung B sao cho có thể loại bớt những đỉnh không liên quan đến bài toán hoặc ít có triển vọng nằm trên đường đi tối ưu. - Sử dụng thông tin bổ sung để xác định một hàm đánh giá cho phép lựa chọn đỉnh cần lấy từ tập MO. Các phương pháp xây dựng hàm đánh giá: + Xác suất một đỉnh nào đó nằm trên đường đi tối ưu + Khoảng cách hay sự khác biệt giữa một đỉnh nào đó với tập các đỉnh đích. Thủ tục TKCT* Vào: Đồ thị G=(N,A) tuỳ ý với đỉnh gốc n0. Tập đỉnh đích ĐICH. Hàm f0: N R+. Ra: Đường đi từ n0 tới ĐICH. Phương pháp: 37
0 { MO{n0}; Tính f (n0) ; While MO  do {n  get(MO); /* Lấy n MO sao cho f0 (n) min */ ĐONG  ĐONG  {n}; if n ĐICH then exit(“ thành công”); if B(n)  then for each m B(n) do if m ĐONG  MO then { MO MO  {m}; Tính f0(m)} 0 0 else if f cũ(m) >f mới(m) then MO MO  {m}}; Write(“ không thành công”) } Trong thủ tục trên f 0 là hàm ước lượng heuristics nào đó, có thể dùng để sắp xếp các đỉnh trước khi xử lý. Các đỉnh trong danh sách MO được sắp theo thứ tự tăng dần của giá trị hàm f0. Nhận xét: Thuật giải TKCT* là tổng quát hơn TKCT khi xem f0 g0. Ví dụ 2.12. Trở lại bài toán trò chơi 8 số (Bài toán 2.1). 0 0 0 Ta lấy hàm f (n) = g (n)+w(n), ở đây g (n) là độ dài đường đi hiện tại từ n 0 đến n, còn w(n) là số lượng các con số không nằm đúng vị trí của chúng ở hình trạng đích. Chẳng hạn, đối với đỉnh đầu n0. 2 8 3 1 6 4 7 5 0 0 Ta có g (n0)=0; w(n0)=4. Do vậy f (n0) = 4; ĐẦU 4 g0 =0 2 2 8 3 2 8 3 2 8 3 1 6 4 6 1 6 4 g0 =1 6 4 1 4 7 5 7 6 5 7 5 38 8 3 2 1 4 7 6 5 Hình vẽ 2.15. Cây trò chơi 8 số
1 2 8 3 1 6 4 7 5 3 4 2 8 3 2 8 3 2 3 0 1 4 1 4 g =2 5 5 1 8 4 6 7 6 5 7 6 5 7 6 5 5 2 8 1 2 3 2 3 7 1 4 1 8 4 0 6 7 6 5 5 1 8 4 7 g =3 7 6 5 7 6 5 6 1 2 3 g0 =4 5 8 4 7 6 5 1 2 3 1 2 3 7 8 4 0 5 8 4 7 * 0 g =5 Hình trên mô tả việc áp7 6dụng 5 ĐÍCH thủ túc 6TKCT 5 , giá trị f đối với mỗi nút chỉ ra trong hình tròn. Các số bên trên mỗi nút là thứ tự xét chúng trong quá trình tìm kiếm. Ví dụ 2.13: Xét bài toán tháp Hà Nội với n=2, lấy hàm f0=g0+h0, trong đó h0(n) là thông tin nói thêm về mối liên hệ giữa n và trạng thái đích. Chẳng hạn: ·h 0=2 nếu ở cọc C chưa có đĩa nào, ·h 0=1 nếu ở cọc C có đĩa to, ·h 0=3 nếu ở cọc C có đĩa nhỏ, ·h 0=0 nếu ở cọc C đã có hai đĩa. Hình vẽ sau chỉ ra kết quả tìm kiếm. g0 =0 h0 = 2, f0=2 h0 = 3, f0=4 0 0 g0 =1 h = 2, f =3 0 h0 = 3 0 g0 =2 h = 1 h = 2 f0=3 f0=5 f0=4 39
h0 = 2 h0 = 0 h0 = 1 g0 =3 f0=5 f0=3 f0=4 ĐICH Hình 2.16. Bài toán tháp Hà Nội với n=2. Một cách tổng quát, có thể dùng thuật toán TKTC* để tìm ra đường đi p:n0 ĐICH sao cho c(p)=g(n*), n* ĐICH. Thật vậy, nếu xem f(n) là giá * đường đi tối ưu từ n0 ĐICH và đi qua n thì có thể viết: f (n)=g(n)+h(n), ở đây: · g(n) : giá đường đi tối ưu từ n0 n, · h(n): giá đường đi tối ưu từ n ĐICH. Đối với thủ tục TKCT * ta sử dụng ước lượng f 0=g0+h0, trong đó g0 được tính như trong thủ tục TKCT, h0 là một ước lượng của h. Kết quả 2.5. (Tính đúng đắn và tính tối ưu của thuật toán). Nếu đối với mỗi đỉnh n N ta có 0 h 0(n) h(n) thì thủ tục TKCT * dừng và cho đường đi p: n0 n* ĐICH tối ưu khi đồ thị là cây. Trong trường hợp đồ thị tuỳ ý phải thêm điều kiện: Tồn tại >0 sao cho a A c(a) . * 0 0 0 Kết quả 2.6. Giả sử thủ tục TKCT sử dụng hàm đánh giá f i(n)=g (n)+h i, 0 0 i=1,2 và giả sử h2 thoả mãn điều kiện h 2(m) – h 2(n) h(m, n), (h(m,n) là độ dài 0 0 đường đi ngắn nhất từ m đến n) và n h 1(n) h 2(n) h(n) thì số nút đưa vào * tập DONG của thuật toán TCTK 2 bao giờ cũng nhỏ hơn số nút đối với thuật * toán TCTK1 . 2.6.2 Quy bài toán về các bài toán con và các chiến lược tìm kiếm trên đồ thị VÀ/HOẶC a. Quy bài toán về các bài toán con Quy bài toán về các bài toán con là việc tách bài toán (vấn đề) ban đầu thành các bài toán (vấn đề) sơ cấp. Ví dụ 2.14. Với bài toán 2.1 (trò chơi n2 -1 số), các bài toán sơ cấp tương ứng với trường hợp chỉ cần một bước chuyển từ trạng thái đầu sang trạng thái đích. Ví dụ 2.15. Xét bài toán tìm cách đi từ Nhà hát lớn đến ga Hà Nội. 40
Bài toán này có thể chia nhỏ thành ba bài toán con: Bài toán 1: Đi từ Nhà hát lớn tới Hồ Hoàn Kiếm. Bài toán 2: Đi từ Hồ Hoàn Kiếm đến Cửa nam. Bài toán 3: Đi từ Cửa nam tới ga Hà Nội. Lời giải bài toán ban đầu nhận được trên cơ sở lời giải của cả ba bài toán con này. Ta có hình vẽ NHL GHN NHL HHK HHK CN CN GHN Ví dụ 2.16. (Bài toán tháp Hà Nội) Xét trường hợp n=3, ta có kết quả như trên hình 2.19. Bài toán ban đầu (111) (333) được quy về 3 bài toán con: Bài toán 1. (111) (122) chuyển 2 đĩa A, B từ cọc 1 sang cọc 2; Bài toán 2. (122) (322) chuyển đĩa C từ cọc 1 sang cọc 3; Bài toán 3. (322) (333) chuyển 2 đĩa A,B từ cọc 2 sang cọc 3. Bài toán 2 là bài toán sơ cấp (có thể giải được ngay!), còn các bài toán lại được phân rã tiếp tục (111) (333) (111) (122) (122) (322) (322) (333) (111) (113) (113) (123) (123) (122) (322) (321) (321) (331) (231) (333) Hình vẽ 2.17. Phân rã bài toán tháp Hà Nội n=3 41
Ta nhận được lời giải của bài toán ban đầu như sau: (111) (113) (123) (122) (322) (321) (311) (333) b. Đồ thị VÀ/HOẶC Đồ thị (có hướng) VÀ/HOẶC là cặp G=(N, A), sao cho với mọi n N tất cả các đỉnh m B(n) cùng thuộc vào một trong hai kiểu là đỉnh VÀ hay đỉnh HOẶC. Nếu các đỉnh con m của n là đỉnh VÀ thì các cung (n, m) m B(n) được nối với nhau bởi ngoặc lớn. Đỉnh con m B(n) là đỉnh VÀ nếu bài toán ứng với đỉnh n không thể giải thông qua một mình bài toán ứng với đỉnh m. Đỉnh con m B(n) là đỉnh HOẶC nếu bài toán ứng với đỉnh n có thể giải thông qua một mình bài toán ứng với đỉnh m Ví dụ 2.17: Giả sử bài toán A có thể giải quyết theo ba cách sau: - Hoặc thông qua giải quyết đồng thời hai bài toán B và C. - Hoặc giải quyết các bài toán D và E. - Hoặc giải bài toán F (phát biểu tại A). Ta có thể biểu thị mối liên hệ đó nhờ đồ thị (hình 2.20, a): A A M N F B C D E F B C D E a) b) Hình 2.18. Đồ thị VÀ/ HOẶC Tuy nhiên đồ thị trên hình 2.15, a) chưa phải đồ thị VÀ/HOẶC, vì các đỉnh con của A có cả đỉnh VÀ và đỉnh HOẶC, do vậy ta chuyển về đồ thị VÀ/HOẶC, được biểu diễn bởi hình 2.15, b). Khi đó 42
- Các đỉnh B, C, D, E là đỉnh VÀ. - Các đỉnh N, M, F là đỉnh HOẶC. Trong đồ thị VÀ/HOẶC các đỉnh tương ứng với các bài toán sơ cấp gọi là đỉnh kết thúc. Sau đây ta sẽ xem xét hai khái niệm liên qua tới đồ thị VÀ/HOẶC là: Đỉnh giải được và đỉnh không giải được. * Định nghĩa đỉnh giải đựơc: - Các đỉnh kết thúc là đỉnh giải được, - Nếu đỉnh n có các đỉnh con là đỉnh HOẶC thì nó là đỉnh giải được tồn tại một đỉnh con của nó giải được, - Nếu một đỉnh có các đỉnh con là đỉnh VÀ thì nó là đỉnh giải được tất cả các đỉnh con của nó là giải được. * Đồ thị lời giải là đồ thị con của đồ thị VÀ/ HOẶC chỉ bao gồm các đỉnh giải được và chứa đỉnh đầu. * Định nghĩa đỉnh không giải được: - Các đỉnh không là kết thúc và không có đỉnh con là đỉnh không giải được, - Nếu đỉnh không là đỉnh kết thúc và có các đỉnh con là đỉnh VÀ thì nó là Commented [TTC1]: Page: 43 không giải được Tồn tại một đỉnh con của nó không giải được, - Nếu đỉnh không là đỉnh kết thúc và có các đỉnh con là đỉnh HOẶC thì nó là không giải được mọi đỉnh con của nó là không giải được. Ví dụ 2.18: Hình vẽ dưới đây là đồ thị VÀ/HOẶC trong đó các đỉnh kết thúc được kí hiệu bởi chữ t, các đỉnh giải được tương ứng với các hình tròn tô đậm, các cung trong đồ thị lời giải cũng được tô đậm. 43 Hình 2.19. Đồ thị VÀ/ HOẶC và đồ thị lời giải
t t t t t t t Sự tương ứng giữa quá trình quy bài toán về các bài toán con với đồ thị VÀ/HOẶC được thể hiện trong bảng sau: Quy bài toán về các bài toán con Đồ thị VÀ/HOẶC Bài toán Đỉnh Toán tử quy bài toán về bài toán con Cung Bài toán ban đầu Đỉnh đầu (đỉnh gốc) Các bài toán sơ cấp Đỉnh cuối, đỉnh kết thúc Các bài toán con phụ thuộc Đỉnh VÀ Các bài toán con độc lập Đỉnh HOẶC Giải bài toán ban đầu. Tìm đồ thị con lời giải. c. Giải bài toán biểu diễn trong không gian trạng thái nhờ phương pháp phân rã Bài toán P1 (P2) có thể đưa về dạng Prob(s 0, ĐICH). Thực chất quá trình giải là tìm dãy trạng thái s0, , sn ĐICH sao cho s i có thể biến đổi trực tiếp thành si+1. Do vậy, một cách tiếp cận là xác định trạng thái trung gian cơ bản g 1, , gk trong dãy s0, , sn và bài toán Prob(s0, ĐICH) được quy về các bài toán con: Prob(s0, ĐICH) Prob(s0, g1) Prob(g i-1, gi) Prob(gk, ĐICH) 44
Song trên thực tế việc tìm ra ngay dãy g1, , gk là rất khó. Có thể làm như sau: Xác định tập G 1 các trạng thái có khả năng là điểm khớp đầu tiên. Giải bài toán Prob(s0, G1) để tìm ra g 1 G1, sau đó xác lập G 2 và giải bài toán Prob(g 1, G2) để tìm ra g2 G2, Cuối cùng giải bài toán Prob(gk, ĐICH) Prob(s0, ĐICH) Prob(s0, G1) Prob(g1, G2) Prob(gk, ĐICH) Có hai cách tiếp cận cơ bản: Phương pháp dựa vào toán tử khoá: Thực chất của bài toán P 1 là xác định dãy toán tử o1, , on sao cho on(on-1( o1(s0) )) ĐICH. Trên thực tế ta mong muốn xác định một tập con các toán tử quan trọng (khoá) f 1, ,fk. Gọi Gfi là tập trạng thái có thể áp dụng fi. Khi đó, giải bài toán Prob(gf1, Gf1) sẽ cho trạng thái gf2 Gf2 ({s0}, ĐICH) Prob(s0, ĐICH) ({s0}, Gf1) ({gf1}, Gf2) ({gfk}, ĐICH) Prob(s0, Gf1) Prob(g1, Gf2) Prob(gfk, ĐICH) Phương pháp xác định sự khác biệt f: So sánh sự khác biệt giữa s0 và tập ĐICH, tìm ra toán tử f1 quan trọng nhất cho phép giảm bớt sự khác biệt lớn nhất d. Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC Trong các thuật toán tìm kiếm chúng ta phải dùng đến hai thủ tục sau: - Thủ tục gán nhãn giải được cho các đỉnh GD(n N) - Thủ tục gán nhãn không giải được cho các đỉnh KGD(n N). 45
Với mỗi đỉnh n N, ta dùng các ký pháp: + Nếu n là đỉnh kết thúc thì kt(n)=True, ngược lại kt(n)=False. “gđ” nếu n là đỉnh giải được + Nhan(n) = “kgđ” nếu n là đỉnh không giải được “kxđ” nếu n không xác định, không đủ thông tin hoặc chưa được xét tới. + kieu(n)=true nếu các đỉnh con của n là đỉnh VÀ Procedure GĐ (n N) { if nhan(n)= “kxđ” then if kt(n) then nhan(n)=”gđ” else if n MO ĐONG then nhan(n)=”kgđ” else if kieu(n) then {bien=True; While B(n)  and bien do {m  get(B(n)); gd(m); bien=(nhan(m)=”gđ”)} if bien then nhan(n)=”gđ” else nhan(n)=”kgđ”} else {bien=false; Repeat {m get(B(n)); gđ(m); bien=(nhan(m)=”gđ”)} Until bien or B(n)= if bien then nhan(n)=”gđ” else nhan(n)=”kgđ”} * Thủ tục tìm kiếm theo chiều rộng Thủ tục TKRM Vào: Cây VA/HOAC G=(N, A) với đỉnh đầu n0. 46
Ra: Thông báo “không thành công” nếu n0 không giải được, “thành công” nếu n0 giải được và đưa ra cây lời giải. Phương pháp: /* sử dụng hai danh sách FIFO: MO, ĐONG */ {MO ={n0}; While MO  do {n get(MO); ĐONG{n}  ĐONG; if B(n)  then {MO MO B(n); /* đưa B(n) vào cuối danh sách MO */ bool = false; For each m B(n) do if kt(m) then {nhan=”gđ”; bool=true} if bool then {gđ(n0); if nhan(n0)=”gđ” then exit(“thành công” else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được /* nếu m B(n) thì n được gọi là tổ tiên của m */ }} else {nhan(n)=”kgđ”; kgđ(n0); if nhan(n0) = “kgđ” then exit (“không thành công” else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} Kết quả 2.7. Nếu cây lời giải tồn tại thì thủ tục TKMR sẽ dừng và đưa ra cây lời giải có độ cao nhỏ nhất. Ví dụ 2.19. Xét cây VA/ HOAC sau đây (Hình 2.17), trên đó thứ tự đưa các nút vào danh sách ĐONG được chỉ ra bởi các số ở bên cạnh các đỉnh. Các đỉnh tô đậm là các đỉnh giải được. Cây lời giải được xác định qua các cung tô đậm. 1 47
3 2 4 7 5 6 8 9 10 t B C t t t Hình 2.20. Đồ thị VÀ/ HOẶC * Thủ tục tìm kiếm theo chiều sâu Thủ tục TKSM Vào: Cây VA/HOAC G=(N,A) với đỉnh đầu n0. Giới hạn sâu D. Ra: Cây lời giải nếu tồn tại. Phương pháp: /* Sử dụng danh sách FIFO tên là ĐONG, và danh sách LIFO tên là MO */ {MO = {n0}; While MO  do {n  get(MO); /*Lấy n là đỉnh đầu của MO */ ĐONG ĐONG {n}; if d(n) D and B(n)  then {MO MO  B(n); /* Đưa B(n) vào đầu danh sách MO */ bool = false; For each m B(n) do {if kt(m) then {nhan=”gđ”; bool=true}} if bool then {gđ(n0); if nhan(n0)=”gđ” then exit(“thành công”) 48
else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được}} else {nhan(n)=”kgđ”; kgđ(n0); if nhan(n0) = “kgđ” then exit (“không thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} Nhận xét: Cũng như ở trên, nếu tất cả các cây lời giải có độ cao lớn hơn D thì chúng sẽ bị bỏ qua trong quá trình tìm kiếm. Do vậy thực tế tồn tại cây lời giải song thuật toán lại không tìm được. Có thể sửa đổi thủ tục TKSM thành thủ tục duyệt sâu dần áp dụng cho cây VA/HOAC. * Thủ tục tìm cây lời giải cực tiểu hoá giá thành. Định nghĩa h(n) giá tối ưu của cây lời giải gốc n: Nếu n là đỉnh kết thúc h(n)=0. Nếu n không là đỉnh kết thúc và các con n1, ,nk là đỉnh HOAC thì h(n)=min(c(n,ni)+h(ni)). Nếu n không là đỉnh kết thúc và các con n1, , nk là đỉnh VA thì: k h(n)= (c(n, n ) + h(n )) đối với giá tổng cộng. i 1 i i h(n)= max (c(n,ni)+h(ni)) đối với giá cực đại. i h(n) không xác định nếu n là đỉnh không giải được. Mục đích tìm kiếm: - Cây lời giải được xây dựng dần trong quá trình mở rộng cây lựa chọn. - Đối với đỉnh n ta sử dụng h*(n) là ước lượng của h(n). - Các đỉnh lá của cây lựa chọn thuộc một trong ba dạng: + Các đỉnh kết thúc. + Các đỉnh không kết thúc + Các đỉnh chưa được xét đến. Các đỉnh này được gọi là các mút. Ta xây dựng ước lượng h* đối với h như sau: n là đỉnh mút. 49
* Nếu n là đỉnh kết thúc h (n)=0. * Nếu n không là đỉnh kết thúc và không có con thì h (n) không xác định. * Nếu n chưa được xét thì h (n) có thể là một ước lượng Heuristics nào đó của h(n). n không là mút: n có các đỉnh con n1, ,nk là đỉnh HOAC * * h (n)=min(c(n,ni)+h (ni)). n có các đỉnh con n1, , nk là đỉnh VA * * h (n)=(c(n,ni)+h (n)) - Đối với giá tổng cộng, * * h (n)=max(c(n,ni)+h (ni)) - Đối với giá cực đại. Ta nhận thấy là trong quá trình tìm kiếm, ở mỗi bước có thể chứa môt tập các cây con có gốc n0 sao cho chúng có thể trở thành phần trên của cây lời giải cuối cùng. Ta gọi các cây này là cây lời giải tiềm tàng gốc n0. Từ cây lựa chọn ta xác định cây lời giải tiềm tàng T0 gốc n0 có nhiều khả năng là phần trên của cây lời giải như sau: Đỉnh đầu n0 T0. Nếu n0 T0 có các đỉnh con n1, , nk là: a/ Đỉnh HOAC thì chọn đỉnh ni sao cho c(n,ni)+h(ni) min. b/ Đỉnh VA thì chọn đỉnh n1, , nk thuộc vào T0. Thủ tục TKCTM Vào: Cây VA/ HOAC G=(N,A) với đỉnh gốc n0. Ra: Cây lời giải tối ưu. Phương pháp {MO{n0}; T0{n0}; While MO  do {Xây dựng cây T0; n get(MO)  Mut(T0); /*Mut(T0) là tập các lá của T0 */ ĐONG ĐONG {n}; if kt(n) then { nhan(n)= “gđ”; get(n0); 50
if nhan(n0)=”gđ” then exit(“thành công”); else loại khỏi MO các đỉnh có tổ tiên là giải được;} else if B(n)  then {MO MO  B(n); for each m B(n) do h*(m); for each m MOĐONG do h*(m) } else {nhan(n)= “kgđ”; kgđ(n0); if nhan(n0) =”kgđ” then exit (“không thành công “) else Loại khỏi MO các đỉnh có tổ tiên là không giải được}}} Nhận xét. Nếu cây VA/ HOAC chỉ chứa đỉnh HOẶC thì thủ tục này chính là thủ tục TKCT, nếu c1 và h*0 đối với mọi đỉnh mút và sử dụng giá cực đại thì thủ tục trở thành TKRM. Kết quả 2.8. Nếu h *(n) h(n) đối với mọi đỉnh nằm trong MO và  a A c(a)  thì thủ tục TKCTM sẽ dừng và cho kết quả là cây lời giải tối ưu. 2.6.3 Biểu diễn vấn đề nhờ logic hình thức và các phương pháp chứng minh a. Logic mệnh đề Một mệnh đề p là một phát biểu chỉ nhận giá trị đúng (T, True, 1) hoặc sai (F, False, 0). Ví dụ 2.20. + 5 nhân 2 hai là 10. + Hà Nội là thủ đô của nước Việt Nam. + Bạn A học giỏi hơn bạn B. Các biểu thức logic mệnh đề được xây dựng trên cơ sở các tên mệnh đề và các phép toán logic theo quy tắc cú pháp nhất định. Tên mệnh đề: thường được ký hiệu bởi các chữ cái la tinh thường a, b, p, q Các phép toán logic bao gồm: - Hội (, and, và). - Tuyển (, or, hoặc). 51
- Phủ định (, not, không). - Kéo theo ( ). - Tương đương ( ). Thứ tự ưu tiên các phép toán: phủ định, kéo theo, tương đương, hội, tuyển. Giá trị chân lý của một biểu thức được tính dựa theo bảng chân lý (truth table) sau: a b ab ab a a b a 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 Khẳng định: i) Mọi biểu thức logic mệnh đề đều có thể đưa về biểu thức tương đương chỉ chứa các phép ,  và  ii) Các phép  và  có tính chất giao hoán, kết hợp, phân phối và luỹ đẳng. Các phép biến đổi tương đương: R1.AB  BA, AB  BA R2.A B  B A R3.AAA, AAA R4.A(BC)  (A  B)  C, A  (B  C)  (A  B)  C R5. AB(A  B), A  B  (A  B) R6.A B  A  B R7. A  (B  C)  (A  B)  (A  C) A  (B  C)  (A  B)  (A C) R8. A  (A  B)  A A (A  B)  A R9. A  A R10.(AB)  AB, (AB)  AB 52
R11.A  A  0 R12. A  0  0, A  1  1 A  0  A, A  1  A R13.1  0,0  1 Cách tính giá trị của một biểu thức logic mệnh đề: + Lập bảng giá trị chân lý. Nếu biểu thức có n biến mệnh đề, ta lập bảng với 2n dòng. + Biến đổi biểu thức về biểu thức tương đương và dựa và bảng giá trị chân lý của các phép toán. b. Logic vị từ Vị từ p(x, ,y) là một phát biểu chứa các biến x, ,y sao cho khi x, y nhận giá trị cụ thể thì p(x, ,y) nhận giá trị đúng hoặc sai. Ví dụ 2.21. p(x,y,z) có nghĩa là x.y=z. Khi đó tính chất giao hoán của phép nhân x.y=y.x được diễn tả dưới dạng: x,y p(x,y,z) p(y,x,z). Các phép toán:  , , , , Các lượng từ: Lượng từ tồn tại () : Khi viết x p(x, y, . . ., z) có nghĩa là tồn tại một giá trị x0 của x sao cho p(x0, y, . . .,z) đúng với mọi giá trị y, . . ., z. Lượng từ mọi (): Khi viết x p(x, y, . . ., z) có nghĩa là đối với mọi giá trị của x ta có p(x, y, . . .,z) đúng với mọi giá trị y, . . ., z. Logic vị từ cho phép diễn đạt hầu hết các khái niệm và nguyên lý của khoa học cơ bản, đặc biệt là toán học và vật lý. Hai phạm vi ứng dụng nỗi bật của logic hình thức là: + Chứng minh định lý tự động + Giải quyết vấn đề. c. Chứng minh định lý nhờ logic hình thức Bài toán: Cho các giả thiết dưới dạng các biểu thức mệnh đề (hoặc logic vị từ) GT1, ,GTm. Hãy rút ra một trong các kết luận KL1, , KLn. 53
Thuật giải của Wong H (dùng cho cả logic mệnh đề và logic vị từ). Vào: Các biểu thức mệnh đề GT1, ,GTm. Các kết luận KL1, ,KLn. Ra: Thông báo “Thành công’ nếu GT1  GTm KL1 KLn. Phương pháp: { For i=1 to m do { Trans(GTi); VT  GTi  VT} for i=1 to n do {Trans (KLi); VP  KLi  VP} /* VT, VP là danh sách các biểu thức ở vế trái, vế phải dấu */ P{(VT,VP)}; /* P là danh sách các kết quả cần chứng minh VT VP */ While P  do { (VT, VP) get(P); if VT  VP= then {chuyển(VT, VP); if VP  VT = then if not tach (VT,VP) then Exit “Không thành công”}} Write(“Thành công”) } Ở đây: Thủ tục Trans(BT): Đưa biểu thức BT về dạng chuẩn, nghĩa là biểu thức chỉ chứa các phép toán: , ,  và thuộc một trong hai dạng sau: k ni l +  ij i 1 j 1 k ni l +  ij trong đó lij = pij hoặc lij = pij và pij là các mệnh đề đơn. i 1 j 1 Ví dụ: Với biểu thức BT=(a b)(cd), thủ tục Trans(BT) sẽ cho ta biểu thức (ab)  (cd) hoặc (ac)(ad)(bc)(bd). Thủ tục chuyen(VT, VP): Chuyển vế các GT i, KLj có dạng phủ định, thay dấu  bên trong GTi và dấu  bên trong KLj bởi dấu phẩy. Ví dụ: Với (VT,VP) là pq, p e, q. Khi đó thủ tục chuyen(VT, VP) cho ta: p  q, p, e q. 54
Hàm tách(VT, VP): Tách thành hai danh sách con nếu có dấu  trong một GTi hoặc dấu  trong một KL j nào đó. Nếu tách được, hàm cho giá trị True, ngược lại cho giá trị False. Ví dụ: Với (VT, VP) là pq, p, e q hàm tách sẽ tách thành hai danh sách con: + p, p, e q + q, p, e q và hàm cho giá trị True. Kết quả: Thuật toán Wong H. dừng sau hữu hạn bước và cho thông báo “Thành công” nếu và chỉ nếu từ GT1, ,GTm có thể suy ra một trong các kết luận KL1, ,KLn. Nhận xét: - Nếu số phép toán liên kết  trong GT i và  trong KL j là m thì thuật giải Wong H sẽ sinh ra từ m đến 2m dòng (VT, VP) P. Ví dụ 2.22. Chứng minh rằng từ (ab) c, (bc) d, a,b suy ra d. Đưa các GTi và KLj về dạng chuẩn và xây dựng P=(VT, VP) ta có a  b  c, b  c  d, a, b d. Do VT  VP = và thủ tục chuyển không thực hiện được nên áp dụng thủ tục Tach(VT, VP) ta thu được 2 dòng: 1. (VT1, VP) = a, b  c  d, a, b d 2. (VT2, VP) = b  c, b  c  d, a, b d Áp dụng thủ tục chuyen(VT1, VP) ta thu được (VT1, VP) =  b   c  d, a, b d, a. Vì VT1  VP =  nên VT1 VP. Đối với (VT2, VP) không chuyển được nên ta tiếp tục tách. Tiếp tục như vậy ta sẽ có lời giải của bài toán. Hình sau đây mô tả việc chứng minh bài toán: abc, bcd, a, b d Tách 55
a,bcd, a, b dbc, bcd, a, b d Chuyển Tách bcd, a, b d, ab, b cd,a,b d c,bcd, a, b d VTVP  Tách Tách CM bcd, a, b d,b c,b, a,b d VTVP  c,cd,a,b d chuyển Tách CM c,a,b d,b c,d,a,b d c,c,a,b d chuyển VTVP  VTVP  CM CM c, a, b d,c VTVP  CM Hình vẽ 2.21. Cây suy diễn trong thủ tục Wong .H Thủ tục hợp giải (Resolution) của Robinson Bản chất của quá trình chứng minh bằng hợp giải của Robinson là chứng minh bằng phản chứng. Để chứng minh từ GT 1, ,GTm suy ra một trong các kết luận KL1, , KLn ta lấy phủ định của KL1, , KLn hợp với giả thiết ra suy ra mâu thuẫn. * Thủ tục Robinson 1 (Dùng cho logic mệnh đề) Vào: Các biểu thức mệnh đề giả thiết GT1, , GTm Các biểu thức mệnh đề kết luận KL1, , KLn Ra: Thông báo “Thành công” nếu GT1 GTm KL1 KLn. Phương pháp: {For i=1 to m do { Trans(GTi); PGTi;} For i=1 to n do {Trans(KLi); P KLi;} /* P=MĐ1, ,MĐk , k=m+n*/ If mt(P) then exit(“Thành công”); P1=; 56
While P P1 and mt(P) do {P1=P; hopgiai(P);} If mt(P) then exit (“Thành công”) Else exit (“Không thành công”);} Ở đây, hàm mt(P) kiểm tra xem trong P có hai mệnh đề p, q sao cho p=q hoặc q=p không?. Nó trả về giá trị True nếu tồn tại cặp p, q như thế và trả về giá trị False nếu ngược lại. Cụ thể: Function mt(P); {mt=false; for each p P do for each q P and q p do if p=q or q=p then return (true)} Còn thủ tục hopgiai(P) tìm cách hợp các mệnh đề dạng p=ab với mệnh đề q=ac thành một mệnh đề r = bc. Procedure Hopgiai(P); {for each p P do for each q P and q p do if p=ab and q=ac then P P{bc}} Ví dụ 2.23. Chứng minh rằng từ (ab) c, (bc) d, a,b suy ra d. Đưa các giả GTi và KLj về dạng chuẩn và xây dựng P ta có P ={a  b  c, b  c  d, a, b, d}. Viết các các xâu thành các dòng riêng biệt dưới dạng 1.a  b  c 2. b  c  d 3. a 4. b 5.d Thực hiện hợp giải các mệnh đề: 57
6. a  c Res(1B, 4) /* Hợp giải dòng 1 với dòng 4. Chữ B chỉ*/ 7. b   c Res(2C, 5) /* rằng thành phần thứ hai của dòng 1 */ 8. c Res(3, 6A) 9.c Res(4, 7A) 10. Mâu thuẩn giữa 8 và 9.  a   b  c a b  b   c  d  d  a  c  b   c c c Mâu thuẫn Hình 2.22. Cây mô tả quá trình hợp giải * Thủ tục Robinson 2 (Dùng cho logic vị từ) Thuật giải Resolution có thể mở rộng để giải quyết các bài toán chứng minh trong logic vị từ cấp 1. Việc hợp giải hai biểu thức vị từ được thực hiện như sau: Giả sử có hai biểu thức: A= P  Q 1 Q2  Qk và B=P  R1  R2  Rt. Khi đó phép hợp giả cho ta biểu thức C = Q1 Q2  Qk  R1  R2  Rt. Do các vị từ Pi, Qi và Rj phụ thuộc và các biến nên để tạo ra các cặp đối ngẫu thực sự P và P ta phải thực hiện các phép gán. Cách chọn phép gán: Để đưa vị từ P(x1, x2, ,xn) về dạng P(t1, t2, ,tn) ta chọn phép gán q= { t1/x1, t2/x2, ,tn/xn} để thay thế mỗi biến x i bởi ti, trong đó ti có thể là biến, hằng hoặc biểu thức. Thủ tục Resolution cho logic vị từ có thể phát biểu như sau: Bước 1: Đưa các GTi và KLj về dạng chuẩn sau: k ni P x1x2 . . .xk  ij i 1 j 1 58
sao cho mọi biến có mặt trong Pij đều thuộc vào tập {x1, x2 ,. . .,xk}. Muốn vậy ta thực hiện các thao tác sau: 1. Khử bỏ các dấu kéo theo và tương đương nhờ A B  AB 2. Đưa dấu phủ định vào trong cùng chừng nào có thể, nhờ các phép biến đổi: (AB)  AB (AB)  AB A  A x A   x A   x A  xA 3. Thay tên biến để cho mỗi lượng từ chỉ có một tên biến riêng. 4. Khử bỏ các lượng từ tồn tại nhờ: x P(x) chuyển thành P(a) x y P(x,y) chuyển thành P(x,g(x)). Hàm g(x) được gọi là hàm Scholem. 5. Chuyển mọi lượng từ  về đầu biểu thức, phần biểu thức gọi là ma trận. k ni P 6. Đưa ma trận về dạng nhờ ápij dụng A(BC)  (AB) (AC) i 1 j 1 7. Loại bỏ các lượng từ  8. Thay thế các liên kết  bởi các dấu phẩy, mỗi dòng được gọi là một câu. Ví dụ: Xét x {P(x) {y {P(y) P(f(x,y))}   y {Q(x,y) P(y)}}}. Áp dụng các bước để đưa về dạng chuẩn như sau: 1.x { P(x) {y { P(y)  P(f(x,y))}   y {Q(x,y)  P(y)}}} 2.x { P(x) {y { P(y)  P(f(x,y))}  y {Q(x,y)  P(y)}}} 3.x { P(x) {y { P(y)  P(f(x,y))}   {Q(x, )  P()}}} 4.x { P(x) {y { P(y)  P(f(x,y))}  {Q(x, g(x))  P(g(x))}}} 5.xy { P(x) {{ P(y)  P(f(x,y))}  {Q(x, g(x))  P(g(x))}}} 6.xy{{P(x)P(y)P(f(x,y))}{P(x)Q(x,g(x))}{P(x)P(g(x))}} 7. {P(x)P(y)P(f(x,y))}{P(x)Q(x,g(x))}{P(x)P(g(x))} 59
8. Tách câu và viết thành các dòng P(x)P(y)P(f(x,y)) P(x)Q(x,g(x)) P(x)P(g(x)) Bước 2. Nếu tìm được một cặp câu P1, P2 và một phép gán q sao cho P1q=P2q thì thông báo “Thành công” và thuật toán dừng. Ngược lại sang bước 3. Bước 3: Tìm cặp câu P = P0  P1 Pk và Q = Q0  Q1  Q2  Qt và phép gán q sao cho P0q = Q0q. Thực hiện hợp giải câu P với câu Q được câu R= P1 Pk  Q1  Q2  Q2  Qt và bổ sung câu R vào danh sách các câu. Bước 4: Nếu không thể xây dựng thêm được các hợp giải và không có cặp câu đối ngẫu thì bài toán sai, ngược lại quay lại bước 3 hoặc bài toán được giải quyết xong và thông báo “Thành công”. Kết quả: Nếu từ GT 1 GT2 GT m KL 1  KL 2  KL n thì thủ tục Resolution dừng và đưa ra thông báo thành công. Ví dụ 2.24. Hãy chứng minh rằng An là sinh viên trường ĐHV biết rằng: - An là sinh viên lớp TIN 40 - Lớp TIN 40 là thuộc khoa CNTT - Khoa CNTT là thuộc trường ĐHV. Để chứng minh điều khẳng định trên, ta đưa vào vị từ P(x,y): nghĩa là “x thuộc y”. Khi đó ta có các giả thiết: P(An, T40), P(T40, CN), P(CN, DHV) và kết luận cần chứng minh là P(An, DHV). Ngoài ra P(x,y) là quan hệ có tính bắc cầu, nghĩa là x, y, z P(x,y) P(y,z) P(x,z). Viết các biểu thức thành từng dòng và trong mỗi dòng thay dấu  bởi dấu phẩy: 60
1.P(x,y) , P(y,z), P(x,z) 2. P(An, T40) 3. P(T40, CN) 4. P(CN, DHV) 5.P(An, DHV) /*Phủ định của kết luận*/ Ta có các bước hợp giải sau 6. P(T40, z), P(An, z) Res(1A, 2) q1 ={An/x, T40/y } 7. P(An, CN) Res(3, 6A) q2 ={CN/z } 8. P(An, y), P(y,DHV) Res(1C, 5) q3 ={An/x, DHV/z} 9. P(CN, DHV} Res(7, 8A) q4 ={CN/y} 10. Mâu thuẫn Res(4, 9). Ví dụ 2.25. Chứng minh rằng nếu nửa nhóm có đơn vị mà mỗi phần tử đều luỹ linh thì nửa nhóm đó là giao hoán. Nhắc lại một số khái niệm: + Nửa nhóm: Là tập X  trên đó có xác định một phép toán hai ngôi có tính chất kết hợp. Nếu phép toán là phép cộng (nhân) thì ta có nửa nhóm cộng (nhân). Trong ví dụ này ta sẽ xét nửa nhóm nhân. + Phần tử đơn vị: Phần tử e của nửa nhóm X được gọi là phần tử đơn vị nếu với mọi x X ta có e.x=x.e=x. + Phần tử luỹ linh: Phần tử x X được gọi là phần tử luỹ linh nếu x.x=e. Để chứng minh khẳng định trên ta sử dụng vị từ: P(x, y, z) : nghĩa là x.y=z. Từ các giả thiết và kết luận của bài toán ta có: 1. P(e, x1, x1) /* e.x1=x1 */ 2. P(x1, e, x1) /* x1e=x1 */ Từ tính kết hợp ta có: x1x2x4 (x1.x2).x4=x1.(x2.x4). Đặt x1.x2=x3, x2.x4=x5. Khi đó, tính chất này có thể được hiểu là: Nếu x1x5=x6 thì x3x4=x6 và nếu x3x4=x6 thì x1x5=x6. Do đó 61
(P(x1, x2, x3) P(x2, x4, x5) P(x1, x5, x6)) P(x3, x4, x6). Đưa về dạng chuẩn ta có: P(x1, x2, x3) P(x2, x4, x5) P(x1, x5, x6) P(x3, x4, x6). Đưa về dạng câu ta có: P(x1, x2, x3), P(x2, x4, x5), P(x1, x5, x6), P(x3, x4, x6). Vậy ta có 3.P(x 1, x2, x3), P(x2, x4, x5), P(x1, x5, x6), P(x3, x4, x6) Hoàn toàn tương tự ta có: 4.P(x 1, x2, x3), P(x2, x4, x5), P(x3, x4, x6), P(x1, x5, x6) 5. P(x1,x1,e) /* x1. x1= e */ Ta cần chứng minh tính chất giao hoán: x, y: x.y=y.x. Lấy phủ định ta có xy x.y y.x. Thay biểu thức dạng x P(x) bởi P(a) ta có P(a,b,c) và P(b,a,c). Vậy ta có: 6. P(a,b,c) 7.P(b,a,c) Thực hiện các bước hợp giải: 8. P(x2,x1,x3), P(x2,e,x6), P(x3,x1,x6) Res(3B,5), q1={x1/x2,x1/x4,e/x5, x2/x1} 9. P(x1,x4,x5), P(e,x4,x6), P(x1,x5,x6) Res(4A,5) q2={x1/x2, e/x3} 10. P(b,x4,x5), P(a,x5,x6), P(c,x4,x6) Res(3A,6) q3={a/x1,b/x2,c/x3} 11. P(x2,x1,x5), P(x2,x5,x1) Res(1,9B) q4={x1/x4, x1/x6, x2/x1} 12. P(x1,x2,x3), P(x3,x2,x1) Res(2,8B) q5={x1/x2, x1/x6, x2/x1} 13. P(a,e,x6), P(c,b,x6) Res(5,10A) q6={b/x1, b/x4, e/x5} 14. P(c,b,a) Res(2,13A) q7={a/x1, a/x6} 15. P(c,a,b) Res(11A,14) q8={c/x2, b/x1, a/x5} 16. P(b,a,c) Res(12A,15) q9={c/x1, a/x2, b/x3} 17. Mâu thuẫn Res(7,16). Nhận xét: Trong ví dụ trên ta chỉ sử dụng một vị từ. Trên thực tế đôi khi sử dụng nhiều vị từ là làm cho bài toán đơn giản hơn. Ta xét ví dụ sau: 62
Ví dụ 2.26. Nếu xem một ai đó đi lừa dối người khác là kẻ bịp bợm và bất kỳ ai đồng tình với kẻ bịp bợm cũng là bịp bợm, hơn nữa trong tập thể có một người nhút nhát đồng tình với kẻ lừa dối thì chắc chắn là có một kẻ bịp bợm tính tình nhút nhát. Ta sử dụng các vị từ sau: BB(x): x là kẻ bịp bợm. LD(x): x là kẻ lừa dối. NN(x): x là kẻ nhút nhát. ĐT(x,y): x đồng tình với y. Khi đó ta có: 1.LD(x), BB(x) 2.ĐT(x,y), BB(y), BB(x) 3. NN(a) 4. LD(b) 5. ĐT(a,b) 6.BB(x), NN(x) 7.BB(a) Res(3, 6B) q 1 ={a/x} 8. BB(b) Res(1A, 4), q2 ={ b/x} 9.NN(b) Res(6A, 8), q 3 ={b/x} 10.BB(b), BB(a) Res(2A, 5), q4 ={a/x, b/y} 11.BB(b) Res(7, 10B) 12. Mâu thuẫn Res(8,11). Tóm lại: Phương pháp của Robinson để chứng minh định lý có nội dung như sau: Lấy các giả thiết hợp cùng phủ định của kết luận và suy ra mâu thuẫn. Muốn vậy ta dùng kỹ thuật hợp giải: Sử dụng các phép gán q={t1/x1, ,tn/xn} để 63
gán cho các biến x1, xn các biểu thức ti, từ đó tìm ra cặp đối ngẫu thực sự P và P. Nếu xuất hiện cặp đối ngẫu P và P thì dừng và khẳng định định lý đúng. 0 Thực chất quá trình hợp giải là đi tìm các cặp câu P1=P1 Q 1 Qr và P =P 0 R  R và phép gán 0 0 . Xây dựng hợp giải (Q  Q  2 2 1 s P1q P2q 1 r R1 Rs)q và bổ sung vào danh sách các câu. d. Giải quyết vấn đề nhờ logic vị từ Trong mục A chúng ta đã nghiên cứu hai phương pháp chứng minh định lý tiêu biểu, ở đây sẽ nghiên cứu việc xác định các phép gán trị cho các biến để từ các giả thiết GT1 GTm suy ra KL1 KLn. Hai cách giải quyêt: 1. Lưu lại vết các phép gán giá trị nhận được cho đến khi đưa đến mâu thuẫn. Ta đưa vào khái niệm hợp các phép gán. Giả sử ,  là hai phép gán trị, hợp của chúng được ký hiệu bởi o sao cho đối với mọi biểu thức P ta có: P o=(P ). Ví dụ 2.27. Giả sử Mai và Dương rất thân nhau. Đi đâu Mai và Dương cũng có nhau. Hơn nữa ta biết rằng hiện nay Mai đang ở thư viện. Hỏi Dương đang ở đâu? Ta đưa vào vị từ: P(x,y): x đang ở vị trí y. Khi đó: x P(Mai, x) P(Dương, x) P(Mai, Thư viện) Cần tìm giá trị của P(Dương,x). Ta có: P(Mai,x)P(Dương,x)P(Dương,x) P(Mai, Thư viện) = P(Mai,x) 64 Hình 2.23. Đồ thị hợp giải
={Thư viện/x} Nhờ hợp phép gán o=={thư viện/x}, ta có câu trả lời hiện nay Dương đang ở thư viện. 2. Cải biên đồ thị lời giải Bên cạnh biểu thức là phủ định của kết luận KL j cần chứng minh ta thêm vào phủ định của chính nó (tức là KLj) và giữ nguyên các phép hợp giải giống như ở trong đồ thị hợp giải. Kết quả là nhận được P(Dương, Thư viện) có nghĩa là câu trả lời đã được xây dựng xong. P(Mai,x)P(Dương,x)P(Dương,x) )P(Dương,x) P(Mai, Thư viện) P(Mai,x) )P(Dương,x) P(Dương, Thư viện) Hình 2.24. Đồ thị chứng minh cải biên 2.6.4. Biểu diễn tri thức và suy diễn Như đã nói ở trong 2.5 về cấu trúc các hệ thống giải quyết vấn đề, có hai xu hướng giải quyết vấn đề sau: -Tổng quát hoá cấu trúc bài toán, đưa về các dạng quen thuộc (không gian trạng thái, quy bài toán về bài toán con, sử dụng logic hình thức). Ở đây mới chú ý đến các thông tin về bài toán. Sau đó sử dụng các chiến lược tìm kiếm. 65
-Cụ thể hoá bài toán trên cơ sở sử dụng các tri thức đặc tả của từng bài toán và của các chuyên gia giải quyết vấn đề để xây dựng các tri thức suy diễn (Xem chương 3) 2.6.5. Phương pháp GPS (General Problem Solving) Phương pháp GPS còn được gọi là phương pháp Mục đích-Phương tiện (Endo-Means) gồm 3 yếu tố cơ bản: - Xác định không gian biểu diễn vấn đề W và tập các trạng thái, trạng thái đầu S0, trạng thái cuối S * và tập các phép biến đổi trạng thái O={O i | Oi: Si Sj}. - Xác định tập các kiểu khác biệt giữa các trạng thái trong không gian ={1, , m} - Xây dựng ma trận M với các cột ứng với các toán tử, các hàng ứng với các kiểu khác biệt, M=(mij)m n. 1 nếu phép biến đổi Oj làm giảm sự khác biệt i mij= 0 nếu ngược lại. Thủ tục GPS Vào: Tập các kiểu khác biệt giữa các trạng thái ={1, , m} Tập các toán tử O={O1, O2, . . . ,On}. Trạng thái đầu S0, trạng thái cuối S*. Ra: Thông báo “Thành công” nếu có thể đưa S0 về S*. Phương pháp: { S=S0; OP=; While S S* do {D=match(S, S*); /*Giả sử D={i1, , ik} */ get(D); /*Chọn ra sự khác biệt quan trọng nhất */ /* Giả sử  là sự khác biệt thứ i trong và OP={Oj |mij=1} */ 66
For j=1 to n do if mij=1 then OP=OP  {Oj}; Oget(OP); /* chọn ra toán tử Oj làm giảm sự khác biệt i nhiều nhất */ S=O(S) }} Ở đây thủ tục match(S, S *) cho phép xác định những sự khác biệt giữa S và S*. Nếu S và S* là các đỉnh trong đồ thị, một ví dụ đơn giản về sự khác biệt giữa S và S* là độ dài đường đi ngắn nhất từ S tới S*. Ví dụ 2.28. Chứng minh rằng R  (P Q)  (Q  P)  R. Một thao tác đơn giản là quy bài toán về dạng: 1) R  (P Q) (Q  P)  R và 2) (Q  P)  R R  (P Q) Sau đó áp dụng thuật giải Wong .H, hoặc Robinson. Ở đây, ta minh hoạ việc giải bài toán bằng cách áp dụng thủ tục GPS. + Không gian biểu diễn vấn đề là không gian biểu diễn các mệnh đề logic. Trạng thái đầu S0 = R  (P Q) Trạng thái đích S* = (Q  P)  R Các phép toán là các phép biến đổi tương đương. (xem trang 50) + Tập các kiểu khác biệt gồm có 6 kiểu khác biệt: V: ở biểu thức này có một biến v nào đó mà ở biểu thức khác không có. N: Một biến v nào đó thuộc vào hai biểu thức với số lần xuất hiện khác nhau. T: Có sự khác biệt về dấu  của biểu thức. Một trong hai biểu thức được bắt đầu bởi dấu . C: Khác nhau về số các phép toán. G: Khác nhau về phương pháp nhóm các mệnh đề. P: Khác nhau về vị trí các thành phần trong hai biểu thức. 67
+ Xây dựng ma trận M: Để đơn giản, ta chỉ lấy các cột tương ứng với R 1R6, R9, R1 R2 R3 R4 R5 R6 R9 V N 1 T 1 1 1 1 C 1 1 G 1 P 1 1 Đặt L1 = S0 = R  (P Q), L0 = S* = (Q  P)  R Đích 1: Biến đổi L1 về L0; Xác định sự khác biệt P. Đích 2: Loại bỏ sự khác biệt P giữa L1 và L0. Xác định tập các toán tử chấp nhận được {R1, R2} Đích 3: Áp dụng R1 vào L1. Đích 4: Biến đổi L1 sang dạng thích hợp cho việc áp dụng R1. Xác định được A = R, B = P Q. Tạo ra biểu thức mới L2= (P Q)  R. Đích 5: Biến đổi L2 về L0. Xác định sự khác biệt C. Đích 6: Loại bỏ sự khác biệt C giữa L2 và L0. Xác định tập các toán tử chấp nhận được {R5, R6}. Đích 7: Áp dụng R5 vào L2. Đích 8: Biến đổi L2 về dạng thích hợp để có thể áp dụng R5. Không xác định được A và B, nên toán tử R5 bị loại. Chuyển sang R6. Đích 9: Áp dụng toán tử R6 vào L2. Đích 10: Biến đổi L2 về dạng thích hợp để có thể áp dụng R6. 68
Xác định được A=P, B=Q. Tạo ra biểu thức mới L3=(P  Q)  R. Đích 11. Biến đổi L3 về L0. Xác định sự khác biệt P. Đích 12: Xoá bỏ sự khác biệt P giữaL3 và L0. Tập toán tử chấp nhận được {R1, R2}. Đích 13: Áp dung R1 vào L3. Đích 14: Biến đổi L3 về dạng thích hợp để có thể áp dụng R1. Ta xác định A = P, B = Q. Xây dựng L4=(Q  P)  R. Đích 15: Biến đổi L4 về L0. Xác định sự khác biệt T giữa L4 và L0 . Đích 16: Loại bỏ sự khác biệt T giữa L4 và L0. Xác định tập các toán tử chấp nhận được {R2, R5, R6, R9} Đích 17: Áp dụng R2 vào L4. Đích này bị loại vì không thể đưa P về đạng có thể áp dụng R2. Chuyển sang áp dụng R5. Đích 18: Áp dụng R5 vào L4. Đích này bị loại. Chuyển sang áp dụng R6. Đích 19: Áp dụng R6 vào L4. Đích này bị loại và chuyển sang R9. Đích 20: Áp dụng R9 vào L4. Đích 21: Biến đổi L4 về dạng thích hợp để có thể áp dụng R9. Ta xác định được A=P Xây dựng L5= (Q  P)  R L5 trùng với L0. Quá trình đã được chứng minh. 2.7. GIẢI QUYẾT VẤN ĐỀ VÀ CÁC KỸ THUẬT HEURISTICS Một số giải thích về Heuristics: 69
1. Theo từ điển tiếng anh Oxford: “Heuristics là nghệ thuật tìm kiếm chân lý. Nói riêng, Heuristics là đặc trưng của quá trình học nhờ đó các học sinh học được cách tự tìm ra cách giải thích các hiện tượng tự nhiên”. 2. Theo Feigenbaum Feldman: “Heuristics là các quy tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối lượng tìm kiếm lời giải trong không gian bài toán cực lớn”. 3. Trong các tài liệu trí tuệ nhân tạo: Heuristics được coi là khái niệm đối lập với thuật giải (Algorithm). Các dấu hiệu đặc trưng của bài toán cho phép xác định nhanh chóng lời giải được gọi là các Heuristics và các quy tắc sử dụng các Heuristics được gọi là các quy tắc Heuristics. Các khía cạnh quan trọng của lập trình Heuristics: 1. Đảm bảo tính tổng quát 2. Điều khiển quá trình tìm kiếm 3. Điều khiển quá trình suy diễn 4. Các hàm đánh giá 5. Đối sánh các cấu trúc thông tin 6. Khả năng học 7. Khả năng đặt kế hoạch. Trong đó các hàm đánh giá được coi là công cụ có hiệu lực nhất. Khi lập trình Heuristics cần chú ý hai vấn đề sau: + Tách các dấu hiệu có ích + Tổ hợp các dấu hiệu này để nhận được các hàm đánh giá tốt. Một kỹ thuật Heuristics được coi là hợp lý nếu nó cho phép đánh giá được các khả năng để làm rõ khả năng nào tốt hơn các khả năng còn lại. Các kỹ thuật Heuristics được chia thành 2 lớp chính: + Lớp định tính: Các luật nếu thì + Lớp định lượng: Các hàm ước lượng Heuristics. Hai cách đưa các thông tin Heuristics đặc tả vào các thủ tục tìm kiếm: 70
+ Các kỹ thuật Heuristic được nạp ngay trong các biểu diễn của bài toán. + Các hàm đánh giá Heuristic nhằm lượng hoá “giá trị” của mỗi khả năng thực hiện. 2.8. MỘT SỐ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ KHÁC 2.8.1. Phương pháp tạo và kiểm tra (Generate and test) Nội dung: 1.Tạo một lời giải thử nghiệm nào đó. Trong không gian bài toán điều này có nghĩa là đưa ra một đường đi bộ phận xuất phát từ trạng thái đầu. 2. Kiểm tra xem nó có phải là lời giải thực sự hay không? 3. Nếu đúng thì dừng và đưa ra thông báo thành công. Ngược lại chuyển về bước 1. Nhận xét: -Về thực chất thủ tục tạo và kiểm tra sẽ cho lời giải nếu quả thật nó tồn tại và do tính tạo sinh ngẫu nhiên nên nó phải duyệt không gian bài toán một cách hệ thống. -Thủ tục này tổng quát hơn thủ tục tìm kiếm theo chiều sâu, theo chiều rộng, sâu dần, 2.8.2. Phương pháp leo đồi (Hill climbing) Phương pháp này là một biến thể của phương pháp tạo và kiểm tra trong đó thông tin phản hồi khi kiểm tra được dùng để trợ giúp quá trình tạo sinh lời giải ở bước tiếp theo. Nội dung: 1. Tạo sinh lời giải thử nghiệm giống như trong thủ tục tạo và kiểm tra. Nếu nó là lời giải thực sự thì dừng và đưa ra thông báo thành công. Ngược lại tiếp tục thực hiện bước sau. 2. Từ lời giải này, áp dụng một số luật nào đó để sinh ra một tập mới các lời giải thử nghiệm. 3. Với mọi phần tử trong tập các lời giải này, ta làm như sau: 71
- Nếu nó là lời giải thực sự thì dừng. - Nếu ngược lại, ta xem phần tử này có phải là phần tử gần nhất so với lời giải thực sự cho đến thời điểm hiện taị không. Nếu đúng ta giữ lại. Ngược lại, sang bước 4. 4. Lấy phần tử tốt nhất nhận được ở trên và dùng nó như lời giải thử nghiệm mới và chuyển sang bước 2. 2.8.3. Phương pháp thoả mãn các ràng buộc (constraint satisfaction method) Phương pháp này bổ trợ cho các phương pháp tìm kiếm đã nêu ở trên. Mục đích đặt ra là tìm các trạng thái của bài toán sao cho thoả mãn một tập ràng buộc nào đó. Quá trình tìm kiếm lời giải bao gồm hai phần: + Tìm kiếm trong không gian các ràng buộc + Tìm kiếm trong không gian bài toán ban đầu. Nội dung: Thực hiện các bước sau đây cho đến khi tìm được lời giải đầy đủ của bài toán hoặc tất cả các đường đi đều đã được duyệt nhưng không thu được kết quả. 1. Chọn một đỉnh chưa được xét trong đồ thị tìm kiếm. 2. Áp dụng các luật suy dẫn đối với các ràng buộc vào đỉnh đã chọn để sinh ra tất cả các ràng buộc mới có thể có. 3. Nếu tập các ràng buộc mới có chứa mâu thuẫn thì đưa ra thông báo bế tắc. 4. Nếu tập các ràng buộc mô tả lời giải đầy đủ của bài toán thì dừng và đưa ra thông báo thành công. Ngược lại sang bước 5. 5. Áp dụng các luật trong không gian trạng thái để tạo ra các lời giải bộ phận tương hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm kiếm. Ví dụ 2.30. Xét bài toán điền chữ S END + MORE MONEY 72
Ràng buộc: - Hai chữ khác nhau có giá trị khác nhau. - Các ràng buộc về phép toán số học. Các trạng thái: - Trạng thái đầu: S, E, N, D, M, O, R, Y chưa xác định. - C1, C2, C3, C4 chưa xác định /*C i là các giá trị nhớ của các cột tính từ phải sang trái */ Trạng thái đầu CONST M=1 M=1, S=8 hoặc 9 O=0 O=0 hay 1 O=0 N=E hay N=E+1 N=E+1 N+R>9 C2=1 E 9 E=2 N=3 R=8 hoặc 9 2+D=Y 2+D=10+Y C1=0 N=3 N=3 D+2>9 D>7 R=8 R=9 D=8 D=9 S=9 Y=1 Y=0 Mâu thuẫn Mâu thuẫn Hình 2.25. Đồ thị giải kết hợp và các ràng buộc 73
2.9. CÁC CHIẾN LƯỢC ĐIỀU KHIỂN Như đã chỉ ra trong 2.5, quá trình giải quyết vấn đề bao gồm: - Biểu diễn vấn đề. - Các kỹ thuật tìm kiếm. - Các chiến lược điều khiển. - Các kỹ thuật Heuristics. Các chiến lược điều khiển bao gồm các quyết định: - Hướng tìm kiếm trong không gian bài toán. - Xử lý cạnh tranh. Hướng tìm kiếm Ba cách lựa chọn hướng tìm kiếm: - Xuất phát từ hình trạng đầu đi đến hình trạng cuối, gọi là chiến lược điều khiển dựa trên dữ liệu hay suy diễn tiến (data-driven control strategy, forward chaining strategy). Các kỹ thuật nêu trong 2.7.1, 2.7.2, 2.7.3 thuộc loại này. - Xuất phát từ hình trạng cuối để ngược trở lại đi tới hình trạng đầu, gọi là chiến lược điều khiển dựa trên luật hay suy diễn lùi, hướng đích (Rule-driven control Strategy, backward chaining strategy goal-driven strategy). - Xuất phát từ cả hình trạng đầu và hình trạng cuối (mixed control strategy). Ba nhân tố ảnh hưởng tới quá trình lựa chọn hướng tìm kiếm: - Số hình trạng đầu và số hình trạng đích. Ưu tiên hướng tìm kiếm từ tập ít các tình huống đi tới tập các tình huống nhiều hơn. - Theo một hướng nào đó, hằng số phân nhánh (Branching factor) là số trung bình các nút có thể đạt tới từ một nút nào đó. Ưu tiên hướng tìm kiếm với hằng số phân nhánh nhỏ hơn. - Yêu cầu giải thích quá trình lập luận đối với người sử dụng. Nếu có thì ưu tiên hướng tìm kiếm gần gũi với cách nghĩ của họ. Ví dụ 2.31. - Đối với bài toán tìm đường đi từ nhà đến một nơi nào đó không quen biết, chiến lược điều khiển tốt là backward chaining 74
- Đối với bài toán tích phân nên dùng forward chaining. Xử lý cạnh tranh Xử lý cạnh tranh xuất hiện khi có hơn một khả năng có thể áp dụng. Cách xử lý cạnh tranh: - Chọn ngẫu nhiên. - Chọn theo một tiêu chuẩn nào đó. - Đưa ra một số ràng buộc. Các kỹ thuật đối sánh xem các đỉnh có thoả mãn các ràng buộc hay không: + Xây dựng chỉ dẫn. + Đối sánh các giá trị các biến. + Đối sánh xấp xỉ. + Lọc các đỉnh đã được đối sánh. 2.10. CÁC HỆ THỐNG GIẢI QUYẾT VẤN ĐỀ Có thể đưa ra danh sách các hệ thống giải quyết vấn đề được nghiên cứu và cài đặt sau đây: - Các chương trình chơi cờ tướng, cờ GO, cờ Đam, Các chương trình trò chơi cờ carô, chơi bài. - Các chương trình giải bài toán hình học phẳng, hình học không gian. Các chương trình giải quyết các bài toán thuộc lĩnh vực toán: + Tính tích phân bất định. + Chứng minh định lý sử dụng logic toán học sơ cấp. + Kiểm tra các chứng minh toán học. + Trợ giúp xử lý các biểu thức toán học. + Xác định những đặc điểm tương tự về hình học. + Chương trình giải tích hồi quy Heuristic. + Chứng minh định lý tự động sử dụng phương pháp Resolution. + Tìm các hàm tuyến tính để đánh giá và nhận dạng - Các hệ thống MULTIPLE, GPS. - Các hệ thống tự động dẫn xuất các câu trả lời. 75
Những hệ thống giải quyết vấn đề lớn: - Hệ chuyên gia. - Hệ trợ giúp quyết định. Chương III BIỂU DIỄN TRI THỨC VÀ SUY DIỄN (KNOW LEDYE REPRESENTATION AND ENGINEERING) 3.1. NHẬP MÔN Khái niệm biểu diễn tri thức được đề cập nhiều trong các tài liệu về TTNT. Tuy nhiên, chỉ đến khi xuất hiện các hệ chuyên gia và ứng dụng của nó, khái niệm này mới thực sự có cơ sở lý luận và thực tế vững chắc. Ta hiểu biểu diễn tri thức là thể hiện các mô tả về thế giới bên ngoài dưới dạng sao cho các máy thông minh có thể đưa tới những kết luận về môi trường xung quanh nó, trên cơ sở một cách hình thức các mô tả này. Tri thức và suy diễn là hai thành phần trong bất kỳ một hệ xử lý dựa trên tri thức nào. Các phương pháp biểu diễn tri thức chủ yếu: - Biểu diễn nhờ logic hình thức - Biểu diễn nhờ hệ sản xuất - Biểu diễn nhờ mạng ngữ nghĩa - Biểu diễn nhờ các Frame - Biểu diễn dùng bộ ba OAV Trong bất kỳ phương pháp biểu diễn và xử lý tri thức nào chúng ta cần lưu tâm tới hai vấn đề: - Các sự kiện (facts): Các thông tin về đối tượng - Các phương pháp biểu diễn các sự kiện trong một hệ phát biểu hình thức nào đó. 3.2. TRI THỨC VÀ DỮ LIỆU 76
Trên đây ta đã đưa ra những so sánh căn bản giữa lập trình truyền thống (conventional programming) và lập trình TTNT (A.I. programming). Sự tiến hoá có thể tóm tắt trong sơ đồ sau: Tri thức Dữ liệu Thuật giải Heuristic Thuật giải Suy diễn Lập trình truyền thống Lập trình TTNT Theo quan điểm cấu trúc dữ liệu: Bit, Byte, Từ, số nguyên, Các cấu trúc dữ liệu phức hợp: số thực, mảng, bản ghi, Mạng ngữ nghiã, frame, danh tệp, sách, biểu diễn các ký hiệu tượng trưng. Theo quan điểm ngôn ngữ lập trình: Ngôn ngữ định hướng xử Ngôn ngữ xử lý danh sách, các lý dữ liệu ký hiệu tượng trưng (logic) Như vậy dữ liệu và tri thức cùng là những dạng khác nhau của thông tin, nên rất khó có thể phân biệt rạch ròi giữa tri thức và dữ liệu. Tuy vậy, có thể dẫn ra các cung bậc khác nhau dẫn từ dữ liệu đến tri thức: Tri thức Tính chủ động Nhúng vào không gian với “metric ngữ nghĩa” Thang chia Cấu trúc bên ngoài Cấu trúc bên trong 77 Diễn giải bên trong Dữ liệu
3.3. PHÂN LOẠI TRI THỨC 3.2.1. Các dạng tri thức Tri thức tồn tại dưới ba dạng cơ bản sau: - Tri thức mô tả: Cho ta một sự kiện mà không có thông tin về cấu trúc, mối liên hệ bên trong, bên ngoài cũng như phương pháp sử dụng tri thức đó. Ví dụ 3.1: Vinh là thành phố đẹp. - Tri thức thủ tục: Mô tả phương pháp kiến thiết, ghép nối và suy diễn các tri thức đã có, tạo nên những tri thức mới. Ví dụ 3.2: Nếu a đúng và có luật suy diễn từ a b thì b đúng. - Tri thức điều khiển: Dùng để chỉ ra phương pháp điều khiển sử dụng các tri thức mô tả và các tri thức thủ tục. Ví dụ 3.3: - Các tri thức mô tả là các tri thức về đỉnh, cung. - Các tri thức thủ tục là các thủ tục tìm kiếm. - Các tri thức điều khiển là các chiến lược điều khiển. 3.2.2. Các cấp độ của tri thức - Tri thức tĩnh, thuần nhất: Các tri thức bất biến đối với không gian, thơì gian. Ví dụ 3.4: Nếu hàm số f(x) có đạo hàm trên đoạn [a, b] thì liên tục trên đoạn đó. - Tri thức động phụ thuộc vào không gian, tình huống. Ví dụ 3.5: Sỹ Thuỷ là vua phá lưới giải vô địch Quốc gia mùa bóng 1999- 2000. - Tri thức động phụ thuộc vào thời gian, quan hệ nhân quả. 78
Ví dụ 3.6: Kỷ lục nhảy cao của Việt nam là 2,02m. 3.4. BẢN CHẤT CỦA TRI THỨC CHUYÊN GIA Chuyên gia là người có uy tín cao trong một lĩnh vực nào đó, được đông đảo mọi người công nhận là người có khả năng giải một lớp các bài toán hẹp nào đó mà phần lớn những người khác không thể giải quyết được như vậy. Các chuyên gia có khả năng như vậy là vì họ có một lượng lớn các tri thức tích luỹ cùng với các tri thức đặc tả trong lĩnh vực cụ thể được lưu trong bộ nhớ dài hạn. Chẳng hạn, các chuyên gia cờ thế giỏi hoặc các nhà bác học nhận giải Nobel thường có thể chứa 5.10 4 đến 10 5 các bộ thông tin heuristic. (Theo các chuyên gia tâm lý học, để làm được như vậy phải mất ít nhất 10 năm). Tri thức thu nạp được là thông tin nhận được được tổ chức, tạo chỉ dẫn và lưu trữ sao cho dễ dàng truy nhập tới. Việc thu nạp tri thức chính là quá trình tạo các lớp thông tin. Các tri thức thu nạp được bao gồm hai dạng: - Các nguyên lý, các lý thuyết tổng quát. - Các heuristic và các lý thuyết đặc tả. 3.5. CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC 3.5.1. Biểu diễn tri thức sử dụng logic hình thức Trong chương 2 (Phần 2.7.3) ta đã đưa vào các khái niệm cơ bản về logic mệnh đề và logic vị từ. Ở đó các tri thức về bài toán cần giải quyết được thể hiện dưới dạng các biểu thức logic. Trong phần này ta quan tâm đến việc biểu diễn bằng logic vị từ các tri thức của các chuyên gia giải quyết vấn đề. Một cách tổng quát các tri thức chuyên gia được thể hiện dưới dạng luật: GT KL, ở đây GT và KL là các biểu thức logic. Ta thường xét tới các luật dưới dạng Horn: 79
p1   pn q1 qm Dạng 1: n=0, m=0, luật có dạng:  F(t1, ,tk) nếu t1, ,tk là các hạng thức cụ thể nào đó thì nó cho ta một sự kiện trong CSDL. Ngược lại nếu ti là biến thì nó cho ta một tập các sự kiện. Dạng 2: n 1, m=0, luật có dạng: p1 pn  Dạng này thường được dùng để diễn đạt các câu hỏi trong các phương pháp chứng minh nhờ phản chứng nhằm dẫn ra mâu thuẫn (xem phương pháp Resolution). Dạng 3: n 1, m=1, luật có dạng: p1 pn q Đây là dạng hay gặp nhất trong thực tế. Dạng này có nghĩa là nếu các sự kiện p1, ,pn đúng thì sự kiện q cũng đúng. Dạng 4: n=0, m>1, luật có dạng:  q1 qm Dạng này thường được dùng khi thiếu thông tin. Dạng 5: n 1, m 1 p1   pn q1 qm Đây là dạng tổng quát nhất. Chẳng hạn: CHAME(x,y) CHA(x,y)ME(x,y). Trong thực tế xử lý các dạng 4, 5 thường không sử dụng do tính phức tạp. Tuy nhiên, một luật dạng này tương đương với một tập các luật dạng 3, nghĩa là nó tương đương với: p1   pn q2  qm q1 p1   pn q1 q3 qm q2 p1   pn q1 qm-1 qm 80
3.5.2. Biểu diễn tri thức nhờ mạng ngữ nghĩa Một cách hình thức mạng ngữ nghĩa là đồ thị định hướng G=(N,A), trong đó N là tập các đối tượng, các sự kiện hay khái niệm cụ thể, A là tập các mối liên hệ giữa các cặp đối tượng, sự kiện hay khái niệm. Ví dụ 3.7: Về mạng ngữ nghĩa. AN2 ISA Hà nội Địa danh AKO r3 ISA ISA Nơi Vườn nghỉ thú r3 AKO Voi r3 r1 r3 r1 ISA r1 Gấu ISA Sư tử ISA Động vật Hình 3.1. Một ví dụ về mạng ngữ nghĩa Trong đó Voi, Gấu, Sư tử là những thể hiện cụ thể của frame “động vật”, được mô tả bởi: ( , , ) Các tên: Loài, sống ở, Ăn được gọi là Slot. Hà nội, Vườn thú là những thể hiện của các frame “Địa danh” và “Nơi nghỉ” tương ứng. r 1 là quan hệ cùng có 4 chân. r 3 là quan hệ “ở tại”. 81
ISA là quan hệ loài đặc biệt “là” (is a) AKO là quan hệ đặc biệt “bao gồm” (a kind of) 3.5.3. Biểu diễn tri thức sử dụng các luật sản xuất Các sản xuất có dạng: p 1  . . .  pm q. Tuỳ thuộc vào bản chất của lĩnh vực đang quan tâm mà có những ngữ nghĩa khác nhau về sản xuất. Trong logic vị từ p1, ,pm, q là những biểu thức logic, còn chính là phép toán kéo theo theo nghĩa thông thường. Trong văn phạm: G=(N,T,P,S), N là tập các ký hiệu không kết thúc, T là tập ký hiệu kết thúc, S N là ký hiệu đầu, P là tập các sản xuất có dạng , ở đây ,  (N U T)*. Mỗi sản xuất p:  có nghĩa là nếu có xuất hiện xâu thì có thể thay nó bởi xâu . Do vậy có thể định nghĩa: L(G)={ T*  S }. Trong ngôn ngữ lập trình, các sản xuất có nghĩa là các câu lệnh If p1 pm then q Theo nghĩa thường gặp trong các hệ chuyên gia (expert system) cơ sở tri thức bao gồm hai bộ phận: + Cơ sở dữ liệu các sự kiện F (facts) F={f1, ,fm}. + Cơ sở các luật sản xuất R (rules). Các luật sản xuất P có dạng: f i1  fik q, có nghĩa là nếu trong F đã có các sự kiện fi1, ,fik thì nó chứa thêm sự kiện q. 3.5.4. Biểu diễn tri thức sử dụng các frame Tư tưởng về frame (khung) do Miminsky đưa ra năm 1975. Frame về thực chất là sự tổng quát hoá của các bản ghi. Mỗi kiểu frame được mô tả bởi: Tên frame : : . . . 82
: Trong đó có thể là: * Nếu lấy giá trị ngầm định (default) PART OF có nghĩa là frame này tạo thành một phần cấu thành của một frame khác. IS A có nghĩa là fame này là một biến thể của frame khác. Lưu ý: Các frame được nối với nhau tạo thành một cấu trúc danh sách phức hợp giống như mạng ngữ nghĩa, song đối với các liên kết kiểu PART OF, ISA có sự xuất hiện của việc di truyền các thuộc tính. 3.6. CÁC KHÍA CẠNH XỬ LÝ TRI THỨC Ba khía cạnh cơ bản trong xử lý tri thức là: Suy diễn, tổng hợp và chuyển đổi tri thức. 3.6.1. Chuyển đổi tri thức Thông thường các hệ cơ sở tri thức thường biểu diễn tri thức theo 4 mức: Dạng biểu diễn ngoài Dạng biểu diễn quan niệm Dạng biểu diễn trong Dạng biểu diễn vật lý Có ba loại phép chuyển đổi tri thức được mô tả trong hình sau: NSD1 NSDn Khung nhìn 1 Khung nhìn n Dạng biểu diễn ngoài Biến đổi mức 1 Biến83 đổi mức 2 HỆ QUẢN TRỊ CƠ SỞ TRI THỨC
Dạng biểu diễn quan niệm Dạng biểu diễn trong Biến đổi mức 3 Cơ sở tri thức Hình 3.2. Các mức biểu diễn tri thức và chuyển đổi tri thức 3.6.2. Tổng hợp tri thức Tổng hợp tri thức là quá trình liên kết, sắp xếp, khái quát hoá các nội dung tri thức làm cơ sở cho khả năng học, tạo ra những tri thức mới ở cấp độ cao hơn. Có hai lớp kỹ thuật tổng hợp tri thức: Lớp 1: Bao gồm các kỹ thuật xây dựng tri thức từ các dữ liệu Lớp 2: Bao gồm các kỹ thuật xây dựng tri thức điều khiển từ các tri thức mô tả và tri thức thủ tục ban đầu. Các kỹ thuật cơ bản bao gồm: Học của máy: - Học ngẫu nhiên - Học thông qua mạng nơron - Học thông qua xác định các tham số - Học nhờ phương pháp GPS - Học các quan niệm. - Học tương tự. - Học thông qua khám phá quy luật. Quy nạp: 84
- Quy nạp không hoàn toàn - Quy nạp hoàn toàn - Quy nạp cấu trúc Hướng dữ liệu: - Dựa trên dữ liệu mẫu - Giải thuật di truyền Tạo kiểm tra 3.6.3. Suy diễn tri thức Suy diễn tri thức bao gồm các cơ chế liên kết các tri thức đã có để suy dẫn ra các tri thức mới. Phương thức biểu diễn tri thức có ảnh hưởng lớn đến cơ chế suy diễn tri thức. Các phương pháp suy diễn tri thức: Phương pháp suy diễn Trong logic mệnh đề, logic vị từ, dựa trên hai phương thức: Modus ponens A, A B . Nghĩa là nếu A đúng và A B đúng thì B B đúng. A B,B Modus tollens  B . Nghĩa là nếu B sai và A B đúng thì A sai. Suy diễn tiến: Xuất phát từ các vị từ đã cho ban đầu, sử dụng các luật cho đến khi đưa ra kết luận mong muốn. Suy diễn lùi: Xuất phát từ các kết luận mong muốn, xem những luật có khả năng suy ra chúng, thêm các tiền đề vào danh sách các kết luận cần chứng minh và tiếp tục như vậy. Phương pháp quy diễn Suy diễn trên cơ sở tương tự giữa các sự kiện. 85
Phương pháp quy nạp - Quy nạp hoàn toàn. - Quy nạp không hoàn toàn. - Quy nạp cấu trúc. 3.7. CÁC HỆ CƠ SỞ TRI THỨC Vai trò của các kỹ sư xử lý tri thức Các kỹ sư tri thức có trách nhiệm: - Phát triển phần mềm hệ thống, quản trị phần mềm hệ thống, đảm bảo cập nhật, sửa đổi và suy diễn tri thức. - Phân tích phương cách giải quyết vấn đề của chuyên gia con người. - Trao đổi với các chuyên gia con người nhằm giúp họ có thể diễn đạt tri thức và cơ chế suy diễn dưới dạng có thể mã hoá trong máy tính. - Bảo trì hệ thống, đảm bảo tính nhất quán (tính phi mâu thuẫn), tính không dư thừa của tri thức. Các thành phần trong hệ cơ sở tri thức Các thành phần trong một hệ cơ sở tri thức và mối quan hệ giữa chúng được mô tả bởi hình vẽ sau: NSD Giao diện bằng ngôn ngữ tự nhiên Hệ chuyên gia Cơ sở tri thức Các loại hệ cơ sở tri thức: 86