Bài giảng Trí tuệ nhân tạo (Bản đẹp)

Mục lục 
CHƯƠNG 1 MỞ ĐẦU 1 
1. Hệ thống thông minh 1 
1.1. Kiểm soát tình huống và lựa chọn 1 
1.2. Học 2 
1.3. Sử dụng tri thức 2 
2. Giới thiệu trí tuệ nhân tạo 3 
2.1. Một số ví dụ 3 
2.2. Khái niệm 6 
2.3. Hệ cơ sở tri thức 7 
3. Một số bài toán 8 
CHƯƠNG 2 GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM 13 
1. Khái niệm 13 
1.1. Không gian trạng thái 13 
1.2. Tìm kiếm trên không gian trạng thái 15 
2. Các nguyên lý tìm kiếm 17 
2.1. Các nguyên lý cơ bản 17 
2.2. Các nguyên lý thử sai 18 
2.3. Các nguyên lý heuristic 19 
2.4. Cài đặt các nguyên lý 22 
3. Aùp dụng 23 
3.1. Cài đặt thuật giải 23 
3.2. Giải quyết vấn đề 25 
CHƯƠNG 3 TÌM KIẾM VỚI HEURISTIC 29 
1. Khái niệm 29 
2. Thuật giải A* 31 
3. Thuật giải A0* 34 
3.1. Tìm kiếm trên cây AND/OR 35 
3.2. Thêm heuristic - Thuật giải AO* 38 
CHƯƠNG 4 TRÒ CHƠI ĐỐI KHÁNG VÀ PHƯƠNG PHÁP GPS 43 
1. Trò chơi đối kháng 43 
1.1. Khái niệm 43 
1.2. Thuật giải 44 
1.3. Bàn thêm về heuristic 49 
2. Phương pháp giải quyết vấn đề tổng quát (GPS) 50 
2.1. Khái niệm 50 
2.2. Thuật giải 51 
CHƯƠNG 5 SUY LUẬN LOGIC 63 
1. Suy luận 63 
2. Suy luận với logic mệnh đề 64 
2.1. Khái niệm 64 
2.2. Một số cơ chế phát sinh sự kiện (quy tắc suy diễn) 65 
2.3. Suy luận 67 
3. Suy luận với logic cấp 1 71 
3.1. Khái niệm 71 
3.2. Suy luận 72 
CHƯƠNG 6 SUY LUẬN VỚI THÔNG TIN KHÔNG CHẮC CHẮN 79 
1. Phân bố xác suất 79 
1.1. Khái niệm 79 
1.2. Suy luận 81 
2. Suy luận xấp xỉ 83 
2.1. Khái niệm 83 
2.2. Suy luận 85 
3. Giới thiệu một số suy luận khác 87 
3.1. Phân bố khả xuất 87 
3.2. Logic mờ 88 
CHƯƠNG 7 BIỂU DIỄN TRI THỨC 97 
1. Tri thức 97 
1.1. Khái niệm 97 
1.2. Biểu diễn tri thức 99 
2. Biểu diễn bằng logic vị từ 100 
2.1. Biểu diễn các tri thức đơn giản 100 
2.2. Biểu diễn mối quan hệ Instance và isa 101 
2.3. Suy diễn bằng hợp giải (resolution) 101 
3. Biểu diễn bằng luật sản xuất 103 
3.1. Khái niệm 103 
3.2. Biểu diễn 105 
3.3. Suy diễn 105 
3.4. Bàn thêm 106 
4. Lập trình logic 107 
4.1. Các thành phần 107 
4.2. Sự kiện và luật 107 
4.3. Hợp giải và prolog 108 
4.4. Một số ví dụ 109 
CHƯƠNG 8 CÁC BIỂU DIỄN CÓ CẤU TRÚC 117 
1. Mạng ngữ nghĩa 117 
1.1. Khái niệm 117 
1.2. Biểu diễn 118 
1.3. Suy diễn 120 
1.4. Đồ thị khái niệm 121 
1.5. Chuyển về logic vị từ 123 
1.6. Một ví dụ phức tạp 124 
2. Giới thiệu một số biểu diễn khác 127 
2.1. Biểu diễn bằng khung (Frames) 127 
2.2. Biểu diễn tri thức bằng bộ ba OAV 128 
2.3. Bộ nhớ kết hợp (biểu diễn tri thức mô phỏng hệ thần kinh) 129 
CHƯƠNG 9 THU NẠP TRI THỨC 135 
1. Mở đầu 135 
2. Tổng quan về thu nhận tri thức 136 
2.1. Khái niệm 136 
1.1. Các cách tiếp cận 138 
3. Phương pháp cây quyết định 139 
3.1. Khái niệm 139 
3.2. Tiếp cận cực tiểu Entropy trung bình 139 
4. Phương pháp không gian thế hệ 141 
4.1. Khái niệm 141 
4.2. Thuật toán 141 
5. Phương pháp xây dựng một giải thích 144 
5.1. Khái niệm 144 
5.2. Thuật toán 144 
CHƯƠNG 10 MỘT SỐ CHỦ ĐỀ 151 
1. Mạng neuron nhân tạo 151 
1.1. Khái niệm 151 
1.2. Giới thiệu một số luật học 154 
2. Thuật toán di truyền 158 
2.1. Khái niệm 158 
2.2. Mô hình và Thuật toán 158 
3. Xử lý ràng buộc 161 
3.1. Khái niệm 161 
3.2. Thuật giải 164 
4. Máy vector hỗ trợ (Supported Vector Machine - SVM) 167 
4.1. Khái niệm 167 
4.2. Thuật toán 167 
4.3. Tách phi tuyến 168 
PHỤ LỤC 2 NGÔN NGỮ PROLOG 175 
1. Giới thiệu prolog 175 
1.1. Các thành phần của chương trình 175 
1.2. Sự kiện và luật 175 
1.3. Quan hệ 176 
1.4. Các kiểu đối tượng 177 
1.5. Cơ chế tìm kiếm 180 
1.6. Vài ví dụ lập trình prolog 182 
2. Thảo luận 185 
2.1. Biểu diễn cây 185 
2.2. Dùng đại số quan hệ 188 
PHỤ LỤC 3 NGHIÊN CỨU TÌNH HUỐNG 191 
1. Thiết kế hướng đối tượng dùng C++ 191 
1.1. Một thiết kế đơn giản 191 
1.2. Một thiết kế tổng quát 194 
2. Cài đặt thuật toán A* bằng prolog 201 
3. Xây dựng hệ chuyên gia đơn giản bằng prolog 203 
3.1. Cơ sở tri thức 203 
3.2. Cài đặt bằng prolog 203 
4. Xây dựng một cơ chế thu nhận tri thức 205 
4.1. Cơ sở tri thức 205 
4.2. Minh họa cơ chế học 206 
5. Đối sánh 208 
5.1. Khái niệm 208 
5.2. Đối sánh biểu thức 208 
Lời nói đầu 
Ngày nay, hầu hết các lĩnh vực đều có sự tham gia của máy tính. Trong 
một số lĩnh vực, vai trò của máy tính là rất quan trọng. Thế nhưng, vẫn 
còn đó nhiều công việc, dù giản đơn, dù nguy hiểm, dù nhàm chán, con 
người vẫn cứ phải đảm nhiệm. 
Liệu có thể xây dựng những hệ có khả năng hành động như con người, suy 
nghĩ như con người. Những hệ như vậy sẽ làm thay con người nhiều việc, 
cũng như hỗ trợ con người một cách hiệu quả; để con người tập trung vào 
những hoạt động mang tính sáng tạo. 
Trí tuệ nhân tạo (AI – Artificial Intelligence) là một nhánh của công nghệ 
thông tin nghiên cứu các phương pháp xây dựng trí tuệ cho máy. Tài liệu 
này giới thiệu cho sinh viên những khía cạnh cơ sở quan trọng của AI. Tài 
liệu gồm 10 chương được chia làm 4 phần chính. Chương 1 giới thiệu về AI. 
Phần 1, gồm các chương 2, 3 và 4, giới thiệu các phương pháp giải quyết 
vấn đề. Phần 2, gồm các chương 5 và 6, giới thiệu các phương pháp suy 
luận, các phương pháp xử lý thông tin không chắc chắn. Phần 3, gồm các 
chương 7, 8 và 9, giới thiệu các phương pháp biểu diễn và thu nhận tri 
thức. Phần 4, gồm chương 10 và hai phụ lục, giới thiệu một số chủ đề như 
mạng neuron nhân tạo, thuật toán di truyền, xử lý ràng buộc; cũng giới 
thiệu về prolog và thử giải quyết một số tình huống. 
Dù rất cố gắng, tài liệu được viết ra không khỏi có thiếu sót. Rất mong sự 
góp ý của bạn đọc để lần tái bản sau được tốt hơn. 
Nhân dịp này tôi xin chân thành cảm ơn Ban chủ nhiệm khoa Công nghệ 
thông tin trường Đại học Kỹ thuật Công nghệ đã tạo điều kiện cho tôi 
hoàn thành tài liệu này. 
Mọi ý kiến đóng góp xin gởi về hvduc@hcm.vnn.vn. Xin chân thành cảm 
ơn. 
 TpHCM, Tháng 07/2006 
 Tác giả 
Chương 1 
Mở đầu 
Mục tiêu của AI là xây dựng những hệ thống suy nghĩ và hành động như 
con người. Khi ấy hệ thống sẽ được gọi là thông minh. Nó phải có khả 
năng giải quyết vấn đề như con người khi đứng trước những tình huống 
tương tự. 
1. Hệ thống thông minh 
1.1. Kiểm soát tình huống và lựa chọn 
Xét hệ giải phương trình bậc hai. Yêu cầu hệ giải những phương trình sau: 
1) x2 – 3x – 4 = 0 
2) x2 – 4x + 3 = 0 
3) x2 – 4x + 4 = 0 
4) x2 – 4 = 0 
5) x2 + 1 = 0 
6) x2 – 4x + 5 = 0 
Trường hợp 1 
Với hệ luôn luôn tính theo một thủ tục cho trước, chẳng hạn với phương 
trình thứ 1: 
Tính Δ = 25 
Suy ra x1 = -1, x2 = 4 
Ta không thể cho rằng hệ là thông minh. 
Trường hợp 2 
Với hệ có những trả lời bất ngờ, chẳng hạn với 
Phương trình thứ 1: Vì a – b + c = 0, ta có x1 = -1 và x2 = -c/a = 4; 
Phương trình thứ 2: Vì a + b + c = 0, ta có x1 = 1 và x2 = c/a = 3; 
Phương trình thứ 3: Biến đổi thành (x – 2)2 = 0, ta có x1 = x2 = 2; 
Phương trình thứ 4: Biến đổi thành (x – 2)(x + 2) = 0, ta có x1= 2, x2 
= -2 
Phương trình thứ 5: Vì x2 + 1 > 0, phương trình vô nghiệm; 
Phương trình thứ 6: Vì Δ = -4<0, phương trình vô nghiệm. 
Và ta có thể cho rằng hệ là thông minh. 
1.2. Học 
Xét một trò chương trình chơi cờ vua đơn giản. Với những ván cờ đầu tiên, 
chúng ta thua nó và ta nghĩ nó là thông minh. Cho đến khi ta tìm được 
một cách thắng và phát hiện thấy dù thua, nó vẫn cứ thực hiện những 
nước đi cũ. Thế là ta thất vọng, vì nó chơi quá máy móc, chương trình 
chẳng còn tí gì là thông minh. Nếu như nó có khả năng rút ra kinh 
nghiệm từ những ván cờ thua thì lại khác. Tức hệ đã có khả năng học. 
Trở lại hệ giải phương trình bậc hai. Ta lại yêu cầu hệ giải phương trình 
x2 – x + 6 = 0 
Ta chờ đợi hệ giải như sau: 
Tìm thấy x = 3 là nghiệm, suy ra x1 = 3, x2 = -2. 
Tuy nhiên hệ không biết cách giải này. Ta sẽ dạy hệ tri thức sau: thử xem 
x có là nghiệm với x = -3, -2, -1, 0, 1, 2, 3. Rồi yêu cầu hệ giải lại. Và hệ 
giải như sau: 
Tìm thấy x = -2 là nghiệm, suy ra x1 = -2, x2 = 3. 
Bây giờ yêu cầu hệ giải phương trình 1 ở trên 
x2 – 3x – 4 = 0 
Có khả năng hệ sẽ giải khác với cách giải cũ 
Tìm thấy x = -1 là nghiệm, suy ra x1 = -1, x2 = 4. 
1.3. Sử dụng tri thức 
Tiếp tục với hệ giải phương trình bậc hai. Bây giờ chúng ta yêu cầu hệ giải 
một phương trình bậc ba 
x3 – 2x2 – x + 2 = 0 
Có thể hệ không giải được. Tuy nhiên giả sử hệ có tri thức: nếu a là một 
nghiệm của phương trình f(x) = 0 thì nghiệm của nó gồm a và các nghiệm 
của phương trình g(x) = 0, trong đó f(x) = (x – a)g(x). 
Bây giờ ta cung cấp cho hệ một nghiệm x = 1. Lúc này hệ có thể giải như 
sau: 
Vì 1 là nghiệm, biến đổi x3 – 2x2 – x + 2 = (x – 1)(x2 – x – 2) 
Phương trình x2 – x – 2 = 0 có a – b + c = 0 nên có hai nghiệm là 1 
và 2 
Vậy phương trình có 3 nghiệm: x1 = -1, x2 = 1, x3 = 2 
Muốn sử dụng được tri thức chương trình phải có khả năng nhận biết các 
sự kiện, các mối liên hệ và suy luận. Rõ ràng một hệ giải phương trình bậc 
hai như vậy xứng đáng được gọi là thông minh. 
2. Giới thiệu trí tuệ nhân tạo 
2.1. Một số ví dụ 
Ví dụ 1.1 
Tìm đường đi ngắn nhất từ N đến L với bảng dữ liệu được cho như sau 
N → C 10 N → D 19 T → C 5 H → L 15 
C → D 10 T → G 15 D → U 10 D → L 10 
N → T 8 T → L 18 D → H 15 
• Ta thấy từ đỉnh N có thể đi đến đỉnh C, T hoặc D. 
Nên chọn đỉnh nào? lý do? Có khả năng thu được đường đi tối ưu 
không? 
Giả sử ta chọn đỉnh C, và từ C có thể đi đến đỉnh D. 
• Có nên đi tiếp và chọn D hay quay lui để chọn T hoặc D? 
• Dù ta có chọn phương án nào đi nữa thì cũng phải giải thích được là vì 
sao? 
• Rõ ràng ta cần một chiến lược lựa chọn mà ta gọi là suy diễn. Chẳng 
hạn nếu suy diễn theo hướng ưu tiên khoảng cách ngắn nhất (toàn cục 
trên tất cả các nhánh) thì đường đi tìm thấy sẽ là N→ T→ L. Còn nếu 
suy diễn tham lam (cục bộ tại đỉnh chọn) thì đường đi tìm thấy sẽ là 
N→ C→ D→ L 
Ví dụ 1.2 
Chứng minh mệnh đề (⎤ a+⎤ b+c) ( ⎤ b+⎤ c+d) a b → d. 
Nếu cách giải quyết là tương tự như ở ví dụ 1 thì cái gì đóng vai trò đỉnh? 
Hơn nữa từ đỉnh hiện hành ta có thể đi đến các đỉnh nào? Làm sao phát 
sinh ra các đỉnh mới? 
Thử áp dụng phương pháp chứng minh phản chứng cho ví dụ này. Thay vì 
chứng minh α → β ta đi chứng minh α ⎤ β → 0. Như vậy mệnh đề trên là 
tương đương với 
(⎤ a+⎤ b+c) ( ⎤ b+⎤ c+d) a b⎤ d → 0. 
Khác với ví dụ 1, ở đây ta phải sử dụng tri thức. Với tri thức ( α + ⎤ β ) β → 
α, ta coi như là từ 2 đỉnh α + ⎤ β và β phát sinh ra đỉnh mới α. Như vậy 
đỉnh ở đây là biểu thức và luật dẫn là cơ chế phát sinh ra đỉnh mới. Bắt 
đầu suy diễn với các đỉnh (⎤ a+⎤ b+c), ( ⎤ b+⎤ c+d), a, b và ⎤ d. 
• Từ 2 đỉnh (⎤ a+⎤ b+c) và a sinh ra đỉnh ⎤ b+c 
• Rồi từ ⎤ b+⎤ c+d và b cho ta ⎤ c+d 
• Cứ như vậy cho đến đích (goal) cuối là đỉnh rỗng ∅. 
• Các đỉnh ở đây ta gọi là sự kiện. Các tri thức dùng để phát sinh đỉnh 
mới như ( α + ⎤ β ) β → α ta gọi là luật. Và một lần nữa, câu hỏi “chiến 
lược phát sinh là gì?” Lại được đặt ra. Trong tình huống này, nếu lựa 
chọn phương án phát sinh tất cả các đỉnh sau mỗi bước sẽ dễ dẫn đến 
tình trạng bùng nổ tổ hợp, là tình trạng mà chúng ta không hề mong 
muốn. Ta không chờ đợi một thuật toán giúp giải các bài toán như thế 
này mà chỉ hy vọng có thêm những tri thức giúp tránh tình trạng bùng 
nổ tồi tệ nói trên. Các tri thức như vậy được gọi là các heuristic. 
Ví dụ 1.3 
Trò chơi tic-tac-toe (giống trò chơi caro quen thuộc nhưng giới hạn trên 
bảng 3×3). Mỗi đối thủ có 3 quân, nhiệm vụ của họ là xếp cho 3 quân 
thẳng hàng đồng thời ngăn cản đối phương thực hiện nhiệm vụ. Trò chơi 
được chia làm 2 giai đoạn. Giai đoạn đặt quân giống với trò chơi caro, giai 
đoạn di chuyển quân chỉ được phép dịch chuyển quân sang ô trống lân cận 
(dùng lân cận 4). 
Trò chơi được bắt đầu với bảng rỗng 
• Người thứ 1 sẽ chọn nước đi nào trong số 3 nước đi sau để đặt quân? 
X X 
 X 
phải chăng nên suy diễn theo hướng ưu tiên số đường mở khả dĩ? Nếu 
vậy thì phương án cuối sẽ là phương án được chọn. Thật ra, ta biết là 
với các trò chơi loại này, người chơi cần phải tính sâu hơn trước khi có 
quyết định. 
• Quả vậy, những suy diễn ban đầu có thể không còn chính xác nữa khi 
người đi chịu khó đánh giá thêm các thế biến ở các mức sâu hơn. Ngoài 
ra, trong ví dụ này ta còn quan sát thấy sự kém tường minh của đích. 
Ví dụ 1.4 
Chứng minh biểu thức R(⎤ P → Q) = (Q+P)R bằng cách áp dụng các luật 
như giao hoán ab = ba, a+b=b+a; kết hợp (ab)c = a(bc), (a+b)+c = a+(b+c) 
v..v.. 
Làm cách nào có thể áp dụng một luật? Muốn áp dụng luật, chẳng hạn, 
a+b = b+a lên (Q+P)R trước tiên cần nhận diện (đối sánh) Q là a và P là b 
và thu được kết quả (P+Q)R. 
• Như vậy bằng cách đối sánh một bộ phận hoặc toàn thể các sự kiện ta 
tìm thấy các luật có thể áp dụng được. Áp dụng các luật này sẽ cho ta 
kết quả mới là các sự kiện được phát sinh. Quá trình suy diễn ở đây có 
thể đi theo hướng làm giảm dần sự khác biệt giữa kết quả tìm được và 
đích. 
2.2. Khái niệm 
(a) Trí tuệ nhân tạo là gì 
Các ví dụ nêu trên đưa ra cho chúng ta một số khái niệm mới, tạo tình 
huống dẫn chúng ta đi tìm hiểu một nhánh thú vị của khoa học máy tính 
đó là ngành trí tuệ nhân tạo. 
Những khái niệm mới được giới thiệu ở đây là: 
1 Tri thức; 
2 Heuristic; 
3 Luật; 
4 Sự kiện; 
5 Đối sánh; 
6 Suy diễn; 
7 Chương trình thông minh. 
Định nghĩa 1.1 
AI là một nhánh của khoa học máy tính nghiên cứu và tạo ra các chương 
trình thực hiện các công việc như người. 
Chương trình được tạo ra nhằm thực hiện các công việc như người, tức là 
thực hiệïn một cách thông minh: kiểm soát tình huống và lựa chọn. Nó thể 
hiện hành vi tương tự con người ... ->g+r->d)); 
 } 
 } 
 return 0; 
}; 
Tổ chức cây tìm kiếm 
class Node{ 
public: 
 City *c; 
 Node *father; 
 int g; 
 Node(City*,Node*,int d=0); 
}; 
Node::Node(City*ic,Node*f,int d){ 
 c = ic; 
 father = f; 
 g = d; 
} 
int operator<(const Node& a, const Node& b){ 
 return a.g<b.g; 
} 
struct myless: less{ 
 bool operator()(const Node*& x, const Node*& y) const { 
 return x->g>y->g; 
 } 
}; 
(c) Minh họa 
void main(){ 
 City v[8]={'n','c','t','d','u','h','l','g'}; 
 City::AddRoad(0,3,19); City::AddRoad(0,2,8); 
City::AddRoad(0,1,10); 
 City::AddRoad(1,3,10); 
 City::AddRoad(3,6,10); City::AddRoad(3,5,15); 
City::AddRoad(3,4,10); 
 City::AddRoad(5,6,15); 
 City::AddRoad(2,7,15); City::AddRoad(2,6,18); 
City::AddRoad(2,1,5); 
 //tìm đường đi từ n đến l 
 if (Solve(v[0],v[6])) 
 cout<<"success\n"; 
 else 
 cout<<"fail\n"; 
} 
1.2. Một thiết kế tổng quát 
(a) Cơ sở tri thức 
//Cơ sở tri thức 
class KB{ public: 
 virtual void *Start()=0; 
 virtual void *Goal()=0; 
 virtual void Bn(void*,Container &)=0; 
 virtual void Show(void*)=0; }; 
//Bản đồ là một cơ sở tri thức 
class Map: public KB{ 
 int n, m; 
 struct Road {int f; int t;}; 
 typedef char City; 
 char *Cities; 
 Road *Roads; 
 Road Set(int, int); 
 public: 
 Map(); 
 ~Map(); 
 virtual void *Start(); 
 virtual void *Goal(); 
 virtual void Bn(void*,Container &); 
 virtual void Show(void*); 
}; 
//Tháp Hà Nội cũng là một cơ sở tri thức 
class HNTower: public KB{ 
 int n; 
 struct State {int a, b, c;}; 
 WorkList sl; 
 void *MakeState(int, int, int); 
 public: 
 HNTower(int d = 2){n=d;} 
 ~HNTower(); 
 virtual void *Start(); 
 virtual void *Goal(); 
 virtual void Bn(void*,Container &); 
 virtual void Show(void*);}; 
(b) Mô tơ suy diễn 
class Engine{ 
 public: 
 virtual int Reasone(KB &)=0; 
 virtual void Report(KB *)=0; 
}; 
//Suy diễn tiến bằng cơ chế tìm kiếm. 
class Search: public Engine{ 
 struct Snote {void *State; Snote *Father;}; 
 void MakeNote(void*,Snote*); 
 WorkList open, close; 
 public: 
 ~Search(); 
 virtual int Reasone(KB &); 
 virtual void Report(KB*); 
}; 
(c) Hệ cơ sở tri thức 
//Hệ giải bài toán gồm một cơ sở tri thức và một mô tơ suy diễn. 
class GPSystem{ 
 protected: 
 KB *kb; 
 Engine *e; 
 public: 
 GPSystem(); 
 GPSystem(KB*,Engine*); 
 virtual Solve(); 
}; 
(d) Cài đặt 
Cơ sở tri thức bản đồ 
Map::Map() 
{ 
 n = 8; 
 m = 11; 
 Cities = new char[n+1]; 
 strcpy(Cities,"nctduhlg"); 
 Roads = new Road[m]; 
 Roads[0].f = 0; Roads[0].t = 3; 
 Roads[1].f = 0; Roads[1].t = 2; 
 Roads[2].f = 0; Roads[2].t = 1; 
 Roads[3].f = 1; Roads[3].t = 3; 
 Roads[4].f = 3; Roads[4].t = 6; 
 Roads[5].f = 3; Roads[5].t = 5; 
 Roads[6].f = 3; Roads[6].t = 4; 
 Roads[7].f = 5; Roads[7].t = 6; 
 Roads[8].f = 2; Roads[8].t = 7; 
 Roads[9].f = 2; Roads[9].t = 6; 
 Roads[10].f = 2; Roads[10].t = 1; 
} 
Map::~Map() 
{ 
 delete Cities; 
 delete Roads; 
} 
void *Map::Start(){ 
 return &Cities[0]; 
} 
void *Map::Goal(){ 
 return &Cities[6]; 
} 
void Map::Bn(void *s, Container &c){ 
 for (int i=0; i<m; i++) 
 if (*((City*)(s))==Cities[Roads[i].f]) 
 c.Store(&Cities[Roads[i].t]); 
} 
void Map::Show(void*s){ 
 cout<<*(char*)(s); 
} 
Cơ sở tri thức tháp Hà Nội 
HNTower::~HNTower() 
{ 
 State *n; 
 sl.GoToHead(); 
 while (0!=(n=(State*)(sl.Retrieve()))) 
{ delete n; sl.GoNext();} 
} 
void *HNTower::MakeState(int a, int b, int c) 
{ 
 State *n; sl.GoToHead(); 
 while (0!=(n=(State*)(sl.Examine()))) 
 { 
 if ((n->a==a)&&(n->b==b)&&(n->c==c)) return n; 
 sl.GoNext(); 
 } 
 n = new State; 
 n->a = a; 
 n->b = b; 
 n->c = c; 
 sl.Store(n); 
 return n; 
} 
void *HNTower::Start() 
{ 
 return (MakeState(3,0,0)); 
} 
void *HNTower::Goal() 
{ 
 return (MakeState(0,0,3)); 
} 
void HNTower::Bn(void *s, Container &c) 
{ 
 State t = *(State*)(s); 
 if (t.a == 3) {c.Store(MakeState(2,1,0)); 
c.Store(MakeState(2,0,1)); return;} 
 if (t.b == 3) {c.Store(MakeState(1,2,0)); 
c.Store(MakeState(0,2,1)); return;} 
 if (t.c == 3) {c.Store(MakeState(1,0,2)); 
c.Store(MakeState(0,1,2)); return;} 
 if ((t.a == 2) && (t.b==1)) 
{c.Store(MakeState(3,0,0)); c.Store(MakeState(2,0,1)); 
c.Store(MakeState(0,1,2)); return;} 
 if ((t.a == 2) && (t.c==1)) 
{c.Store(MakeState(3,0,0)); c.Store(MakeState(2,1,0)); 
c.Store(MakeState(0,2,1)); return;} 
 if ((t.b == 2) && (t.a==1)) 
{c.Store(MakeState(0,3,0)); c.Store(MakeState(0,2,1)); 
c.Store(MakeState(1,0,2)); return;} 
 if ((t.b == 2) && (t.c==1)) 
{c.Store(MakeState(0,3,0)); c.Store(MakeState(1,2,0)); 
c.Store(MakeState(2,0,1)); return;} 
 if ((t.c == 2) && (t.a==1)) 
{c.Store(MakeState(0,0,3)); c.Store(MakeState(0,1,2)); 
c.Store(MakeState(1,2,0)); return;} 
 if ((t.c == 2) && (t.b==1)) 
{c.Store(MakeState(0,0,3)); c.Store(MakeState(1,0,2)); 
c.Store(MakeState(2,1,0)); return;} 
} 
void HNTower::Show(void*s) 
{ 
 State t = *(State*)(s); 
 cout<<'('<<t.a<<','<<t.b<<','<<t.c<<")\n"; 
} 
Mô tơ suy diễn 
void Search::MakeNote(void*s,Snote*f){ 
 Snote *n; 
 open.GoToHead(); 
 while (0!=(n=(Snote*)(open.Examine()))) { 
 if (n->State==s) return; 
 open.GoNext(); 
 } 
 close.GoToHead(); 
 while (0!=(n=(Snote*)(close.Examine()))) { 
 if (n->State==s) return; 
 close.GoNext(); 
 } 
 Snote *tmp = new Snote; tmp->State = s; tmp->Father = f; 
 open.Store(tmp); 
 open.GoToHead(); 
} 
Search::~Search(){ 
 Snote *n; 
 open.GoToHead(); 
 close.GoToHead(); 
 while (0!=(n=(Snote*)(open.Retrieve()))){ delete n; 
open.GoNext();} 
 while (0!=(n=(Snote*)(close.Retrieve()))){ delete n; 
close.GoNext();} 
} 
void Search::Report(KB *kb){ 
 close.GoToHead(); 
 Snote *n=(Snote*)(close.Examine()), *t; 
 kb->Show(n->State); t = n->Father; 
 close.GoNext(); 
 while (0!=(n=(Snote*)(close.Examine()))) { 
 if (t==n) { 
 kb->Show(n->State); 
 t = n->Father; 
 } 
 delete n; 
 close.GoNext(); 
 } 
} 
int Search::Reasone(KB &kb){ 
 void *s = kb.Start(), *g = kb.Goal(), *m; 
 Snote *n; 
 Queue q; 
 MakeNote(s,0); 
 while (0!=(n=(Snote*)(open.Retrieve()))) { 
 close.Store(n); 
 if (n->State==g) return 1; 
 kb.Bn(n->State,q); 
 while (0!=(m = q.Retrieve())) MakeNote(m,n); 
 open.GoToHead(); 
 } 
 return 0; 
}; 
Hệ cơ sở tri thức 
GPSystem::GPSystem(){ 
 kb = 0; 
 e = 0; 
} 
GPSystem::GPSystem(KB*k,Engine*E){ 
 kb = k; 
 e = E; 
} 
int GPSystem::Solve(){ 
 return (e->Reasone(*kb)); 
} 
(e) Minh họa 
void main(){ 
 KB *kb = new HNTower; 
 Engine *e = new Search; 
 GPSystem s(kb,e); 
 if (s.Solve()) e->Report(kb); else cout<<"\nfail"; 
 delete kb; 
 delete e; 
} 
2. Cài đặt thuật toán A* bằng prolog 
domains 
 city = symbol 
 dist = integer 
database 
 open(city, city, dist) 
 close(city, city, dist) 
 done 
predicates 
 road(city, city, dist) 
 heuristic(city, dist) 
 init 
 repeat 
 check(city, dist) 
 bn(city, dist) 
 run 
 report 
 report(city) 
 min(city, city, dist) 
 p(dist) 
clauses 
 road(n,c,10). 
 road(d,l,10). 
 heuristic(n,26). 
 heuristic(c,20). 
 heuristic(t,18). 
 heuristic(d,10). 
 heuristic(g,30). 
 heuristic(l,0). 
 heuristic(u,30). 
 heuristic(h,15). 
 min(F,T,X):-open(F,T,X), not(p(X)). 
 p(X):- open(_,T1,X), heuristic(T1, D1), 
 open(_,T2,Y), heuristic(T2, D2), 
 X+D1>Y+D2. 
 run:- repeat, min(X,Y,D), retract(open(X,Y,D)), 
 asserta(close(X,Y,D)), check(Y,D), done. 
 check(X,_):-X=l, assert(done). 
 check(X,D):-bn(X,D). 
 report:-retract(close(X,Y,D)), 
 write(D),nl,write(Y), report(X). 
 report(z). 
 report(X):-close(Z,X,_), write("<-",X), report(Z). 
 bn(X,D):- road(X,Y,D1), D2 = D + D1, 
 asserta(open(X,Y,D2)), fail. 
 bn(_,_). 
goal 
 init, assertz(open(z,n,0)), run, report. 
3. Xây dựng hệ chuyên gia đơn giản bằng prolog 
Hệ có thể nhận biết trái cây đang xét là loại trái nào. 
3.1. Cơ sở tri thức 
(a) Mô tả 
Dùng mạng ngữ nghĩa 
vàng đỏ màu mọc trên cây 
 Trái táo 
cực bắc không có ở hình tròn 
nhỏ kích thước dùng làm rượu 
 Trái nho 
thân mềm mọc trên cây không có gai 
(b) Thủ tục 
Dùng luật sản xuất 
1. Nếu X là đối tượng và tất cả các thuộc tính của nó đều đúng 
→ X là loại trái cây đang xét; 
2. Nếu A là thuộc tính của X và A chưa biết 
→ hỏi trái cây đang xét có thuộc tính A không 
3.2. Cài đặt bằng prolog 
domains 
 object = symbol 
 attribute = symbol 
 val = integer 
 vlist = val* 
predicates 
 rule(object, attribute, val) 
 min(vlist, val) 
 isa(object) 
 obj(object) 
 value(object, val) 
database 
 /*lưu các chứng cứ*/ 
 term(attribute, val) 
clauses 
 /*tri thức mô tả các loại trái cây*/ 
 obj(apple). 
 obj(grape). 
 rule(apple, on_tree, 1). 
 rule(apple, round, 1). 
 rule(apple, yellow_red, 1). 
 rule(apple, north_hole, 0). 
 rule(grape, small, 1). 
 rule(grape, soft_tree, 1). 
 rule(grape, wine, 1). 
 rule(grape, gai, 0). 
 /*tri thức thủ tục cho mô tơ suy diễn*/ 
 value(X, 1) if rule(X, Y, V), term(Y, V). 
 value(X, 0) if rule(X, Y, U), term(Y, V), U = 1 - V. 
 isa(X) if obj(X), 
 findall(Y, value(X, Y), L), 
 write(L), nl, 
 min(L,1). 
 value(X, V) if rule(X, Y, W), 
 write("does it have : ",Y," 0/1? "), 
 readint(U), assert(term(Y, U)), 
 V=U*W + (1-W)*(1-U). 
 /*các tiện ích*/ 
 min([X], X) if !. 
 min([0|_], 0) if !. 
 min([1|T], V) if min(T, V). 
goal 
 isa(X), writeline(X). 
4. Xây dựng một cơ chế thu nhận tri thức 
Xét bài toán hệ thức lượng trong tam giác. Để giải bài toán này chúng ta 
có hàng loạt các công thức. 
Giả sử chúng ta cung cấp cho hệ các công thức như: 
Ach
CBA
haS
b
a
sin
2
1
×=
=++
×=
π
thì hệ sẽ thu hoạch được gì? 
Thay vì hệ chỉ biết những gì ta dạy, ta muốn hệ có khả năng tổng quát hoá. Muốn 
vậy, chúng ta phải cung cấp cho hệ những tri thức khác cho phép hệ có thể suy 
luận để tổng quát hoá các công thức mà chúng ta vừa dạy cho nó. Cơ chế học 
được đưa ra ở đây dựa vào phương pháp học bằng cách xây dựng một giải thích. 
4.1. Cơ sở tri thức 
Dùng luật sản xuất 
1. Nếu X là một cạnh 
→ X là một đại lượng; 
2. Nếu X là một góc 
→ X là một đại lượng; 
3. Nếu X là một đường cao 
→ X là một đại lượng; 
4. Nếu X là diện tích 
→ X là một đại lượng; 
5. Nếu X, Y, Z là các đại lượng 
→ (X, Y, Z) là một bộ 3 các đại lượng; 
6. Nếu S là diện tích và 
Y, Z là các đại lượng cùng đỉnh 
→ (X, Y, Z) có một ràng buộc; 
7. Nếu X, Y, Z là các đại lượng có các đỉnh đôi một khác nhau 
→ (X, Y, Z) có một ràng buộc; 
8. Nếu (X, Y, Z) là một bộ 3 các đại lượng và 
(X, Y, Z) có một ràng buộc 
→ (S, Y, Z) là một công thức 
4.2. Minh họa cơ chế học 
Ký hiệu 
c(X) : X là một cạnh; 
g(X): X là một góc; 
d(X): X là diện tích; 
v(X): X là đường cao; 
dl(X): X là một đại lượng; 
b3(X, Y, Z): (X, Y, Z) là một bộ 3 các đại lượng; 
rb(X, Y, Z): (X, Y, Z) có một ràng buộc; 
ct(X, Y, Z): (X, Y, Z) là một công thức; 
cd(X, Y): X, Y là các đại lượng cùng đỉnh; 
kd(X, Y, Z): X, Y, Z là các đại lượng có các đỉnh đôi một khác nhau. 
Cây giải thích khi học công thức 
ahaS ×= 2
1
như sau 
 ct(X,Y,Z) 
 b3(X,Y,Z) rb(X,Y,Z) 
 dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) 
 d(X) c(Y) v(Z) d(S) cd(a,a) 
 d(S) c(a) v(a) 
và kết quả hệ học được luật mới cụ thể hơn 
9. Nếu X là diện tích và 
Y là một cạnh và 
Z là một đường cao và 
Y, Z cùng đỉnh 
→ (X, Y, Z) là một công thức 
Tương tự, cây giải thích khi học công thức 
π=++ CBA 
như sau 
 ct(X,Y,Z) 
 b3(X,Y,Z) rb(X,Y,Z) 
 dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) 
 g(X) g(Y) g(Z) kd(a,b,c) 
 g(a) g(b) g(c) 
kết quả hệ học được luật mới 
10. Nếu X, Y, Z là 3 góc có đỉnh khác nhau đôi một 
 → (X, Y, Z) là một công thức 
Cuối cùng, cây giải thích khi học công thức 
Achb sin×= 
như sau 
 ct(X,Y,Z) 
 b3(X,Y,Z) rb(X,Y,Z) 
 dl(X) dl(Y) dl(Z) d(X) cd(Y,Z) kd(X,Y,Z) 
 g(X) g(Y) g(Z) kd(b,c,a) 
 v(b) c(c) g(a) 
kết quả hệ học được luật mới 
11. Nếu X là đường cao và 
Y là cạnh và 
Z là góc và 
X, Y, Z có đỉnh khác nhau đôi một 
 → (X, Y, Z) là một công thức 
5. Đối sánh 
5.1. Khái niệm 
Định nghĩa 3.1 
Đối sánh là quá trình so sánh hai hoặc nhiều cấu trúc để phát hiện ra 
chúng là giống hay khác nhau. 
Các trường hợp 
1. Đơn giản nhất là so sánh bằng nhau 
Chẳng hạn kết quả đối sánh hai xâu acdebfba và acdebeba là khác 
nhau sau khi so sánh từng ký tự một 
2. Phức tạp hơn là trường hợp phải biến đổi trước khi so sánh bằng nhau 
Chẳng hạnï kết quả đối sánh hai xâu (ab(cd)e) và (ab?xe) là giống nhau 
sau khi thay ?x bởi (cd) 
3. Trường hợp phức tạp nhất đòi hỏi biến đổi dạng biểu diễn trước khi đối 
sánh. 
Chẳng hạn một đối tượng ảnh biểu diễn dưới dạng đa mức xám đối 
sánh với các mô tả theo logic vị từ, rõ ràng một so sánh trực tiếp là 
không thể trừ phi một dạng được biến đổi về dạng còn lại. 
4. Ngoài ra còn một số kiểu đối sánh khác 
Chẳng hạn yêu cầu đối sánh chỉ các phần tử khoá. 
5.2. Đối sánh biểu thức 
Ta có thể viết luật, sự kiện dưới dạng biểu thức. Với biểu thức ta có thể 
• Dùng cấu trúc cây nhị phân để biểu diễn 
• Phép thay thế các biến tự do trên cấu trúc cây cho phép sinh ra các sự 
kiện mới một cách dễ dàng, trực quan và có thể cài đặt được. 
Xét ví dụ sau 
Ví dụ 3.1 
Aùp dụng luật x + y = y + x trên biểu thức (a + 2*b) + c*d 
• Biểu diễn biểu thức 
• Biểu diễn luật 
• Áp dụng luật cho đỉnh cộng (+) đầu tiên tìm thấy 
Bài tập 
Xét bài toán biến đổi biểu thức mệnh đề, hãy 
1. Mô tả cấu trúc dữ liệu cho mệnh đề 
2. Mô tả cấu trúc dữ liệu cho luật 
3. Mô tả quá trình áp dụng luật đưa biểu thức về dạng chuẩn 
Tài liệu tham khảo 
1 Trí tuệ nhân tạo - Đỗ Trung Tuấn, 1998 
2 Trí tuệ nhân tạo, các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri thức 
- Nguyễn Thanh Thủy 
3 Trí tuệ nhân tạo, các phương pháp và ứng dụng - Bạch Hưng Khang - Hoàng 
Kiếm 
4 Giải một bài toán trên máy tính như thế nào (tập 1&2) - Hoàng Kiếm 
5 Lập trình C cho trí tuệ nhân tạo - Herbert Schildt 
6 Introduction Artificial Intellegent & Expert System - Dan W Patterson 
7 Problem Solving & Artificial Intellegent - Jean - Louis Laurière 
8 Artificial Intellegence – Elaine Rich – Kevin Knight, 1991 
9 Artificial Intellegence A Modern Approach – Stuart Russell – Peter Norvig, 
1995 
10 Turbo prolog