Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 4: Bài toán tìm kiếm 2 có nội dung trình bày về heuristic, tìm kiếm tham lam, thuật giải A*, sự nới lỏng, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO amp ỨNG DỤNG Bài toán tìm kiếm II THS. BÙI THỊ DANH KHOA CNTT Nội dung Heuristic Tìm kiếm tham lam Thuật giải A Sự nới lỏng 2 Heuristic Các thuật toán tìm kiếm mù duyệt trạng thái theo mọi hướng không sử dụng thông tin của trạng thái đích. Ước lượng chi phí đến trạng thái đích. Liệu có tìm đường nhanh hơn 3 Heuristic Heuristic là một hàm ước lượng mức độ gần của một trạng thái so với trạng thái đích Kí hiệu là h s với s là trạng thái. Heuristic được thiết kế cho từng bài toán tìm kiếm cụ thể Một số hàm heuristic phổ biến Khoảng cách Euclidean Mahattan. 4 Ví dụ - Tìm đường đi cho Pacman Hàm h s là hàm Euclidean 5 Ví dụ - Tìm đường đi trên bản đồ Hàm h s là khoảng cách đường chim bay 6 Ví dụ - N-Puzzle Hàm h s số ô khác biệt giữa 2 puzzle 7 Nội dung Heuristic Tìm kiếm tham lam Thuật giải A Sự nới lỏng 8 Tìm kiếm tham lam greedy search Chiến lược duyệt mở rộng trạng thái được ước lượng là gần trạng thái đích nhất Hàm heuristic tương ứng h s có giá trị nhỏ nhất Sử dụng hàng đợi ưu tiên để triển khai với độ ưu tiên là h s Tùy chọn đánh dấu các trạng thái đã được xem xét Đánh dấu khi trạng thái được lấy khỏi hàng đợi 9 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 Start 1 9 h 4 4 h 5 h 12 1 h 6 p 15 q 4 r h 11 h 9 h 6 S null PQ Start 12 10 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 Start 1 9 h 4 4 h 5 h 12 1 h 6 p 15 q 4 r h 11 h 9 h 6 S Start 12 PQ e 4 d 8 p 11 11 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 Start 1 9 h 4 4 h 5 h 12 1 h 6 p 15 q 4 r h 11 h 9 h 6 S e 4 PQ h 6 r 6 d 8 p 11 12 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 Start 1 9 h 4 4 h 5 h 12 1 h 6 p 15 q 4 r h 11 h 9 h 6 S h 6 PQ r 6 d 8 q 9 p 11 13 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 Start 1 9 h 4 4 h 5 h 12 1 h 6 p 15 q 4 r h 11 h 9 h 6 S r 6 PQ f 4 d 8 q 9 p 11 14 Ví dụ Goal a 2 h 0 2 h 8 h 5 b 1 8 c 2 5 h 11 2 e 3 d h 4 f 9 h 8 .
