Tri tue nhan tao

Ví dụ 1: Không gian bài tóan bình đựng nước.
Cho hai bình đựng nước, một bình có dung tích 4 lít và một bình khác có dung
tích 3 lít, cả hai bình không có dấu dung tích. Trạng thái ban đầu của hai bình là
rỗng, dùng một bơm nước làm đầy nước với hai bình. Làm cách nào để có chính
xác 2 lít nước trong bình 4 lít ?
Vậy, không gian trạng thái cho bài tóan này là gì ?
Giải :
Cho cặp biến số nguyên (x,y) biểu diễn các trạng thái trong không gian trạng
thái cho bài tóan này, trong đó x là số lít nước trong bình 4 lít và y là số lít nước
trong bình 3 lít.
Không gian trạng thái cho bài tóan được mô tả bằng các thành phần như sau
:
+ Trạng thái ban đầu của bài tóan : hai bình đều rỗng đó là cặp số nguyên
(0,0).
+ Trạng thái đích của bài tóan : cần có chính xác 2 lít nước trong bình 4 lít đó
là cặp số nguyên (2,n), tronng đó n là số không xác đ
+ Trạng thái khác của bài tóan : đó là cặp số nguyên (x,y) mô tả các trạng
thái trong không gian bài tóan.
+ Trạng thái chuyển tiếp của bài tóan : đó la’ bước chuyển tiếp từ trạng thái
hiện có đến trạng thái mới nhờ thông luật áp dụng của bài tóan. Luật áp dụng
là luật mà vế điều kiện của nó hợp với trạng thái hiện hữu để vế kết luận
của nó phát sinh ra trạng thái mới. Tập các luật giải bài tóan bình đựng nước
được liệt kê là
Luật 1 : (x,y/ x < 4 ) → (4,y).
Luật 2 : (x,y/ y < 3 ) → (x,3).
Luật 3 : (x,y/ x > 0 ) → (0,y).
Luật 4 : (x,y/ y > 0 ) → (x,0).
Luật 5 : (x,y/ x + y >= 4 và y > 0 ) → (4,y – (4 – x)).
Luật 6 : (x,y/ x + y >= 3 và x > 0 ) → (x – (3 –y),3).
Luật 7 : (x,y/ x + y < 4 và y > 0 ) → (x + y,0).
Luật 8 : (x,y/x + y < 3 và x > 0 ) → (0,x + y)
ng gian trạng thái cho bài tóan này được biểu diễn bằng đồ thị như hình



Ví dụ 3 : Không gian bài tóan ba tu sĩ và ba kẻ ăn thịt người.
Ba tu sĩ và ba kẻ ăn thịt người ở bên này sông muốn qua bên kia sông bằng
một chiếc thuyền có sức chở tối đa là 2 thành viên. Bài tóan đặt ra là ở bất kỳ nơi
nào bên này sông, trên thuyền hoặc bên kia sông, nếu số tu sĩ ít hơn số kẻ ăn thịt
người thì số tu sĩ sẽ bị ăn thịt bởi số kẻ ăn thịt người. Hãy sắp xếp các chuyến
thuyền qua lại sông sao cho đưa mọi người sang bên kia sông an tòan ?
Vậy, không gian bài tóan này là gì ?
Giải : Không gian trạng thái cho bài tóan này được mô tả bằng các thành phần như
sau :
+ Trạng thái ban của bài tóan : Tất cả mọi người và thuyền ở bên này s
với cấu hình là (MMM, CCC, B), trong đó M là tu sĩ, C là kẻ ăn thịt người và B
thuyền.
+ Trạng thái đích của bài tóan : Tất cả mọi người và thuyền đều được
bên kia kia sông an tòan, vì thế cấu hình đích bên này sông là (_, _, _).
+ Ràng buộc của bài tóan : Số tu sĩ phải là luôn luôn lớn hơn hoặc bằng so
ăn thịt người ở bất cứ nơi nào bên này sông, trên thuyền hoặc bên kia sông.
+ Trạng thái khác của bài tóan : cấu hình số tu sĩ, số kẻ ăn thịt ngươ
thuyền ở bên này sông hoặc ở bên kia sông.
+ Trạng thái chuyển tiếp của bài tóan : bước dịch chuyển thuyền đưa một
thành viên qua lại sông.
Bài tóan ba tu sĩ và ba kẻ ăn thịt người được giải gồm các bước như sau :
Bên này sông Bên kia sông
0. Trạng thái ban đầu (MMM,CCC,B) ( _ , _ , _ )
1. Hai kẻ ăn thịt người (MMM, C, _ ) (_ , CC, B)
qua bên kia sông.
2. Một kẻ ăn thịt người (MMM, CC, B) ( _ , C,