Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái
Chương V
ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM
TRONG KHÔNG GIAN TRẠNG THÁI
Nội dung chính
: Trong chương này, các kỹ thuật sâu hơn cho việc cài đặt các thuật toán
tìm kiếm sẽ được trình bày một cách chi tiết. Trước hết là tìm kiếm đệ quy (recursive search)
– một phương pháp thực hiện tìm kiếm sâu kèm theo lần ngược với cách thức tự nhiên và
ngắn gọn. Tìm kiếm đệ quy được tăng cường nhờ sử dụng sự hợp nhất (unification) để tìm
kiếm các không gian trạng thái do các biểu thức của phép tính vị từ sinh ra. Sự kết hợp này
cho ta thuật toán tìm kiếm hướng mẫu (pattern – directed search). Phần tiếp theo trong nội
dung chương V giới thiệu mô hình hệ sinh (production system) – một cấu trúc tổng quát để
giải các bài toán hướng mẫu, nó được sử dụng khá nhiều không những để mô hình hóa việc
giải quyết các vấn đề của con người, mà còn để xây dựng các hệ chuyên gia và những ứng
dụng Trí tuệ nhân tạo khác. Cuối cùng, một cách giải bài toán trí tuệ nhân tạo khác cũng
được đề cập đến – kiến trúc bảng đen (blackboard architecture).
Mục tiêu cần đạt :
Sau chương này, sinh viên có thể :

¾ Vận dụng thuật toán tìm kiếm đệ quy kết hợp lần ngược trên không gian trạng thái.
¾ Hiểu thuật toán hướng mẫu khi thực hiện việc tìm kiếm trong không gian trạng thái.
¾ Vận dụng hệ sinh cho một bài toán.
¾ Hiểu các ưu điểm của hệ sinh
¾ Hiểu các ứng dụng kiến trúc bảng đen trong GQVĐ.
Kiến thức tiên quyết
: Lý thuyết đồ thị, Các thuật toán tìm kiếm trên đồ thị, Lý thuyết trò
chơi, …
Tài liệu tham khảo :
[1] George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence
– Wesley Publishing Company, Inc – 1997 (Chapter 4)
[2] Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc

của thuật toán, một danh sách closed toàn cục sẽ được dùng để phát hiện các trạng thái lặp
lại, còn danh sách open thì tiềm ẩn trong các mẩu tin hoạt động của môi trường đệ quy.
Function Depthsearch (trạng thái hiện hành); % closed toàn cục
Begin
If trạng thái hiện hành là trạng thái đích then
trả lời (thành công);
For mỗi trạng thái hiện hành có con chưa được kiểm tra do
begin
Con := con chưa được kiểm tra kế tiếp;
If con không phải là thành viên của closed
then if depthsearch (con) = thành công
then trả lời (thành công);
end;
Trả lời (thất bại);
End; % tìm kiếm đã đến cùng
Thay vì phát sinh tất cả các con của một trạng thái và đưa chúng vào danh sách open, thuật
toán này phát sinh mỗi lần một con và tìm kiếm theo phép đệ quy các nút cháu của từng con
đó trước khi phát sinh các anh em của nó. Thuật toán này sẽ gán một thứ tự cho các bước
80 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái
phát sinh trạng thái. Trong tìm kiếm theo đệ quy đối với một trạng thái con, nếu có một con
nào đó của trạng thái này là đích, thuật toán đệ quy sẽ trả lời thành công và bỏ qua tất cả các
trạng thái anh em. Ngược lại, các trạng thái anh em kế tiếp được phát sinh. Cứ như vậy thuật
toán sẽ tìm kiếm toàn bộ đồ thị lần lượt theo từng độ sâu một.
Thuật toán đệ quy cho phép bỏ qua danh sách open trong suốt quá trình thực hiện. Cơ chế
mà một ngôn ngữ lập trình sử dụng để cài đặt đệ quy là dùng mẩu tin hoạt động (activation
record) cho từng lần gọi đệ quy. Quá trình lần ngược sẽ tác động khi tất cả các con cháu của
một trạng thái không phải là đích, làm cho bước đệ quy đó thất bại. Việc thực hiện đệ quy
cho phép lập trình viên thu hẹp tầm nhìn của họ vào một trạng thái duy nhất cùng với các
con của nó thay vì phải duy trì một danh sách open gồm nhiều trạng thái.

else Thêm current_goal vào closed;
while còn dữ kiện hoặc luật đồng nhất do
begin case
current_goal đồng nhất với dữ kiện:
return tập phép thế;
current goal là ¬p:
pattern_search(p);
if pattern_search thất bại then return {}
else return fail
current_goal đồng nhất với kết luận của luật (q → p):
begin
áp dụng phép thế đồng nhất mục tiêu vào tiền đề (q);
pattern_search (q);
if pattern_search thành công
then return hợp của tập phép thế của p và q;
else return fail;
end;
current_goal có dạng (p
1
∧ p
2
…):
begin
for mỗi thành phần p
i
do
begin
pattern_search(p
i
);

End;
82 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái
II HỆ THỐNG LUẬT SINH (HỆ SINH –
PRODUCTION SYSTEM)
II.1 Định nghĩa hệ sinh
Hệ sinh là một mô hình tính toán quan trọng trong trí tuệ nhân tạo về cả hai mặt: thực hiện
các thuật toán tìm kiếm và mô hình hóa việc giải các bài toán của con người.
Một hệ sinh được định nghĩa bởi:
1. Tập luật sinh (Production rules): Mỗi luật sinh có dạng condition → action (điều
kiện → hành động). Phần điều kiện của luật là một mẫu cho biết khi nào thì có thể áp
dụng luật. Phần hành động quy định các bước giải toán tương ứng điều kiện.
2. Bộ nhớ làm việc (Working memory): Chứa một mô tả về trạng thái hiện thời của
bài toán trong quá trình suy luận. Mô tả này là một mẫu sẽ được đối sánh với phần
điều kiện của một luật sinh để chọn ra bước giải thích hợp. Khi phần điều kiện của
luật phù hợp với nội dung trong bộ nhớ làm việc, hành động phát sinh từ điều kiện đó
sẽ được thực hiện làm thay đổi nội dung bộ nhớ làm việc.
3. Chu trình nhận dạng - hành động (Recognize – act cycle) : Là cấu trúc điều khiển
của hệ sinh.
Cấu trúc điều khiển của một hệ sinh khá đơn giản: Bộ nhớ làm việc được khởi đầu với mô tả
của bài toán. Trạng thái hiện hành của việc giải bài toán được duy trì dưới dạng một tập các
mẫu trong bộ nhớ làm việc. Các mẫu này được đối sánh với phần điều kiện của các luật sinh,
các luật có điều kiện phù hợp với mẫu trong bộ nhớ làm việc được gọi là tập luật tranh chấp
(conflict set). Sau đó một trong các luật sinh này sẽ được chọn và được kích hoạt. Để kích
hoạt một luật, phần hành động của nó được thục hiện và làm thay đổi nội dung bộ nhớ làm
việc. Chu trình điều khiển sẽ lặp lại với nội dung đã được thay đổi trong bộ nhớ làm việc.
Quá trình này kết thúc khi nội dung của bộ nhớ làm việc không còn phù hợp với điều kiện
của luật nào nữa.
Một quá trình giải quyết tranh chấp (conflict resolution) sẽ chọn một luật từ tập luật tranh
chấp để kích hoạt. Chiến lược giải quyết tranh chấp có thể rất đơn giản như chọn luật đầu

theo thứ tự từ điển. Trong ví dụ này, một luật sinh sẽ được áp dụng nếu điều kiện của nó phù
hợp với một phần của dãy chữ cái trong bộ nhớ làm việc. Khi một luật được kích hoạt, phần
dãy phù hợp với điều kiện luật này được thay thế bởi dãy ở phần hành động của luật đó.

Tập luật sinh
Bước
Bộ nhớ làm việc
Tập luật
tranh chấp
Luật
kích hoạt
Dừng
Hình 5.2 – Các bước thực hiện của một hệ sinh đơn giản
84 Võ Huỳnh Trâm – Trần Ngân Bình