Sưu tầm bởi: www.daihoc.com.vn
92
Annie Thấp T.Bình Không Cháy
Kartie Thấp Nhẹ Có Không

VC
.Cao
(Cao) = (0/1,1/1) = (0,1)
VC
.Cao
(T.B) = (1/1,0/1) = (1,0)
VC
.Cao
(Thấp) = (1/2,1/2)

VC
.Nặng
(Nhẹ) = (1/2,1/2)
VC
.Nặng
(T.B) = (1/2,1/2)
VC
.Nặng
(Nặng) = (0,0)

VKem (Có) = (0/2,2/2) = (0,1)
VKem


phải)
(Màu tóc vàng) và (có dùng kem)  không cháy nắng
(Màu tóc vàng) và (không dùng kem)  cháy nắng
(Màu tóc nâu)  không cháy nắng
(Màu tóc đỏ)  cháy nắng
Khá đơn giản phải không? Có lẽ không có gì phải nói gì thêm. Chúng ta hãy thực hiện
bước cuối cùng là tối ưu tập luật.

II.4. Tối ưu tập luật
II.4.1. Loại bỏ mệnh đề thừa
Khác so với các phương pháp loại bỏ mệnh đề thừa đã được trình bày trong phần
biểu diễn tri thức (chỉ quan tâm đến logic hình thức), phương pháp loại bỏ mệnh đề
thừa ở đây dựa vào dữ liệu. Với ví dụ và tập luật đã có ở phần trước, bạn hãy quan
sát luật sau :
(Màu tóc vàng) và (có dùng kem)  không cháy nắng
Bây giờ ta hãy lập một bảng (gọi là bảng Contigency), bảng thống kê những người có
dùng kem tương ứng với tóc màu vàng và bị cháy nắng hay không. Trong dữ liệu đã
cho, có 3 người không dùng kem.
Sưu tầm bởi: www.daihoc.com.vn
94
Không cháy
nắng
Cháy nắng
Màu
vàng
2 0
Màu

R  R
Ai E F

Ai
G H
Trong đó
E là số phần tử trong P thỏa cả Ai và R.
F là số phần tử trong P thỏa Ai và không thỏa R
Sưu tầm bởi: www.daihoc.com.vn
95
G là số phần tử trong P không thỏa Ai và thỏa R
H là số phần tử trong P không thỏa Ai và không thỏa R
Nếu tổng F+H = 0 thì có thể loại bỏ mệnh đề Ai ra khỏi luật.

II.4.2. Xây dựng mệnh đề mặc định
Có một vấn đề đặt ra là khi gặp phải một trường hợp mà tất cả các luật đều không
thỏa thì phải làm như thế nào? Một cách hành động là đặt ra một luật mặc định đại
loại như :
Nếu không có luật nào thỏa  cháy nắng (1)
Hoặc
Nếu không có luật nào thỏa  không cháy nắng. (2)
(chỉ có hai luật vì thuộc tính mục tiêu chỉ có thể nhận một trong hai giá trị là cháy
nắng hay không cháy nắng)
Giả sử ta đã chọn luật mặc định là (2) thì tập luật của chúng ta sẽ trở thành :
(Màu tóc vàng) và (không dùng kem)  cháy nắng
(Màu tóc đỏ)  cháy nắng
Nếu không có luật nào thỏa  không cháy nắng. (2)

3) Ứng dụng nguyên lý thứ tự, hãy giải bài toán chia đồ vật sau. Có n vật với
khối lượng lần lượt là M
1
, M
2
, … Mn. Hãy tìm cách chia n vật này thành hai
nhóm sao cho chênh lệch khối lượng giữa hai nhóm này là nhỏ nhất.
4) Viết chương trình giải bài toán mã đi tuần.
5) Viết chương trình giải bài toán 8 hậu.
6) Viết chương trình giải bài toán Ta-canh bằng thuật giải A
*
.
7) Viết chương trình giải bài toán tháp Hà Nội bằng thuật giải A
*
.
8)
*
Viết chương trình tìm kiếm đường đi ngắn nhất trong một bản đồ tổng
quát. Bản đồ được biểu diễn bằng một mảng hai chiều A, trong đó A[x,y]=0 là
có thể đi được và A[x,y]= 1 là vật cản. Cho phép người dùng click chuột trên
màn hình để tạo bản đồ và xác định điểm xuất phát và kết thúc. Chi phí để đi
từ một ô bất kỳ sang ô kế cận nó là 1.
Mở rộng bài toán trong trường hợp chi phí để di chuyển từ ô (x,y) sang một
bất kỳ kế (x,y) là A[x,y].
CHƯƠNG 2
1. Viết chương trình minh họa các bước giải bài toán đong nước (sử dụng đồ họa
càng tốt).
2. Viết chương trình cài đặt hai thuật toán Vương Hạo và Robinson trong đó liệt
kê các bước chứng minh một biểu thức logic.
3. Viết chương trình giải bài toán tam giác tổng quát bằng mạng ngữ nghĩa (lưu