Tìm kiếm heuristic

Tổng quan • Tìm kiếm heuristic Tối ưu kiểu “Tham lam” (“Greedy Best-First Search) • Những điểm không thích hợp của tìm kiếm heuristic “Tham lam”. • Mẹo: tính luôn chi phí đi đến trạng thái hiện tại. • Việc tìm kiếm kết thúc khi nào? • Heuristic chấp nhận được • Tìm kiếm A* là đầy đủ • Tìm kiếm A* luôn dừng • Khuyết điểm của A* • Tiết kiệm nhiều bộ nhớ với IDA* (Iterative Deepening A*)...
Nội dung trích xuất từ tài liệu:
Tìm kiếm heuristic Tìm kiếm heuristic Tìm kiếm A* Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Ref: http://www.cs.cmu.edu/~awm/tutorials 1 Tổng quan • Tìm kiếm heuristic Tối ưu kiểu “Tham lam” (“Greedy Best-First Search) • Những điểm không thích hợp của tìm kiếm heuristic “Tham lam”. • Mẹo: tính luôn chi phí đi đến trạng thái hiện tại. • Việc tìm kiếm kết thúc khi nào? • Heuristic chấp nhận được • Tìm kiếm A* là đầy đủ • Tìm kiếm A* luôn dừng • Khuyết điểm của A* • Tiết kiệm nhiều bộ nhớ với IDA* (Iterative Deepening A*) 2 Tìm kiếm Heuristic - Các phương pháp tìm kiếm mù (blind search): thông tin về trạng thái đích không đóng vai trò trong việc tìm kiếm. Nên đi S đường nào? a b c G - Có thể sử dụng ước lượng khoảng cách đến đích giữa các trạng thái để tìm đường đi? 3 Tìm kiếm Heuristic Giả sử ngoài việc đặc tả tìm kiếm chuẩn ta cũng có một heuristic. Một hàm heuristic ánh xạ một trạng thái thành một ước lượng về chi phí đến đích từ trạng thái đó. Bạn có thể nghĩ ra ví dụ về heuristics? VD. đối với bài toán 8-puzzle? VD. để lập đường đi trong ma trận? Ký hiệu heuristic bằng một hàm h(s) tính các trạng thái thành giá trị chi phí. 4 Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 5 Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 6 Heuristic theo Khoảng cách Euclide GOAL a 2 2 ...