Bài giảng Trí tuệ nhân tạo: Giải quết vấn đề - Nguyễn Nhật Quang (TT)

Trí Tuệ Nhân Tạo Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn Trường Đại học Bách Khoa Hà Nội Viện Công nghệ Thông tin và Truyền thông Năm học 2012-2013 Nội dung môn học: ④Giới thiệu về Trí tuệ nhân tạo ④Tác tử ④Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc ⑨Tìm kiếm với tri thức bổ sung (Informed search) ④Logic và suy diễn ④Biểu diễn tri thức ④Biểu diễn tri thức không chắc chắn ④Học máy Trí tuệ nhân tạo 2 Nhắc lại: Tìm kiếm theo cấu trúc cây ④Một chiến lược (phương pháp) tìm kiếm = Một cách xác định thứ tự xét các nút của cây Trí tuệ nhân tạo 3 Tìm kiếm với tri thức bổ sung ④Các chiến lược tìm kiếm cơ bản (uninformed search strategies) chỉ sử dụng các thông tin chứa trong định nghĩa của bài toán ⑨ Không phù hợp với nhiều bài toán thực tế (do đòi hỏi chi phí quá cao về thời gian và bộ nhớ) ④Các chiến lược tìm kiếm với tri thức bổ sung (informed search strategies) sử dụng các tri thức cụ thể của bài toán → Quá trình tìm kiếm hiệu quả hơn ⑨ Các giải thuật tìm kiếm best-first (Greedy best-first, A*) ⑨ Các giải thuật tìm kiếm cục bộ (Hill-climbing, Simulated annealing, Local beam, Genetic algorithms) ⑨ Các giải thuật tìm kiếm đối kháng (MiniMax, Alpha-beta pruning) Trí tuệ nhân tạo 4 Best-first search ④Ý tưởng: Sử dụng một hàm đánh giá f(n) cho mỗi nút của cây tìm kiếm ⑨ Để đánh giá mức độ “phù hợp” của nút đó ⮳ Trong quá trình tìm kiếm, ưu tiên xét các nút có mức độ phù hợp cao nhất ④ Cài đặt giải thuật ⑨ Sắp thứ tự các nút trong cấu trúc fringe theo trật tự giảm dần về mức độ phù hợp ④ Các trường hợp đặc biệt của giải thuật Best-first search ⑨ Greedy best-first search ⑨ A* search Trí tuệ nhân tạo 5 ... - tailieumienphi.vn