Các bài toán có yếu tố suy diễn
Nguyễn Xuân Huy
Trong lĩnh vực trí tuệ nhân tạo ta thường gặp một số bàitoán tin có chứa các yếu tố suy
diễn theo kiểu nếu X suy ra Y và Y suy ra Z thìX cũng suy ra Z. Các bài toán thuộc loại
này không khó lắm, tuy nhiên chúngthường đòi hỏi một số nhận xét tinh tế nhằm rút ngắn
quá trình suy diễn. Chúngta thử trình bày một cách giải vài bài thuộc loại này:
Bài toán Tham quan Một lớp học có n học sinh mang tên A, B, C... Giữa các nhóm họcsinh
có một số quan hệ tạm gọi là quan hệ ảnh hưởng, thí dụ, nếu ta viết AB> C thì có nghĩa là
hai bạn A và B đồng thời cùng thuyết phục thì có thể yêucầu bạn C tham gia một hoạt
động nào đó cùng với mình. Cho biết m quan hệ giữacác nhóm học sinh trong lớp. Giả sử
một nhóm X của lớp muốn rủ các bạn cùng lớpđi tham quan thành Cổ Loa chẳng hạn. Hãy
cho biết những bạn nào sẽ có mặt trongnhóm tham quan đó
Dữ liệu vào ghi trong tệp văn bản THAMQUAN.INP với cấu trúc như sau:
* Dòng đầu tiên: hai số tự nhiên n và m biểu thị sốhọc sinh trong lớp và số các quan hệ, 2
=< n =< 26, 1 =< m =<50.
* Tiếp theo là m dòng, mỗi dòng biểu thị một quan hệdạng X > Y.
* Dòng cuối cùng là danh sách các học sinh trongnhóm X.
Hiển thị trên màn hình danhsách các học sinh đi tham quan, kể cả các bạn trong nhóm X.
Thí dụ:
THAMQUAN.INP
Sau khi thực hiện chương trình ta sẽ thu được: ABCDEFH
Thí dụ trên cho chúng ta biết lớp học có 10 bạn học sinh mang tên là A B C D E F G H I
vàJ. Có 4 quan hệ giữa các nhóm như sau:
(B cóthể rủ được C)
(C vàE có thể rủ được A và F)
H > D (H cóthể rủ được D)
AC > BDEH (A vàC có thể rủ được B, D, E và H)
Hai bạn X = AB đứng ra rủ các bạn trong lớp đi tham quan. Vậy những aisẽ có mặt trong
buổi tham quan
Bài giải
Hãy tưởng tượng vào buổi sáng hôm tham quan, đến giờ hẹn ta chỉ gặp haibạn A và B. Hai

Tệp f dùng để quản lý dữ liệu vào (tệp THAMQUAN.INP).Biến lop dùng để chứa tên học
sinh của lớp. Sau khi biết giá trị n là số họcsinh, biến lop kiểu tập sẽ được khởi trị như sau:
lop:=[ ];
for i:=0 to n-1 do
lop:=lop+[chr(ord('A')+i)];
Biến m chứa số lượng các quan hệ. Hai mảng traivà phai chứa các tập ở mỗi vế trái và
phải tương ứng của mỗi quan hệ.Với thí dụ đã cho, sau khi đọc dữ liệu từ tệp
THAMQUAN.INP ta thu được
n=10, m=4,
trai[1]=[B], phai[1]=[C]
trai[2]=[C,E], phai[2]=[A,F]
trai[3]=[H], phai[3]=[D]
trai[4]=[A,C], phai[4]=[B,D,E,H]
Thủ tục Ru(x,y) cho biết nhóm x rủ được nhóm y khi đósẽ hoạt động như sau.
procedure Ru(x: KieuNhom; var y:KieuNhom);
var truoc: KieuNhom;
i: integer;
begin
y:=x;
for i:=1 to m do dau[i]:=0;
repeat
truoc:=y;
for i:=1 to m do
if dau[i] = 0 then
if (trai[i] <= y) then
begin
y:=y+phai[i];
dau[i]:=1;
end;
until y=truoc;

Var i:byte;
begin
x:= [ ];
for i:=1 to length(s) do
if (s[i] in lop) then
x:=x=[s[i]];
end;