Lec 4-TTNT. p.1
Lec 4
Tìm kiếm kinh nghiệm
TTNT. p.2
Tìm kiếm kinh nghiệm (heuristic)
◼Heuristics: là các phỏng đoán, ước chừng dựa
trên kinh nghiệm, trực giác.
◼Các hệ giải quyết AI sử dụng heuristic trong
hai tình huống cơ bản:
– Bài toán được định nghĩa chính xác nhưng chi phí tìm
lời giải bằng TK vét cạn là không thể chấp nhận.
VD: Sự bùng nổ KGTT trong trò chơi cờ vua.
–Vấn đề với nhiều sự mơ hồ trong lời phát biểu bài
toán hay dữ liệu cũng như tri thức sẵn có.
VD: Chẩn đoán trong y học.
TTNT. p.3
Giải quyết bài toán bằng tìm kiếm
heuristic
◼Tìm biểu diễn thích hợp mô tả các trạng thái và
các toán tử của bài toán
◼Xây dựng hàm đánh giá
◼Thiết kế chiến lược chọn trạng thái để phát triển
ở mỗi bước.
TTNT. p.4
Giải thuật Heuristic
◼Một giải thuật heuristic có thể được xem gồm 2
phần:
– Phép đo heuristic: thể hiện qua hàm đánh giá
heuristic (evaluation function), dùng để đánh giá các
đặc điểm của một trạng thái trong KGTT.
– Giải thuật tìm kiếm heuristic:
•Tìm kiếm tốt nhất-đầu tiên (best-first search): Tìm kiếm
theo chiều rộng + hàm đánh giá
•Tìm kiếm leo đồi (hill-climbing): Tìm kiếm theo chiều sâu +
hàm đánh giá
TTNT. p.5
KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng
của các trạng thái.