tailieunhanh - Bài giảng Trí tuệ nhân tạo: Chương 3 - Nguyễn Văn Hòa

Chương 3 giúp người học hiểu về "Các chiến lược tìm kiếm Heuristics". Nội dung trình bày cụ thể gồm có: Khái niệm, tìm kiếm tốt nhất trước, phương pháp leo đồi, cài đặt hàm đánh giá, thu giảm ràng buộc, giải thuật cắt tỉa α-β,. | Chương 3: Các chi n lư c tìm ki m Heuristics 1 N i dung Khái niệm Tìm kiếm tốt nhất trước Phương pháp leo đồi Cài đặt hàm đánh giá Thu giảm ràng buộc Giải thuật cắt tỉa α-β 2 Gi i h n không gian h th ng 8-puzzle Lời giải cần trung bình 22 cấp (depth) Độ rộng của bước ~ 3 Tìm kiếm vét cạn cho 22 cấp cần x 1010 states Nếu chỉ giới hạn ở d=12, cần trung bình triệu trạng thái [24 puzzle có 1024 trạng thái] ⇒ Cần chiến lược tìm kiếm heuristic 3 Tìm ki m Heuristics Any estimate of how close a state is to a goal Designed for a particular search problem Examples: Manhattan distance, Euclidean distance 10 5 Tìm ki m Heuristic (tt) Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau: Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. .