Bài toán tìm kiếm I
THS. BÙI THỊ DANH
BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG
Nội dung chính
Tổng quan bài toán tìm kiếm
Cây tìm kiếm
Các thuật toán tìm kiếm mù
2
Bài toán tìm kiếm
Bài toán tìm đường đi
◦Tìm đường ngắn nhất,
◦Tìm đường nhanh nhất
◦Tìm đường có nhiều cảnh đẹp nhất
Các hành động:
◦Đi thẳng
◦Rẽ trái
◦Rẽ phải
3
Bài toán tìm kiếm
Giải bài toán puzzle
◦Tìm cách đạt đến “cấu hình” xác định
Các hành động:
◦Di chuyển các miếng ghép
4
Bài toán tìm kiếm
Một bài toán tìm kiếm gồm 5 thành phần:
◦Không gian trạng thái: S
◦Tập các hành động: Action(s)
◦Trạng thái bắt đầu: start
◦Hàm kiểm tra trạng thái đích: IsGoal(s)
◦Hàm xác định trạng thái kế tiếp: Successor(s)
◦Thường đi kèm với hành động và chi phí tương ứng
Một lời giải của bài toán tìm kiếm là một chuỗi các hành động để di chuyển từ trạng thái
bắt đầu đến trạng thái đích.
5