he luat sinh
Các đặc tính của giải thuật SSS:
Lời giải là một PATH từ điểm START đến điểm GOAL
Tìm kiếm là sự kiểm tra có hệ thống các đường dẫn đến GOAL
Backtracking cho phép giải thuật "phục hồi" khi đi vào một nhánh không có đáp án.
Các danh sách sẽ giữ các trạng thái đang xem xét:
Danh sách Open: cho phép hệ thống backtrack về các trạng thái chưa được xét.
Danh sách Close: cho phép hệ thống kiểm tra sự quay vòng tránh lặp vô tận
Dùng STACK cho DFS, QUEUE cho BFS và dùng PRIORITY QUEUE cho BFS.
Tìm kiếm đệ qui là giải thuật tìm kiếm trên SSS với các đặc tính:
Ngắn gọn xúc tích hơn
Tiếp cận của giải thuật tự nhiên hơn
Hợp nhất với phương thức hiện thực của Logic vị từ
Các giải thuật tìm kiếm đệ qui chính:
Tìm kiếm đệ qui - Recursive Search (RS)
Tìm kiếm theo mẫu - Pattern Directed Search (PDS)
Các giải thuật tìm kiếm đệ qui được sử dụng rộng rải trong các shell của các Hệ chuyên gia (Expert System).
Pattern Directed Search là nền tản của PROLOG
Đệ qui là sự định nghĩa một đối tượng bằng cách sử dụng chính đối tượng đó - Toán học
Đệ qui được dùng để định nghĩa và phân tích các cấu trúc dữ liệu cũng như các thủ tục xử lý trong ngành máy tính.
Một thủ tục đệ qui bao gồm:
Thành phần đệ qui, trong đó thủ tục gọi chính nó để lặp lại chuổi các thao tác.
Thành phần dừng dùng để dừng quá trình đệ qui vô tận. (lặp vô tận)
Hai thành phần này tồn tại đồng thời trong tất cả các định nghĩa đệ qui cũng như giải thuật đệ qui.
Đệ qui là một cấu trúc điều khiển dữ liệu tự nhiên cho những cấu trúc không xác định số phần tử cố định: list, tree, và đồ thị.
Function Member(item, list);
if List rỗng then return (Fail)
else
if Item = phần tử đầu của list then return (succes)
else
Tail:= List \ phần tử đầu;
member (item, Tail);
end
end;
Đệ qui có đầy đủ tính năng của các cấu trúc điều khiển truyền thống như Loop và rẽ nhánhmọi chương trình viết được bằng cấu trúc truyền thống đều có thể viết đệ qui.
Đệ qui thích hợp biểu diễn các cấu trúc toán học thuận tiện trong việc kiểm tra tính đúng đắn của giải thuật đệ qui.
Công thức đệ qui cũng thường được dùng trong việc sinh và kiểm tra chương trình tự động.
Đệ qui là công cụ tự nhiên và mạnh mẻ cho hiện thực các chiến lược giải quyết vấn đề của AI.
Function Depth_First_Search;
Begin
if Open rỗng then return (fail);
Current_state := phần tử đầu tiên của open;
If (current_state là mục tiêu) then return (Success)
else begin
open:=phần đuôi của open;
Closed := Closed + current_state;
for mỗi phần tử con Y của current_state do
if not (Y in close) and not (Y in open) then thêm Y vào đầu của Open;
End;
depth_first_search;
End;
Các giải thuật Search đã tìm hiểu và Recursive Seach không trình bày cách biểu diển một trạng thái trong không gian trạng thái cũng như cách sinh các trạng thái mới.
Pattern-Directed Search là một giải thuật search đệ quy dùng Logic Vị từ để hiện thực việc sinh các trạng thái mới.
Paterm-Directed Search xuất phát từ goal và các modus ponen dạng q(x)->p(x) để chuyển trạng thái. Các modus ponen này gọi là các luật sinh.
Giải thuật: Xuất phát từ goal P, áp dụng một giải thuật để tìm các rule với P ở vế phải , sau đó xem vế trái Q là subgoal. Đệ quy với Q cho đến khi Qx là một sự kiện trong kho tri thức.
Sự kiện (FACT) trong kho tri thức?????
Function Pattern_search(current_goal);
Begin
If current_goal có trong closed then retuen fail
else thêm current_goal vào trong closed;
while còn trong database các rule hay fact chưa xét
begin case
current_goal trùng với fact:
return(success);
current_goal là một phép hội:
for mỗi thành phần hội Pi do
pattern_search(Pi);
If tất cả các hội đều success
then return success else return fail.
end;
Current_goal là vế phải một rule:
áp dụng các thành phần vào vế trái Q.
if pattern_search(Q) then return success else return fail;
end;
end; /* case
Return fail;
End;
PDS dùng các rule và thành phần hội để sinh các trạng thái con.
Tách bạch quá trình điều khiển của giải thuật và dữ liệu của giải thuật
Cùng giải thuật chỉ cần thay đổi database : Fact & Rule ta sẽ áp dụng cho các bài toán khác nhau.
Xây dựng các shell và có thể vận hành cho các hệ thống khác nhau bằng cách thay đổi Database.
Để đơn giản hoá giải thuật chưa giải quyết ở mức độ có các biến trong các rule. Ví dụ P(x)^Q(x) chỉ thõa khi P và Q cùng thỏa với cùng giá trị X.
Các phép , v,.. cũng chưa giải quyết trong giải thuật này.
Function Pattern_search(current_goal);
Begin
If current_goal có trong Closed then return fail else thêm current_goal vào Closed;
while còn các rule hay fact chưa xét
case
current_goal trùng với fact: return(success);
current_goal là negated(p):
if pattern_search(p) then return fail
else return{}
end;
current_goal là một phép hội:
for mỗi thành phần hội Pi do
if not (pattern_search(Pi)) the return fail else thay thế tất cả các biến cho các thành phần hội khác.
If tất cả các hội đều success then return các thành phần hội else return fail.
end;
current_goal là phép tuyển:
repeat cho mọi thành phần tuyển Vi;
until (pattern_search(Vi) or (hết thành phần hội)
if pattern_search (Vi) then return các thay thế else return fail;
end;
Current_goal là vế phải một rule:
áp dụng các thành phần vào vế trái Q.
if pattern_search(Q) then return kết hợp của Current_goal và các thay thế của Q else return fail;
end; end; /* case*/
return fail; End;
Khái niệm: Hệ luật sinh là một mô hình tính toán quan trọng trong các bài toán tìm kiếm cũng như mô phỏng cách giải quyết vấn đề của con người trong lĩnh vực ứng dụng AI.
Định nghĩa: Hệ luật sinh là một mô hình tính toán cung cấp cơ chế điều khiển Pattern_directed trong quá trình giải quyết vấn đề (Proplem solving process).
Cấu trúc hệ luật sinh bao gồm 3 thành phần:
Production rules ( Tập luật sản sinh)
Working memory (Vùng nhớ làm việc)
Recognize-action control (Bộ điều khiển nhận dạng và hành động)
Production rules: là một tập các luật sản sinh được đặc tả dạng:
Condition - Action (điều kiện - hành động)
Một luật là một mắt xích của kho tri thức giải quyết vấn đề. Kho tri thức là một database của các production rules.
Thành phần Condition: là một mẫu (pattern) dùng xác định điều kiện áp dụng của rule cho một vấn đề tương ứng.
Thành phần action: mô tả bước giải quyết vấn đề tương ứng sẽ được thực hiện. Đây là phần sẽ tác động lên hiện trạng của không gian tìm kiếm.
Working memory chứa những đặc tả trạng thái hiện tại của quá trình suy luận. Chúng được lưu trữ như là tập các mẫu.
Những đặc tả này là các mẫu để so trùng với các condition của các production rules.
Khi một production rule được so trùng phần condition thì phần action của nó có thể được áp dụng, và phần action này được xây dựng đặc thù để tác động trực tiếp lên working memory.
Working memory được khởi tạo bằng trạng thái bắt đầu của vấn đề cần giải quyết.
Working memory diễn tả hiện trạng của vấn đề cần suy luận
Hệ luật sinh là khung làm việc tổng quát để thực thi các giải thuật tìm kiếm. Với đặc tính đơn giản, dể sửa đổi, và linh động, hệ luật sinh được dùng như một công cụ quan trọng để xây dựng các hệ chuyên gia và các ứng dụng AI khác
Các ưu điểm của Hệ luật sinh:
Tách bạch giữa Tri thức & Điều khiển:
Điều khiển: nằm trong chu trình Recognize-Action
Tri thức: được chứa đựng trong bản thân các luật sinh.
Cung cấp khả năng cập nhật tri thức mà không cần điều chỉnh chương trình. Thay đổi mã chương trình mà không ảnh hưởng đến tập luật sinh.
Dễ dàng áp dụng trong tìm kiếm trên không gian trạng thái. Các state của working memory là các node. Các production rule là các chuyển đổi giữa các trạng thái (cơ chế sinh các trạng thái mới)
Tính độc lập của các luật sinh.
Khả năng áp dụng heuristic cho việc điều khiển quá trình hoạt động.
Theo dõi và giải thích quá trình hoạt động
Độc lập với ngôn ngữ & có thể dùng như kỹ thuật mô phỏng giải pháp của người.
Bạn đang đọc truyện trên: Truyen3h.Co