Giải quyết vấn đề bằng tìm kiếm
Russell and Norvig 3rd ed., chap. 3.1-3.2
1
Các trò chơi đố!
2
Bài toán ba thầy tu và ba con quỷ
Mục tiêu: đưa tất cả người và quỷ sang bờ phải
của con sông an toàn.
Điều kiện:
□Nếu số người ở mỗi bờ ít hơn số quỷ thì người sẽ bị
quỷ ăn thịt
□Mỗi lượt thuyền chỉ chở được nhiều nhất 2 người và
không được trống
3
Biểu diễn bài toán
Một biểu diễn trạng thái cho phép mô tả trạng thái và
mục tiêu của bài toán:
(ML, CL, B)
ML: số lượng thầy tu ở bờ trái
CL: số lượng quỷ ở bờ trái
B: vị trí của con thuyền
Trạng thái ban đầu: (3,3,L) Mục tiêu: (0,0,R)
4
Tác nhân giải quyết bài toán
Biểu diễn bài toán
□Các trạng thái và hành động (hàm kế vị).
Biểu diễn mục tiêu
□Trạng thái mong muốn của thế giới.
Tìm kiếm
□Xác định chuỗi các hành động có thể có để dẫn tới các trạng thái
đã biết giá trị và sau đó chọn chuỗi tốt nhất.
Thực thi
□Căn cứ vào giải pháp, thực hiện các hành động.
Giả định:
□Môi trường là có thể quan sát đầy đủ, xác định trước
□Tác nhân biết ảnh hưởng của các hành động của nó
5