Giáo trình Trí tuệ nhân tạo (Phần 2)

 90
Chương 3 
PHÂN RÃ BÀI TOÁN - TÌM KIẾM LỜI GIẢI 
TRÊN ĐỒ THỊ VÀ/ HOẶC 
1. Đặt vấn đề. 
Trong chương 2, chúng ta đã nghiên cứu việc biểu diễn bài toán thông qua 
các trạng thái và các toán tử. Khi đó việc tìm lời giải của bài toán được quy về 
việc tìm đường đi trong không gian trạng thái. Trong chương này chúng ta sẽ 
nghiên cứu một phương pháp luận khác để giải quyết vấn đề, dựa trên việc quy 
vấn đề về các vấn đề con. 
Ý tưởng chủ yếu là xuất phát từ bài toán ban đầu, tách ra các bài toán con, 
quá trình này tiếp tục đối với các bài toán con cho đến khi gặp các bài toán sơ 
cấp (bài toán có lời giải ngay). 
Ví dụ 1. Xét bài toán tính tích phân dxxxx )(ln 2 . 
Thông thường để tính tích phân bất định, chúng ta thường sử dụng các 
quy tắc tính tích phân: tích phân của tổng, quy tắc tích phân từng phần hay các 
phép biến đổi v.v để đưa tích phân cần tính về tích phân của các hàm số sơ 
cấp mà chúng ta đã biết cách tính. Đối với tích phân trên, áp dụng quy tắc tích 
phân của tổng ta đưa về hai tích phân xlnxdx và tích phân x3dx. Áp dụng quy 
tắc tích phân từng phần ta đưa tích phân xlnx về tích phân xdx. Quá trình trên 
có thể biểu diễn bởi đồ thị trong Hình 1. 
Hình 1. 
 x(lnx+x2)dx
 xlnxdx x3dx 
 xdx 
 91
Trong bài toán tích phân, các tích phân cơ bản là các trạng thái kết thúc. 
Ví dụ 2. Bài toán tìm đường đi trên bản đồ giao thông. 
 Bài toán này đã được phát biểu như bài toán tìm đương đi trong không 
gian trạng thái, trong đó mỗi trạng thái ứng với một thành phố, mỗi toán tử ứng 
với một con đường, nối thành phố này với thành phố khác. Bây giờ ta đưa ra 
một cách bểu diễn khác dựa trên việc quy vấn đề về các vấn đề con.. Xét bản đồ 
giao thông giữa các thành phố trong Hình 2. 
 A 
 C D H 
 F E G 
 I B K 
 Hình 2. 
Giả sử ta cần tìm đường đi từ thành phố A đến thành phố B. Có một con 
sông chảy qua hai thành phố E và G và có cầu qua sông ở mỗi thành phố đó. 
Như vậy mọi đường đi từ A đến B đều phải đi qua E hoặc G. Khi đó bài toán 
tìm đường đi từ A đến B được quy về một trong hai bài toán: 
1) Bài toán tìm đường đi từ A đến B qua E 
2) Bài toán tìm đường đi từ A đến B qua G 
Mỗi một bài toán trên lại có thể phân nhỏ như sau: 
1) Bài toán tìm đường đi từ A đến B qua E được quy về: 
1.1. Tìm đường đi từ A đến E và 
1.2. Tìm đường đi từ E đến B 
 92
2) Bài toán tòm đường đi từ A đến B qua G được quy về: 
2.1. Tìm đường đi từ A đến G và 
2.2. Tìm đường đi từ G đến B 
Tổng quát, từ bài toán P ta đưa về một trong các trường hợp: 
- Đưa P về các bài toán tương đương: P1, P2,..., Pk 
- Đưa P về các bài toán con: P1, P2,..., Pk 
Phương pháp phân chia bài toán ban đầu như trên đã gặp trong lập trình truyền 
thống với cách gọi “chia để trị” , “Modul hoá”. 
2. Đồ thị VÀ/HOẶC: 
 Không gian trạng thái mô tả việc quy vấn đề về các vấn đề con có thể biểu 
diễn dưới dạng đồ thị định hướng đặc biệt gọi là đồ thị và/hoặc. Đồ thị này được 
xây dựng như sau: 
 Mỗi bài toán ứng với một đỉnh của đồ thị. Nếu có một toán tử quy bài 
toán về các bài toán tương đương thì sẽ có các cung đi từ bài toán xuất phát đến 
các bài toán tương đương đó. Nếu một toán tử quy bài toán về các bài toán con 
thì cũng có các cung nối từ bài toán xuất phát đến các bài toán con, ngoài ra giữa 
các cung này cũng có đường nới với nhau.. Chẳng hạn, giả sử bài toán A được 
đưa về hai bài táon tương đương A1 và A2. Bài toán A1 lại được quy về hai bài 
toán con B1 và B2, ta có biểu diễn như hình 3. 
 A 
 A1 A2 
B1 B2 
Hình 3 
 93
Một cách hình thức ta có thể định nghĩa đồ thị và/hoặc như sau: 
Đồ thị G = (V, E) được gọi là đồ thị VÀ/HOẶC nếu Vn  , T(n) hoặc 
các bài toán con của n (n gọi là các đỉnh VÀ) hoặc là tập các bài toán tương 
đương với n (n gọi là đỉnh HOẶC). 
Cách biểu diễn như sau: 
 n 
 n1 n2 ...... nk 
n được gọi là đỉnh HOẶC (n n1 ... nk ) 
 n 
 n1 n2 ...... nk 
 n được gọi là đỉnh VÀ (n n1... nk ) 
Khi đó để giải bài toán n ta phải tìm đồ thị con của G là một cây có gốc là 
đỉnh xuất phát n sao cho mọi đỉnh trên đồ thị con này đưa về được các bài toán 
sơ cấp (đỉnh kết thúc). 
Nhận xét: Gọi VA: tập các đỉnh VÀ 
 VO: tập các đỉnh HOẶC 
 Nếu VA=    tìm lời giải trên đồ thị biểu diễn bằng không gian trạng thái 
Khi đó: 
- Bài toán n được gọi là giải được nếu: 
+ hoặc n là đỉnh kết thúc 
+ hoặc T(n)={n1, n2,..., nk} và nếu n là đỉnh HOẶC )...1( ki  sao cho ni 
giải được, ngược lại ni giải được ki ...1  . 
- Bài toán n được gọi là không giải được nếu: 
 94
+ hoặc n là đỉnh lá và n không phải là đỉnh kết thúc. 
+ hoặc T(n)={n1, n2,..., nk}và nếu n là đỉnh HOẶC )...1( ki  sao cho nj 
không giải được, ngược lại ni không giải được ki ...1  . 
 Để tìm lời giải của bài toán khi được phân rã về đồ thị VÀ/HOẶC không 
phải tìm đường đi mà phải đi tìm đồ thị con gọi là đồ thị con lời giải (hay cây 
lời giải) 
Cây lời giải là đồ thị con G’ của G thoả: 
- Đỉnh gốc (xuất phát) '0 Vn 
- 'Vn  , n giải được. 
 Ta có sự tương quan: 
Phân rã bài toán Đồ thị VÀ/HOẶC 
Bài toán Đỉnh 
Chuyển bài toán thành các bài toán con Cung 
Bài toán sơ cấp Đỉnh cuối 
Các bài toán con phụ Đỉnh VÀ 
Các bài toán con độc lập Đỉnh HOẶC 
Giải bài toán Tìm đồ thị con lời giải bài toán 
3. Các phương pháp tìm kiếm lời giải trên đồ thị và/hoặc. 
Sau khi lựa chọn mô tả bài toán và các toán tử quy bài toán về bài toán 
con, ta có thể xây dựng đồ thị Và/hoặc để giải quyết bài toán ban đầu hoặc 
chứng tỏ tính không giải được của nó. Cũng như đồ thị trong không gian trạng 
thái, đồ thị và/hoặc có thể cho dưới dạng tường minh hoặc không tường minh 
trên cơ sở toán tử xây dựng. 
 95
Các phương pháp tìm kiếm trên đồ thị và/hoặc khác nhau chủ yếu ở 
phương pháp lựa chọn và sắp xếp đỉnh trước khi tháo chúng. Tương tự như 
trong không gian trạng thái, ta cung có các phương pháp sau: 
- Tìm kiếm theo chiều rộng. 
- Tìm kiếm theo chiều sâu. 
- Tìm kiếm cây lời giải có giá nhỏ nhất. 
Các quá trình này khác hẳn với các quá trình lựa chọn trong không gian 
trạng thái. Sự khác biệt chủ yếu là do việc kiểm tra tính kết thúc của quá trình 
tìm kiếm và các phương pháp sắp xếp và lựa chọn đỉnh để xét phức tạp hơn 
nhiều.. Thay cho việc tìm kiếm đỉnh thoả mãn điều kện đích, chúng ta phải tiến 
hành tìm kiếm đồ thị lời giải. Do đó, ở những thời điểm nhất định, ta phải kiểm 
tra xem đỉnh đầu có giải được hay không, nếu đỉnh đầu giải được thì kết thúc 
công việc, trong trường hợp ngược lại thì tiếp tục xét các nút. Nếu đỉnh đang xét 
không phải là đỉnh kết thúc và nó là đỉnh lá, tức là đỉnh không giải được. Lúc 
này phải kiểm tra đỉnh đàu có phải không giải được hay không, nếu đúng thì 
dừng, ngược lại, tiếp tục tìm kiếm. 
Trước khi tìm kiếm lời giải trong đồ thị VÀ/HOẶC, chúng ta xây dựng 
các hàm kiểm tra một đỉnh n nào đó tại thời điểm đang xét có giải được hay 
không giải được không? 
Function giaiduoc(n):boolean; 
Begin 
 If then 
 giaiduoc:=true 
 else 
 if T(n)null then 
 if T(n)VA then 
)(
))((
nTm
mgiaiduocandgiaiduoc
 96
 else 
)(
))((
nTm
mgiaiduocorgiaiduoc
 else 
 giaiduoc:=false; 
End; 
Function khonggd(n):boolean; 
Begin 
 If T(n)null then 
 if T(n)VA then 
)(
))((
nTm
mkhonggdorkhonggd
 else 
)(
))((
nTm
mkhonggdandkhonggd
 else 
 if then 
 khonggd:=true 
 else 
 khonggd:=false; 
End; 
3.1. Phương pháp tìm kiếm chiều rộng: 
Procedure TKR; 
Begin 
 Push(n0, MO); 
 While MOnull do 
 begin 
 n:=pop(MO); 
 97
 push(DONG, n); 
 if T(n)null then 
 for )(nTm do 
 begin 
 push(m, MO); 
 if T(m)=null then 
 if giaiduoc(m) then 
 if giaiduoc(n0) then 
 exit 
 else 
 for k MO do 
 if giaiduoc(k) then 
 MO:=MO-[k] 
 Else 
 If khonggd(m) then 
 If khonggd(n0) then 
 Exit 
 Else 
 For k MO do 
 if khonggd(k) then 
 MO:=MO-[k] 
 end; 
 end; 
 write(‘Khong ket luan’); 
End; 
 Nhận xét: 
Nếu tồn tại cây lời giải thì thủ tục tìm kiếm rộng sẽ dừng và cho kết quả là 
cây lời giải có độ cao nhỏ nhất. 
 98
Ví dụ. Xét đồ thị Hình 3. 
 A 
      B    C    D 
    E*  F    G  H*    I 
      J  K        L* 
    M*  N   
        O*  Hình 3     
Các đỉnh kết thúc là các đỉnh đánh dấu *. Quá trình tìm kiếm lời giải của đò thị 
trên bằng phương pháp tìm kiếm rộng có thể trình bày ở bảng sau 
 n T(n) MO DONG 
 A 
 A B, C, D B C D A 
 B E*, F C D F A B 
 C G D F G A B C 
 D H*, I F G I A B C D 
 F J G I J A B C D F 
 G K0 I J A B C D F G 
 I L* Dừng 
 Cây lời giải ở Hình 4. 
 A 
 D 
 H* I 
 L* 
Hình 4 
3.2. Tìm kiếm theo chiều sâu: 
 99
Hoàn toàn tương tự tìm kiếm theo chiều rộng, chỉ khác thứ tự lấy các 
đỉnh trong danh sách MO ra xét. Ở đây MO được truy xuất theo nguyên tắc 
LIFO. 
 Ví dụ. Xét đồ thị ở Hình 5. 
 A 
 B C 
 D E F* G 
 H* I* J* K* L* M* 
Hình 5. 
Quá trình tìm theo chiều sâu tiến hành như sau: 
 n T(n) MO DONG 
 A 
 A B, C B C 
 C F* , G BG 
 G L*, M* : giải được A giải được 
Cây lời giải ở Hình 6. 
 A 
 C 
 F* G 
 L* M* 
Hình 6. 
 100
3.3. Tìm kiếm cây lời giải cực tiểu: 
Cây G=(V, E) biểu diễn sự phân rã của bài toán gốc n0. 
Ứng với mỗi phép chuyển bài toán n sang bài toán v tốn chi phí c(u,v). 
c: E R+ 
(u,v) c(u,v) 
Vấn đề đặt ra tìm cây lời giải có tổng chi phí bé nhất. 
Đối với không gian trạng thái, ta đã sử dụng hàm đánh giá để sắp thứ tự các nút 
trong MO trước khi xử lý và hàm h(n) là giá của đường đi tối ưu từ đỉnh 
n DICH. Trong cây VÀ/HOẶC đó chính là khái niệm giá tối ưu của cây lời 
giải với gốc là đỉnh n đã cho. 
Đối với đỉnh n V, giá của n được tính phụ thuộc vào quy ước chọn giá chung 
của đồ thị. Có 2 loại giá: giá cực đại (max) và giá tổng cộng (). 
Định nghĩa giá tối ưu của cây lời giải có gốc n như sau: 
- Nếu n là đỉnh kết thúc thì h(n) = 0 
- Nếu n không phải là đỉnh kết thúc và n là đỉnh hoặc có tập T(n) = {n1,. 
. .,nk} khác rỗng thì h(n) = min(c(n,ni)+h(ni)). 
- Nếu n không phải là đỉnh kết thúc và n là đỉnh và có tập T(n) = {n1,. . 
.,nk} khác rỗng thì : 
+ Đối với giá tổng cộng 
k
i
ii nhnncnh
1
))(),(()( 
+ Đối với giá cực đại ))(),(()( ii nhnncnh  
- h(n) không xác định đối với những đỉnh không giải được. 
 101
Tương tự như trong không gian trạng thái ta xác đinh ước lượng của h là h0 tại 
các đỉnh không phải là đỉnh không giải được.. Cây lời giải được xây dựng dần 
dần trong quá trình mở rộng cây lựa chọn, tại mỗi thời điểm các nút lá của nó 
thuộc một trong ba dạng sau: 
- Các đỉnh kết thúc. 
- Các đỉnh lá không phải là đỉnh kết thúc. 
- Các đỉnh chưa được xử lý. 
Trong cây 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 đầy đủ (cũng giống như các 
đường đi từ đỉnh n0 đến các đỉnh trong danh sách MO trong giải thuật tìm kiếm 
trên đồ thị biểu diễn bài toán trong không gian trạng thái ). 
Ta gọi các cây này là cây lời giải tiềm tàng gốc n0. Như vậy bài toán tìm kiếm 
cây lời giải cực tiểu có thể đưa về hai bài toán con: 
Bài toán 1. Xác định ước lượng h0(n) 
1) n là đỉnh lá 
- Nếu n là đỉnh kết túc thì h0(n) = 0 
 - Nếu n không phải là đỉnh kết thúc thì h0(n) không xác đinh (có thể gán 
giá trị ) 
 - Nếu n chưa được xử lý thì h0(n) nhận một giá trị ước lưọng dựa trên 
thông tin về bài toán (thưòng tham khảo ý kiến chuyên gia) 
2) n không phải là đỉnh lá, T(n) = {n1,,nk} 
 - Nếu n là đỉnh Hoặc thì h0(n) = min(c(n,ni)+h(ni)) 
- Nếu n là đỉnh Và thì 
- Đối với giá tổng cộng 
k
i
ii nhnncnh
1
00 ))(),(()( 
 102
- Đối với giá cực đại h0(n) = Max(c(n,ni)+h0(ni)) 
Bài toán 2. Xây dựng cây lời giải tiềm tàng G’ mô tả quá trình chuyển bài toán 
n0 về bài toán n. Gọi G’ = (V’, E’) là đồ thị con của G với tập đỉnh V” xác định 
như sau: 
- n0 V’ 
- Với mỗi n V’ có các đỉnh con n1,, nk. Nếu n là đỉnh hoặc thì 
chọn đỉnh con ni vào V’ sao cho c(n,ni) + h0(ni) nhỏ nhất và 
khonggd(ni) = false. Nếu n là đỉnh và thì chọn tất cả các đỉnh ni 
vào V’ nếu khonggd(ni) = false với mọi i. 
Thuật toán. 
Input: 
Cây và hoặc G = (V,E) với gốc n0. 
 Giá trị ước lương ban đầu h0. 
 Tập đỉnh kết thúc. 
 c: E R+ và laọi chi phí (tổng công hoặc cực đại) 
Output: 
 Cây lời giải tối ưu. 
Method: 
 push(MO,n0); 
 while MO null do 
 begin 
 Xây dựng cây tiềm tàng G’; 
 n:= pop(MO Lá(G’); 
 Push(DONG,n); 
 103
 if n là đỉnh kết thúc then 
 begin 
if giaiduoc(n0) then 
 exit; { Cây lời giải là G’} 
 for k MO do 
 if giaiduoc(k) then 
 MO := MO - {k}; 
 end 
 else 
 if T(n) null then 
 for m T(n) do 
 begin 
 push(MO,m); 
 Tính lại h0(m) 
 end 
 else 
 if khonggd(n) then 
 begin 
 if khonggd(n0) then 
 exit; 
 for k MO do 
 if khonggd(k) then 
 MO:= MO - {k}; 
 104
 for m DONG do 
 Tính lại h0(m) 
end; 
writeln(‘khong co loi giai’); 
end; 
4. Cây tìm kiếm và các đấu thủ. 
 Trong nhiều trò chơi trên máy tính có thể sinh ra các cây ứng với các 
nước đi của đấu thủ. Đặc thù của loại trò chơi này là chúng thể hiện sụ luân 
phiên giữa hai đấu thủ. Việc chọn các nước đi cho mỗi đấu thủ tương ứng với 
việc tìm kiếm cây. Để quyết định một trong những lựa chọn có thể được, người 
ta phải nhớ nhiều tình huống của bài toán. Tuy nhiên không thể lưu trữ quá 
nhiều thông tin và cũng không xử lý tất cả trạng thái của bài toán được. Do vậy 
người ta có thể dùng một chiến thuật phù hợp, chỉ quyết định trên tập tình huống 
hạn chế. 
4.1. Thủ tục minimax. 
 Xét trò chơi với hai đấu thủ Max và Min, Max tìm cách làm cực đại giá trị 
hàm ước lượng thông qua việc xác định gá trị hàm ước lượng ở mỗi nước đi có 
thể và chọn nước đi tương ứng với giá trị lớn nhất, tiếp theo đó đối thủ Min tìm 
cách làm cực tiểu giá trị ước lượng này. 
 Diễn đạt theo ngôn ngữ đồ thị Và/Hoặc, Mỗi đỉnh tương ứng với nước đi 
của Max, giá trị của đỉnh này sẽ lấy giá trị cực đại của các giá trị của các đỉnh 
con và đỉnh này quy ước gọi là đỉnh Hoặc. Một đỉnh tương ứng với nước đi của 
Min sẽ lấy giá trị cực tiểu trong số các giá trị đối với các đỉnh con của nó và 
đỉnh này quy ước gọi là đỉnh loại Và. 
Ví dụ. Trò chơi caro trên bảng ô vuông. Đấu thủ Max đặt các dấu X, đấu thủ 
Min đặt dấu O. Ta xét ước lượng c(p) đối với mỗi thế cờ p như sau: 
 105
 c(p) = (số dòng, số cột, số đường chéo còn mở đới với Max) – 
 (số dòng, số cột, số đường chéo còn mở đối với min) 
 Giả sử ta hạn chế kích thước 3x3 và ở mỗi nước đi, các đấu thủ tính trước 
hai nước. Nếu đấu thủ Max đi trước độc giả có thể kiểm tra, nước đi đầu tiên của 
Max sẽ là: 
 X 
4.2. Thủ tục Alpha – Beta 
Các giá trị ước lượng phát sinh tương ứng với các đỉnh Và, Hoặc được gọi là các 
 -giá trị và -giá trị tương ứng. Thủ tục alpha-beta bắt đầu từ nút gốc với giá trị 
alpha là - và beta là + . Thủ tục alpha-beta gọi đệ quy với dãy số giữa alpha 
và beta. Để thực hiện tìm kiếm minimax bằng thủ tục alpha – beta, có các bước sau: 
1) Nếu mức của cây là gốc, lấy giá trị alpha là - và gia trị beta là + . 
2) Nếu đã đến bước kết thúc tìm kiếm, tính giá trị hàm ước lượng của vị trí hiện 
tại cho đấu thủ tương ứng. Cho ra kết quả. 
3) Nếu mức ứng với đấu thủ min: 
i) Cho đến khi các nút con được kiểm tra bằng thủ tục alpha – beta hoặc 
cho đến khi alpha >= beta, thực hiện các bước sau: 
+ Dùng thủ tục alpha – beta với ... ủa nó như thế 
nào? và dựa vào hiểu biết của ta mà xác định xem quả cam đó là ngon hay 
không ngon, ngon vừa,... 
Như vậy, tri thức là dạng dữ liệu bậc cao. Khó phân biệt giữa tri thức và dữ 
liệu (không có ranh giới rõ ràng giữa chúng). Tuy nhiên ta có thể phân biệt theo 
bảng sau: 
Dữ liệu Tri thức 
- Định lượng 
- Có cấu trúc đơn giản 
- Ở dạng đơn giản
- Định tính 
- Không có cấu trúc hoặc có 
cấu trúc phức hợp 
- Ở dạng phức hợp 
  149
2. Các dạng mô tả tri thức (các phương pháp biểu diễn tri thức) 
(Để máy tính có thể sử dụng được tri thức, có thể xử lý được tri thức, chúng ta 
cần phải biểu diễn tri thức dưới dạng thuận tiện cho máy tính. Đó là mục tiêu 
của biểu diễn tri thức). Sau nhiều cố gắng, các nhà TTNT đã phát triển một số 
cách biểu diễn (thể hiện) tri thức có hiệu quả trong máy. 
2.1. Biểu diễn tri thức bằng logic 
Như ta đã nghiên cứu ở phần trước, ta có thể biểu diễn bài toán bằng các biểu 
thức logic (logic mệnh đề, logic vị từ) 
2.2. Biểu diễn tri thức bằng mạng ngữ nghĩa 
Phương pháp biểu diễn tri thức bằng cách dùng một đồ thị G = (V, E) gồm tập 
đỉnh V và tập cung E. Trong đó các đỉnh ứng với các đối tượng, khái niệm hay 
sự kiện cụ thể, các cung thể hiện quan hệ giữa các đối tượng. Có một cung nối 
giữa hai đối tượng a và đối tượng b, ký hiệu a b nếu có một quan hệ nào 
đó giữa hai đối tượng a, b. 
Có 2 loại quan hệ đặc biệt 
- "a là b" nghĩa là đối tượng a thuộc vào tập đối tượng được biểu diễn bởi 
khái niệm b hoặc tập các đối tượng biểu diễn bởi khái niệm a là tập con 
của tập đối tượng biểu diễn khái niệm b. (quan hệ is-a) 
Ví dụ Yến chim 
- Ngược lại với quan hệ "là" là quan hệ "bao gồm". Khi có " a là b" (hoặc 
"b bao gồm a"), các thông tin cơ bản về các đối tượng được cho bởi b sẽ 
truyền lại cho a (nghĩa là a được thừa hưởng những gì b có). 
  150
Ví dụ 
Ưu điểm: 
- Cho phép biểu diễn một cách trực quan các sự kiện và các mối liên hệ 
giữa chúng. 
- Tính mô đun cao theo nghĩa các tri thức mới được thêm vào hoàn toàn 
độc lập với các tri thức cũ. 
- Có thể áp dụng một số cơ chế suy diễn trên mạng: cơ chế truyền và thừa 
hưởng thông tin giữa các đối tượng, cơ chế "cháy" trên mạng 
Nhược điểm: 
- Không có một phương pháp suy diễn chung nào cho mọi loại mạng ngữ 
nghĩa 
- Khó kiểm soát quá trình cập nhật tri thức để dẫn đến mâu thuẫn trong cơ 
sở tri thức. 
2.3. Biểu diễn tri thức bằng khung (Frame) 
Khung thực chất là sự tổng quát hoá của cấu trúc bản ghi trong Pascal và 
tương tự như cấu trúc đối tượng trong C++ 
Một khung được mô tả bởi cấu trúc: 
- Tên khung: Định danh đối tượng mô tả 
- Các khe (slot): trên mỗi khe lưu trữ các thông tin, n\miền giá trị, thuộc 
tính và chiều mũi tên chỉ đến các khung khác 
cánh 
Chim 
bay 
Con vậtYến Chíp chíp 
Cánh cụt
đi 
Không khí 
is‐a 
is‐a is‐a
is‐a hoạt động 
hoạt động 
thở  có
  151
Ví dụ Xét khung (frame) mô tả tập học sinh HOCSINH 
Frame HOCSINH 
 IS-A: 
 PART-OF: NGUOI-DI-HOC 
 A KIND OF: (HOCSINHCOSO, HOCSINHTRUNGHOC) 
 Cân nặng: 10-60kg 
 Chiều cao: 80-170cm 
Cấu trúc frame này cho ta một "khung dữ liệu" để khoanh vùng các đối tượng 
là học sinh. Trường hợp gặp một người cao 175cm, nặng 45kg thì ta có thể 
khẳng định rằng đó không phải là học sinh vì không thoã mãn các ràng buộc đã 
có. 
Ngoài ra, một trong những đặc trưng quan trọng của frame là khả năng thừa kế 
các thông tin của các khe có cùng tên ở đối tượng bậc trên. 
Ví dụ Trong frame HOCSINHCOSO, HOCSINHTRUNGHOC có khe chiều 
cao với giá trị mô tả miền, thì sau khi thừa kế thông tin ở mức trên Frame 
HOCSINH, khe này cần phải lấy các giá trị trong khoảng 80-170cm. 
2.4. Biểu diễn tri thức bằng các luật sản xuất 
Phương pháp biểu diễn tri thức nhờ logic (logic mệnh đề và logic vị từ) khá 
trực quan song chỉ phù hợp khi không có quá nhiều luật suy diễn. 
Một tri thức được thể hiện bằng một câu Horn dạng chuẩn: 
p1  p2 .... pn q 
(Các câu Horn dạng này còn được gọi là luật if- then và được biểu diễn như sau: 
if P1 and....and Pm then Q) 
Một câu Horn dạng tổng quát: 
p1  p2 .... pn q1  q2 .... qm 
  152
Lưu ý: 
Nếu có luật dạng: p1  p2 .... pn q1  q2 .... qm thì tương đương với m 
luật sau: 
p1  p2 .... pn   q2 .... qm q1 
p1  p2 .... pn   q1   q3... qm q2 
p1  p2 .... pn   q1.... qm-1 qm 
Tuy nhiên ta chỉ xét câu Horn dạng chuẩn (m=1) 
- Nếu n=0, m=1: câu Horn có dạng q: gọi là sự kiện (fact) q. 
- Nếu n>0, m=1: câu Horn có dạng: p1  p2 .... pn q: gọi là luật (rule). 
Trong các hệ chuyên gia, cơ sở tri thức gồm 2 phần: tập các sự kiện (facts) và 
tập luật (rules). 
Ví dụ 
1) Ta có các luật về kinh nghiệm dự báo thời tiết: 
"Chuồn chuồn bay thấp thì mưa, bay cao thì nắng, bay vừa thì râm" 
a: chuồn chuồn bay thấp, b: chuồn chuồn bay cao, c: chuồn chuồn bay vừa 
d: trời mưa, e: trời nắng, f: trời râm 
lúc đó ta có các luật sau: 
a d 
b e 
c f 
2) Nhiều định lý trong toán học có thể biểu diễn bởi các luật, ví dụ: 
Nếu tam giác có một góc bằng 600 và tam giác có hai cạnh bằng nhau thì tam 
giác đó là tam giác đều. 
3. Suy diễn trên luật sản xuất 
3.1. Khái niệm 
Suy diễn là quá trình suy luận dựa vào các quy luật đã cho, thiết lập các thông 
tin mới từ các thông tin đã biết. Suy diễn sẽ sử dụng tập sự kiện làm tiên đề. 
  153
Các phương pháp suy diễn dần dần chuyển từ các giả thiết về các kết luận 
bằng cách thêm vào giả thiết những sự kiện đã được khẳng định đúng, dựa trên 2 
phương thức: 
- Modus ponens: A, A B 
 B 
nghĩa là nếu A đúng và A B đúng thì B cũng đúng 
 - Modus tollens B, A B 
 A 
nghĩa là nếu B sai và biết rằng A B đúng thì A cũng sai. 
Trong quá trình suy diễn, ta cần quan tâm đến các vấn đề sau: 
- Xây dựng tập luật, câu hỏi nào được chọn để người sử dụng trả lời 
- Chọn quá trình tìm kiếm như thế nào 
- Thông tin nhận được có ảnh hưởng đến quá trình tìm kiếm không 
3.2. Bài toán 
Cho tập sự kiện F= {f1, f2,...,fn} và tập luật R= {r1, r2,...,rm}. Chứng minh tập 
kết luận G đúng. 
3.3. Các phương pháp suy diễn 
Quá trình suy diễn trong hệ luật sản xuất bao gồm 2 phương pháp cơ bản: suy 
diễn tiến và suy diễn lùi. 
a) Suy diễn tiến (lập luận tiến - forward chaining hoặc forward reasoning) 
(Tư tưởng cơ bản của suy diễn tiến là áp dụng luật suy diễn Modus Ponens tổng quát) 
Là quá trình suy diễn bắt đầu từ tập sự kiện đã biết, rút ra những sự kiện mới 
và cứ như vậy cho đến khi có được sự kiện cần chứng minh hoặc không có luật 
nào sinh ra các sự kiện mới (tập sự kiện đúng là cực đại). 
- Phương pháp 
GỌi T là tập các sự kiện tại thời điểm đang xét (khởi tạo tập T=F: tập sự kiện 
đúng ban đầu ). 
  154
Xét các luật ri có dạng: p1  p2  .... pn q và pj T nj ,1  nghĩa là 
left (ri) T 
thì T= T+ right (ri) 
quá trình lặp lại cho đến khi G T hoặc không có luật nào sinh ra thêm sự kiện 
mới. 
- Giải thuật 
Procedure suydientien; 
Begin 
 T:= F; 
 S:= loc(R, T); { S: là tập luật có dạng p1  p2  .... pn q sao cho pj T 
nj ,1  } 
 While G  T and S do 
 Begin 
 r := get(S); 
 T:= T + right(r); 
 R:=R \ {r}; 
 S:= loc(R,T); 
 End; 
 If G  T then write (“thành công”) 
 Else write (“không thành công”); 
End; 
Ví dụ 
1) Cho trước tập sự kiện F={a,b}. Sử dụng các luật: 
r1: a c 
r2: b d 
r3: c e 
r4: a  d e 
  155
r5: b  c f 
r6: e  f g 
cần suy ra g 
r T S R 
r1 
r2 
r3 
r4 
r5 
r6 
a, b 
a, b, c 
a, b, c, d 
a, b, c, d, e 
a, b, c, d, e 
a, b, c, d, e, f 
a. b, c, d, e, f, g 
r1, r2, r3 
r2, r3, r5 
r3, r4, r5 
r4, r5 
r5 
r6 
r1, r2, r3, r4, r5, r6 
r2,...r6 
r3,..., r6 
r4, r5, r6 
r5, r6 
r6 
g T nên bài toán được chứng minh (g: true) 
Chú ý 
- Quá trình suy diễn tiến là quá trình xem xét các luật, với mỗi luật ta xét 
phần điều kiện (ở vế trái) tới phần kết luận (ở vế phải) và khi mà tất cả 
các đièu kiện của luật đều thoã mãn thì ta suy ra sự kiện trong phần kết 
luận. Chính vì lẽ đó mà có tên là suy diễn tiến. 
- Trong mỗi bước của thủ tục, người ta xét một luật trong tập luật. So sánh 
mỗi điều kiện (ở vế trái) của tập luật với các sự kiện trong cơ sở sự kiện, 
nếu tất cả các điều kiện của luật được thoã mãn thì sự kiện trong phần kết 
luận được xem là sự kiện được suy ra. nếu sự kiện này là sự kiện mới 
(không có trong bộ nhớ làm việc) thì nó được đưa vào bộ nhớ làm việc. 
Quá trình trên cứ lặp lại cho đến khi nào không có luật nào sinh ra sự kiện 
mới. 
  156
- Quá trình suy diễn tiến không định hướng tới giải quyết một vấn đề nào 
cả, không hướng tới tìm ra câu trả lời cho một câu hỏi nào cả. Suy diễn 
tiến chỉ là quá trình suy ra các sự kiện mới từ các sự kiện có trong bộ nhớ 
làm việc. 
b) Suy diễn lùi (lập luận lùi - backward chaining hoặc backward reason) 
Là quá trình xuất phát từ sự kiện cần chứng minh và thay vào đó là những sự 
kiện ở vế trái của 1 luật có vế phải là sự kiện cần chứng minh. Quá trình này 
được thực hiện cho đến khi đưa về các sự kiện là tập sự kiện con của tập sự kiện 
giả thiết. 
(Nghĩa là: để đưa ra kết luận b, ta thử tìm tất cả các luật có dạng: a1  .... an 
b, để có b, phải đưa ra các kết luận a1,...,an. Quá trình xác định ai cũng tương tự 
như đối với b, nếu đến một lúc nào đó phát hiện được rằng có một ai nào đó 
không dẫn xuất được từ các giả thiết thì quay lui sang các luật sản xuất khác 
sinh ra b có dạng b1....bm b. Ngược lại, nếu mọi ai đều dẫn xuất được giả 
thiết thì quá trình dẫn xuất ra b là đúng) 
- Giải thuật 
GỌi T là tập các sự kiện cần chứng minh tại thời điểm đang xét (khởi tạo T= 
G, G là tập kết luận). 
 S(p) ={ri R / right(ri) = p} ( là tập các luật trong R sao cho vế phải chứa p) 
Procedure suydienlui (g); 
 Begin 
 T:= {g}; 
 If T F then write (‘g đã được chứng minh ‘) 
 Else 
 Begin 
 p:=get(T); 
 If S(p) = {} then write (‘g không chứng minh được ‘) 
  157
 Else 
 For ri S(p) do 
 Begin 
 T:= T \ right(ri); 
 T:= T + left(ri); 
 For l T \ F do suydienlui(l); 
 End; 
End; 
Ví dụ 
1) Cho tập sự kiện F={p, r}, và tập luật R: 
r1) p q 
r2) q  r s 
Chứng minh s 
p r T S(p) 
s 
q 
r2 
r1 
s 
q, r 
r, p 
r2 
r 
Nhận xét 
- Suy diễn tiến: 
Ưu điểm: 
i) Làm việc tốt khi bài toán có bản chất là đi thu thập thông tin rồi thấy điều cần 
suy diễn 
ii) Cho ra khối lượng lớn các thông tin từ một số thông tin ban đầu. Nó sinh ra 
nhiều thông tin mới. 
iii) Suy diễn tiến là tiếp cận lý tưởng đối với các loại bài toán cần giải quyết 
các nhiệm vụ như lập kế hoạch, điều hành, điều khiển và diễn dịch. 
  158
Nhược điểm: 
i) Không cảm nhận được rằng chỉ cần một vài thông tin quan trọng. Hệ thống 
hỏi các câu hỏi có thể hỏi mà không biết rằng chỉ một ít câu đã đi đến kết luận 
được. 
ii) Hệ thống có thể hỏi cả câu hỏi không liên quan. Có thể các câu trả lời cũng 
quan trọng nhưng làm người dùng lúng túng khi phải trả lời các câu chẳng 
dính đến chủ đề. 
- Suy diễn lùi: 
Ưu điểm: 
i) Phù hợp với bài toán đưa ra giả thuyết và liệu giả thuyết đó có đúng hay 
không? 
ii) Tập trung vào đích đã cho. Nó tạo ra một loạt câu hỏi chỉ liên quan đến vấn 
đề đang xét, thuận tiện đối với người dùng. 
iii) Khi suy diễn một điều gì từ thông tin đã biết , nó chỉ tìm trên một phần của 
cơ sở tri thức thích đáng đối với bài toán đang xét. 
iv) Suy diễn lùi được đánh giá cao trong các bài toán như là chẩn đoán, dự 
đoán và tìm lỗi. 
Nhược điểm: 
Nhược điểm cơ bản của loại suy diễn này là nó thường tiếp theo dòng suy 
diễn thay vì đúng ra phải dừng ở đó mà sang nhánh khác. 
- Như vậy, dựa vào các ưu và nhược điềm của từng loại suy diễn mà ta nên 
chọn kỹ thuật suy diễn nào để áp dụng vào bài toán. Trước tiên, ta xem 
xét các chuyên gia giải nó như thế nào?. Nếu cần thu thập dữ liệu rồi mới 
quyết định suy diễn cái gì thì ta chọn suy diễn tiến. còn nếu đã có giử 
thuyết và cần chứng minh cái đích này thì ta dùng suy diễn lùi. 
Ví dụ Một bác sĩ có thể hiểu hàng trăm vấn đề có thể xảy ra với một cá 
nhân, nhưng vẫn phải tìm hiểu hiện trạng của bệnh nhân, lúc đó cần suy diễn 
  159
tiến. Nguợc lại bác sĩ hầu như thấy được bệnh ( ví dụ như viêm họng) thì ông ta 
dùng suy diễn lùi. 
Bài tập 1. Cho các biểu thức logic mệnh đề đúng sau: 
1) ac 
2) ab f 
3) (d +b)f i 
4) h + a + f 
5) fgh i 
6) (a + d + c ) 
7) ad gh 
Chứng minh hoặc bác bỏ mệnh đề i bằng phương pháp suy diễn tiến và suy diễn lùi 
Lời giải 
- Biểu diễn các biểu thức đúng đã cho bằng luật sản xuất (xác định tập luật, tập 
sự kiện ban đầu, tập sự kiện cần chứng minh) 
Quá trình biến đổi 
3) (d+b)f i  ((d+b)f )+i (d+b)+f+i  (db)+f+i  
(d+f+i)(b+f+i)  (df i )(bf i) 
4) h + a + f  (ha)+f  ha f 
1) (a + d + c )  (ac)+d  ac d 
2) ad gh )  (ad)+(gh) )  ((ad)+g) ((ad)+h)  (ad g)(ad h) 
Tập sự kiện F={a, c}, tập sự kiện cần chứng minh G={i} 
Tập luật R: 
r1) ab f r5) fgh i 
r2) (df i ) r6) ac d 
r3) (bf i ) r7) ad g 
r4) ha f r8) ad h 
  160
- Suy diễn tiến (tiến hành lập bảng sau) 
r T S R 
r6 
r7 
r8 
r4 
r2 
a, c 
a, c, d 
a, c, d, g 
a, c, d, g, h 
a, c, d, g, h, f 
a, c, d, g, h, f, i 
r6 
r7, r8 
r8 
r4 
r2, r5 
r1, r2, r3, r4, r5, r6, r7, 
r8 
r1,...r5, r7, r8 
r1,...r5, r8 
r1,...r5 
r1, r2, r3,r5 
(trong đó: r: là luật đang xét, T: tập sự kiện đúng tại thời điểm đang xét, S: tập 
các luật có dạng các mệnh đề ở vế trái thuộc T. R là tập luật tại thời điểm đang 
xét) 
Vì i T (là tập sự kiện đúng). Vậy i được chứng minh 
- Suy diễn lùi (tiến hành lập bảng sau) 
p r T S(p) 
i 
f 
b 
quay lui 
f 
h 
d 
r2 
r1 
r2 
r8 
r6 
i 
d, f 
d, b 
d 
d, h 
d 
 
r2, r3, r5 
r1, r2 
 
r2 
r8 
r6 
Vậy i được chứng minh 
  161
Bài tập 2. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 
1) pt a 5) p t 
2) qt s 6) apq c 
3) pq b 7)bc t 
4) b st 8) pq 
Biểu diễn tri thức đã cho dưới dạng luật sản xuất và dùng phương pháp suy diễn 
tiến và suy diễn lùi để chứng minh hoặc bác bỏ sự kiện s1. 
Bài tập 3. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 
1) (a+c)b f 
2) e +f + a 
3) gfh i 
4) (e+ f)b gi 
5) (a+ e +c)abc 
Dùng phương pháp suy diễn tiến và suy diễn lùi để chứng minh hoặc bác bỏ sự 
kiện i1. 
Bài tập 4.. Cho cơ sở tri thức được biểu diễn bằng các biểu thức logic đúng sau 
1) efh 
2) a + g + d 
3) h + c + d 
4) af bg 
5) ke d 
6) (ef a )(c+ e +f ) 
- Biểu diễn tri thức đã cho dưới dạng luật sản xuất 
- Dùng phương pháp suy diễn tiến để chứng minh sự kiện d1 đúng. Cho biết 
các luật dư thừa trong vết suy diễn 
  162
Bài tập 5.. Trong một lớp học, có một nhóm học sinh gồm 10 bạn có tên lần 
lượt là: A, B, C, D, E, F, G, H, I và J. Giữa các bạn học sinh đó có mối quan hệ 
gọi là quan hệ ảnh hưởng. Ví dụ: nếu ta viết AB>C thì có nghĩa là hai bạn đồng 
thời cùng thuyết phục bạn C tham gia một hoạt động nào đó. Giả sử ban đầu có 
bốn bạn E, F, H, I tham gia dự thi sản phẩm phần mềm do nhà trưòng tổ chức và 
ta cũng biết được rằng: 
1) ACH>B 
2) BH>ACD 
3) ABCI>BDI 
4) ADEI>BCG 
5) CGI>AJE 
6) H>BC 
Hãy dùng phương pháp suy diễn tiến để chứng minh rằng cả 10 bạn trong nhóm 
trên đều tham gia dự thi sản phẩm phần mềm.