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

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!
Nội dung trích xuất từ tài liệu:
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ÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNGBài toán tìm kiếm IITHS. BÙI THỊ DANHBM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCMNội dungHeuristicTìm kiếm tham lamThuật giải A*Sự nới lỏng 2HeuristicCá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ủatrạng thái đích. Ước lượng chi phí đến trạng thái đích. Liệu có tìm đường nhanh hơn?!? 3HeuristicHeuristic 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.◦… 4Ví dụ - Tìm đường đi cho PacmanHàm h(s) là hàm Euclidean 5Ví dụ - Tìm đường đi trên bản đồHàm h(s) là khoảng cách đường chim bay 6Ví dụ - N-PuzzleHàm h(s): số ô khác biệt giữa 2 puzzle… 7Nội dungHeuristicTìm kiếm tham lamThuật giải A*Sự nới lỏng 8Tì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ấtSử 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 9Ví 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)} 10Ví 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)} 11Ví dụ ...