TÌM KIẾM DỰA TRÊN CƠ SỞ ĐỆ QUI

Tìm kiếm đệ quy

Một chuyển đổi trực tiếp của thuật toán tìm kiếm sâu thành dạng đệ quy sẽ minh họa cho sự tương đương của đệ quy và lặp lại đơn giản. Thuật toán này sử dụng các biến toàn cục closed và open để duy trì danh sách các trạng thái:

Function Depthsearch ; % open và closed toàn cục

Begin

If open rỗng then trả lời (thất bại);

Trạng thái hiện hành := phần tử đầu tiên của open;

If trạng thái hiện hành là trạng thái đích

then trả lời (thành công)

Else

begin

Open := open - phần tử đầu tiên của open;

Closed := closed + trạng thái hiện hành;

For mỗi trạng thái con của trạng thái hiện hành doIf chưa có trong closed hay open % xây dựng ngăn xếp

then bổ sung con đó vào đầu danh sách open

end;

Tìm kiếm sâu; % đệ quy

End;

Tìm kiếm sâu như vừa được trình bày sẽ không sử dụng hết sức mạnh của phép đệ quy. Nó vẫn còn khả năng đơn giản hóa thủ tục bằng cách sử dụng chính phép đệ quy (thay gì một danh sách open) để sắp xếp các trạng thái trong không gian trạng thái. Trong phiên bản này 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

thenif 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 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.

Tìm kiếm trong không gian trạng thái là một quá trình đệ quy. Để tìm đường đi từ trạng thái hiện hành đến đích, bạn chuyển đến một trạng thái con và thực hiện phép đệ quy. Nếu trạng thái con đó không dẫn đến đích, bạn thử lần lượt các trạng thái anh em của nó. Phép đệ quy sẽ chia một bài toán lớn và khó (tìm kiếm khắp không gian) thành các bài toán nhỏ và đơn giản hơn (phát sinh các con của một trạng thái) và áp dụng chiến lược đệ quy cho từng bài toán nhỏ đó. Quá trình cứ tiếp tục như vậy cho đến khi phát hiện được đích hoặc hết không gian.

Tìm kiếm hướng mẫu (Pattern – directed search)

Trong phần này chúng ta sẽ áp dụng tìm kiếm đệ quy vào không gian các suy diễn logic, kết quả sẽ là một thủ tục tìm kiếm tổng quát dùng cho phép tính vị từ.

Giả sử cần phải viết một thuật toán để xác định xem một biểu thức phép tính vị từ cho trước có phải là kết quả logic của môt tập các khẳng định nào đó hay không. Thuật toán này phải tìm một trình tự suy diễn tạo nên biểu thức đích. Thuật toán sẽ đề nghị một tìm kiếm hướng mục tiêu với câu hỏi ban đầu tạo nên đích và các modus ponens xác định các chuyển tiếp giữa các trạng thái. Cho trước một đích, thuật toán sẽ dùng phương pháp đồng nhất để chọn các phép kéo theo có kết luận phù hợp với đích đó. Sau khi đồng nhất đích với kết luận của phép kéo theo và đã áp dụng các thay thế vừa suy ra được, tiền đề của phép kéo theo sẽ trở thành một đích mới gọi là đích phụ (subgoal). Sau đó thuật toán sẽ thực hiện đệ quy đối với đích phụ này. Nếu đích phụ phù hợp với một sự kiện trong cơ sở tri thức, cuộc tìm kiếm kết thúc. Chuỗi suy diễn dẫn từ đích ban đầu đến các sự kiện cho trước sẽ chứng minh đích xuất phát là đúng.

Phiên bản hoàn chỉnh của thuật toán tìm kiếm hướng mẫu có thể trả lời một tập các đồng nhất thỏa mãn từng đích phụ là:

Function pattern_search (current_goal);

Begin

If current_goal Î closed then return fail

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₁Ù p₂ …):

begin

for mỗi thành phần p_ido

begin

pattern_search(p i );

if pattern_search thất bại then return fail;

else áp dụng các phép thế vào các p_i còn lại;

end;

if pattern_search thành công cho tất cả các p_i

then return hợp của các tập phép thế;

else return fail;

end;

current_goal có dạng (p₁Ú p₂…):

begin

repeat cho mỗi p_i

pattern_search(p i );

until không còn thành phần p_i nào hoặc thành công;

if pattern_search thành công then return {phép thế};

else return fail;

end;

return fail;

End;