Luận Văn Trí tuệ nhân tạo

MỤC LỤC




Trang

LỜI NÓI ĐẦU 6

NHẬP MÔN 8



PHẦN I


GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM


Chương 1. CÁC CHIẾN THUẬT TÌM KIẾM MÙ 16


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


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


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


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


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


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


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


1.4. Quy vấn đề về các vấn đề con.


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


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


1.4.2. Đồ thị và/hoặc 30


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


Chương 2. CÁC CHIẾN LƯỢC TÌM KIẾM KINH NGHIỆM 36


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


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


2.3. Tìm kiếm leo đồi 40


2.4. Tìm kiếm BEAM 41




Chương 3. CÁC CHIẾN LƯỢC TÌM KIẾM TỐI ƯU .42


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


3.1.1. Thuật toán A* 44


3.1.2. Thuật toán tìm kiếm nhánh – và – cận .46


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


3.2.1. Tìm kiếm leo đồi 49


3.2.2. Tìm kiếm gradient 50


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


3.3. Tìm kiếm mô phỏng sự tiến hoá. Thuật toán di truyền 52


Chương 4. TÌM KIẾM CÓ ĐỐI THỦ 58


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


4.2. Chiến lược Minimax .60


4.3. Phương pháp cắt cụt alpha – beta .64




PHẦN II


TRI THỨC VÀ LẬP LUẬN


Chương 5. LOGIC MỆNH ĐỀ .69


5.1. Biểu diễn tri thức 69


5.2. Cú pháp và ngữ nghĩa của logic mệnh đề .71


5.2.1. Cú pháp 71


5.2.2. Ngữ nghĩa .72


5.3. Dạng chuẩn tắc .74


5.3.1. Sự tương đương của các công thức 74


5.3.2. Dạng chuẩn tắc .75


5.3.3. Các câu Horn 76


5.4. Luật suy diễn 77


5.5. Luật phân giải, chứng minh bác bỏ bằng luật phân giải .80




Chương 6. LOGIC VỊ TỪ CẤP MỘT 84


6.1. Cú pháp và ngữ nghĩa của logic vị từ cấp một .85


6.1.1. Cú pháp 85


6.1.2. Ngữ nghĩa .87


6.2. Chuẩn hoá các công thức 90


6.3. Các luật suy diễn 92


6.4. Thuật toán hợp nhất 95


6.5. Chứng minh bằng luật phân giải .98


6.6. Các chiến lược phân giải 103


6.6.1. Chiến lược phân giải theo bề rộng .105


6.6.2. Chiến lược phân giải sử dụng tập hỗ trợ 106


6.6.3. Chiến lược tuyến tính .107


6.7. Sử dụng logic vị từ cấp một để biểu diễn tri thức 107


6.7.1. Vị từ bằng .108


6.7.2. Danh sách và các phép toán trên danh sách .108


6.8. Xây dựng cơ sở tri thức 113


6.9. Cài đặt cơ sở tri thức .115


6.9.1. Cài đặt các hạng thức và các câu phân tử .116


6.9.2. Cài đặt cơ sở tri thức 119


Chương 7. BIỂU DIỄN TRI THỨC BỞI CÁC LUẬT 122

VÀ LẬP LUẬN 122


7.1. Biểu diễn tri thức bởi các luật nếu – thì 122


7.2. Lập luận tiến và lập luận lùi trong các hệ dựa trên luật 124


7.2.1. Lập luận tiến .125


7.2.2. Lập luận lùi .128


7.2.3. Lập luận lùi như tìm kiếm trên độ thị và/hoặc .130


7.3. Thủ tục lập luận tiến .132


7.3.1. Thủ tục For_chain 133


7.3.2. Thủ tục rete .136




7.3.3. Hệ hành động dựa trên luật 143


7.4. Thủ tục lập luận lùi . 147


7.5. Biểu diễn tri thức không chắc chắn 151


7.6. Hệ lập trình logic 153


7.7. Hệ chuyên gia .157


Chương 8. LOGIC KHÔNG ĐƠN ĐIỆU .159


8.1. Lập luận có thể xem xét lại và logic không đơn điệu .159


8.2. Đặc điểm của logic không đơn điệu .161


8.3. Logic mặc định .163


8.4. Giả thiết thế giới đóng 167


8.5. Bổ sung vị từ .169


8.6. Hạn chế phạm vi .171


Chương 9. LƯỚI NGỮ NGHĨA VÀ HỆ KHUNG .174


9.1. Ngôn ngữ mô tả khái niệm .174


9.2. Lưới ngữ nghĩa .176


9.3. Khung .181


Chương 10. TRI THỨC KHÔNG CHẮC CHẮN 186


10.1. Không chắc chắn và biểu diễn 187


10.2. Một số khái niệm cơ bản của lý thuyết xác suất .189


10.3. Mạng xác suất .197


10.3.1. Định nghĩa mạng xác suất 198


10.3.2. Vấn đề lập luận trong mạng xác suất .200


10.3.3. Khả năng biểu diễn của mạng xác suất 201


10.3.4. Sự độc lập của các biến trong mạng xác suất .204


10.4. Suy diễn trong mạng có cấu trúc cây 205


10.5. Mạng kết nối đơn 212


10.6. Suy diễn trong mạng đa kết nối 220


10.6.1. Suy diễn trong mạng đa kết nối 220




10.6.2. Biến đổi mạng đa kết nối thành mạng kết nối đơn .221


10.6.3. Phương pháp mô phỏng ngẫu nhiên .223


10.7. Lý thuyết quyết định .228


Chương 11. LOGIC MỜ VÀ LẬP LUẬN XẤP XỈ .234


11.1. Tập mờ 235


11.1.1. Khái niệm tập mờ .235


11.1.2. Một số khái niệm cơ bản liên quan đến tập mờ .239


11.1.3. Tính mờ và tính ngẫu nhiên .242


11.1.4. Xác định các hàm thuộc .243


11.2. Các phép toán trên tập mờ 248


11.2.1. Các phép toán chuẩn trên tập mờ .248


11.2.2. Các phép toán khác trên tập mờ .250


11.3. Quan hệ mờ và nguyên lý mở rộng 255


11.3.1. Quan hệ mờ 255


11.3.2. Hợp thành của các quan hệ mờ 256


11.3.3. Nguyên lý mở rộng .258


11.4. Logic mờ .259


11.4.1. Biến ngôn ngữ và mệnh đề mờ 259


11.4.2. Các mệnh đề hợp thành 262


11.4.3. Kéo theo mờ - Luật if-then mờ .264


11.4.4. Luật Modulus – Ponens tổng quát 267


11.5. Hệ mờ .270


11.5.1. Kiến trúc của hệ mờ .271


11.5.2. Cơ sở luật mờ .272


11.5.3. Bộ suy diễn mờ .273


11.5.4. Mờ hoá .275


11.5.5. Khử mờ .277


11.5.6. Hệ mờ là hệ tính xấp xỉ vạn năng .278


TÀI LIỆU THAM KHẢO 279





LỜI NÓI ĐẦU





Trí tuệ nhân tạo (TTNT) là một lĩnh vực của khoa học máy tính, nghiên cứu sự thiết kế của các tác nhân thông minh ( “Computational intelligence is the studi of the degn of intelligens”). Các áp dụng của TTNT rất đa dạng và phong phú, hiện nay đã có nhiều hệ thông minh ra đời: các hệ chuyên gia, các hệ điều khiển tự động, các robot, các hệ dịch tự động các ngôn ngữ tự nhiên , các hệ nhận dạng, các chương trình chưi cờ, Kỹ thuật của TTNT đã được sử dụng trong việc xây dựng các hệ mềm, nhằm tạo ra các hệ mềm mang yếu tố thông minh, linh hoạt và tiện dụng. Ở nước ta, trong những năm gần đây, TTNT đã được đưa vào chương trình giảng dạy cho sinh viên các năm cuối ngành Tin học và Công nghệ thông tin. Cuốn sách này được hình thành trên cơ sở giáo trình TTNT mà chúng tôi đã giảng dạy cho sinh viên và các lớp cao học ngành Tin học và ngành Công nghệ thông tin trong các năm học từ 1997 tới nay, tại khoa Công nghệ thông tin, Đại học Khoa học tự nhiên, nay là khoa Công nghệ, Đại học Quốc gia Hà nội.


Cuốn sách này được viết như một cuốn nhập môn về TTNT, đối tượng phục vụ chủ yếu của nó là sinh viên các ngành Tin học và Công nghệ thông tin. Nội dung cuốn sách gồm hai phần:


Phần 1: Giải quyết vấn đề bằng tìm kiếm. Trong phần này, chúng tôi trình bày các phương pháp biểu diễn các vấn đề và các kỹ thuật tìm kiếm. các kỹ thuật tìm kiếm, đặc biệt là tìm kiếm kinh nghiệm ( heuristic serch), được sử dụng thường xuyên trong nhiều lĩnh vực nghiên cứu của TTNT.


Phần 2: Biểu diễn tri thức và lập luận. Phần này đề cập đến các ngôn ngữ biểu diễn tri thức, đặc biệt là các logic và các phương pháp luận trong mỗi ngôn ngữ biểu diễn tri thức. Các kỹ thuật biểu diễn tri thức và lập luận đóng vai trò quan trọng trong việc thiết kế các hệ thông minh.


Tuy nhiên với mong muốn cuốn sách này có thể dùng làm tài liệu tham khảo cho một phạm vi rộng rãi các đọc giả, chúng tôi cố gắng trình bày một cách hệ thống các khái niệm và các kỹ thuật cơ bản của TTNT, nhằm giúp cho đọc giả có cơ sở để đi vàonghiên cứu các lĩnh vực chuyên sâu của TTNT, chẳng hạn như lập kế hoạch (planning),học máy(machine learning),




nhìn máy (computer viison), hiểu ngôn ngữ tự nhiên (natural language understanding).


Hai ngôn ngữ thao tác ký hiệu được sử dụng nhiều trong lập trình TTNT là Lisp và Prolog. Trong các sách viết về TTNT các năm gần đây, một số tác giả, chẳng hạn trong 5 và [7] , đã sử dụng common Lisp để mô tả thuật toán. Trong 20, các tác giả lại sử dụng Prolog để biểu diễn thuật toán. Ở nước ta, các ngôn ngữ Lisp và Prolog được ít người biết đến, vì vậy chúng tôi biểu diễn các thuật toán trong sách này theo cách truyền thống. Tức là chúng tôi sử dụng các cấu trúc điều khiển ( tuần tự, điều kiện, lặp) mà mọi người quen biết. Đặc biệt, chúng tôi sử dụng cấu trúc loop do <dãy câu> để biểu diễn rằng, <dãy câu> được thực hiện lặp. Toán tử exit để thoát khỏi vòng lặp, còn toán tử stop đẻ dừng sự thực hiện thuật toán, các bạn có thể lựa chọn một trong các ngôn ngữ sau để sử dụng: Common Lisp, Scheme, Prolog, Smalltalk, C** hoặc ML (xem [28]).


Chúng tôi xin chân thành cảm ơn giáo sư Nguyễn Văn Hiệu, chủ nhiệm khoa Công nghệ, Đại học Quốc gia Hà nội đã tạo điều kiện thuận lợi cho chúng tôi viết cuốn sách này.


Cuốn sách chắc chắn không tránh khỏi những thiếu sót. Chúng tôi mong nhận được sự góp ý của độc giả. Thư góp ý xin gửi về Bộ môn Khoa Học Máy Tính, Khoa Công Nghệ, Đại Học Quốc Gia Hà Nội.




Tác giả