Thuật toán giải bài toán suy diễn tiến

Suy diễn tiến - Một giải thuật thú vị

Lê Nhật Quang

Đã bao giờ bạn muốn xây dựng một chương trình giải toán tự động, chỉ cần nhập một đề

toán, sau đó, chương trình trình sẽ đưa ra phương pháp giải, hoặc hơn nữa, chương trình

sẽ tự động tính toán luôn kết quả cho bạn. Nếu câu trả lời là ″có″ thì thuật giải này sẽ là

công cụ tuyệt vời để hỗ trợ cho bạn đấy! Bây giờ, chúng ta cùng tìm hiểu về thuật giải

này:

I/ Giới thiệu thuật giải:

1/ Hệ luật dẫn: là luật phát biểu dưới dạng:

If p1,p2,…,pn then q1,q2,…,qm

Trong đó, các ký hiệu pi,qj là các sự kiện nào đó.

VD : - If a>b, b>c then a>c

- If a=b then b=a

…

2/ Mô hình hệ luật dẫn: Gồm 2 thành phần cơ bản (F,R)

F là tập sự kiện , R là tập luật dẫn, mỗi luật có dạng: A---->B (A là giả thiết, B là kết luận

của luật)

VD: Các liên hệ suy dẫn trên các yếu tố của một tam giác theo hệ luật dẫn:

(1) Tập sự kiện:

F={a,b,c,A,B,C,R,S,p,ha,hb,hc,…}

Trong đó: sự kiện a tương đương với ″biết cạnh a″

sự kiện b tương đương với ″biết cạnh b″

…

(2) Tập luật dẫn:

R={ r1 : A,B-> C,

r2: a,b,c->S,

…

}

3/ Vấn đề suy diễn:

Giả sử có hệ luật dẫn (F,R). Cho trước một tập sự kiện giả thiết GT và một tập sự kiện mục

tiêu G.

Hỏi có thể suy ra các sự kiện mục tiêu G từ GT hay không?

4/ Suy diễn tiến:

Là quá trình suy ra các sự kiện mới từ những sự kiện đang có dự trên sự áp dụng của các

luật dẫn, tập sự kiện xuất phát là các sự kiện trong giả thiết.

Quá trình suy diễn kết thúc khi đạt được các sự kiện mục tiêu hoặc khi không suy diễn

thêm được sự kiện gì mớidựa trên các luật dẫn.

VD: GT={a,b,A} G={S}

Quá trình suy diễn:

- a,b,A -> B (luật a,b,A -> B dựa trên định lý hàm số Sin)

GT1={a,b,A,B}