tailieunhanh - Giáo trình Trí tuệ nhân tạo (Artificial Intelligence): Phần 2

Phần 2 Giáo trình Trí tuệ nhân tạo (Artificial Intelligence) gồm các chương: Chương 5 – Các phương pháp tìm kiếm lời giải thỏa mãn các ràng buộc, chương 6 – Các phương pháp lập luận trên logic mệnh đề, chương 7 – Các phương pháp lập luận trên logic cấp một, chương 8 – Prolog, chương 9 – Lập luận với tri thức không chắc chắn, chương 10 – Học mạng nơron nhân tạo. | Chương 5 - Các phương pháp tìm kiếm lời giải thỏa mãn các ràng buộc 1. Các bài toán thỏa mãn các ràng buộc a. Bài toán 8 quân hậu Hãy đặt trên bàn cờ 8 quân hậu sao cho không có hai quân hậu nào cùng hang hoặc cùng cột hoặc cùng đường chéo. Bài toán 8 quân hậu có thể biểu diễn bởi 5 thành phần như sau - Trạng thái mảng một chiều 8 phần tử HAU 0 1 . . 7 phần tử HAU i biểu diễn dòng đặt con hậu cột i. Ví dụ HAU i j có nghĩa là con hậu cột I đặt ở dòng j. - Trạng thái đầu Một mảng ngẫu nhiên 8 phần tử mỗi phần tử nhận giá trị từ 0 đến 7 - Trạng thái đích Gán các giá trị khác nhau phạm vi từ 0 đến 7 cho các phần tử của mảng sao cho i-HAU i j-HAU j không nằm trên cùng đường chéo phụ và i HAU i j HAU j không nằm trên cùng đường chéo chính . - Chi phí không xác định Trong bài toán này trạng thái đích là không tường minh mà được xác định bởi tập các ràng buộc. Khác với các bài toán trước lời giải của bài toán này không phải là đường đi từ trạng thái đầu đến trạng thái đích mà là một phép gán các giá trị cho các biến mô tả trong trạng thái của bài toán sao cho phép gán thỏa mãn các ràng buộc của trạng thái đích. Để giải các bài toán thỏa mãn các ràng buộc chúng ta không cần xác định 5 thành phần như các bài toán trong các chương trước mà chúng ta cần quan tâm đến các thành phần sau - Tập các biến mô tả trạng thái của bài toán HAU 0 HAU 1 . HAU 7 trong bài toán 8 quân hậu HAU i là số hiệu dòng đặt con hậu ở cột I ví dụ HAU 0 0 có nghĩa là con hậu cột đầu tiên cột 0 sẽ đặt ở dòng đầu tiên dòng 0 . - Miền giá trị cho các biến HAU i c 0 1 2 3 4 5 6 7 - Tập ràng buộc với j thì HAU i HAU j không có hai con hậu cùng hàng ngang i-HAU i J-HAU j không có hai con hậu nào cùng đường chéo phụ i HAU i J HAU j không có hai con hậu nào cùng đường chéo chính Lời giải của bài toán là một phép gán giá trị trong miền giá trị cho các biến sao cho thỏa mãn các ràng buộc của bài toán. b. Bài toán tô màu đồ thị Sử dụng ba màu để tô bản đồ các tỉnh của một nước sao cho các tỉnh kề nhau thì có .