Chương 1. Giới thiệu: trình bày tổng quan về AI, lịch sử ra đời và phát triển và các lính vực ứng dụng của AI. Các phương pháp tìm kiếm lời giải: trình bày các kỹ thuật tìm kiếm cơ bản được áp dụng để giải quyết các vấn đề và được áp dụng rộng rãi trong các lĩnh vực của trí tuệ nhân tạo. Các giải thuật tìm kiếm lời giải cho trò chơi: trình bày một số kỹ thuật tìm kiếm trong các trò chơi có đối thủ.
Các phương pháp lập luận trên logic mệnh đề: trình bày cú pháp, ngữ nghĩa của logic mệnh đề và một số thuật toán lập luận trên logic mệnh đề. Các phương pháp lập luận trên logic vị từ cấp một: trình bày cú pháp, ngữ nghĩa của logic vị từ cấp một và một số thuật toán lập luận cơ bản trên logic vị từ cấp một. Prolog: Giới thiệu chung về ngôn ngữ Prolog, cú pháp, ngữ nghĩa và cấu trúc chương trình trong Prolog, một số phiên bản mới của Prolog như SWI Prolog,… Chương 7. Lập luận với tri thức không chắc chắn: Giới thiệu về tri thức không chắc chắn và một số cách tiếp cận biểu diễn và xử lý tri thức không chắc chắn.
Học mạng noron nhân tạo: Giới thiệu về phương pháp và các kỹ thuật cơ bản trong lập luận sử dụng mạng noron nhân tạo. Chương 2 – Bài toán và phương pháp tìm kiếm lời giải 1. Bài toán và các thành phần của bài toán Chương này giới thiệu các giải thuật máy tính có thể giải các bài toán mà thông thường đòi hỏi trí thông minh của con người, như bài toán đong nước, bài toán 8 sô trên bàn cờ, bài toán tìm đường như mô tả bên dưới đây. Để thiết kế giải thuật chung giải các bài toán này, chúng ta nên phát biểu bài toán theo dạng 5 thành phần: Trạng thái bài toán, trạng thái đầu, trạng thái đích, các phép chuyển trạng thái, lược đồ chi phí các phép chuyển trạng thái (viết gọn là chi phí).
Bài toán đong nước 9l 3l 5l Sử dụng ba can 3 lít, 5 lít và 9 lít, làm thế nào để đong được 7 lít nước. Bài toán này được phát biểu lại theo 5 thành phần như sau: - Trạng thái: Gọi số nước có trong 3 can lần lượt là a, b, c (a ≤ 3, b ≤ 5, c ≤ 9), khi đó bộ ba (a, b, c) là trạng thái của bài toán - Trạng thái đầu: (0, 0, 0) // cả ba can đều rỗng - Trạng thái đích (-, -, 7) // can thứ 3 chứa 7 lít nước - Phép chuyển trạng thái: từ trạng thái (a,b,c) có thể chuyển sang trạng thái (x,y,z) thông qua các thao tác như làm rỗng 1 can, chuyển từ can này sang can kia đến khi hết nước ở can nguồn hoặc can đích bị đầy. - Chi phí mỗi phép chuyển trạng thái: mỗi phép chuyển trạng thái có chi phí là 1. Một lời giải của bài toán là một dãy các phép chuyển trạng thái (đường đi) từ trạng thái đầu đến trạng thái đích.
Bảng dưới đây là 2 lời giải của bài toán trên: a b c Đầu a b c 0 0 0 0 0 0 3 0 0 0 5 0 0 0 3 3 2 0 3 0 3 3 0 2 0 0 6 3 5 2 3 0 6 Đích 3 0 7 0 3 6 Lời giải 2 (chi phí: 5) 3 3 6 1 5 6 0 5 7 Đích Lời giải 1 (chi phí: 9) b. Bài toán di chuyển 8 số trên bàn cờ Trạng thái đầu Trạng thái đích Cho bàn cờ kích thước 3 x 3, trên bàn cờ có 8 quân cờ đánh số từ 1 đến 8 (hình vẽ). Trên bàn cờ có một ô trống. Chúng ta có thể chuyển một quân cờ có chung cạnh với ô trống sang ô trống.
Hãy tìm dãy các phép chuyển để từ trạng thái ban đầu về trạng thái mà các quan cờ được xếp theo trật tự như Trạng thái đích của hình trên. Bài toán di chuyển 8 số trên bàn cờ có thể phát biểu dưới dạng 5 thành phần như sau: - Biểu diễn trạng thái: mảng 2 chiều kích thước 3x3, phần tử của mảng lưu số hiệu quân cờ (từ 0 đến 9, 0 là vị trí trống). Cũng có thể biểu diễn trạng thái bàn cờ bằng mảng một chiều gồm 9 phần tử: ba phần tử đầu tiên biểu diễn các ô thuộc dòng đầu tiên của bàn cờ, ba phần tử tiếp biểu diễn các quân cờ thuộc dòng thứ hai, ba phần tử cuối cùng biểu diễn các quân cờ thuộc dòng cuối cùng. Ở đây chúng tôi sử dụng mảng hai chiều 3x3 để cho giống với bàn cờ trên thực tế.
- Trạng thái đầu (hình vẽ trên) - Trạng thái đích (hình vẽ trên) - Phép chuyển trạng thái: đổi chỗ ô có số hiệu 0 với một trong các ô có cùng cạnh. - Chi phí: mỗi phép chuyển có chi phí 1. Lời giải của bài toán là dãy các phép chuyển từ trạng thái đầu đến trạng thái đích. Một lời giải của bài toán là: UP, UP, RIGHT, DOWN, LEFT, UP, RIGHT, RIGHT, DOWN, LEFT, LEFT, UP, RIGHT, DOWN, RIGHT, DOWN (chú ý: up, down, right, left là biểu diễn sự dịch chuyển ô trống lên trên, xuống dưới, sang phải, sang trái) c.
Bài toán tìm đường đi Một ôtô robot tìm đường đi từ thành phố Arad đến thành phố Bucharest. Biết rằng xe robot này không có bản đồ đầy đủ như trên hình vẽ trên, nhưng khi nó đến một thành phố mới, nó có bộ cảm biến đọc được biển chỉ đường đến các thành lân cận, trên biển chỉ đường có khoảng cách. Bài toán tìm đường có thể phát biểu theo 5 thành phần như sau: - Trạng thái: vị trí của ôtô robot (tên thành phố) - Trạng thái đầu: Thành phố Arad - Trạng thái đích: Thành phố Bucharest - Phép chuyển trạng thái: từ thành phố sang thành phố lân cận - Chi phí: khoảng cách giữa 2 thành phố trong phép chuyển trạng thái Lời giải của bài toán là dãy các phép chuyển từ trạng thái đầu đến trạng thái đích, hay là đường đi từ thành phố đầu đến thành phố đích. Một ví dụ của lời giải bài toán là: Arad Sibiu Fagaras Bucharest.
Giải thuật tổng quát tìm kiếm lời giải a. Không gian trạng thái của bài toán Mỗi bài toán với 5 thành phần như mô tả ở trên, chúng ta có thể xây dựng được một cấu trúc đồ thị với các nút là các trạng thái của bài toán, các cung là phép chuyển trạng thái. Đồ thị này được gọi là không gian trạng thái của bài toán. Không gian trạng thái có thể là vô hạn hoặc hữu hạn.
Ví dụ, với bài toán di chuyển 8 số trên bàn cờ, không gian trạng thái có số lượng là 8! (8 giai thừa) trạng thái. Lời giải của bài toán là một đường đi trong không gian trạng thái có điểm đầu là trạng thái đầu và điểm cuối là trạng thái đích. Nếu không gian trạng thái của bài toán là nhỏ, có thể liệt kê và lưu vừa trong bộ nhớ của máy tính thì việc tìm đường đi trong không gian trạng thái có thể áp dụng các thuật toán tìm đường đi trong lý thuyết đồ thị. Tuy nhiên, trong rất nhiều trường hợp, không gian trạng thái của bài toán là rất lớn, việc duyệt toàn bộ không gian trạng thái là không thể.
Trong môn học Trí tuệ nhân tạo này, chúng ta sẽ tìm hiểu các phương pháp tìm kiếm lời giải trong các bài toán có không gian trạng thái lớn. Giải thuật tổng quát tìm kiếm lời giải của bài toán Với các bài toán có 5 thành phần ở trên, chúng ta có giải thuật chung để tìm kiếm lời giải của bài toán. Ý tưởng là sinh ra các lời giải tiềm năng và kiểm tra chúng có phải là lời giải thực sự của bài toán. Một lời giải tiềm năng là một đường đi trong không gian trạng thái của bài toán có nút đầu là trạng thái đầu và mỗi cung của đường đi là một phép chuyển hợp lệ giữa các trạng thái kề với cung đó.
Lời giải thực sự của bài toán là lời giải tiềm năng có nút cuối cùng là trạng thái đích. Các lời giải tiềm năng là các đường đi có cùng nút đầu tiên và dãy các cung là dãy các phép chuyển hợp lệ từ trạng thái đầu đó. Các lời giải tiềm năng có thể tổ chức theo cây, gốc của cây là trạng thái đầu, cây được phát triển bằng cách bổ sung vào các nút liền kề với trạng thái đầu, sau đó liên tiếp bổ sung vào các con của các nút lá, … Lược đồ chung để tìm lời giải của bài toán 4 thành phần trên là xây dựng cây lời giải tiểm năng (hay là cây tìm kiếm) và kiểm tra lời giải tiềm năng có là lời giải thực sự của bài toán hay không. Các bước của giải thuật chung là như sau: xây dựng cây tìm kiếm mà nút gốc là trạng thái đầu, lặp lại 2 bước: kiểm tra xem trạng thái đang xét có là trạng thái đích không, nếu là trạng thái đích thì thông báo lời giải, nếu không thì mở rộng cây tìm kiếm bằng cách bổ sung các nút con là các trạng thái láng giềng của trạng thái đang xét.
Giải thuật chung được trình bày trong bảng sau: Đầu vào của giải thuật là bài toán (problem) với 5 thành phần (biểu diễn trạng thái tổng quát, trạng thái đầu, trạng thái đích, phép chuyển trạng thái, chi phí phép chuyển trạng thái) và một chiến lược tìm kiếm (strategy); đầu ra của giải thuật là một lời giải của bài toán hoặc giá trị failure nếu bài toán không có lời giải. Giải thuật sinh ra cây các lời giải tiềm năng, nút gốc là trạng thái đầu của bài toán, mở rộng cây theo chiến lược (strategy) đã định trước đến khi cây chứa nút trạng thái đích hoặc không thể mở rộng cây được nữa. Function General_Search(problem, strategy) returns a solution, or failure cây-tìm-kiếm trạng-thái-đầu; while (1) { if (cây-tìm-kiếm không thể mở rộng được nữa) then return failure nút-lá Chọn-1-nút-lá(cây-tìm-kiếm, strategy) if (node-lá là trạng-thái-đích) then return Đường-đi(trạng-thái-đầu, nút- lá) else mở-rộng(cây-tìm-kiếm, các-trạng-thái-kề(nút-lá)) } Trong giải thuật chung này, chiến lược tìm kiếm (strategy) sẽ quyết định việc chọn nút lá nào trong số nút lá của cây để mở rộng cây tìm kiếm, ví dụ như nút lá nào xuất hiện trong cây sớm hơn thì được chọn trước để phát triển cây (đây là chiến lược tìm kiếm theo chiều rộng), hoặc nút lá nào xuất hiện sau thì được chọn để mở rộng cây (đây là chiến lược tìm kiếm theo chiều sâu). Chiến lược tìm kiếm có thể được cài đặt thông qua một cấu trúc dữ liệu để đưa vào và lấy ra trạng thái lá của cây tìm kiếm.
Hai cấu trúc dữ liệu cơ bản là hàng đợi và ngăn xếp.